libopkg/hash_table.c

   1 /* hash.c - hash tables for opkg
   2
   3    Steven M. Ayer, Jamey Hicks
   4
   5    Copyright (C) 2002 Compaq Computer Corporation
   6
   7    This program is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU General Public License as
   9    published by the Free Software Foundation; either version 2, or (at
  10    your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful, but
  13    WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    General Public License for more details.
  16 */
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include "hash_table.h"
  22 #include "opkg_message.h"
  23 #include "libbb/libbb.h"
  24
  25
  26 static unsigned long
  27 djb2_hash(const unsigned char *str)
  28 {
  29         unsigned long hash = 5381;
  30         int c;
  31         while ((c = *str++))
  32                 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
  33         return hash;
  34 }
  35
  36 static int
  37 hash_index(hash_table_t *hash, const char *key)
  38 {
  39         return djb2_hash((const unsigned char *)key) % hash->n_buckets;
  40 }
  41
  42 /*
  43  * this is an open table keyed by strings
  44  */
  45 void
  46 hash_table_init(const char *name, hash_table_t *hash, int len)
  47 {
  48         if (hash->entries != NULL) {
  49                 opkg_msg(ERROR, "Internal error: non empty hash table.\n");
  50                 return;
  51         }
  52
  53         memset(hash, 0, sizeof(hash_table_t));
  54
  55         hash->name = name;
  56         hash->n_buckets = len;
  57         hash->entries = xcalloc(hash->n_buckets, sizeof(hash_entry_t));
  58 }
  59
  60 void
  61 hash_print_stats(hash_table_t *hash)
  62 {
  63         printf("hash_table: %s, %d bytes\n"
  64                 "\tn_buckets=%d, n_elements=%d, n_collisions=%d\n"
  65                 "\tmax_bucket_len=%d, n_used_buckets=%d, ave_bucket_len=%.2f\n"
  66                 "\tn_hits=%d, n_misses=%d\n",
  67                 hash->name,
  68                 hash->n_buckets*(int)sizeof(hash_entry_t),
  69                 hash->n_buckets,
  70                 hash->n_elements,
  71                 hash->n_collisions,
  72                 hash->max_bucket_len,
  73                 hash->n_used_buckets,
  74                 (hash->n_used_buckets ?
  75                         ((float)hash->n_elements)/hash->n_used_buckets : 0.0f),
  76                 hash->n_hits,
  77                 hash->n_misses);
  78 }
  79
  80 void hash_table_deinit(hash_table_t *hash)
  81 {
  82     int i;
  83     if (!hash)
  84         return;
  85
  86     /* free the reminaing entries */
  87     for (i = 0; i < hash->n_buckets; i++) {
  88         hash_entry_t *hash_entry = (hash->entries + i);
  89         free (hash_entry->key);
  90         /* skip the first entry as this is part of the array */
  91         hash_entry = hash_entry->next;
  92         while (hash_entry)
  93         {
  94           hash_entry_t *old = hash_entry;
  95           hash_entry = hash_entry->next;
  96           free (old->key);
  97           free (old);
  98         }
  99     }
 100
 101     free (hash->entries);
 102
 103     hash->entries = NULL;
 104     hash->n_buckets = 0;
 105 }
 106
 107 void *hash_table_get(hash_table_t *hash, const char *key)
 108 {
 109   int ndx= hash_index(hash, key);
 110   hash_entry_t *hash_entry = hash->entries + ndx;
 111   while (hash_entry)
 112   {
 113     if (hash_entry->key)
 114     {
 115       if (strcmp(key, hash_entry->key) == 0) {
 116          hash->n_hits++;
 117          return hash_entry->data;
 118       }
 119     }
 120     hash_entry = hash_entry->next;
 121   }
 122   hash->n_misses++;
 123   return NULL;
 124 }
 125
 126 int hash_table_insert(hash_table_t *hash, const char *key, void *value)
 127 {
 128      int bucket_len = 0;
 129      int ndx= hash_index(hash, key);
 130      hash_entry_t *hash_entry = hash->entries + ndx;
 131      if (hash_entry->key) {
 132           if (strcmp(hash_entry->key, key) == 0) {
 133                /* alread in table, update the value */
 134                hash_entry->data = value;
 135                return 0;
 136           } else {
 137                /*
 138                 * if this is a collision, we have to go to the end of the ll,
 139                 * then add a new entry
 140                 * before we can hook up the value
 141                 */
 142                while (hash_entry->next) {
 143                     hash_entry = hash_entry->next;
 144                     if (strcmp(hash_entry->key, key) == 0) {
 145                         hash_entry->data = value;
 146                         return 0;
 147                     }
 148                     bucket_len++;
 149                }
 150                hash_entry->next = xcalloc(1, sizeof(hash_entry_t));
 151                hash_entry = hash_entry->next;
 152                hash_entry->next = NULL;
 153
 154                hash->n_collisions++;
 155                if (++bucket_len > hash->max_bucket_len)
 156                     hash->max_bucket_len = bucket_len;
 157           }
 158      } else
 159           hash->n_used_buckets++;
 160
 161      hash->n_elements++;
 162      hash_entry->key = xstrdup(key);
 163      hash_entry->data = value;
 164
 165      return 0;
 166 }
 167
 168 int hash_table_remove(hash_table_t *hash, const char *key)
 169 {
 170     int ndx= hash_index(hash, key);
 171     hash_entry_t *hash_entry = hash->entries + ndx;
 172     hash_entry_t *next_entry=NULL, *last_entry=NULL;
 173     while (hash_entry)
 174     {
 175         if (hash_entry->key)
 176         {
 177             if (strcmp(key, hash_entry->key) == 0) {
 178                 free(hash_entry->key);
 179                 if (last_entry) {
 180                     last_entry->next = hash_entry->next;
 181                     free(hash_entry);
 182                 } else {
 183                     next_entry = hash_entry->next;
 184                     if (next_entry) {
 185                         memmove(hash_entry, next_entry, sizeof(hash_entry_t));
 186                         free(next_entry);
 187                     } else {
 188                         memset(hash_entry, 0 , sizeof(hash_entry_t));
 189                     }
 190                 }
 191                 return 1;
 192             }
 193         }
 194         last_entry = hash_entry;
 195         hash_entry = hash_entry->next;
 196     }
 197     return 0;
 198 }
 199
 200 void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data)
 201 {
 202     int i;
 203     if (!hash || !f)
 204         return;
 205
 206     for (i = 0; i < hash->n_buckets; i++) {
 207         hash_entry_t *hash_entry = (hash->entries + i);
 208         do {
 209             if(hash_entry->key) {
 210                 f(hash_entry->key, hash_entry->data, data);
 211             }
 212         } while((hash_entry = hash_entry->next));
 213     }
 214 }
 215