Proper Memory allocation

Question

I have the following construction:

typedef struct bucket {
    char *key;
    ENTRY *data;
    struct bucket *next;
} bucket;

typedef struct {
    size_t size;
    bucket **table;
} hash_table;

But I have no idea how to allocate memory for that. I tried:

hash_table* ht = malloc(sizeof(hash_table)*101);

in order to create a hashtable for 101 entries but it din't work! Can anyone help me? I would really appreciate it!

Answer 1

The hash_table will always be only sizeof(hash_table) bytes big. The table element is a pointer to an array of poiinters to bucket elements. So you'd need something like this:

hash_table* ht = malloc(sizeof(hash_table));
ht->size = 101;
ht->table = malloc(sizeof(bucket*)*ht->size);

But I suspect that there may be some initialization method that comes with that, and you could then do something like this:

hash_table* ht = alloc_hash_table(101);

Anyway, I'm kind of rusty in C, so take this with a grain of salt.

Answer 2

Not quite. Assuming this is C, you probably want to make a function:

 hash_table* init_table(size_t size) {
     size_t i;
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table));
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)malloc(sizeof(bucket*)*size);
     if (ht->table == NULL) {
         free(ht);
         return NULL;
     }
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

You might need some other fields in that struct.

If you wanted to be tricky, and never realloc the bucket, you can do this:

 hash_table* init_table(size_t size) {
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table)+sizeof(bucket)*size);
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)(ht+1);
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

EDIT: I fixed my bucket* table's to bucket**

EDIT2: I've gotten rid of the memsets and added error checking for malloc.

Answer 3

It doesn't make sense to allocate all 101 (or however many) buckets upfront, you'd typically allocate them one at a time, when inserting new data into the table.

It does make sense to pre-allocate the hash array, which will have a fixed size, but that is an array of bucket pointers, not an array of buckets, so some of the answers are wrong.

You'd have something like this, to create a an empty hash table, with a fixed-size bucket array:

hash_table * hash_table_new(size_t capacity)
{
  size_t i;

  hash_table *t = malloc(sizeof *t);
  t->size = capacity;
  t->bucket = malloc(t->size * sizeof *t->bucket);
  for(i = 0; i < t->size; i++)
    t->bucket[i] = NULL;
  return t;
}

This code:

• Allocates a hash_table structure to hold the table
• Initializes it's size with indicated capacity
• Allocates an array of bucket pointers of the proper length
• Makes sure each bucket pointer is NULL (which cannot properly be done with memset(), as it's not safe to assume that "all bits zero" is the way NULL looks in memory)
• Uses sizeof whenever possible, but not on types, so no parenthesis
• Doesn't cast the return value of malloc(), since that is never a good idea in C
• Doesn't check the return value of malloc(), of course you should do that in real code

A second function would be needed to do an actual hash insert, which will then need to allocate a new bucket, compute the hash value from the key, pick the proper location in the hash table's array, and insert the new entry there.

Answer 4

There's a few things worong with your typedef's. Assuming your using MSVC.

An easy way to declare the types you have here would be something like;

This typedef includes the _type {} type, *ptype; format which declares the type and the pointer to your custom type all at the same time. If you see down in hash_table, your are able to use pbucket *table, which eliminates the extra *** in your code and can help when doing dynamic allocation (help so mucah as to keep your head straight about what your allocating etc..). Your original typedef, if you look had typedef struct bucket {} bucket;, you need to at least modify one of the two "bucket" names you have there when you specify your typedef.

You also need to cast if your using C++ build settings, if using plain C you may not need the cast, so your malloc line would be (with the following typedef changes I made);

hash_table* ht = (phash_table) malloc(sizeof(hash_table)*101);

Either way, this snippet should work for you;

typedef struct _bucket {    
    char *key;    
    void *data;    
    _bucket *next;
} bucket, *pbucket;

typedef struct _hash_table {    
    size_t size;    
    pbucket *table;
}hash_table, *phash_table;