X-Git-Url: https://git.karo-electronics.de/?a=blobdiff_plain;f=shash.c;fp=shash.c;h=740b0527d894731e2a93cced3384faf2727fc591;hb=77c1b73cfc33cbf0f18b1af04d09c3dac1444547;hp=b3dcf29fe9282586ba65506d044151463947b71f;hpb=8f4efc482d5ff3316f0a80cba0bbac26db821bd1;p=mdnsd.git diff --git a/shash.c b/shash.c index b3dcf29..740b052 100644 --- a/shash.c +++ b/shash.c @@ -1,169 +1,365 @@ +/* + * Copyright (c) 1998-1999 Jeremie Miller + * Copyright (C) 2013 Ole Reinhardt + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the copyright holders nor the names of + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF + * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * For additional information see http://www.ethernut.de/ + * + */ + +/* This code is based on + * Based on BSD licensed mdnsd implementation by Jer + * http://dotlocal.org/mdnsd/ + * + * Unfortunately this site is now longer alive. You can still find it at: + * http://web.archive.org/web/20080705131510/http://dotlocal.org/mdnsd/ + * + * mdnsd - embeddable Multicast DNS Daemon + * ======================================= + * + * "mdnsd" is a very lightweight, simple, portable, and easy to integrate + * open source implementation of Multicast DNS (part of Zeroconf, also called + * Rendezvous by Apple) for developers. It supports both acting as a Query and + * a Responder, allowing any software to participate fully on the .localnetwork + * just by including a few files and calling a few functions. All of the + * complexity of handling the Multicast DNS retransmit timing, duplicate + * suppression, probing, conflict detection, and other facets of the DNS + * protocol is hidden behind a very simple and very easy to use interface, + * described in the header file. The single small c source file has almost no + * dependencies, and is portable to almost any embedded platform. + * Multiple example applications and usages are included in the download, + * including a simple persistent query browser and a tool to advertise .local + * web sites. + * + * The code is licensed under both the GPL and BSD licenses, for use in any + * free software or commercial application. If there is a licensing need not + * covered by either of those, alternative licensing is available upon request. + * + */ + +/*! + * \file gorp/hash/shash.c + * \brief Simple hastable implementation of a string ==> void* hashtable + * Minimal and efficient + * + * \verbatim + * + * $Id$ + * + * \endverbatim + */ + #include #include -#include "xht.h" +#include +#include "shash.h" + +/*! + * \addtogroup xgSHash + */ +/*@{*/ -typedef struct xhn_struct +typedef struct node_struct { char flag; - struct xhn_struct *next; + struct node_struct *next; char *key; void *val; -} *xhn; +} *SHNODE; -struct xht_struct +struct string_hash_table_struct { int prime; - xhn zen; + SHNODE zen; }; -/* Generates a hash code for a string. - * This function uses the ELF hashing algorithm as reprinted in +/*! + * \brief Generates a hash code for a string. + * + * This function uses the ELF hashing algorithm as reprinted in * Andrew Binstock, "Hashing Rehashed," Dr. Dobb's Journal, April 1996. + * + * \param s The string to hash + * + * \return The calculated hash value */ -int _xhter(const char *s) -{ - /* ELF hash uses unsigned chars and unsigned arithmetic for portability */ - const unsigned char *name = (const unsigned char *)s; - unsigned long h = 0, g; - - while (*name) - { /* do some fancy bitwanking on the string */ - h = (h << 4) + (unsigned long)(*name++); - if ((g = (h & 0xF0000000UL))!=0) - h ^= (g >> 24); - h &= ~g; +static int32_t StrToHash(const char *str) +{ + /* ELF hash uses uint8_ts and unsigned arithmetic for portability */ + const uint8_t *name = (const uint8_t *)str; + uint32_t hash = 0; + uint32_t g; + + while (*name) { + /* do some fancy bit calculations on the string */ + hash = (hash << 4) + (uint32_t)(*name++); + g = (hash & 0xF0000000UL); + if (g != 0) { + hash ^= (g >> 24); + } + hash &= ~g; } - return (int)h; + return (int32_t)hash; } -xhn _xht_node_find(xhn n, const char *key) +/*! + * \brief Initialise a new hash + * + * \param prime size of the hash (!!! You have to use a _prime_ number (e.g. 5, 7, 11, 13, ...) !!!) + * + * \return pointer to the new hash + */ +SHASH SHashInit(int prime) { - for(;n != 0; n = n->next) - if(n->key != 0 && strcmp(key, n->key) == 0) - return n; - return 0; + SHASH xnew; + + xnew = (SHASH)malloc(sizeof(struct string_hash_table_struct)); + xnew->prime = prime; + xnew->zen = (SHNODE)malloc(sizeof(struct node_struct)*prime); /* array of SHNODE size of prime */ + memset(xnew->zen, 0, sizeof(struct node_struct)*prime); + return xnew; } +/*! + * \brief Search the node for the given key in the hash table + * + * \param node starting node to search from + * \param key The key to get + * + * \return The node or NULL of node was not found + */ -xht xht_new(int prime) +static SHNODE SHashFindNode(SHNODE node, const char *key) { - xht xnew; - - xnew = (xht)malloc(sizeof(struct xht_struct)); - xnew->prime = prime; - xnew->zen = (xhn)malloc(sizeof(struct xhn_struct)*prime); /* array of xhn size of prime */ - bzero(xnew->zen,sizeof(struct xhn_struct)*prime); - return xnew; + for(; node != 0; node = node->next) { + if((node->key != 0) && (strcmp(key, node->key) == 0)) { + return node; + } + } + return 0; } -/* does the set work, used by xht_set and xht_store */ -void _xht_set(xht h, char *key, void *val, char flag) + +/*! + * \brief Helper function: Add a new entry to the hash table + * + * \param hash The hashtable to insert the new entry in + * \param key The key, under which the value should be entered + * \param val Void* pointer to be saved under 'key' in the hash table + * \param flag If flag != 0 the node memory is freed first and managed by this function + */ + +static void SHashDoSet(SHASH hash, char *key, void *val, char flag) { - int i; - xhn n; + int32_t i; + SHNODE node; - /* get our index for this key */ - i = _xhter(key) % h->prime; + /* Get the hash index of the key */ + i = StrToHash(key) % hash->prime; - /* check for existing key first, or find an empty one */ - if((n = _xht_node_find(&h->zen[i], key)) == 0) - for(n = &h->zen[i]; n != 0; n = n->next) - if(n->val == 0) + /* Does the key just exists? If not, find an empty one */ + node = SHashFindNode(&hash->zen[i], key); + if (node == 0) { + for(node = &hash->zen[i]; node != 0; node = node->next) { + if(node->val == 0) { break; + } + } + } - /* if none, make a new one, link into this index */ - if(n == 0) - { - n = (xhn)malloc(sizeof(struct xhn_struct)); - n->next = h->zen[i].next; - h->zen[i].next = n; + /* If the key does not exists, create a new node and link into the hash */ + if (node == 0) { + node = (SHNODE)malloc(sizeof(struct node_struct)); + node->next = hash->zen[i].next; + hash->zen[i].next = node; } - /* when flag is set, we manage their mem and free em first */ - if(n->flag) - { - free(n->key); - free(n->val); + /* If flag is set, the node memory will be freed first and then reused with the new key / value pair */ + if (node->flag) { + free(node->key); + free(node->val); } - n->flag = flag; - n->key = key; - n->val = val; + node->flag = flag; + node->key = key; + node->val = val; } -void xht_set(xht h, char *key, void *val) + +/*! + * \brief Add a new entry to the hash table + * + * The caller is responsible for the key storage. No copies are made. + * Do not free these valued before calling SHashFree()!!! + * + * If val is set to NULL, the entry is cleared and the memory is reused but + * never freed. The number of keys can only grow up to peak usage. + * + * \param hash The hashtable to insert the new entry in + * \param key The key, under which the value should be entered + * \param val Void* pointer to be saved under 'key' in the hash table + */ + +void SHashSet(SHASH hash, char *key, void *val) { - if(h == 0 || key == 0) + if ((hash == 0) || (key == 0)) { return; - _xht_set(h, key, val, 0); + } + SHashDoSet(hash, key, val, 0); } -void xht_store(xht h, const char *key, int klen, void *val, int vlen) + +/*! + * \brief Add a new entry to the hash table + * + * Unlike SHashSet() where key and values are managed in the callers memory + * space, here they are copied into the hash table and freed when + * val is 0 or by calling SHashFree(). + * + * If val is set to NULL, the entry is cleared and the memory is freed. + * + * \param hash The hashtable to insert the new entry in + * \param key The key, under which the value should be entered + * \param kley Size of the key + * \param val Void* pointer to be saved under 'key' in the hash table + * \param vlen Size of the value + */ + +void SHashStore(SHASH hash, const char *key, int key_len, void *val, int value_len) { - char *ckey, *cval; + char *ckey; + char *cval; - if(h == 0 || key == 0 || klen == 0) + if((hash == 0) || (key == 0) || (key_len == 0)) { return; + } - ckey = (char*)malloc(klen+1); - memcpy(ckey,key,klen); - ckey[klen] = '\0'; - cval = (void*)malloc(vlen+1); - memcpy(cval,val,vlen); - cval[vlen] = '\0'; /* convenience, in case it was a string too */ - _xht_set(h, ckey, cval, 1); -} + ckey = (char*)malloc(key_len+1); + memcpy(ckey, key, key_len); + ckey[key_len] = '\0'; + + /* Assume the value is a string too and store it with a trailing + zero for safety reasons + */ + cval = (void*)malloc(value_len+1); + memcpy(cval, val, value_len); + cval[value_len] = '\0'; + SHashDoSet(hash, ckey, cval, 1); +} -void *xht_get(xht h, const char *key) +/*! + * \brief Retrive a value associated to key from the hash table + * + * Return the value or NULL of the key was not found. + * + * \param hash The hast table to get the value from + * \param key Key to get the value for + * \return pointer to the value, NULL if no key was not found + */ +void *SHashGet(SHASH hash, const char *key) { - xhn n; + SHNODE node; - if(h == 0 || key == 0 || (n = _xht_node_find(&h->zen[_xhter(key) % h->prime], key)) == 0) + if ((hash == 0) || (key == 0)) { return 0; + } - return n->val; + node = SHashFindNode(&hash->zen[StrToHash(key) % hash->prime], key); + if (node == NULL) { + return 0; + } + + return node->val; } +/*! + * \brief Free the hash table and all entries + * + * \param hash The hast table to free + */ -void xht_free(xht h) +void SHashFree(SHASH hash) { - xhn n, f; + SHNODE node; + SHNODE temp; int i; - if(h == 0) return; + if(hash == 0) { + return; + } - for(i = 0; i < h->prime; i++) - for(n = (&h->zen[i])->next; n != 0;) - { - f = n->next; - if(n->flag) - { - free(n->key); - free(n->val); + for (i = 0; i < hash->prime; i++) { + for (node = (&hash->zen[i])->next; node != 0; ) { + temp = node->next; + if (node->flag) { + free(node->key); + free(node->val); } - free(n); - n = f; + free(node); + node = temp; } + } - free(h->zen); - free(h); + free(hash->zen); + free(hash); } -void xht_walk(xht h, xht_walker w, void *arg) +/*! + * \brief Interate over the hash table and call a callback for each key + * that has a value set. + * + * + * \param hash The hash table to iterate though + * \param cb SHASH_CB callback function + * \param arg An optional user pointer to pass to the callback function + */ +void SHashForEach(SHASH hash, SHASH_CB cb, void *arg) { int i; - xhn n; + SHNODE node; - if(h == 0 || w == 0) + if ((hash == 0) || (cb == 0)) { return; + } - for(i = 0; i < h->prime; i++) - for(n = &h->zen[i]; n != 0; n = n->next) - if(n->key != 0 && n->val != 0) - (*w)(h, n->key, n->val, arg); + for(i = 0; i < hash->prime; i++) { + for(node = &hash->zen[i]; node != 0; node = node->next) { + if(node->key != 0 && node->val != 0) { + (*cb)(hash, node->key, node->val, arg); + } + } + } } +/*@}*/