summaryrefslogtreecommitdiffstats
path: root/hash_table.c
diff options
context:
space:
mode:
Diffstat (limited to 'hash_table.c')
-rw-r--r--hash_table.c155
1 files changed, 155 insertions, 0 deletions
diff --git a/hash_table.c b/hash_table.c
new file mode 100644
index 0000000..76e1aa3
--- /dev/null
+++ b/hash_table.c
@@ -0,0 +1,155 @@
+/* hash.c - hash tables for ipkg
+
+ Steven M. Ayer, Jamey Hicks
+
+ Copyright (C) 2002 Compaq Computer Corporation
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+*/
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "hash_table.h"
+#include "ipkg_message.h"
+
+
+static int hash_index(hash_table_t *hash, const char *pkg_name);
+static int rotating(const char *key, int len, int prime);
+
+static int hash_index(hash_table_t *hash, const char *pkg_name)
+{
+ return rotating(pkg_name, strlen(pkg_name), hash->n_entries);
+}
+
+static int rotating(const char *key, int len, int prime)
+{
+ unsigned int hash, i;
+ for (hash=len, i=0; i<len; ++i)
+ hash = (hash<<4)^(hash>>28)^key[i];
+ return (hash % prime);
+}
+
+
+/*
+ * this is an open table keyed by strings
+ */
+int hash_table_init(const char *name, hash_table_t *hash, int len)
+{
+ static int primes_table[] = {
+ 379, 761, 983, 1423, 2711, 3361, 3931, 4679, 5519, 6701, 9587,
+ 19471, 23143, 33961, 46499, 49727, 99529, 0
+ };
+ int *picker;
+
+ if (hash->entries != NULL) {
+ /* we have been here already */
+ return 0;
+ }
+
+ hash->name = name;
+ hash->entries = NULL;
+ hash->n_entries = 0;
+ hash->hash_entry_key = NULL;
+
+ picker = primes_table;
+ while(*picker && (*picker++ < len));
+ if(!*picker)
+ fprintf(stderr, "%s: primes table might not be big enough (! << %d)\n", __FUNCTION__, len);
+ --picker;
+
+ hash->n_entries = *picker;
+ hash->entries = (hash_entry_t *)calloc(hash->n_entries, sizeof(hash_entry_t));
+ if (hash->entries == NULL) {
+ fprintf(stderr, "%s: Out of memory.\n", __FUNCTION__);
+ return ENOMEM;
+ }
+ return 0;
+}
+
+void hash_table_deinit(hash_table_t *hash)
+{
+ free(hash->entries);
+ hash->entries = NULL;
+ hash->n_entries = 0;
+}
+
+void *hash_table_get(hash_table_t *hash, const char *key)
+{
+ int ndx= hash_index(hash, key);
+ hash_entry_t *hash_entry = hash->entries + ndx;
+ while (hash_entry)
+ {
+ if (hash_entry->key)
+ {
+ if (strcmp(key, hash_entry->key) == 0) {
+ // ipkg_message(NULL, IPKG_DEBUG, "Function: %s. Key found for '%s' \n", __FUNCTION__, key);
+ return hash_entry->data;
+ }
+ }
+ hash_entry = hash_entry->next;
+ }
+ return NULL;
+}
+
+int hash_table_insert(hash_table_t *hash, const char *key, void *value)
+{
+ int ndx= hash_index(hash, key);
+ hash_entry_t *hash_entry = hash->entries + ndx;
+ if (0) ipkg_message(NULL, IPKG_DEBUG2, "Function: %s. Inserting in hash for '%s' \n", __FUNCTION__, key);
+ if (hash_entry->key) {
+ if (strcmp(hash_entry->key, key) == 0) {
+ /* alread in table, update the value */
+ if (0) ipkg_message(NULL, IPKG_DEBUG2, "Function: %s. Value already in hash for '%s' \n", __FUNCTION__, key);
+ hash_entry->data = value;
+ return 0;
+ } else {
+ /*
+ * if this is a collision, we have to go to the end of the ll,
+ * then add a new entry
+ * before we can hook up the value
+ */
+ if (0) ipkg_message(NULL, IPKG_DEBUG2, "Function: %s. Value already in hash by collision for '%s' \n", __FUNCTION__, key);
+ while (hash_entry->next)
+ hash_entry = hash_entry->next;
+ hash_entry->next = (hash_entry_t *)malloc(sizeof(hash_entry_t));
+ if (!hash_entry->next) {
+ return -ENOMEM;
+ }
+ hash_entry = hash_entry->next;
+ hash_entry->next = NULL;
+ }
+ }
+ hash->n_elements++;
+ hash_entry->key = strdup(key);
+ hash_entry->data = value;
+
+ return 0;
+}
+
+
+void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data)
+{
+ int i;
+ if (!hash || !f)
+ return;
+
+ for (i = 0; i < hash->n_entries; i++) {
+ hash_entry_t *hash_entry = (hash->entries + i);
+ do {
+ if(hash_entry->key) {
+ f(hash_entry->key, hash_entry->data, data);
+ }
+ } while((hash_entry = hash_entry->next));
+ }
+}
+