pelles hashtable

[czerny]

Hallo,

I needed a simple hashtable, so I decided to test the included implementation.
I wrote a little test file to learn how it is used.

Code: [Select]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>


int main(int argc, char **argv)
{
_ENTRY *item, *ret;
char command, buffer[200];

item = malloc(sizeof(_ENTRY));

if (_hcreate(10)) do {

printf("\n[q]uit [i]nsert [f]ind : ");

while ('\n'==(command = getchar()));

switch (command) {

case 'i' : printf(" name : "); scanf("%s", buffer);
item->key  = malloc(strlen(buffer)+1);
strcpy(item->key, buffer);

printf("phone : "); scanf("%s", buffer);
item->data = malloc(strlen(buffer)+1);
strcpy(item->data, buffer);

ret = _hsearch(*item, _ENTER);
if (ret) printf("\n> ok\n"); else printf("\n> ups\n");
break;

case 'f' : printf("name : "); scanf("%s", buffer);
item->key = buffer;
ret = _hsearch(*item, _FIND);
if (ret) printf("\n> %s -> %s\n", ret->key, (char *)ret->data);
else printf("\n> ups\n");
break;

case 'q' : _hdestroy();
break;

default  : printf("?\n");
}

} while ( command != 'q' );

free(item);

return 0;
}

But it is not clear to me, how to free the key and data memory afterwards. May be I have not understand how to use this at all. Any hints?

czerny

[CommonTater]

In general... for every time you use malloc(), calloc() or realloc() you need a matching call to free()...

The order can matter... if you are using malloc for the key and data entry in the table you need to free them before you destroy the entry.  To not do so will cause memory leaks.  To do it in the wrong order --removing the entry first-- will result in undefined behaviour since the entry pointer is no longer valid.  So, you get into a loop of unwinding the array or linked list that holds your entries, tearing it down entry by entry.

As a general comment... I usually try not to put code in switch statements.  What I do is write functions and call them from the switch statment.  The resulting code is nicely modular, allowing you to troubleshoot, modify, even replace, whole sections of code without any consequence to the switch itself. You'll understand why the first time you have to diagnose a problem in a switch statement gone wrong... the more code you have in there, the harder the problem is to find.  As a very smart teacher once advised: "Think in smaller blobs".

[TimoVJL]

Maybe this helps:

Code: [Select]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

char *data[] = {"aaa","bbb","ccc"};

int main(void)
{
ENTRY e, *ep;
int i;
char *p;

hcreate(5);
int eidx = 0;
ENTRY **earr = malloc(5*sizeof(ENTRY*));
memset(earr, 0, sizeof(earr));
for (i = 0; i < sizeof(data)/sizeof(data[0]); i++)
{
e.key = data[i];
//e.data = (void *)i;
p = malloc(10);
sprintf(p, "%d", i);
e.data = p;
ep = hsearch(e, ENTER);
if (ep)
earr[eidx++] = ep;
else free(p);
}
for (int idx = 0; earr[idx];idx++)
{
printf("%s %s\n", earr[idx]->key, (char*)earr[idx]->data);
free(earr[idx]->data);
}
hdestroy();
free(earr);
return 0;
}If there are any errors, let me know.
EDIT: fixed missing free()  for earr

[czerny]

Hi tmovjl,

in my understanding the _ENTRY pointer array is created by _hcreate() and freed by _hdestroy(). Your earr is a unnecessary copy of this and should deallocated by yourself.
Your data array is not dynamic data. Maybe this is the point.

czerny

[TimoVJL]

That earr is just an array of pointers of _ENTRY's.
With that list you can go trough entries and print or free allocated memory.

[czerny]

timovjl,

what about this?

Code: [Select]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

char *data[] = {"aaa","bbb","ccc"};

int main(void)
{
_ENTRY e, *ep;
int i;
char *p;

_hcreate(5);

for (i = 0; i < sizeof(data)/sizeof(data[0]); i++)
{
e.key = data[i];
//e.data = (void *)i;
p = malloc(10);
sprintf(p, "%d", i);
e.data = p;
ep = _hsearch(e, _ENTER);
if (!ep) free(p);
}
for (i = 0; i < sizeof(data)/sizeof(data[0]); i++)
{
e.key = data[i];
ep = _hsearch(e, _FIND);
printf("%s %s\n", ep->key, (char*)ep->data);
free(ep->data);
}
_hdestroy();
return 0;
}
But the keys are not dynamic data! :-(

czerny

[TimoVJL]

That data[] array was just for example of inputs when testing that concept.
Think those as test data from user.
_hcreate and earr must be same size.

[czerny]

Hi,

I should have read the documentation better! Pelle wrote: ' ... so the two pointers must point to permanent memory ...'.

I think about the pros and cons of the two ways to design datastructures. The one way is to operate on existing data, like Pelles hash table, the other way carrys the data too and frees it afterwards.

It is obvious that the first way is the less memory consuming way if the data memory is anyway needed in other contextes. The second way then works on a copy of the data. But this might be less error-prone.

Imagine you have an array of ints and want to sort them with a binary tree. If the tree is designed in the first way (operates on addresses) the following can happen. If the int addresses are insert in the tree and then the referenced ints read back inorder and filled in the array, the array gets destroyed. A similar can happen with pointers too. Say we have an array of string pointers with some equal strings. We read them in the tree which (for example) does refuse identical strings, than ...

It is clear that these all are programming errors. But I think that datastructures should have as little as possible sideeffects.

What do you think?

czerny

[czerny]

I have made an little example which works in the second way.

There is a little naming error!

The function 'hashfunc()' should better named 'keybuilder()' because it should only produce uniq long keys. The hash function is build in (modulo) and is in this example not intended to be changeable.

czerny

[czerny]

I have done a stringmap based on Pelles hash functions, to understand it better.

Because of the limitations of Pelles hash, there is only one stringmap possible per thread.