Ufdjrw

I don't understand why my program seg faults at this line: if ((**table->table).link == NULL){ I seem to have malloc-ed memory for it, and I tried looking at it with gdb. *table->table was accessible and not NULL, but **table->table was not accessible.
Definition of hash_t:

struct table_s 
 struct node_s **table;
 size_t bins; 
 size_t size;
;

typedef struct table_s *hash_t;

void set(hash_t table, char *key, int value)
 unsigned int hashnum = hash(key)%table->bins;
 printf("%d n", hashnum);
 unsigned int i;
 for (i = 0; i<hashnum; i++)
 (table->table)++;
 
 if (*(table->table) == NULL)
 struct node_s n = key, value, NULL;
 struct node_s *np = &n;
 *(table->table) = malloc(sizeof(struct node_s));
 *(table->table) = np;
 else
 while ( *(table->table) != NULL)
 if ((**table->table).link == NULL)
 struct node_s n = key, value, NULL;
 struct node_s *np = &n;
 (**table->table).link = malloc(sizeof(struct node_s));
 (**table->table).link = np;
 break;
 else if (strcmp((**table->table).key, key) == 0)
 break;
 
 *table->table = (**(table->table)).link;
 
 if (table->size/table->bins > 1)
 rehash(table);
 
 

I'm calling set from here:

 for (int i = 0; i < trials; i++) 
 int sample = rand() % max_num;
 sprintf(key, "%d", sample);
 set(table, key, sample);
 

Your hashtable works like this: You have bins bins and each bin is a linked list of key / value pairs. All items in a bin share the same hash code modulo the number of bins.

You have probably created the table of bins when you created or initialised the hash table, something like this:

table->table = malloc(table->bins * sizeof(*table->table);

for (size_t i = 0; i < table->bins; i++) table->table[i] = NULL;

Now why does the member table have two stars?

• The "inner" star means that the table stores pointers to nodes, not the nodes themselves.


• 
  

  The "outer" start is a handle to allocated memory. If your hash table were of a fixed size, for example always with 256 bins, you could define it as:

  
  
  

  struct node_s *table[256];
  

  
  
  

  If you passed this array around, it would become (or "decay into") a pointer to its first element, a struct node_s **, just as the array you got from malloc.

  
  


• You access the contents of the l´bins via the linked lists and the head of linked list i is table->table[i].

You code has other problems:

• What did you want to achieve with (table->table)++? This will make the handle to the allocated memory point not to the first element but tho the next one. After doing that hashnum times, *table->table will now be at the right node, but you will have lost the original handle, which you must retain, because you must pass it to free later when you clean up your hash table. Don't lose the handle to allocated memory! Use another local pointer instead.




• You create a local node n and then make a link in your linked list with a pointer to that node. But the node n will be gone after you leave the function and the link will be "stale": It will point to invalid memory. You must also create memory for the node with malloc.

A simple implementation of your has table might be:

void set(hash_t table, char *key, int value)

 unsigned int hashnum = hash(key) % table->bins;

 // create (uninitialised) new node
 struct node_s *nnew = malloc(sizeof(*nnew));

 // initialise new node, point it to old head
 nnew->key = strdup(key);
 nnew->value = value;
 nnew->link = table->table[hashnum];

 // make the new node the new head
 table->table[hashnum] = nnew;

This makes the new node the head of the linked list. This is not ideal, because if you overwrite items, the new ones will be found (which is good), but the old ones will still be in the table (which isn't good). But that, as they say, is left as an exercise to the reader.

(The strdup function isn't standard, but widely available. It also creates new memory, which you must free later, but it ensures, that the string "lives" (is still valid) after you have ceated the hash table.)

Please not how few stars there are in the code. If there is one star too few, it is in hash_t, where you have typecasted away the pointer nature.