• C

C hashtable library

Hi there,
Is there a hashtable library for C.  Does POSIX/standard C library has a hash table API? thanks.
ambuliAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

phoffric\Commented:
The three functions hcreate(), hsearch(), and hdestroy() allow the caller to create and manage a hash search table containing entries consisting of a key (a string) and associated data. Using these functions, only one hash table can be used at a time.
http://linux.die.net/man/3/hsearch
phoffric\Commented:
Conforming To

The functions hcreate(), hsearch(), and hdestroy() are from SVr4, and are described in POSIX.1-2001. The functions hcreate_r(), hsearch_r(), and hdestroy_r() are GNU extensions.
http://linux.die.net/man/3/hsearch
sarabandeCommented:
only one hash table can be used at a time
that means they were using static or global memory.

perhaps the following c functions also would meet your requirements:

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

typedef struct hashitem
{
   char * key;
   void * data;
} HASHITEM, *PHASHITEM;

typedef struct hashnode
{
     struct hashitem  item;
     struct hashnode * pnext;
} HASHNODE, *PHASHNODE;

typedef unsigned int (* PHASHFUNC)(const char * psz);

typedef struct hashtable
{
     PHASHNODE table;
     int size;
     PHASHFUNC hashfunc;
} HASHTABLE, *PHASHTABLE;

PHASHTABLE hash_create(int maxslots, PHASHFUNC func)
{
      PHASHTABLE pt = (PHASHTABLE)calloc(sizeof(HASHTABLE), 1);
      pt->table = (PHASHNODE)calloc(maxslots, sizeof(HASHNODE));
      pt->size  = maxslots;
      pt->hashfunc = func;
      return pt;
}

void hash_free(PHASHTABLE pt)
{
     int n;
     PHASHNODE pnode, pnext;
     for (n = 0; n < pt->size; n++)
     {
            pnode = &pt->table[n];
            if (pnode->item.key != NULL)
                 free(pnode->item.key); 
            pnode = pnode->pnext;
            while (pnode != NULL)
            {
                  if (pnode->item.key != NULL)
                       free(pnode->item.key); 
                  pnext = pnode->pnext;
                  free(pnode);
                  pnode = pnext;
           }
     }
     free (pt->table);
     free (pt);
}

int hash_insert(PHASHTABLE pt, const char * pkey, void * pdata)
{
      unsigned int hash;
      PHASHNODE pnode;
      hash = pt->hashfunc(pkey);
      pnode = &pt->table[hash%pt->size];
      while (pnode->item.key != NULL)
      {
          if (strcmp(pnode->item.key, pkey) == 0)
               return 0;  // duplicate key
          if (pnode->pnext == NULL)
          {
              pnode->pnext = (PHASHNODE)calloc(1, sizeof(HASHNODE));
          }
          pnode = pnode->pnext;
     }
    pnode->item.key = strdup(pkey);
    pnode->item.data = pdata;
    pnode->pnext = NULL;
    return 1;
}   

PHASHITEM hash_search(PHASHTABLE pt, const char * pkey)
{
      unsigned int hash;
      PHASHNODE pnode;
      hash = pt->hashfunc(pkey);
      pnode = &pt->table[hash%pt->size];
      while (pnode->item.key != NULL)
      {
          if (strcmp(pnode->item.key, pkey) == 0)
              return &pnode->item;
          if (pnode->pnext == NULL)  break;
          pnode = pnode->pnext;
     }
     return NULL;
}

unsigned int HashValue(const char * psz)
{
     unsigned int hash = 676277; // use some odd starter
     char * p = (char *)psz;
     int    r = 7;
     while (*p)
     {
          unsigned int c = *p;  
          hash += (c+r) + (c/((r%31)+1)) + ((r*r+1)/c);
          r += c + r - 17;
          p++;
     }
     return hash;
}      

int main()
{
    PHASHITEM pitem = NULL;
    PHASHTABLE pt = hash_create(100, HashValue);
    hash_insert(pt, "John Brown", (void*)12345);
    hash_insert(pt, "Tina Miller", (void*)11111);
    hash_insert(pt, "Anna Smith", (void*)22222);
    hash_insert(pt, "James Trunk", (void*)3333);
    hash_insert(pt, "Jerry Cotton", (void*)44444);
    hash_insert(pt, "Anna Williams", (void*)98765);
    pitem = hash_search(pt, "Tina Miller");
    pitem = hash_search(pt, "Berta Newman");
    hash_free(pt);
    return 0;
}

Open in new window


the above code easily could be enhanced to handle keys other than strings.

Sara

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.