tools/cfzy/libconfizery/cfzy_htable.c

   1 /*
   2  * Copyright (c) 2013, Olivier MATZ <zer0@droids-corp.org>
   3  * All rights reserved.
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <stdio.h>
  29 #include <string.h>
  30 #include <stdlib.h>
  31 #include <stdint.h>
  32 #include <sys/queue.h>
  33
  34 #include "cfzy_htable.h"
  35
  36 /* return the hash from name */
  37 static uint32_t hash_name(const char *name)
  38 {
  39         uint32_t h = 0;
  40         const unsigned char *c;
  41
  42         /* XXX add murmurhash ? */
  43         for (c = (const unsigned char *)name; *c; c++)
  44                 h += ((((uint32_t)*c) << 4) + (((uint32_t)*c) >> 4)) * 11;
  45
  46         return h & CFZY_HTABLE_MASK;
  47 }
  48
  49 /* return the hlist_elt associated to the given name. If not found,
  50  * return NULL. */
  51 static struct cfzy_hlist_elt *
  52 __cfzy_htable_lookup(const struct cfzy_htable *htable, const char *name)
  53 {
  54         struct cfzy_hlist_elt *e;
  55         uint32_t h = hash_name(name);
  56
  57         LIST_FOREACH(e, &htable->buckets[h], next) {
  58                 if (!strcmp(name, e->name))
  59                         break;
  60         }
  61         return e;
  62 }
  63
  64 /* return the object associated to the given name. If not found,
  65  * return NULL. */
  66 void *cfzy_htable_lookup(const struct cfzy_htable *htable, const char *name)
  67 {
  68         struct cfzy_hlist_elt *e = __cfzy_htable_lookup(htable, name);
  69         if (e == NULL)
  70                 return NULL;
  71         return e->ptr;
  72 }
  73
  74 /* add an entry in the htable, allocating a new hlist_elt */
  75 int cfzy_htable_add(struct cfzy_htable *htable, const char *name,
  76                     void *ptr)
  77 {
  78         struct cfzy_hlist_elt *e;
  79         uint32_t h;
  80
  81         /* The ptr should not be NULL, else we won't differentiate a
  82          * lookup matching a NULL element and a non-matching one */
  83         if (ptr == NULL)
  84                 return -1;
  85
  86         e = malloc(sizeof(struct cfzy_hlist_elt));
  87         if (e == NULL)
  88                 return -1;
  89
  90         e->name = strdup(name);
  91         if (e->name == NULL) {
  92                 free(e);
  93                 return -1;
  94         }
  95
  96         e->ptr = ptr;
  97         h = hash_name(name);
  98         LIST_INSERT_HEAD(&htable->buckets[h], e, next);
  99
 100         return 0;
 101 }
 102
 103 /* delete and free an hlist_elt from the htable */
 104 static int __cfzy_htable_del(struct cfzy_hlist_elt *e)
 105 {
 106         LIST_REMOVE(e, next);
 107         free(e->name);
 108         free(e);
 109         return 0;
 110 }
 111
 112 /* delete an entry from the htable, freeing the hlist_elt */
 113 int cfzy_htable_del(struct cfzy_htable *htable, const char *name)
 114 {
 115         struct cfzy_hlist_elt *e = __cfzy_htable_lookup(htable, name);
 116
 117         if (e == NULL)
 118                 return -1;
 119
 120         return __cfzy_htable_del(e);
 121 }
 122
 123 /* allocate and initialize a new htable */
 124 struct cfzy_htable *cfzy_htable_alloc(void)
 125 {
 126         struct cfzy_htable *htable;
 127         unsigned i;
 128
 129         htable = malloc(sizeof(struct cfzy_htable));
 130         if (htable == NULL)
 131                 return NULL;
 132
 133         for (i = 0; i < CFZY_HTABLE_SIZE; i++) {
 134                 LIST_INIT(&htable->buckets[i]);
 135         }
 136         return htable;
 137 }
 138
 139 /* empty the htable, freeing hlist_elt structures, and free the htable */
 140 void cfzy_htable_free(struct cfzy_htable *htable, void (*free_fct)(void *))
 141 {
 142         struct cfzy_hlist_elt *e;
 143         unsigned i;
 144
 145         for (i = 0; i < CFZY_HTABLE_SIZE; i++) {
 146                 while ((e = LIST_FIRST(&htable->buckets[i])) != NULL) {
 147                         if (free_fct != NULL)
 148                                 free_fct(e->ptr);
 149
 150                         __cfzy_htable_del(e);
 151                 }
 152         }
 153         free(htable);
 154 }