Thread: Hash Table pointer question

As part of my C course I'm trying to teach myself pointers in depth. I've looked up some abstract data types to implement with structures.

I came across this implementation of a hash table, with seperate chaining as a collision mechanism. I'm confused with the some of the ways data is accessed using pointers. I've also left out the hash function.

Just to clarify:

-Is list_t **table a pointer to a pointer to a linked list structure?

-Looking at the line below, is an array of **table pointers being made, each of which point to a pointer to a linked list?

Code:

 for(i=0; i<size; i++) new_table->table[i]

-When a lookup hash is performed in lookup, does the line below pull out a pointer to a linked list contained within the table[] array?

Code:

list = hashtable->table[hashval]

Subsequently, does this line deference the pointer above and access the element within the linked list?

Code:

list = list->next

Many thanks.

Originally Posted by gibson221

-Is list_t **table a pointer to a pointer to a linked list structure?

Yes. table is a "pointer to a pointer to a list_t". Since list_t is basically a linked list structure, you're right.

Originally Posted by gibson221

-Looking at the line below, is an array of **table pointers being made, each of which point to a pointer to a linked list?

Code:

 for(i=0; i<size; i++) new_table->table[i]

Almost right, you have one to many "*" or "pointer to" in there. An array of *tables is being made. He's malloc'ing an "array of pointers to list_t". If you look at the malloc there, he mallocs sizeof(list_t *) * size. That is an array with size elements of type list_t * (pointer to list_t).

Originally Posted by gibson221

-When a lookup hash is performed in lookup, does the line below pull out a pointer to a linked list contained within the table[] array?

Code:

list = hashtable->table[hashval]

Basically, yes. list is being used as an iterator. This sets it to the first element in the linked list for the hash value hashval. The loop moves list through the linked list looking for that exact string, and if found, returns that node of the linked list.

Originally Posted by gibson221

Subsequently, does this line deference the pointer above and access the element within the linked list?

Code:

list = list->next

Sort of, yes. list is a pointer to a struct, so list->next dereferences the pointer and gives the 'next' element. Basically, this is the part where the iterator is being moved to the next element in the linked list.

Originally Posted by anduril462

Almost right, you have one to many "*" or "pointer to" in there. An array of *tables is being made. He's malloc'ing an "array of pointers to list_t". If you look at the malloc there, he mallocs sizeof(list_t *) * size. That is an array with size elements of type list_t * (pointer to list_t).

Thanks for clearing that up. Just one question, so by malloc'ing an array of pointers to a list_t to **table, an array of *tables is being made because a *table deferences **table and is a pointer to a linked list?

Also, when is a explicit return type required with malloc in this case? For instance is the following also valid?

Code:

((new_table->table = (list_t *) malloc(sizeof(list_t) * size))

Thanks again.

Originally Posted by gibson221

Thanks for clearing that up. Just one question, so by malloc'ing an array of pointers to a list_t to **table, an array of *tables is being made because a *table deferences **table and is a pointer to a linked list?

Yeah, I think you more or less understand. To (hopefully) clarify:

by malloc'ing an array of pointers to list_t to **table, an array of *tables is being made, because of the close relationship between arrays and pointers in C. Doing table[i] is the same as doing *(table + i). To take that a little further, adding an integer (like an array index) to a pointer type (such as table, a list_t **) results in the same type, that is (table + i) is the same type as table. Therefore, since table[i] == *(table + i), and the type of (table + i) is the same as the type of table, when you do table[i], you are basically dereferencing a list_t ** and getting a list_t *.

Originally Posted by gibson221

Also, when is a explicit return type required with malloc in this case? For instance is the following also valid?

Code:

((new_table->table = (list_t *) malloc(sizeof(list_t) * size))

Valid, yes, but often, casting the return value of malloc is not recommended. Read this: FAQ > Casting malloc - Cprogramming.com.

OK great, that makes sense now. Thanks.