I am trying to understand the ff searching algorithm, (that tries to find the index of the element being searched). However, I don't know how it can work with any type of data type. So, the ff questions still remain
- inside the code, it says we can use char pointer since char is only one byte. However, once we made it a char pointer, doesn't it become 8 bytes instead of one byte? also even if it becomes, one byte, how does it help us deal with any type of data(as it claims to do so inside the code)?
- since the whole thing claims, it can work for any type of data, does this work for user-defined data(like structs)? if so, I would appreciate an explanation on how to do so.(i.e. how can we make this work for both int a[] ={7,3,5,7,8,90} and struct student {char name, int score, int id} struct student stude_array [] ={{"Rebeka",92,10},{"Alext",97,11},{"james",90,12}}* data types and search for specific element in each arrays? thank you for your help in advance.
#include <stdio.h>
#include <stdbool.h>
// A compare function that is used for searching an integer
// array
bool compare (const void * a, const void * b)
{
return ( *(int*)a == *(int*)b );
}
// General purpose search() function that can be used
// for searching an element *x in an array arr[] of
// arr_size. Note that void pointers are used so that
// the function can be called by passing a pointer of
// any type. ele_size is size of an array element
int search(void *arr, int arr_size, int ele_size, void *x,
bool compare (const void * , const void *))
{
// Since char takes one byte, we can use char pointer
// for any type/ To get pointer arithmetic correct,
// we need to multiply index with size of an array
// element ele_size
char *ptr = (char *)arr;
int i;
for (i=0; i<arr_size; i )
if (compare(ptr i*ele_size, x))
return i;
// If element not found
return -1;
}
int main()
{
int arr[] = {2, 5, 7, 90, 70};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 7;
printf ("Returned index is %d ", search(arr, n,
sizeof(int), &x, compare));
return 0;
}
CodePudding user response:
- inside the code, it says we can use char pointer since char is only one byte. However, once we made it a char pointer, doesn't it become 8 bytes instead of one byte?
It's talking there about the pointer and pointer arithmetic, not about the pointed-to object. No part of the pointed-to data is converted, and the size of a pointer (which is not necessarily 8 bytes) has nothing to do with it.
also even if it becomes, one byte, how does it help us deal with any type of data(as it claims to do so inside the code)?
The key thing here is that pointer arithmetic, such as ptr i*ele_size
, operates in units the size of the pointed-to type. If you want to perform such computations in one-byte units, then you need to do it with a pointer to a character type (or to an extension type of that size).
- since the whole thing claims, it can work for any type of data, does this work for user-defined data(like structs)?
The search()
function can work with any type of data. Whether it does work depends on the user passing a pointer to a compare
function that is appropriate to the particular type of data provided in that call.
if so, I would appreciate an explanation on how to do so.(i.e. how can we make this work for both int a[] ={7,3,5,7,8,90} and struct student {char name, int score, int id} struct student stude_array [] ={{"Rebeka",92,10},{"Alext",97,11},{"james",90,12}} data types and search for specific element in each arrays?
You already presented an example of how to use it for an array of int
. For the struct array, you must, again, provide an appropriate comparison function. So,
bool compare_students(const void * a, const void * b) {
const struct student *student_a = a;
const struct student *student_b = b;
// comparison details left as an exercise ...
}
// ...
void f(void) {
struct student student_array[] = {{"Rebeka", 92, 10}, {"Alext", 97, 11},
{"james", 90, 12}};
struct student james = {"james", 90, 12};
struct student john = {"John", 99, 17};
int index = search(student_array, 3, sizeof(struct student), &james,
compare_students);
printf("james: %d\n", index);
index = search(student_array, 3, sizeof(struct student), &john,
compare_students);
printf("john: %d\n", index);
}
CodePudding user response:
This function will only work for data that has no pointers to nested data. Only then a byte-by-byte comparison will work. This is called shallow comparison.
Let's say you have a struct
with a dynamically allocated (i.e. using malloc()
or friend) char *
string member. When you have two of these structs, the actual text of these strings can be the same, but, because their memory is dynamically allocated, the char *
struct
members being compared are two different pointers/addresses.
Then, even if a struct
does not have dynamically allowed memory, there are situations where this dumb shallow compares will fail. This is because the memory occupied by a struct
can have unused bytes (or even bits when having bit fields); this is called padding. If a structure contains a char
and a 4-byte int
for example, it's common to get 3 unused bytes between where the char
and int
are. Unless you explicitly make sure that the padding is set to the same value (e.g. 0), the padding can contain random data, which will of course fail the comparison (or even worse, work most of the time by sheer luck and sometimes not).
I hope this helps.