From 718e3744195351130f4ce7dbe0613f4b3e23df93 Mon Sep 17 00:00:00 2001
From: paul <paul>
Date: Fri, 13 Dec 2002 20:15:29 +0000
Subject: Initial revision

---
 lib/hash.c | 182 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 182 insertions(+)
 create mode 100644 lib/hash.c

(limited to 'lib/hash.c')

diff --git a/lib/hash.c b/lib/hash.c
new file mode 100644
index 00000000..40975079
--- /dev/null
+++ b/lib/hash.c
@@ -0,0 +1,182 @@
+/* Hash routine.
+ * Copyright (C) 1998 Kunihiro Ishiguro
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra 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.
+ *
+ * GNU Zebra 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.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <zebra.h>
+
+#include "hash.h"
+#include "memory.h"
+
+/* Allocate a new hash.  */
+struct hash *
+hash_create_size (unsigned int size, 
+		  unsigned int (*hash_key) (), int (*hash_cmp) ())
+{
+  struct hash *hash;
+
+  hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
+  hash->index = XMALLOC (MTYPE_HASH_INDEX, 
+			 sizeof (struct hash_backet *) * size);
+  memset (hash->index, 0, sizeof (struct hash_backet *) * size);
+  hash->size = size;
+  hash->hash_key = hash_key;
+  hash->hash_cmp = hash_cmp;
+  hash->count = 0;
+
+  return hash;
+}
+
+/* Allocate a new hash with default hash size.  */
+struct hash *
+hash_create (unsigned int (*hash_key) (), int (*hash_cmp) ())
+{
+  return hash_create_size (HASHTABSIZE, hash_key, hash_cmp);
+}
+
+/* Utility function for hash_get().  When this function is specified
+   as alloc_func, return arugment as it is.  This function is used for
+   intern already allocated value.  */
+void *
+hash_alloc_intern (void *arg)
+{
+  return arg;
+}
+
+/* Lookup and return hash backet in hash.  If there is no
+   corresponding hash backet and alloc_func is specified, create new
+   hash backet.  */
+void *
+hash_get (struct hash *hash, void *data, void * (*alloc_func) ())
+{
+  unsigned int key;
+  unsigned int index;
+  void *newdata;
+  struct hash_backet *backet;
+
+  key = (*hash->hash_key) (data);
+  index = key % hash->size;
+
+  for (backet = hash->index[index]; backet != NULL; backet = backet->next) 
+    if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
+      return backet->data;
+
+  if (alloc_func)
+    {
+      newdata = (*alloc_func) (data);
+      if (newdata == NULL)
+	return NULL;
+
+      backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
+      backet->data = newdata;
+      backet->key = key;
+      backet->next = hash->index[index];
+      hash->index[index] = backet;
+      hash->count++;
+      return backet->data;
+    }
+  return NULL;
+}
+
+/* Hash lookup.  */
+void *
+hash_lookup (struct hash *hash, void *data)
+{
+  return hash_get (hash, data, NULL);
+}
+
+/* This function release registered value from specified hash.  When
+   release is successfully finished, return the data pointer in the
+   hash backet.  */
+void *
+hash_release (struct hash *hash, void *data)
+{
+  void *ret;
+  unsigned int key;
+  unsigned int index;
+  struct hash_backet *backet;
+  struct hash_backet *pp;
+
+  key = (*hash->hash_key) (data);
+  index = key % hash->size;
+
+  for (backet = pp = hash->index[index]; backet; backet = backet->next)
+    {
+      if (backet->key == key && (*hash->hash_cmp) (backet->data, data)) 
+	{
+	  if (backet == pp) 
+	    hash->index[index] = backet->next;
+	  else 
+	    pp->next = backet->next;
+
+	  ret = backet->data;
+	  XFREE (MTYPE_HASH_BACKET, backet);
+	  hash->count--;
+	  return ret;
+	}
+      pp = backet;
+    }
+  return NULL;
+}
+
+/* Iterator function for hash.  */
+void
+hash_iterate (struct hash *hash, 
+	      void (*func) (struct hash_backet *, void *), void *arg)
+{
+  int i;
+  struct hash_backet *hb;
+
+  for (i = 0; i < hash->size; i++)
+    for (hb = hash->index[i]; hb; hb = hb->next)
+      (*func) (hb, arg);
+}
+
+/* Clean up hash.  */
+void
+hash_clean (struct hash *hash, void (*free_func) (void *))
+{
+  int i;
+  struct hash_backet *hb;
+  struct hash_backet *next;
+
+  for (i = 0; i < hash->size; i++)
+    {
+      for (hb = hash->index[i]; hb; hb = next)
+	{
+	  next = hb->next;
+	      
+	  if (free_func)
+	    (*free_func) (hb->data);
+
+	  XFREE (MTYPE_HASH_BACKET, hb);
+	  hash->count--;
+	}
+      hash->index[i] = NULL;
+    }
+}
+
+/* Free hash memory.  You may call hash_clean before call this
+   function.  */
+void
+hash_free (struct hash *hash)
+{
+  XFREE (MTYPE_HASH_INDEX, hash->index);
+  XFREE (MTYPE_HASH, hash);
+}
-- 
cgit v1.2.1