root/libutil/strhash.c

/* */

DEFINITIONS

1. strhash_open
2. strhash_assign
3. strhash_strdup
4. strhash_first
5. strhash_next
6. strhash_reset
7. strhash_close

   1 /*
   2  * Copyright (c) 2005, 2006 Tama Communications Corporation
   3  *
   4  * This file is part of GNU GLOBAL.
   5  *
   6  * This program is free software: you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation, either version 3 of the License, or
   9  * (at your option) any later version.
  10  * 
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  * 
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19 
  20 #ifdef HAVE_CONFIG_H
  21 #include <config.h>
  22 #endif
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26 
  27 #include "checkalloc.h"
  28 #include "die.h"
  29 #include "strhash.h"
  30 #include "hash-string.h"
  31 #include "pool.h"
  32 
  33 /** @file
  34 
  35 String Hash (associative array): usage and memory status
  36 
  37 @code
  38 hash = strhash_open(10);                        // allocate hash buckets.
  39 
  40 entry = strhash_assign(hash, "name1", 0);       // get entry for the name.
  41 
  42         entry == NULL                           // entry not found.
  43 
  44 entry = strhash_assign(hash, "name1", 1);       // allocate entry for the name.
  45                                                 entry
  46                                                 +-------------+
  47                                                 |name: "name1"|
  48                                                 |value:    *---->(void *)NULL
  49                                                 +-------------+
  50 // strhash_xxx() doesn't affect entry->value. So, you can use it freely.
  51 
  52 entry->value = strhash_strdup(hash, "NAME1", 0);
  53                                                 entry
  54                                                 +-------------+
  55                                                 |name: "name1"|
  56                                                 |value:    *---->"NAME1"
  57                                                 +-------------+
  58 
  59 entry = strhash_assign(hash, "name1", 0);       // get entry of the name.
  60 
  61                                                 entry
  62                                                 +-------------+
  63                                                 |name: "name1"|
  64                                                 |value:    *---->"NAME1"
  65                                                 +-------------+
  66 char *s = (char *)entry->value;
  67 
  68         s == "NAME1"
  69 
  70 strhash_close(hash);                            // free resources.
  71                                                 entry
  72 @endcode
  73 */
  74 
  75 #define obstack_chunk_alloc check_malloc
  76 #define obstack_chunk_free free
  77 
  78 /**
  79  * strhash_open: open string hash table.
  80  *
  81  *      @param[in]      buckets  size of bucket table
  82  *      @return sh      #STRHASH structure
  83  */
  84 STRHASH *
  85 strhash_open(int buckets)
  86 {
  87         STRHASH *sh = (STRHASH *)check_calloc(sizeof(STRHASH), 1);
  88         int i;
  89 
  90         sh->htab = (struct sh_head *)check_calloc(sizeof(struct sh_head), buckets);
  91         for (i = 0; i < buckets; i++)
  92                 SLIST_INIT(&sh->htab[i]);
  93         sh->buckets = buckets;
  94         sh->pool = pool_open();
  95         sh->entries = 0;
  96         return sh;
  97 }
  98 /**
  99  * strhash_assign: assign hash entry.
 100  *
 101  *      @param[in]      sh      #STRHASH structure
 102  *      @param[in]      name    name
 103  *      @param[in]      force   if entry not found, create it.
 104  *      @return         pointer of the entry
 105  *
 106  * If specified entry is found then it is returned, else if the @CODE{force == 1}
 107  * then new allocated entry is returned. <br>
 108  * This procedure doesn't operate the contents of @CODE{entry->value}.
 109  */
 110 struct sh_entry *
 111 strhash_assign(STRHASH *sh, const char *name, int force)
 112 {
 113         struct sh_head *head = &sh->htab[__hash_string(name) % sh->buckets];
 114         struct sh_entry *entry;
 115 
 116         /*
 117          * Lookup the name's entry.
 118          */
 119         SLIST_FOREACH(entry, head, ptr)
 120                 if (strcmp(entry->name, name) == 0)
 121                         break;
 122         /*
 123          * If not found, allocate an entry.
 124          */
 125         if (entry == NULL && force) {
 126                 entry = pool_malloc(sh->pool, sizeof(struct sh_entry));
 127                 entry->name = pool_strdup(sh->pool, name, 0);
 128                 entry->value = NULL;
 129                 SLIST_INSERT_HEAD(head, entry, ptr);
 130                 sh->entries++;
 131         }
 132         return entry;
 133 }
 134 /**
 135  * strhash_strdup: allocate memory and copy string.
 136  *
 137  *      @param[in]      sh      #STRHASH structure
 138  *      @param[in]      string  string
 139  *      @param[in]      size    size of string
 140  *      @return         allocated string
 141  *
 142  */
 143 char *
 144 strhash_strdup(STRHASH *sh, const char *string, int size)
 145 {
 146         return pool_strdup(sh->pool, string, size);
 147 }
 148 /**
 149  * strhash_first: get first entry
 150  *
 151  *      @param[in]      sh      #STRHASH structure
 152  */
 153 struct sh_entry *
 154 strhash_first(STRHASH *sh)
 155 {
 156         sh->cur_bucket = -1;            /* to start from index 0. */
 157         sh->cur_entry = NULL;
 158         return strhash_next(sh);
 159 }
 160 /**
 161  * strhash_next: get next entry
 162  *
 163  *      @param[in]      sh      #STRHASH structure
 164  */
 165 struct sh_entry *
 166 strhash_next(STRHASH *sh)
 167 {
 168         struct sh_entry *entry = NULL;
 169 
 170         if (sh->buckets > 0 && sh->cur_bucket < sh->buckets) {
 171                 entry = sh->cur_entry;
 172                 if (entry == NULL) {
 173                         while (++sh->cur_bucket < sh->buckets) {
 174                                 entry = SLIST_FIRST(&sh->htab[sh->cur_bucket]);
 175                                 if (entry)
 176                                         break;
 177                         }
 178                 }
 179                 sh->cur_entry = (entry) ? SLIST_NEXT(entry, ptr) : NULL;
 180         }
 181         return entry;
 182 }
 183 /**
 184  * strhash_reset: reset string hash.
 185  *
 186  *      @param[in]      sh      #STRHASH structure
 187  */
 188 void
 189 strhash_reset(STRHASH *sh)
 190 {
 191         int i;
 192 
 193         /*
 194          * Free and reinitialize entries for each bucket.
 195          */
 196         for (i = 0; i < sh->buckets; i++) {
 197                 SLIST_INIT(&sh->htab[i]);
 198         }
 199         /*
 200          * Free all memory in sh->pool but leave it valid for further allocation.
 201          */
 202         pool_reset(sh->pool);
 203         sh->entries = 0;
 204 }
 205 /**
 206  * strhash_close: close hash array.
 207  *
 208  *      @param[in]      sh      #STRHASH structure
 209  */
 210 void
 211 strhash_close(STRHASH *sh)
 212 {
 213         pool_close(sh->pool);
 214         free(sh->htab);
 215         free(sh);
 216 }

/* */