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