1 1 Generics!2 Goals 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 old code is cheaper than writing new code"• 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 generic modules to create large programs"2 3 Generic 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); int 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); 4 Generic 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?"3 5 Generic 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); int 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); Do you see any problems with this approach? (Think before looking at next slide.)"6 Generic Data Structures via typedef!• Problems"• Awkward: Client must define structure type and create structures of that type"• Limiting: Client might already use “Item_T” for some other purpose!"• Limiting: Client might need two Stack objects holding different types of data!!!"• We need another approach…"4 7 Generic 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); int 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); 8 Generic 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 an"actual parameter"of type char* with"a formal parameter"of type void*"/* stack.h */ typedef struct Stack *Stack_T; Stack_T Stack_new(void); void Stack_free(Stack_T s); int 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);5 9 Generic 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 assign"a void* return value"to a char*"/* stack.h */ typedef struct Stack *Stack_T; Stack_T Stack_new(void); void Stack_free(Stack_T s); int 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); 10 Generic Data Structures via void*!• Problem: Client must know what type of data a void pointer is pointing to"• Solution: None"/* client.c */ int *i; … Stack_T s; s = Stack_new(); Stack_push(s, "hello"); … i = Stack_top(s); Client pushes a string"Client considers retrieved"value to be a pointer to"an int. This is legal. But "itʼs trouble."6 11 Generic Data Structures via void*!• Problem: Stack items must be pointers"• E.g. Stack items cannot be of primitive types (int, double, etc.)"• Solution: none"/* client.c */ … int i = 5; … Stack_T s; s = Stack_new(); … Stack_push(s, 5); … Stack_push(s, &i); Not OK to match an"actual parameter"of type int with"a formal parameter"of type void*"OK, but"awkward"12 Generic Algorithms Example!• Suppose we want to add a function to the Stack module"/* stack.h */ typedef struct Stack *Stack_T; Stack_T Stack_new(void); void Stack_free(Stack_T s); int 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); Should return 1 (TRUE) iff s1 and s2 are equal, "that is, contain equal items in the same order"7 13 Generic 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)) { … } What does this return?"14 Addresses 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 structures"int i=5; int j=5; 5 5 i j8 15 Generic 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)) { … } What does this return?"16 Generic 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 */
View Full Document