Bifalgorithm post · Computer science one · Function Pointers

How can pointer arithmetic and comparators implement a generic getMax()?

How can pointer arithmetic and comparators implement a generic getMax()? (Computer science one · Function Pointers) — "There are a couple of issues here that w…

Ideas in this flowchart

  • Accéder génériquement aux éléments d’un tableau de void * en C
  • Les pointeurs void * ne peuvent pas être indexés directement avec arr[i].
  • Pour les types intégrés, le compilateur connaît la taille des éléments et calcule automatiquement l’offset.
  • La fonction doit recevoir la taille de chaque élément en octets via un paramètre size_t size.
  • L’accès aux éléments génériques nécessite de calculer manuellement l’arithmétique des pointeurs.
  • L’adresse du i-ième élément se calcule avec arr + i * size.
  • Ce calcul produit l’adresse mémoire de l’élément sous forme de pointeur void *.
  • getMax() transmet au comparateur l’adresse de l’élément maximal actuel et celle du i-ième élément.
  • Si le comparateur renvoie une valeur négative, maxIndex est mis à jour avec i.
  • La version finale de getMax() parcourt le tableau générique et renvoie l’indice du plus grand élément.
Feed/

How can pointer arithmetic and comparators implement a generic getMax()?

No cover

Channel

Computer science one

1 page

"There are a couple of issues here that we have to deal with. When working with generic void * pointers in C and using arrays, you cannot simply index using the usual 0, 1, 2, etc. indices. Recall that when elements are stored in an array, the index represents an offset of a memory address. If the array is an array of integers or double or some other built-in type, the compiler knows how large each one is and is able to compute the appropriate offset given the usual 0, 1, 2, etc. indices. However, when dealing with void * elements, a function must be told how many bytes each element takes. C uses an unsigned integer type, size_t to indicate a size in bytes, so we’ll use it as well. We modify the function signature above to pass in a size_t size parameter.\n\nWe now need a way to access each element in the array. The array itself is generic. We cannot simply use indices such as arr[i] to access elements. Since it is a void * pointer, we cannot simply dereference it using an index. The compiler doesn’t know how many bytes each element takes, so it cannot compute an offset using the index variable i. Instead, we need to do the pointer arithmetic ourselves. We could use the size parameter, say arr[i*size] to compute the offset of the i-th element, but this still dereferences a void pointer, which we generally do not want to do. Instead, we can use the pointer arr and do some simple arithmetic; arr is the starting memory location, so if we simply add i*size to it, that gives us the memory location of the i-th element as a void pointer!\n\nvoid *first = arr + 0 * size; //first element\n\nvoid *second = arr + 1 * size; //second element\n\nvoid *third = arr + 2 * size; //third element\n\n...\n\nvoid *x = arr + i * size; //i-th element\n\nWe can use this in our getMax() function to iterate over each element in the array and pass it to our comparator. The comparator expects generic void pointers, and that is what our pointer arithmetic is computing. Passing two memory addresses to the comparator determines which is the larger of two elements in the array. To do this, we call the comparator on the maximum element we’ve found so far and the i-th element in the loop. If it returns something negative, then we know that the “max” element is less than the i-th element and so update our maxIndex variable. Making these changes results in the this final version.\n\nint getMax(const void *arr, int n, size_t size,\n\nint(*cmp)(const void *, const void *)) {\n\nint i, maxIndex = 0;\n\nfor(i=1; i<n; i++) {\n\nif(cmp(arr + maxIndex * size, arr + i * size) < 0) {\n\n//we've found something larger, update the max_index:\n\nmaxIndex = i;\n\n}\n\n}\n\nreturn maxIndex;\n\n}"

Flowchart preview
👍
0
0 comments0 shares

Sign in to view and post comments.