11GenericsProfessor Jennifer Rexfordhttp://www.cs.princeton.edu/~jrex2Goals of this Lecture• Help you learn about:• Generic modules • Data structures that can store multiple types of data• Functions that can work on multiple types of data• How to create generic modules in C• Which wasn’t designed with generic modules in mind!•Why?• Reusing existing code is easier/cheaper than writing new code; reuse reduces software costs• Generic modules are more reusable than non-generic ones• A power programmer knows how to create generic modules• A power programmer knows how to use existing generic modules to create large programs23Generic Data Structures Example• Recall Stack module from last lecture• Items are strings (type char*)/* stack.h */typedef struct Stack *Stack_T;Stack_T Stack_new(void);void Stack_free(Stack_T s);void Stack_push(Stack_T s, const char *item);char *Stack_top(Stack_T s);void Stack_pop(Stack_T s);int Stack_isEmpty(Stack_T s);4Generic Data Structures Example• Stack operations (push, pop, top, etc.) make sense for items other than strings too• So Stack module could (and maybe should) be generic• Problem: How to make Stack module generic?• How to define Stack module such that a Stack object can store items of any type?35Generic Data Structures via typedef• Solution 1: Let clients define item type/* client.c */struct Item {char *str; /* Or whatever is appropriate */};…Stack_T s;struct Item item;item.str = "hello";s = Stack_new();Stack_push(s, item);…/* stack.h */typedef struct Item *Item_T;typedef struct Stack *Stack_T;Stack_T Stack_new(void);void Stack_free(Stack_T s);void Stack_push(Stack_T s, Item_T item);Item_T Stack_top(Stack_T s);void Stack_pop(Stack_T s);int Stack_isEmpty(Stack_T s);6Generic Data Structures via typedef• Problem: Awkward for client to define structure type and create structures of that type• Problem: Client (or some other module in same program) might already use “Item_T” for some other purpose!• Problem: Client might need two Stack objects holding different types of data!!!• We need another approach…47Generic Data Structures via void*• Solution 2: The generic pointer (void*)/* stack.h */typedef struct Stack *Stack_T;Stack_T Stack_new(void);void Stack_free(Stack_T s);void Stack_push(Stack_T s, const void *item);void *Stack_top(Stack_T s);void Stack_pop(Stack_T s);int Stack_isEmpty(Stack_T s);8Generic Data Structures via void*• Can assign a pointer of any type to a void pointer/* client.c */…Stack_T s;s = Stack_new();Stack_push(s, "hello");…OK to match anactual parameterof type char* witha formal parameterof type void*/* stack.h */typedef struct Stack *Stack_T;Stack_T Stack_new(void);void Stack_free(Stack_T s);void Stack_push(Stack_T s, const void *item);void *Stack_top(Stack_T s);void Stack_pop(Stack_T s);int Stack_isEmpty(Stack_T s);59Generic Data Structures via void*• Can assign a void pointer to a pointer of any type/* client.c */char *str;…Stack_T s;s = Stack_new();Stack_push(s, "hello");…str = Stack_top(s);OK to assigna void* return valueto a char*/* stack.h */typedef struct Stack *Stack_T;Stack_T Stack_new(void);void Stack_free(Stack_T s);void Stack_push(Stack_T s, const void *item);void *Stack_top(Stack_T s);void Stack_pop(Stack_T s);int Stack_isEmpty(Stack_T s);10Generic Data Structures via void*• Problem: Client must know what type of data a void pointer is pointing to• Solution: None• Void pointers subvert the compiler’s type checking• Programmer’s responsibility to avoid type mismatches/* client.c */int *i;…Stack_T s;s = Stack_new();Stack_push(s, "hello");…i = Stack_top(s);Client pushes a stringClient considers retrievedvalue to be a pointer toan int! Legal!!! Trouble!!!611Generic Data Structures via void*• Problem: Stack items must be pointers• E.g. Stack items cannot be of primitive types (int, double, etc.)• Solution: none• In C, there is no mechanism to create truly generic data structures• (In C++: Use template classes and template functions)• (In Java: Use generic classes)/* client.c */…int i = 5;…Stack_T s;s = Stack_new();…Stack_push(s, 5);…Stack_push(s, &i);Not OK to match anactual parameterof type int witha formal parameterof type void*OK, butawkward12Generic Algorithms Example• Suppose we wish to add another function to the Stack module/* stack.h */typedef struct Stack *Stack_T;Stack_T Stack_new(void);void Stack_free(Stack_T s);void Stack_push(Stack_T s, const void *item);void *Stack_top(Stack_T s);void Stack_pop(Stack_T s);int Stack_isEmpty(Stack_T s);int Stack_areEqual(Stack_T s1, Stack_T s2);Returns 1 (TRUE) iff s1 and s2 are equal, that is, contain equal items in the same order713Generic Algorithm Attempt 1• Attempt 1• Checks if s1 and s2 are identical, not equal• Compares pointers, not items• That’s not what we want/* stack.c */…int Stack_areEqual(Stack_T s1, Stack_T s2) {return s1 == s2;}/* client.c */char str1[] = "hi";char str2[] = "hi";Stack_T s1 = Stack_new();Stack_T s2 = Stack_new();Stack_push(s1, str1);Stack_push(s2, str2);if (Stack_areEqual(s1,s2)) {…}Returns 0 (FALSE)Incorrect!14Addresses vs. Values• Suppose two locations in memory have the same value• The addresses of the variables are not the same• That is “(&i == &j)” is FALSE• Need to compare the values themselves• That is “(i == j)” is TRUE• Unfortunately, comparison operation is type specific• The “==“ works for integers and floating-point numbers• But not for strings and more complex data structuresint i=5;int j=5;55ij815Generic Algorithm Attempt 2• Attempt 2• Checks if nodes are identical• Compares pointers, not items• That is still not what we want/* stack.c */…int Stack_areEqual(Stack_T s1, Stack_T s2) {struct Node *p1 = s1->first;struct Node *p2 = s2->first;while ((p1 != NULL) && (p2 != NULL)) {if (p1 != p2)return 0;p1 = p1->next;p2 = p2->next;}if ((p1 != NULL) || (p2 != NULL))return 0;return 1;}/* client.c */char str1[] = "hi";char str2[] = "hi";Stack_T s1 = Stack_new();Stack_T s2 = Stack_new();Stack_push(s1, str1);Stack_push(s2, str2);if (Stack_areEqual(s1,s2)) {…}Returns 0 (FALSE)Incorrect!16Generic Algorithm Attempt 3• Attempt 3• Checks if items are identical• Compares pointers to items, not items themselves• That is still not what we want/* stack.c */…int Stack_areEqual(Stack_T s1, Stack_T s2) {struct Node *p1 =
View Full Document
Unlocking...