L4: Creating a Generic Swap Function for Data Types of Arbitrary Size
Notes
Generic Swap
The generic swap function in the last lecture is useful for 4-byte figures. How to make it be a universial function? Look at the following realization:
void swap(void *vp1, void *vp2, int size)
{
char buffer[size];
memcpy(buffer, vp1, size);
memcpy(vp1, vp2, size);
memcpy(vp2, buffer, size);
};
int x=17; y=37;
swap(&x,&y,sizeof(int));
void * means a generic pointer.
char buffer[size] is to set aside enough space to hold byte info.
memcpy(target, source, size) is a more generic function to copy byte info with respect to the byte length.
Most energy is used to dynamically allocate and deallocate buffer.
The perk of using this method compared to C++ template is that this way is lean and economical, while the C++ template will generate patches as much as the call times in the executables.
Wrong usage:
int i = 44;
short j=5;
swap(&i, &j, sizeof(short))
If using generic code, you have to be very careful about the type. The above usage will cause unexpected result as the short and int are different types with different byte lengthes.
Another example of the generic code (a very complicated case):
char * husband = strdup("Fred");
char * wife = strdup("Wilma");
// Right usage
swap(&husband, &wife, sizeof(char *))
Note here we are acturally swap the bit patterns (address stored in char *) of two char pointers. We still need the reference operator &. See the blackboard:
Some terrible errors:
swap(husband, wife, sizeof(char *)) // will swap the first 4 chars in heap
swap(husband, &wife, sizeof(char *)) // will make things chaos, the first 4 chars will be interpreted as an address!
Generic lsearch
An example for linear search:
int lsearch(int key, int array[], int size){
for (i=0;i<size;i++){
if (array[i]==key){
return i;
}
}
return -1;
}
Let’s make it generic! How about a undefinite type of array?
void *lsearch(void *key, void *base, int n, int elemSize){
for (i=0;i<n;i++){
void *elemAddr = (char *) base + i*elemSize;
if (memcmp(key, elemAddr, elemSize)==0)
return elemAddr;
return NULL;
}
}
It does not work for character pointers or C-strings.
Qustions
Appendix
C++ Template
Function templates are special functions that can operate with generic types. This allows us to create a function template whose functionality can be adapted to more than one type or class without repeating the entire code for each type.
template <class myType>
myType GetMax (myType a, myType b) {
return (a>b?a:b);
}
int x, y;
GetMax <int> (x, y);
Glossary
perk 额外好处 sedate v. 安慰 sentinel 哨兵
Updated 2020-08-06