RCS/hashtab.c,v

   1 head    1.2;
   2 access;
   3 symbols;
   4 locks; strict;
   5 comment @ * @;
   6
   7
   8 1.2
   9 date    2007.07.22.13.33.26;    author khansen; state Exp;
  10 branches;
  11 next    1.1;
  12
  13 1.1
  14 date    2004.06.30.07.55.43;    author kenth;   state Exp;
  15 branches;
  16 next    ;
  17
  18
  19 desc
  20 @@
  21
  22
  23 1.2
  24 log
  25 @convert tabs to whitespaces
  26 @
  27 text
  28 @/*
  29  * $Id: hashtab.c,v 1.1 2004/06/30 07:55:43 kenth Exp $
  30  * $Log: hashtab.c,v $
  31  * Revision 1.1  2004/06/30 07:55:43  kenth
  32  * Initial revision
  33  *
  34  */
  35
  36 /**
  37  *    (C) 2004 Kent Hansen
  38  *
  39  *    The XORcyst is free software; you can redistribute it and/or modify
  40  *    it under the terms of the GNU General Public License as published by
  41  *    the Free Software Foundation; either version 2 of the License, or
  42  *    (at your option) any later version.
  43  *
  44  *    The XORcyst is distributed in the hope that it will be useful,
  45  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  46  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  47  *    GNU General Public License for more details.
  48  *
  49  *    You should have received a copy of the GNU General Public License
  50  *    along with The XORcyst; if not, write to the Free Software
  51  *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  52  */
  53
  54 /**
  55  * This file contains an implementation of a hash table.
  56  * Both keys and values are of type void *.
  57  * To implement hashing and key comparison, you have to supply two functions
  58  * for doing this job. If keys are strings, then you can use the default
  59  * functions below.
  60  */
  61
  62 #include <stdlib.h>
  63 #include <string.h>
  64 #include "hashtab.h"
  65
  66 #define SAFE_FREE(a) if (a) { free(a); a = NULL; }
  67
  68 /*---------------------------------------------------------------------------*/
  69
  70 /**
  71  * Supplies default hashing function when key is a string.
  72  */
  73 int HASHTAB_STRKEYHSH(void *key)
  74 {
  75     int i;
  76     unsigned char *s = (unsigned char *)key;
  77     int sum = 0;
  78     for (i=0; s[i] != '\0'; i++) {
  79         sum += s[i];
  80     }
  81     return sum;
  82 }
  83
  84 /**
  85  * Supplies default key comparison function when key is a string.
  86  */
  87 int HASHTAB_STRKEYCMP(void *key1, void *key2)
  88 {
  89     return (strcmp((char *)key1, (char *)key2) == 0) ? 1 : 0;
  90 }
  91
  92 /*---------------------------------------------------------------------------*/
  93
  94 /**
  95  * Creates a hash table.
  96  * @@param size Number of slots
  97  * @@param keyhsh Procedure which computes h(k)
  98  * @@param keycmp Procedure which compares two keys
  99  * @@return The newly created hash table
 100  */
 101 hashtab *hashtab_create(int size, keyhashproc keyhsh, keycompareproc keycmp)
 102 {
 103     int i;
 104     /* Allocate space for hash table */
 105     hashtab *ht = (hashtab *)malloc( sizeof(hashtab) );
 106     if (ht != NULL) {
 107         /* Allocate space for slots */
 108         ht->size = size;
 109         ht->slots = (hashtab_slot **)malloc( sizeof(hashtab_slot *) * size );
 110         if (ht->slots != NULL) {
 111             /* Set the hash and comparator procedures */
 112             ht->keyhsh = keyhsh;
 113             ht->keycmp = keycmp;
 114             /* Initialize the slots */
 115             for (i=0; i<size; i++) {
 116                 ht->slots[i] = NULL;
 117             }
 118         }
 119     }
 120     /* Return the created hash table */
 121     return ht;
 122 }
 123
 124 /**
 125  * Puts something in a hash table.
 126  * @@param ht Hash table
 127  * @@param key Key
 128  * @@param data Data
 129  */
 130 void hashtab_put(hashtab *ht, void *key, void *data)
 131 {
 132     int i;
 133     hashtab_slot *s;
 134     hashtab_slot *fresh;
 135     /* Create a new entry */
 136     fresh = (hashtab_slot *)malloc( sizeof(hashtab_slot) );
 137     if (fresh != NULL) {
 138         fresh->key = key;
 139         fresh->data = data;
 140         fresh->next = NULL;
 141         /* Figure out in which slot to put it */
 142         i = ht->keyhsh(key) % ht->size;
 143         /* Now put it! */
 144         if (ht->slots[i] == NULL) {
 145             /* Start the list */
 146             ht->slots[i] = fresh;
 147         }
 148         else {
 149             /* Add to end of list */
 150             for (s = ht->slots[i]; s->next != NULL; s = s->next) ;
 151             s->next = fresh;
 152         }
 153     }
 154 }
 155
 156 /**
 157  * Gets the data associated with given key.
 158  * @@param ht Hash table
 159  * @@param key Key
 160  * @@return The data associated with key, or <code>NULL</code> if key not found
 161  */
 162 void *hashtab_get(hashtab *ht, void *key)
 163 {
 164     hashtab_slot *s;
 165     int i = ht->keyhsh(key) % ht->size;
 166     for (s = ht->slots[i]; s != NULL; s = s->next) {
 167         if (ht->keycmp(key, s->key)) {
 168             return s->data;
 169         }
 170     }
 171     return NULL;
 172 }
 173
 174 /**
 175  * Removes something from hash table.
 176  * @@param ht Hash table
 177  * @@param key Key
 178  * @@return Data associated with key
 179  */
 180 void *hashtab_remove(hashtab *ht, void *key)
 181 {
 182     hashtab_slot *s;
 183     int i = ht->keyhsh(key) % ht->size;
 184     for (s = ht->slots[i]; s != NULL; s = s->next) {
 185         if (ht->keycmp(key, s->key)) {
 186             // TODO: remove s...
 187             return NULL;
 188         }
 189     }
 190     return NULL;
 191 }
 192
 193 /**
 194  * Finalizes hash table.
 195  * @@param ht The hash table to finalize
 196  */
 197 void hashtab_finalize(hashtab *ht)
 198 {
 199     hashtab_slot *s;
 200     hashtab_slot *t;
 201     int i;
 202     for (i=0; i<ht->size; i++) {
 203         s = ht->slots[i];
 204         while (s != NULL) {
 205             t = s->next;
 206             SAFE_FREE(s);
 207             s = t;
 208         }
 209     }
 210     SAFE_FREE(ht->slots);
 211     free(ht);
 212 }
 213 @
 214
 215
 216 1.1
 217 log
 218 @Initial revision
 219 @
 220 text
 221 @d2 5
 222 a6 2
 223  * $Id$
 224  * $Log$
 225 d48 7
 226 a54 7
 227         int i;
 228         unsigned char *s = (unsigned char *)key;
 229         int sum = 0;
 230         for (i=0; s[i] != '\0'; i++) {
 231                 sum += s[i];
 232         }
 233         return sum;
 234 d62 1
 235 a62 1
 236         return (strcmp((char *)key1, (char *)key2) == 0) ? 1 : 0;
 237 d76 19
 238 a94 19
 239         int i;
 240         /* Allocate space for hash table */
 241         hashtab *ht = (hashtab *)malloc( sizeof(hashtab) );
 242         if (ht != NULL) {
 243                 /* Allocate space for slots */
 244                 ht->size = size;
 245                 ht->slots = (hashtab_slot **)malloc( sizeof(hashtab_slot *) * size );
 246                 if (ht->slots != NULL) {
 247                         /* Set the hash and comparator procedures */
 248                         ht->keyhsh = keyhsh;
 249                         ht->keycmp = keycmp;
 250                         /* Initialize the slots */
 251                         for (i=0; i<size; i++) {
 252                                 ht->slots[i] = NULL;
 253                         }
 254                 }
 255         }
 256         /* Return the created hash table */
 257         return ht;
 258 d105 22
 259 a126 22
 260         int i;
 261         hashtab_slot *s;
 262         hashtab_slot *fresh;
 263         /* Create a new entry */
 264         fresh = (hashtab_slot *)malloc( sizeof(hashtab_slot) );
 265         if (fresh != NULL) {
 266                 fresh->key = key;
 267                 fresh->data = data;
 268                 fresh->next = NULL;
 269                 /* Figure out in which slot to put it */
 270                 i = ht->keyhsh(key) % ht->size;
 271                 /* Now put it! */
 272                 if (ht->slots[i] == NULL) {
 273                         /* Start the list */
 274                         ht->slots[i] = fresh;
 275                 }
 276                 else {
 277                         /* Add to end of list */
 278                         for (s = ht->slots[i]; s->next != NULL; s = s->next) ;
 279                         s->next = fresh;
 280                 }
 281         }
 282 d137 8
 283 a144 8
 284         hashtab_slot *s;
 285         int i = ht->keyhsh(key) % ht->size;
 286         for (s = ht->slots[i]; s != NULL; s = s->next) {
 287                 if (ht->keycmp(key, s->key)) {
 288                         return s->data;
 289                 }
 290         }
 291         return NULL;
 292 d155 9
 293 a163 9
 294         hashtab_slot *s;
 295         int i = ht->keyhsh(key) % ht->size;
 296         for (s = ht->slots[i]; s != NULL; s = s->next) {
 297                 if (ht->keycmp(key, s->key)) {
 298                         // TODO: remove s...
 299                         return NULL;
 300                 }
 301         }
 302         return NULL;
 303 d172 13
 304 a184 13
 305         hashtab_slot *s;
 306         hashtab_slot *t;
 307         int i;
 308         for (i=0; i<ht->size; i++) {
 309                 s = ht->slots[i];
 310                 while (s != NULL) {
 311                         t = s->next;
 312                         SAFE_FREE(s);
 313                         s = t;
 314                 }
 315         }
 316         SAFE_FREE(ht->slots);
 317         free(ht);
 318 @