1 /* hash.c - hash tables for opkg
3 Steven M. Ayer, Jamey Hicks
5 Copyright (C) 2002 Compaq Computer Corporation
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.
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.
22 #include "hash_table.h"
23 #include "opkg_message.h"
26 static int hash_index(hash_table_t *hash, const char *pkg_name);
27 static int rotating(const char *key, int len, int prime);
29 static int hash_index(hash_table_t *hash, const char *pkg_name)
31 return rotating(pkg_name, strlen(pkg_name), hash->n_entries);
34 static int rotating(const char *key, int len, int prime)
37 for (hash=len, i=0; i<len; ++i)
38 hash = (hash<<4)^(hash>>28)^key[i];
39 return (hash % prime);
44 * this is an open table keyed by strings
46 int hash_table_init(const char *name, hash_table_t *hash, int len)
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
54 if (hash->entries != NULL) {
55 /* we have been here already */
62 hash->hash_entry_key = NULL;
64 picker = primes_table;
65 while(*picker && (*picker++ < len));
67 fprintf(stderr, "%s: primes table might not be big enough (! << %d)\n", __FUNCTION__, len);
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__);
79 void hash_table_deinit(hash_table_t *hash)
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;
93 hash_entry_t *old = hash_entry;
94 hash_entry = hash_entry->next;
100 free (hash->entries);
102 hash->entries = NULL;
106 void *hash_table_get(hash_table_t *hash, const char *key)
108 int ndx= hash_index(hash, key);
109 hash_entry_t *hash_entry = hash->entries + ndx;
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;
119 hash_entry = hash_entry->next;
124 int hash_table_insert(hash_table_t *hash, const char *key, void *value)
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;
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
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) {
148 hash_entry = hash_entry->next;
149 hash_entry->next = NULL;
153 hash_entry->key = strdup(key);
154 hash_entry->data = value;
160 void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data)
166 for (i = 0; i < hash->n_entries; i++) {
167 hash_entry_t *hash_entry = (hash->entries + i);
169 if(hash_entry->key) {
170 f(hash_entry->key, hash_entry->data, data);
172 } while((hash_entry = hash_entry->next));