Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Copyright (C) 2010 spy
- *
- * 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. The name of the author may not be used to endorse or promote products
- * derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "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 AUTHOR 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.
- */
- /*
- * Dynamic hash tables.
- *
- * As usual, nodes with colliding hashes are doubly-linked in a list.
- * However, these hash tables will automatically grow as they become
- * full (they don't shrink back), so to simplify rehashing those lists
- * of nodes are maintained as parts of a super-list containing all
- * nodes in a table. The end of a particular sub-list is not marked in
- * any way, but the very hashes serve to that purpose. Except for the
- * sub-lists, there's no order in the super-list. Refer to the scheme:
- *
- * ...+-------+...+-------+...+-------+...+-------+...
- * .t_table: | 811 | | 14023 | | 19588 | | 28706 |
- * ...+-------+...+-------+...+-------+...+-------+...
- * : : : :
- * v v v v
- * +---+ +---+ +---+ +---+
- * .t_nodes: ---->| A |------>| B | ->| D | ->| F |....>
- * +---+ +---+ / +---+ / +---+
- * | / | /
- * v / v /
- * +---+ / +---+ /
- * | C |- | E |-
- * +---+ +---+
- */
- #include "hash.h"
- #include "var.h"
- #include <assert.h>
- #include <ctype.h>
- #include <errno.h>
- #include <stdlib.h>
- #include <string.h>
- #include <strings.h>
- #include <sys/types.h>
- #include <syslog.h>
- /*
- * Internal functions.
- */
- /*
- * Bitwise hash function. Author J. Zobel, April 2001.
- * Permission to use this code is freely granted,
- * provided that this statement is retained.
- */
- static int
- zobel_hash(hash_table_t *tp, const char *key)
- {
- int digest = tp->t_salt;
- while (*key)
- digest ^= (digest << 5) + (digest >> 2) +
- (tp->t_nocase ? tolower(*key++) : *key++);
- return (digest % tp->t_size);
- }
- static int
- realloc_hash_table(hash_table_t *tp, size_t nelem)
- {
- hash_node_t *ntp;
- assert(nelem);
- if (!(ntp = calloc(nelem, sizeof (*tp->t_table)))) {
- syslog(LOG_ERR,
- "realloc_hash_table(): calloc() of %i bytes failed (error %i: %s)",
- nelem * sizeof (*tp->t_table), errno, strerror(errno));
- return (-1);
- }
- if (tp->t_table)
- free(tp->t_table);
- tp->t_table = ntp;
- tp->t_size = nelem;
- tp->t_nelem = 0;
- return (0);
- }
- static void
- grow_hash_table(hash_table_t *tp)
- {
- size_t oldsize;
- oldsize = tp->t_size;
- /**
- * todo: configurable per-table growth factors
- */
- (void)realloc_hash_table(tp, (size_t)((float)tp->t_size * 1.30f));
- hash_table_rehash(tp, rand());
- syslog(LOG_INFO, "resized hash table %s from %i to %i", tp->t_name,
- oldsize, tp->t_size);
- }
- static void
- insert_node(hash_table_t *tp, hash_node_t *np, hash_node_t **nnpp)
- {
- if (*nnpp) {
- np->n_prev = (*nnpp)->n_prev;
- (*nnpp)->n_prev = np;
- if (np->n_prev)
- np->n_prev->n_next = np;
- else {
- assert(tp->t_nodes == *nnpp);
- tp->t_nodes = np;
- }
- np->n_next = *nnpp;
- } else {
- np->n_prev = NULL;
- np->n_next = tp->t_nodes;
- tp->t_nodes = np;
- }
- *nnpp = np;
- }
- /*
- * Exported functions.
- */
- /**
- * todo: salt param
- */
- void
- hash_init(hash_table_t *tp, const char *name, size_t off, size_t size,
- boolean_t nocase)
- {
- assert(name);
- assert(size);
- tp->t_name = name;
- tp->t_off = off;
- tp->t_nocase = nocase;
- tp->t_salt = rand();
- tp->t_nodes = NULL;
- if (realloc_hash_table(tp, size)) {
- syslog(LOG_EMERG,
- "hash_init(): panic: failed to allocate memory for hash table %s",
- name);
- abort();
- }
- }
- void
- hash_fini(hash_table_t *tp)
- {
- assert(tp);
- assert(tp->t_table);
- free(tp->t_table);
- }
- void
- hash_node_init(hash_node_t *np, const char *key)
- {
- assert(np);
- assert(key);
- np->n_key = key;
- np->n_next = np->n_pprev = NULL;
- }
- void
- hash_table_rehash(hash_table_t *tp, int salt)
- {
- hash_node_t *np, *walker;
- assert(tp);
- tp->t_salt = salt;
- walker = tp->t_nodes;
- while (walker) {
- np = walker;
- walker = walker->n_next;
- hash_insert(tp, np);
- }
- }
- void
- hash_insert(hash_table_t *tp, hash_node_t *np)
- {
- assert(tp);
- assert(np);
- assert(tp->t_nelem < tp->t_size);
- if (++tp->t_nelem == tp->t_size)
- grow_hash_table(tp);
- insert_node(tp, np, &tp->t_table[zobel_hash(tp, np->n_key)]);
- }
- void
- hash_remove(hash_table_t *tp, hash_node_t *np)
- {
- int digest;
- assert(tp);
- assert(np);
- digest = zobel_hash(tp, np->n_key);
- if (tp->t_table[digest] == np)
- tp->t_table[digest] = np->n_next;
- if (np->n_next)
- np->n_next->n_prev = np->n_prev;
- if (tp->t_nodes == np) {
- assert(!np->n_prev);
- tp->t_nodes = np->n_next;
- } else {
- assert(np->n_prev);
- np->n_prev->n_next = np->n_next;
- }
- --tp->t_nelem;
- }
- void *
- hash_find(hash_table_t *tp, const char *key)
- {
- hash_node_t *np;
- int digest;
- assert(tp);
- assert(key);
- digest = zobel_hash(tp, key);
- for (np = table->t_table[digest];
- np && zobel_hash(np->n_key, tp->t_size) == digest;
- np = np->n_next)
- if (tp->t_nocase ? !strcasecmp(key, np->n_key) :
- !strcmp(key, np->n_key)) {
- if (*np->n_prev != &tp->t_table[digest]) {
- hash_remove(tp, np);
- insert_node(tp, np, &tp->t_table[digest]);
- }
- return (np - tp->t_off);
- }
- return (NULL);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement