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
  25
  26 static int hash_index(hash_table_t *hash, const char *pkg_name);
  27 static int rotating(const char *key, int len, int prime);
  28
  29 static int hash_index(hash_table_t *hash, const char *pkg_name)
  30 {
  31     return rotating(pkg_name, strlen(pkg_name), hash->n_entries);
  32 }
  33
  34 static int rotating(const char *key, int len, int prime)
  35 {
  36     unsigned int hash, i;
  37     for (hash=len, i=0; i<len; ++i)
  38         hash = (hash<<4)^(hash>>28)^key[i];
  39     return (hash % prime);
  40 }
  41
  42
  43 /*
  44  * this is an open table keyed by strings
  45  */
  46 int hash_table_init(const char *name, hash_table_t *hash, int len)
  47 {
  48     static int primes_table[] = {
  49         379, 761, 983, 1423, 2711, 3361, 3931, 4679, 5519, 6701, 9587,
  50         19471, 23143, 33961, 46499, 49727, 99529, 0
  51     };
  52     int *picker;
  53
  54     if (hash->entries != NULL) {
  55         /* we have been here already */
  56         return 0;
  57     }
  58
  59     hash->name = name;
  60     hash->entries = NULL;
  61     hash->n_entries = 0;
  62     hash->hash_entry_key = NULL;
  63
  64     picker = primes_table;
  65     while(*picker && (*picker++ < len));
  66     if(!*picker)
  67         fprintf(stderr, "%s: primes table might not be big enough (! << %d)\n", __FUNCTION__, len);
  68     --picker;
  69
  70     hash->n_entries = *picker;
  71     hash->entries = (hash_entry_t *)calloc(hash->n_entries, sizeof(hash_entry_t));
  72     if (hash->entries == NULL) {
  73         fprintf(stderr, "%s: Out of memory.\n", __FUNCTION__);
  74         return ENOMEM;
  75     }
  76     return 0;
  77 }
  78
  79 void hash_table_deinit(hash_table_t *hash)
  80 {
  81     int i;
  82     if (!hash)
  83         return;
  84
  85     /* free the reminaing entries */
  86     for (i = 0; i < hash->n_entries; i++) {
  87         hash_entry_t *hash_entry = (hash->entries + i);
  88         free (hash_entry->key);
  89         /* skip the first entry as this is part of the array */
  90         hash_entry = hash_entry->next;
  91         while (hash_entry)
  92         {
  93           hash_entry_t *old = hash_entry;
  94           hash_entry = hash_entry->next;
  95           free (old->key);
  96           free (old);
  97         }
  98     }
  99
 100     free (hash->entries);
 101
 102     hash->entries = NULL;
 103     hash->n_entries = 0;
 104 }
 105
 106 void *hash_table_get(hash_table_t *hash, const char *key)
 107 {
 108   int ndx= hash_index(hash, key);
 109   hash_entry_t *hash_entry = hash->entries + ndx;
 110   while (hash_entry)
 111   {
 112     if (hash_entry->key)
 113     {
 114       if (strcmp(key, hash_entry->key) == 0) {
 115          // opkg_message(NULL, OPKG_DEBUG, "Function: %s. Key found for '%s' \n", __FUNCTION__, key);
 116          return hash_entry->data;
 117       }
 118     }
 119     hash_entry = hash_entry->next;
 120   }
 121   return NULL;
 122 }
 123
 124 int hash_table_insert(hash_table_t *hash, const char *key, void *value)
 125 {
 126      int ndx= hash_index(hash, key);
 127      hash_entry_t *hash_entry = hash->entries + ndx;
 128      if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Inserting in hash for '%s' \n", __FUNCTION__, key);
 129      if (hash_entry->key) {
 130           if (strcmp(hash_entry->key, key) == 0) {
 131                /* alread in table, update the value */
 132                if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Value already in hash for '%s' \n", __FUNCTION__, key);
 133                hash_entry->data = value;
 134                return 0;
 135           } else {
 136                /*
 137                 * if this is a collision, we have to go to the end of the ll,
 138                 * then add a new entry
 139                 * before we can hook up the value
 140                 */
 141                if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Value already in hash by collision for '%s' \n", __FUNCTION__, key);
 142                while (hash_entry->next)
 143                     hash_entry = hash_entry->next;
 144                hash_entry->next = (hash_entry_t *)malloc(sizeof(hash_entry_t));
 145                if (!hash_entry->next) {
 146                     return -ENOMEM;
 147                }
 148                hash_entry = hash_entry->next;
 149                hash_entry->next = NULL;
 150           }
 151      }
 152      hash->n_elements++;
 153      hash_entry->key = strdup(key);
 154      hash_entry->data = value;
 155
 156      return 0;
 157 }
 158
 159
 160 void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data)
 161 {
 162     int i;
 163     if (!hash || !f)
 164         return;
 165
 166     for (i = 0; i < hash->n_entries; i++) {
 167         hash_entry_t *hash_entry = (hash->entries + i);
 168         do {
 169             if(hash_entry->key) {
 170                 f(hash_entry->key, hash_entry->data, data);
 171             }
 172         } while((hash_entry = hash_entry->next));
 173     }
 174 }
 175