shash.c

   1 /*
   2  * Copyright (c) 1998-1999 Jeremie Miller <jer@jabber.org>
   3  * Copyright (C) 2013 Ole Reinhardt <ole.reinhardt@embedded-it.de>
   4  *
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the copyright holders nor the names of
  17  *    contributors may be used to endorse or promote products derived
  18  *    from this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  27  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  28  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  29  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
  30  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  * For additional information see http://www.ethernut.de/
  34  *
  35  */
  36
  37 /* This code is based on
  38  * Based on BSD licensed mdnsd implementation by Jer <jer@jabber.org>
  39  * http://dotlocal.org/mdnsd/
  40  *
  41  * Unfortunately this site is now longer alive. You can still find it at:
  42  * http://web.archive.org/web/20080705131510/http://dotlocal.org/mdnsd/
  43  *
  44  * mdnsd - embeddable Multicast DNS Daemon
  45  * =======================================
  46  *
  47  * "mdnsd" is a very lightweight, simple, portable, and easy to integrate
  48  * open source implementation of Multicast DNS (part of Zeroconf, also called
  49  * Rendezvous by Apple) for developers. It supports both acting as a Query and
  50  * a Responder, allowing any software to participate fully on the .localnetwork
  51  * just by including a few files and calling a few functions.  All of the
  52  * complexity of handling the Multicast DNS retransmit timing, duplicate
  53  * suppression, probing, conflict detection, and other facets of the DNS
  54  * protocol is hidden behind a very simple and very easy to use interface,
  55  * described in the header file. The single small c source file has almost no
  56  * dependencies, and is portable to almost any embedded platform.
  57  * Multiple example applications and usages are included in the download,
  58  * including a simple persistent query browser and a tool to advertise .local
  59  * web sites.
  60  *
  61  * The code is licensed under both the GPL and BSD licenses, for use in any
  62  * free software or commercial application. If there is a licensing need not
  63  * covered by either of those, alternative licensing is available upon request.
  64  *
  65  */
  66
  67 /*!
  68  * \file gorp/hash/shash.c
  69  * \brief Simple hastable implementation of a string ==> void* hashtable
  70  *        Minimal and efficient
  71  *
  72  * \verbatim
  73  *
  74  * $Id$
  75  *
  76  * \endverbatim
  77  */
  78
  79 #include <stdlib.h>
  80 #include <string.h>
  81 #include <inttypes.h>
  82 #include "shash.h"
  83
  84 /*!
  85  * \addtogroup xgSHash
  86  */
  87 /*@{*/
  88
  89 typedef struct node_struct
  90 {
  91     char flag;
  92     struct node_struct *next;
  93     char *key;
  94     void *val;
  95 } *SHNODE;
  96
  97 struct string_hash_table_struct
  98 {
  99     int prime;
 100     SHNODE zen;
 101 };
 102
 103 /*!
 104  * \brief Generates a hash code for a string.
 105  *
 106  * This function uses the ELF hashing algorithm as reprinted in
 107  * Andrew Binstock, "Hashing Rehashed," Dr. Dobb's Journal, April 1996.
 108  *
 109  * \param s     The string to hash
 110  *
 111  * \return      The calculated hash value
 112  */
 113
 114 static int32_t StrToHash(const char *str)
 115 {
 116     /* ELF hash uses uint8_ts and unsigned arithmetic for portability */
 117     const uint8_t *name = (const uint8_t *)str;
 118     uint32_t hash = 0;
 119     uint32_t g;
 120
 121     while (*name) {
 122         /* do some fancy bit calculations on the string */
 123         hash = (hash << 4) + (uint32_t)(*name++);
 124         g = (hash & 0xF0000000UL);
 125         if (g != 0) {
 126             hash ^= (g >> 24);
 127         }
 128         hash &= ~g;
 129     }
 130
 131     return (int32_t)hash;
 132 }
 133
 134
 135 /*!
 136  * \brief Initialise a new hash
 137  *
 138  * \param prime size of the hash (!!! You have to use a _prime_ number (e.g. 5, 7, 11, 13, ...) !!!)
 139  *
 140  * \return      pointer to the new hash
 141  */
 142 SHASH SHashInit(int prime)
 143 {
 144     SHASH xnew;
 145
 146     xnew = (SHASH)malloc(sizeof(struct string_hash_table_struct));
 147     xnew->prime = prime;
 148     xnew->zen = (SHNODE)malloc(sizeof(struct node_struct)*prime); /* array of SHNODE size of prime */
 149     memset(xnew->zen, 0, sizeof(struct node_struct)*prime);
 150     return xnew;
 151 }
 152
 153 /*!
 154  * \brief Search the node for the given key in the hash table
 155  *
 156  * \param node  starting node to search from
 157  * \param key   The key to get
 158  *
 159  * \return      The node or NULL of node was not found
 160  */
 161
 162 static SHNODE SHashFindNode(SHNODE node, const char *key)
 163 {
 164     for(; node != 0; node = node->next) {
 165         if((node->key != 0) && (strcmp(key, node->key) == 0)) {
 166             return node;
 167         }
 168     }
 169     return 0;
 170 }
 171
 172
 173 /*!
 174  * \brief Helper function: Add a new entry to the hash table
 175  *
 176  * \param hash  The hashtable to insert the new entry in
 177  * \param key   The key, under which the value should be entered
 178  * \param val   Void* pointer to be saved under 'key' in the hash table
 179  * \param flag  If flag != 0 the node memory is freed first and managed by this function
 180  */
 181
 182 static void SHashDoSet(SHASH hash, char *key, void *val, char flag)
 183 {
 184     int32_t i;
 185     SHNODE node;
 186
 187     /* Get the hash index of the key */
 188     i = StrToHash(key) % hash->prime;
 189
 190     /* Does the key just exists? If not, find an empty one */
 191     node = SHashFindNode(&hash->zen[i], key);
 192     if (node == 0) {
 193         for(node = &hash->zen[i]; node != 0; node = node->next) {
 194             if(node->val == 0) {
 195                 break;
 196             }
 197         }
 198     }
 199
 200     /* If the key does not exists, create a new node and link into the hash */
 201     if (node == 0) {
 202         node = (SHNODE)malloc(sizeof(struct node_struct));
 203         node->next = hash->zen[i].next;
 204         hash->zen[i].next = node;
 205     }
 206
 207     /* If flag is set, the node memory will be freed first and then reused with the new key / value pair */
 208     if (node->flag) {
 209         free(node->key);
 210         free(node->val);
 211     }
 212
 213     node->flag = flag;
 214     node->key = key;
 215     node->val = val;
 216 }
 217
 218
 219 /*!
 220  * \brief Add a new entry to the hash table
 221  *
 222  * The caller is responsible for the key storage. No copies are made.
 223  * Do not free these valued before calling SHashFree()!!!
 224  *
 225  * If val is set to NULL, the entry is cleared and the memory is reused but
 226  * never freed. The number of keys can only grow up to peak usage.
 227  *
 228  * \param hash  The hashtable to insert the new entry in
 229  * \param key   The key, under which the value should be entered
 230  * \param val   Void* pointer to be saved under 'key' in the hash table
 231  */
 232
 233 void SHashSet(SHASH hash, char *key, void *val)
 234 {
 235     if ((hash == 0) || (key == 0)) {
 236         return;
 237     }
 238     SHashDoSet(hash, key, val, 0);
 239 }
 240
 241
 242 /*!
 243  * \brief Add a new entry to the hash table
 244  *
 245  * Unlike SHashSet() where key and values are managed in the callers memory
 246  * space, here they are copied into the hash table and freed when
 247  * val is 0 or by calling SHashFree().
 248  *
 249  * If val is set to NULL, the entry is cleared and the memory is freed.
 250  *
 251  * \param hash  The hashtable to insert the new entry in
 252  * \param key   The key, under which the value should be entered
 253  * \param kley  Size of the key
 254  * \param val   Void* pointer to be saved under 'key' in the hash table
 255  * \param vlen  Size of the value
 256  */
 257
 258 void SHashStore(SHASH hash, const char *key, int key_len, void *val, int value_len)
 259 {
 260     char *ckey;
 261     char *cval;
 262
 263     if((hash == 0) || (key == 0) || (key_len == 0)) {
 264         return;
 265     }
 266
 267     ckey = (char*)malloc(key_len+1);
 268     memcpy(ckey, key, key_len);
 269     ckey[key_len] = '\0';
 270
 271     /* Assume the value is a string too and store it with a trailing
 272        zero for safety reasons
 273      */
 274     cval = (void*)malloc(value_len+1);
 275     memcpy(cval, val, value_len);
 276     cval[value_len] = '\0';
 277
 278     SHashDoSet(hash, ckey, cval, 1);
 279 }
 280
 281 /*!
 282  * \brief Retrive a value associated to key from the hash table
 283  *
 284  * Return the value or NULL of the key was not found.
 285  *
 286  * \param hash  The hast table to get the value from
 287  * \param key   Key to get the value for
 288  * \return      pointer to the value, NULL if no key was not found
 289  */
 290 void *SHashGet(SHASH hash, const char *key)
 291 {
 292     SHNODE node;
 293
 294     if ((hash == 0) || (key == 0)) {
 295         return 0;
 296     }
 297
 298     node = SHashFindNode(&hash->zen[StrToHash(key) % hash->prime], key);
 299     if (node == NULL) {
 300         return 0;
 301     }
 302
 303     return node->val;
 304 }
 305
 306 /*!
 307  * \brief Free the hash table and all entries
 308  *
 309  * \param hash  The hast table to free
 310  */
 311
 312 void SHashFree(SHASH hash)
 313 {
 314     SHNODE node;
 315     SHNODE temp;
 316     int i;
 317
 318     if(hash == 0) {
 319         return;
 320     }
 321
 322     for (i = 0; i < hash->prime; i++) {
 323         for (node = (&hash->zen[i])->next; node != 0; ) {
 324             temp = node->next;
 325             if (node->flag) {
 326                 free(node->key);
 327                 free(node->val);
 328             }
 329             free(node);
 330             node = temp;
 331         }
 332     }
 333
 334     free(hash->zen);
 335     free(hash);
 336 }
 337
 338 /*!
 339  * \brief Interate over the hash table and call a callback for each key
 340  *        that has a value set.
 341  *
 342  *
 343  * \param hash      The hash table to iterate though
 344  * \param cb        SHASH_CB callback function
 345  * \param arg       An optional user pointer to pass to the callback function
 346  */
 347 void SHashForEach(SHASH hash, SHASH_CB cb, void *arg)
 348 {
 349     int i;
 350     SHNODE node;
 351
 352     if ((hash == 0) || (cb == 0)) {
 353         return;
 354     }
 355
 356     for(i = 0; i < hash->prime; i++) {
 357         for(node = &hash->zen[i]; node != 0; node = node->next) {
 358             if(node->key != 0 && node->val != 0) {
 359                 (*cb)(hash, node->key, node->val, arg);
 360             }
 361         }
 362     }
 363 }
 364
 365 /*@}*/