Correct memory allocation
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 this. I tried:
hash_table* ht = malloc(sizeof(hash_table)*101);
to create a hash table for 101 records, but it doesn't work! Can anyone help me? I would be very grateful!
source to share
Not really. Assuming this is C, you probably want to create 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 may need other fields in this structure.
If you want to be complex and never flip 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 have set the table with bucket * to bucket **
EDIT2: I got rid of memsets and added error checking for malloc.
source to share
It's not practical to allocate all 101 (or as many) buckets in advance, you usually allocate them one at a time when you insert new data into the table.
It makes sense to preallocate a hash array that will be of a fixed size, but this is an array of pointers to a bucket, not an array of buckets, so some of the answers are wrong.
You have something like this to create 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 store the table
- Initializes the size with the specified capacity
- Allocates an array of pointers to a bucket of the appropriate length
- Ensures that every bucket pointer is NULL (which cannot be accomplished with memset (), as it is not safe to assume that "all bits are zero" is the way NULL looks in memory)
- Uses
sizeof
whenever possible, but not by type, so no parentheses - Doesn't return a return value
malloc()
as it is never a good idea in C - Doesn't check the return value of malloc (), of course you have to do it in real code
The actual hash insert would require a second function, which would then have to allocate a new bucket, compute the hash value from the key, select a suitable location in the hash table array, and insert the new entry there.
source to share
hash_table
there will always be only sizeof(hash_table)
bytes. Element table
is a pointer to an array of poiinters elements on bucket
. So, you need something like this:
hash_table* ht = malloc(sizeof(hash_table));
ht->size = 101;
ht->table = malloc(sizeof(bucket*)*ht->size);
But I suspect there might be some kind of initialization method that comes with this, and you could do something like this:
hash_table* ht = alloc_hash_table(101);
Anyway, I'm a little rusty in C, so take this with a grain of salt.
source to share
There are several things about your typedef. Assuming you are using MSVC.
An easy way to declare the types you have here would be something like this:
This typedef includes the type _type {}, * ptype; a format that simultaneously declares a type and a pointer to your own type. If you see down in the hash_table, you can use the pbucket * table, which removes the extra *** in your code and can help with dynamic allocation (help mucah like this to keep your head straight on what you are allocating, etc.) ... Your original typedef, if you look, has a typedef struct bucket {} bucket ;, you need to change at least one of the two bucket names you have when you specify your typedef.
You also need to use if you are using C ++ build settings, if you are using plain C you may not need to cast, so your malloc line will 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;
source to share