hashtab.c

   1 /*
   2  * $Id: hashtab.c,v 1.2 2007/07/22 13:33:26 khansen Exp $
   3  * $Log: hashtab.c,v $
   4  * Revision 1.2  2007/07/22 13:33:26  khansen
   5  * convert tabs to whitespaces
   6  *
   7  * Revision 1.1  2004/06/30 07:55:43  kenth
   8  * Initial revision
   9  *
  10  */
  11
  12 /**
  13  *    (C) 2004 Kent Hansen
  14  *
  15  *    The XORcyst is free software; you can redistribute it and/or modify
  16  *    it under the terms of the GNU General Public License as published by
  17  *    the Free Software Foundation; either version 2 of the License, or
  18  *    (at your option) any later version.
  19  *
  20  *    The XORcyst is distributed in the hope that it will be useful,
  21  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  *    GNU General Public License for more details.
  24  *
  25  *    You should have received a copy of the GNU General Public License
  26  *    along with The XORcyst; if not, write to the Free Software
  27  *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  28  */
  29
  30 /**
  31  * This file contains an implementation of a hash table.
  32  * Both keys and values are of type void *.
  33  * To implement hashing and key comparison, you have to supply two functions
  34  * for doing this job. If keys are strings, then you can use the default
  35  * functions below.
  36  */
  37
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include "hashtab.h"
  41
  42 #define SAFE_FREE(a) if (a) { free(a); a = NULL; }
  43
  44 /*---------------------------------------------------------------------------*/
  45
  46 /**
  47  * Supplies default hashing function when key is a string.
  48  */
  49 int HASHTAB_STRKEYHSH(void *key)
  50 {
  51     int i;
  52     unsigned char *s = (unsigned char *)key;
  53     int sum = 0;
  54     for (i=0; s[i] != '\0'; i++) {
  55         sum += s[i];
  56     }
  57     return sum;
  58 }
  59
  60 /**
  61  * Supplies default key comparison function when key is a string.
  62  */
  63 int HASHTAB_STRKEYCMP(void *key1, void *key2)
  64 {
  65     return (strcmp((char *)key1, (char *)key2) == 0) ? 1 : 0;
  66 }
  67
  68 /*---------------------------------------------------------------------------*/
  69
  70 /**
  71  * Creates a hash table.
  72  * @param size Number of slots
  73  * @param keyhsh Procedure which computes h(k)
  74  * @param keycmp Procedure which compares two keys
  75  * @return The newly created hash table
  76  */
  77 hashtab *hashtab_create(int size, keyhashproc keyhsh, keycompareproc keycmp)
  78 {
  79     int i;
  80     /* Allocate space for hash table */
  81     hashtab *ht = (hashtab *)malloc( sizeof(hashtab) );
  82     if (ht != NULL) {
  83         /* Allocate space for slots */
  84         ht->size = size;
  85         ht->slots = (hashtab_slot **)malloc( sizeof(hashtab_slot *) * size );
  86         if (ht->slots != NULL) {
  87             /* Set the hash and comparator procedures */
  88             ht->keyhsh = keyhsh;
  89             ht->keycmp = keycmp;
  90             /* Initialize the slots */
  91             for (i=0; i<size; i++) {
  92                 ht->slots[i] = NULL;
  93             }
  94         }
  95     }
  96     /* Return the created hash table */
  97     return ht;
  98 }
  99
 100 /**
 101  * Puts something in a hash table.
 102  * @param ht Hash table
 103  * @param key Key
 104  * @param data Data
 105  */
 106 void hashtab_put(hashtab *ht, void *key, void *data)
 107 {
 108     int i;
 109     hashtab_slot *s;
 110     hashtab_slot *fresh;
 111     /* Create a new entry */
 112     fresh = (hashtab_slot *)malloc( sizeof(hashtab_slot) );
 113     if (fresh != NULL) {
 114         fresh->key = key;
 115         fresh->data = data;
 116         fresh->next = NULL;
 117         /* Figure out in which slot to put it */
 118         i = ht->keyhsh(key) % ht->size;
 119         /* Now put it! */
 120         if (ht->slots[i] == NULL) {
 121             /* Start the list */
 122             ht->slots[i] = fresh;
 123         }
 124         else {
 125             /* Add to end of list */
 126             for (s = ht->slots[i]; s->next != NULL; s = s->next) ;
 127             s->next = fresh;
 128         }
 129     }
 130 }
 131
 132 /**
 133  * Gets the data associated with given key.
 134  * @param ht Hash table
 135  * @param key Key
 136  * @return The data associated with key, or <code>NULL</code> if key not found
 137  */
 138 void *hashtab_get(hashtab *ht, void *key)
 139 {
 140     hashtab_slot *s;
 141     int i = ht->keyhsh(key) % ht->size;
 142     for (s = ht->slots[i]; s != NULL; s = s->next) {
 143         if (ht->keycmp(key, s->key)) {
 144             return s->data;
 145         }
 146     }
 147     return NULL;
 148 }
 149
 150 /**
 151  * Removes something from hash table.
 152  * @param ht Hash table
 153  * @param key Key
 154  * @return Data associated with key
 155  */
 156 void *hashtab_remove(hashtab *ht, void *key)
 157 {
 158     hashtab_slot *s;
 159     int i = ht->keyhsh(key) % ht->size;
 160     for (s = ht->slots[i]; s != NULL; s = s->next) {
 161         if (ht->keycmp(key, s->key)) {
 162             // TODO: remove s...
 163             return NULL;
 164         }
 165     }
 166     return NULL;
 167 }
 168
 169 /**
 170  * Finalizes hash table.
 171  * @param ht The hash table to finalize
 172  */
 173 void hashtab_finalize(hashtab *ht)
 174 {
 175     hashtab_slot *s;
 176     hashtab_slot *t;
 177     int i;
 178     for (i=0; i<ht->size; i++) {
 179         s = ht->slots[i];
 180         while (s != NULL) {
 181             t = s->next;
 182             SAFE_FREE(s);
 183             s = t;
 184         }
 185     }
 186     SAFE_FREE(ht->slots);
 187     free(ht);
 188 }