lustre/utils/hash.c

   1 /*****************************************************************************
   2  *  $Id: hash.c,v 1.1.10.2 2008/12/18 18:02:13 johann Exp $
   3  *****************************************************************************
   4  *  Copyright (C) 2003-2005 The Regents of the University of California.
   5  *  Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
   6  *  Written by Chris Dunlap <cdunlap@llnl.gov>.
   7  *
   8  *  This file is from LSD-Tools, the LLNL Software Development Toolbox.
   9  *
  10  *  This is free software; you can redistribute it and/or modify it
  11  *  under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This is distributed in the hope that it will be useful, but WITHOUT
  16  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17  *  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18  *  for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License;
  21  *  if not, write to the Free Software Foundation, Inc., 51 Franklin Street,
  22  *  Fifth Floor, Boston, MA  02110-1301  USA.
  23  *****************************************************************************
  24  *  Refer to "hash.h" for documentation on public functions.
  25  *****************************************************************************/
  26
  27
  28 #if HAVE_CONFIG_H
  29 #  include "config.h"
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #include <assert.h>
  33 #include <errno.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36
  37 #include "thread.h"
  38 #include "hash.h"
  39
  40
  41 /*****************************************************************************
  42  *  Constants
  43  *****************************************************************************/
  44
  45 #define HASH_ALLOC      1024
  46 #define HASH_DEF_SIZE   1213
  47 #define HASH_MAGIC      0xDEADBEEF
  48
  49
  50 /*****************************************************************************
  51  *  Data Types
  52  *****************************************************************************/
  53
  54 struct hash_node {
  55     struct hash_node   *next;           /* next node in list                 */
  56     void               *data;           /* ptr to hashed item                */
  57     const void         *hkey;           /* ptr to hashed item's key          */
  58 };
  59
  60 struct hash {
  61     int                 count;          /* number of items in hash table     */
  62     int                 size;           /* num slots allocated in hash table */
  63     struct hash_node  **table;          /* hash table array of node ptrs     */
  64     hash_cmp_f          cmp_f;          /* key comparison function           */
  65     hash_del_f          del_f;          /* item deletion function            */
  66     hash_key_f          key_f;          /* key hash function                 */
  67 #if WITH_PTHREADS
  68     pthread_mutex_t     mutex;          /* mutex to protect access to hash   */
  69 #endif /* WITH_PTHREADS */
  70 #ifndef NDEBUG
  71     unsigned int        magic;          /* sentinel for asserting validity   */
  72 #endif /* NDEBUG */
  73 };
  74
  75
  76 /*****************************************************************************
  77  *  Prototypes
  78  *****************************************************************************/
  79
  80 static struct hash_node * hash_node_alloc (void);
  81
  82 static void hash_node_free (struct hash_node *node);
  83
  84
  85 /*****************************************************************************
  86  *  Variables
  87  *****************************************************************************/
  88
  89 #if 0
  90 static struct hash_node *hash_free_list = NULL;
  91 #endif
  92
  93 #if WITH_PTHREADS
  94 static pthread_mutex_t hash_free_lock = PTHREAD_MUTEX_INITIALIZER;
  95 #endif /* WITH_PTHREADS */
  96
  97
  98 /*****************************************************************************
  99  *  Macros
 100  *****************************************************************************/
 101
 102 #ifdef WITH_LSD_FATAL_ERROR_FUNC
 103 #  undef lsd_fatal_error
 104    extern void lsd_fatal_error (char *file, int line, char *mesg);
 105 #else /* !WITH_LSD_FATAL_ERROR_FUNC */
 106 #  ifndef lsd_fatal_error
 107 #    define lsd_fatal_error(file, line, mesg) (abort ())
 108 #  endif /* !lsd_fatal_error */
 109 #endif /* !WITH_LSD_FATAL_ERROR_FUNC */
 110
 111 #ifdef WITH_LSD_NOMEM_ERROR_FUNC
 112 #  undef lsd_nomem_error
 113    extern void * lsd_nomem_error (char *file, int line, char *mesg);
 114 #else /* !WITH_LSD_NOMEM_ERROR_FUNC */
 115 #  ifndef lsd_nomem_error
 116 #    define lsd_nomem_error(file, line, mesg) (NULL)
 117 #  endif /* !lsd_nomem_error */
 118 #endif /* !WITH_LSD_NOMEM_ERROR_FUNC */
 119
 120
 121 /*****************************************************************************
 122  *  Functions
 123  *****************************************************************************/
 124
 125 hash_t
 126 hash_create (int size, hash_key_f key_f, hash_cmp_f cmp_f, hash_del_f del_f)
 127 {
 128     hash_t h;
 129
 130     if (!cmp_f || !key_f) {
 131         errno = EINVAL;
 132         return (NULL);
 133     }
 134     if (size <= 0) {
 135         size = HASH_DEF_SIZE;
 136     }
 137     if (!(h = malloc (sizeof (*h)))) {
 138         return (lsd_nomem_error (__FILE__, __LINE__, "hash_create"));
 139     }
 140     if (!(h->table = calloc (size, sizeof (struct hash_node *)))) {
 141         free (h);
 142         return (lsd_nomem_error (__FILE__, __LINE__, "hash_create"));
 143     }
 144     h->count = 0;
 145     h->size = size;
 146     h->cmp_f = cmp_f;
 147     h->del_f = del_f;
 148     h->key_f = key_f;
 149     lsd_mutex_init (&h->mutex);
 150     assert (h->magic = HASH_MAGIC);     /* set magic via assert abuse */
 151     return (h);
 152 }
 153
 154
 155 void
 156 hash_destroy (hash_t h)
 157 {
 158     int i;
 159     struct hash_node *p, *q;
 160
 161     if (!h) {
 162         errno = EINVAL;
 163         return;
 164     }
 165     lsd_mutex_lock (&h->mutex);
 166     assert (h->magic == HASH_MAGIC);
 167     for (i = 0; i < h->size; i++) {
 168         for (p = h->table[i]; p != NULL; p = q) {
 169             q = p->next;
 170             if (h->del_f)
 171                 h->del_f (p->data);
 172             hash_node_free (p);
 173         }
 174     }
 175     assert (h->magic = ~HASH_MAGIC);    /* clear magic via assert abuse */
 176     lsd_mutex_unlock (&h->mutex);
 177     lsd_mutex_destroy (&h->mutex);
 178     free (h->table);
 179     free (h);
 180     return;
 181 }
 182
 183
 184 int
 185 hash_is_empty (hash_t h)
 186 {
 187     int n;
 188
 189     if (!h) {
 190         errno = EINVAL;
 191         return (0);
 192     }
 193     lsd_mutex_lock (&h->mutex);
 194     assert (h->magic == HASH_MAGIC);
 195     n = h->count;
 196     lsd_mutex_unlock (&h->mutex);
 197     return (n == 0);
 198 }
 199
 200
 201 int
 202 hash_count (hash_t h)
 203 {
 204     int n;
 205
 206     if (!h) {
 207         errno = EINVAL;
 208         return (0);
 209     }
 210     lsd_mutex_lock (&h->mutex);
 211     assert (h->magic == HASH_MAGIC);
 212     n = h->count;
 213     lsd_mutex_unlock (&h->mutex);
 214     return (n);
 215 }
 216
 217
 218 void *
 219 hash_find (hash_t h, const void *key)
 220 {
 221     unsigned int slot;
 222     struct hash_node *p;
 223     void *data = NULL;
 224
 225     if (!h || !key) {
 226         errno = EINVAL;
 227         return (NULL);
 228     }
 229     errno = 0;
 230     lsd_mutex_lock (&h->mutex);
 231     assert (h->magic == HASH_MAGIC);
 232     slot = h->key_f (key) % h->size;
 233     for (p = h->table[slot]; p != NULL; p = p->next) {
 234         if (!h->cmp_f (p->hkey, key)) {
 235             data = p->data;
 236             break;
 237         }
 238     }
 239     lsd_mutex_unlock (&h->mutex);
 240     return (data);
 241 }
 242
 243
 244 void *
 245 hash_insert (hash_t h, const void *key, void *data)
 246 {
 247     struct hash_node *p;
 248     unsigned int slot;
 249
 250     if (!h || !key || !data) {
 251         errno = EINVAL;
 252         return (NULL);
 253     }
 254     lsd_mutex_lock (&h->mutex);
 255     assert (h->magic == HASH_MAGIC);
 256     slot = h->key_f (key) % h->size;
 257     for (p = h->table[slot]; p != NULL; p = p->next) {
 258         if (!h->cmp_f (p->hkey, key)) {
 259             errno = EEXIST;
 260             data = NULL;
 261             goto end;
 262         }
 263     }
 264     if (!(p = hash_node_alloc ())) {
 265         data = lsd_nomem_error (__FILE__, __LINE__, "hash_insert");
 266         goto end;
 267     }
 268     p->hkey = key;
 269     p->data = data;
 270     p->next = h->table[slot];
 271     h->table[slot] = p;
 272     h->count++;
 273
 274 end:
 275     lsd_mutex_unlock (&h->mutex);
 276     return (data);
 277 }
 278
 279
 280 void *
 281 hash_remove (hash_t h, const void *key)
 282 {
 283     struct hash_node **pp;
 284     struct hash_node *p;
 285     unsigned int slot;
 286     void *data = NULL;
 287
 288     if (!h || !key) {
 289         errno = EINVAL;
 290         return (NULL);
 291     }
 292     errno = 0;
 293     lsd_mutex_lock (&h->mutex);
 294     assert (h->magic == HASH_MAGIC);
 295     slot = h->key_f (key) % h->size;
 296     for (pp = &(h->table[slot]); (p = *pp) != NULL; pp = &((*pp)->next)) {
 297         if (!h->cmp_f (p->hkey, key)) {
 298             data = p->data;
 299             *pp = p->next;
 300             hash_node_free (p);
 301             h->count--;
 302             break;
 303         }
 304     }
 305     lsd_mutex_unlock (&h->mutex);
 306     return (data);
 307 }
 308
 309
 310 int
 311 hash_delete_if (hash_t h, hash_arg_f arg_f, void *arg)
 312 {
 313     int i;
 314     struct hash_node **pp;
 315     struct hash_node *p;
 316     int n = 0;
 317
 318     if (!h || !arg_f) {
 319         errno = EINVAL;
 320         return (-1);
 321     }
 322     lsd_mutex_lock (&h->mutex);
 323     assert (h->magic == HASH_MAGIC);
 324     for (i = 0; i < h->size; i++) {
 325         pp = &(h->table[i]);
 326         while ((p = *pp) != NULL) {
 327             if (arg_f (p->data, p->hkey, arg) > 0) {
 328                 if (h->del_f)
 329                     h->del_f (p->data);
 330                 *pp = p->next;
 331                 hash_node_free (p);
 332                 h->count--;
 333                 n++;
 334             }
 335             else {
 336                 pp = &(p->next);
 337             }
 338         }
 339     }
 340     lsd_mutex_unlock (&h->mutex);
 341     return (n);
 342 }
 343
 344
 345 int
 346 hash_for_each (hash_t h, hash_arg_f arg_f, void *arg)
 347 {
 348     int i;
 349     struct hash_node *p;
 350     int n = 0;
 351
 352     if (!h || !arg_f) {
 353         errno = EINVAL;
 354         return (-1);
 355     }
 356     lsd_mutex_lock (&h->mutex);
 357     assert (h->magic == HASH_MAGIC);
 358     for (i = 0; i < h->size; i++) {
 359         for (p = h->table[i]; p != NULL; p = p->next) {
 360             if (arg_f (p->data, p->hkey, arg) > 0) {
 361                 n++;
 362             }
 363         }
 364     }
 365     lsd_mutex_unlock (&h->mutex);
 366     return (n);
 367 }
 368
 369
 370 /*****************************************************************************
 371  *  Hash Functions
 372  *****************************************************************************/
 373
 374 unsigned int
 375 hash_key_string (const char *str)
 376 {
 377     unsigned char *p;
 378     unsigned int hval = 0;
 379     const unsigned int multiplier = 31;
 380
 381     for (p = (unsigned char *) str; *p != '\0'; p++) {
 382         hval += (multiplier * hval) + *p;
 383     }
 384     return (hval);
 385 }
 386
 387
 388 /*****************************************************************************
 389  *  Internal Functions
 390  *****************************************************************************/
 391
 392 static struct hash_node *
 393 hash_node_alloc (void)
 394 {
 395 /*  Allocates a hash node from the freelist.
 396  *  Memory is allocated in chunks of HASH_ALLOC.
 397  *  Returns a ptr to the object, or NULL if memory allocation fails.
 398  */
 399 #if 0
 400     int i;
 401 #endif
 402     struct hash_node *p = NULL;
 403
 404     assert (HASH_ALLOC > 0);
 405     lsd_mutex_lock (&hash_free_lock);
 406 #if 0
 407     if (!hash_free_list) {
 408         if ((hash_free_list = malloc (HASH_ALLOC * sizeof (*p)))) {
 409             for (i = 0; i < HASH_ALLOC - 1; i++)
 410                 hash_free_list[i].next = &hash_free_list[i+1];
 411             hash_free_list[i].next = NULL;
 412         }
 413     }
 414     if (hash_free_list) {
 415         p = hash_free_list;
 416         hash_free_list = p->next;
 417     }
 418     else {
 419         errno = ENOMEM;
 420     }
 421 #else
 422     if (!(p = malloc (sizeof(*p))))
 423         errno = ENOMEM;
 424 #endif
 425     lsd_mutex_unlock (&hash_free_lock);
 426     return (p);
 427 }
 428
 429
 430 static void
 431 hash_node_free (struct hash_node *node)
 432 {
 433 /*  De-allocates the object [node], returning it to the freelist.
 434  */
 435     assert (node != NULL);
 436     memset (node, 0, sizeof (*node));
 437     lsd_mutex_lock (&hash_free_lock);
 438 #if 0
 439     node->next = hash_free_list;
 440     hash_free_list = node;
 441 #else
 442     free (node);
 443 #endif
 444     lsd_mutex_unlock (&hash_free_lock);
 445     return;
 446 }