From 8bf49d16a637cca0cd116450dfcabc4c941baf6c Mon Sep 17 00:00:00 2001
From: ticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358>
Date: Sun, 14 Dec 2008 23:10:56 -0500
Subject: * Add ipkg for future development

git-svn-id: http://opkg.googlecode.com/svn/trunk@3 e8e0d7a0-c8d9-11dd-a880-a1081c7ac358
---
(limited to 'hash_table.c')

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));
+    }
+}
+
--
cgit v0.9.1