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 <errno.h>
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include "hash_table.h"
  23 #include "opkg_message.h"
  24 #include "libbb/libbb.h"
  25
  26
  27 static unsigned long
  28 djb2_hash(const unsigned char *str)
  29 {
  30         unsigned long hash = 5381;
  31         int c;
  32         while ((c = *str++))
  33                 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
  34         return hash;
  35 }
  36
  37 static int
  38 hash_index(hash_table_t *hash, const char *key)
  39 {
  40         return djb2_hash((const unsigned char *)key) % hash->n_buckets;
  41 }
  42
  43 /*
  44  * this is an open table keyed by strings
  45  */
  46 int
  47 hash_table_init(const char *name, hash_table_t *hash, int len)
  48 {
  49         if (hash->entries != NULL) {
  50                 fprintf(stderr, "ERROR: %s called on a non empty hash table\n",
  51                                 __FUNCTION__);
  52                 return -1;
  53         }
  54
  55         memset(hash, 0, sizeof(hash_table_t));
  56
  57         hash->name = name;
  58         hash->n_buckets = len;
  59         hash->entries = xcalloc(hash->n_buckets, sizeof(hash_entry_t));
  60
  61         return 0;
  62 }
  63
  64 void
  65 hash_print_stats(hash_table_t *hash)
  66 {
  67         printf("hash_table: %s, %d bytes\n"
  68                 "\tn_buckets=%d, n_elements=%d, n_collisions=%d\n"
  69                 "\tmax_bucket_len=%d, n_used_buckets=%d, ave_bucket_len=%.2f\n"
  70                 "\tn_hits=%d, n_misses=%d\n",
  71                 hash->name,
  72                 hash->n_buckets*(int)sizeof(hash_entry_t),
  73                 hash->n_buckets,
  74                 hash->n_elements,
  75                 hash->n_collisions,
  76                 hash->max_bucket_len,
  77                 hash->n_used_buckets,
  78                 (hash->n_used_buckets ?
  79                         ((float)hash->n_elements)/hash->n_used_buckets : 0.0f),
  80                 hash->n_hits,
  81                 hash->n_misses);
  82 }
  83
  84 void hash_table_deinit(hash_table_t *hash)
  85 {
  86     int i;
  87     if (!hash)
  88         return;
  89
  90     /* free the reminaing entries */
  91     for (i = 0; i < hash->n_buckets; i++) {
  92         hash_entry_t *hash_entry = (hash->entries + i);
  93         free (hash_entry->key);
  94         /* skip the first entry as this is part of the array */
  95         hash_entry = hash_entry->next;
  96         while (hash_entry)
  97         {
  98           hash_entry_t *old = hash_entry;
  99           hash_entry = hash_entry->next;
 100           free (old->key);
 101           free (old);
 102         }
 103     }
 104
 105     free (hash->entries);
 106
 107     hash->entries = NULL;
 108     hash->n_buckets = 0;
 109 }
 110
 111 void *hash_table_get(hash_table_t *hash, const char *key)
 112 {
 113   int ndx= hash_index(hash, key);
 114   hash_entry_t *hash_entry = hash->entries + ndx;
 115   while (hash_entry)
 116   {
 117     if (hash_entry->key)
 118     {
 119       if (strcmp(key, hash_entry->key) == 0) {
 120          // opkg_message(NULL, OPKG_DEBUG, "Function: %s. Key found for '%s' \n", __FUNCTION__, key);
 121          hash->n_hits++;
 122          return hash_entry->data;
 123       }
 124     }
 125     hash_entry = hash_entry->next;
 126   }
 127   hash->n_misses++;
 128   return NULL;
 129 }
 130
 131 int hash_table_insert(hash_table_t *hash, const char *key, void *value)
 132 {
 133      int bucket_len = 0;
 134      int ndx= hash_index(hash, key);
 135      hash_entry_t *hash_entry = hash->entries + ndx;
 136      if (hash_entry->key) {
 137           if (strcmp(hash_entry->key, key) == 0) {
 138                /* alread in table, update the value */
 139                hash_entry->data = value;
 140                return 0;
 141           } else {
 142                /*
 143                 * if this is a collision, we have to go to the end of the ll,
 144                 * then add a new entry
 145                 * before we can hook up the value
 146                 */
 147                while (hash_entry->next) {
 148                     hash_entry = hash_entry->next;
 149                     if (strcmp(hash_entry->key, key) == 0) {
 150                         hash_entry->data = value;
 151                         return 0;
 152                     }
 153                     bucket_len++;
 154                }
 155                hash_entry->next = xcalloc(1, sizeof(hash_entry_t));
 156                hash_entry = hash_entry->next;
 157                hash_entry->next = NULL;
 158
 159                hash->n_collisions++;
 160                if (++bucket_len > hash->max_bucket_len)
 161                     hash->max_bucket_len = bucket_len;
 162           }
 163      } else
 164           hash->n_used_buckets++;
 165
 166      hash->n_elements++;
 167      hash_entry->key = xstrdup(key);
 168      hash_entry->data = value;
 169
 170      return 0;
 171 }
 172
 173 int hash_table_remove(hash_table_t *hash, const char *key)
 174 {
 175     int ndx= hash_index(hash, key);
 176     hash_entry_t *hash_entry = hash->entries + ndx;
 177     hash_entry_t *next_entry=NULL, *last_entry=NULL;
 178     while (hash_entry)
 179     {
 180         if (hash_entry->key)
 181         {
 182             if (strcmp(key, hash_entry->key) == 0) {
 183                 free(hash_entry->key);
 184                 if (last_entry) {
 185                     last_entry->next = hash_entry->next;
 186                     free(hash_entry);
 187                 } else {
 188                     next_entry = hash_entry->next;
 189                     if (next_entry) {
 190                         memmove(hash_entry, next_entry, sizeof(hash_entry_t));
 191                         free(next_entry);
 192                     } else {
 193                         memset(hash_entry, 0 , sizeof(hash_entry_t));
 194                     }
 195                 }
 196                 return 1;
 197             }
 198         }
 199         last_entry = hash_entry;
 200         hash_entry = hash_entry->next;
 201     }
 202     return 0;
 203 }
 204
 205 void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data)
 206 {
 207     int i;
 208     if (!hash || !f)
 209         return;
 210
 211     for (i = 0; i < hash->n_buckets; i++) {
 212         hash_entry_t *hash_entry = (hash->entries + i);
 213         do {
 214             if(hash_entry->key) {
 215                 f(hash_entry->key, hash_entry->data, data);
 216             }
 217         } while((hash_entry = hash_entry->next));
 218     }
 219 }
 220