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 int hash_index(hash_table_t *hash, const char *pkg_name);
  28 static int rotating(const char *key, int len, int prime);
  29
  30 static int hash_index(hash_table_t *hash, const char *pkg_name)
  31 {
  32     return rotating(pkg_name, strlen(pkg_name), hash->n_entries);
  33 }
  34
  35 static int rotating(const char *key, int len, int prime)
  36 {
  37     unsigned int hash, i;
  38     for (hash=len, i=0; i<len; ++i)
  39         hash = (hash<<4)^(hash>>28)^key[i];
  40     return (hash % prime);
  41 }
  42
  43
  44 /*
  45  * this is an open table keyed by strings
  46  */
  47 int hash_table_init(const char *name, hash_table_t *hash, int len)
  48 {
  49     static int primes_table[] = {
  50         379, 761, 983, 1423, 2711, 3361, 3931, 4679, 5519, 6701, 9587,
  51         19471, 23143, 33961, 46499, 49727, 99529, 0
  52     };
  53     int *picker;
  54
  55     if (hash->entries != NULL) {
  56         /* we have been here already */
  57         return 0;
  58     }
  59
  60     hash->name = name;
  61     hash->entries = NULL;
  62     hash->n_entries = 0;
  63     hash->hash_entry_key = NULL;
  64
  65     picker = primes_table;
  66     while(*picker && (*picker++ < len));
  67     if(!*picker)
  68         fprintf(stderr, "%s: primes table might not be big enough (! << %d)\n", __FUNCTION__, len);
  69     --picker;
  70
  71     hash->n_entries = *picker;
  72     hash->entries = (hash_entry_t *)calloc(hash->n_entries, sizeof(hash_entry_t));
  73     if (hash->entries == NULL) {
  74         fprintf(stderr, "%s: Out of memory.\n", __FUNCTION__);
  75         return ENOMEM;
  76     }
  77     return 0;
  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_entries; 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_entries = 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          // opkg_message(NULL, OPKG_DEBUG, "Function: %s. Key found for '%s' \n", __FUNCTION__, key);
 117          return hash_entry->data;
 118       }
 119     }
 120     hash_entry = hash_entry->next;
 121   }
 122   return NULL;
 123 }
 124
 125 int hash_table_insert(hash_table_t *hash, const char *key, void *value)
 126 {
 127      int ndx= hash_index(hash, key);
 128      hash_entry_t *hash_entry = hash->entries + ndx;
 129      if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Inserting in hash for '%s' \n", __FUNCTION__, key);
 130      if (hash_entry->key) {
 131           if (strcmp(hash_entry->key, key) == 0) {
 132                /* alread in table, update the value */
 133                if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Value already in hash for '%s' \n", __FUNCTION__, key);
 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                if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Value already in hash by collision for '%s' \n", __FUNCTION__, key);
 143                while (hash_entry->next) {
 144                     hash_entry = hash_entry->next;
 145                     if (strcmp(hash_entry->key, key) == 0) {
 146                         hash_entry->data = value;
 147                         return 0;
 148                     }
 149                }
 150                hash_entry->next = (hash_entry_t *)calloc(1, sizeof(hash_entry_t));
 151                if (!hash_entry->next) {
 152                     return -ENOMEM;
 153                }
 154                hash_entry = hash_entry->next;
 155                hash_entry->next = NULL;
 156           }
 157      }
 158      hash->n_elements++;
 159      hash_entry->key = xstrdup(key);
 160      hash_entry->data = value;
 161
 162      return 0;
 163 }
 164
 165 int hash_table_remove(hash_table_t *hash, const char *key)
 166 {
 167     int ndx= hash_index(hash, key);
 168     hash_entry_t *hash_entry = hash->entries + ndx;
 169     hash_entry_t *next_entry=NULL, *last_entry=NULL;
 170     while (hash_entry)
 171     {
 172         if (hash_entry->key)
 173         {
 174             if (strcmp(key, hash_entry->key) == 0) {
 175                 free(hash_entry->key);
 176                 if (last_entry) {
 177                     last_entry->next = hash_entry->next;
 178                     free(hash_entry);
 179                 } else {
 180                     next_entry = hash_entry->next;
 181                     if (next_entry) {
 182                         memmove(hash_entry, next_entry, sizeof(hash_entry_t));
 183                         free(next_entry);
 184                     } else {
 185                         memset(hash_entry, 0 , sizeof(hash_entry_t));
 186                     }
 187                 }
 188                 return 1;
 189             }
 190         }
 191         last_entry = hash_entry;
 192         hash_entry = hash_entry->next;
 193     }
 194     return 0;
 195 }
 196
 197 void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data)
 198 {
 199     int i;
 200     if (!hash || !f)
 201         return;
 202
 203     for (i = 0; i < hash->n_entries; i++) {
 204         hash_entry_t *hash_entry = (hash->entries + i);
 205         do {
 206             if(hash_entry->key) {
 207                 f(hash_entry->key, hash_entry->data, data);
 208             }
 209         } while((hash_entry = hash_entry->next));
 210     }
 211 }
 212