1/* Hash routine.
2 * Copyright (C) 1998 Kunihiro Ishiguro
3 *
4 * This file is part of GNU Zebra.
5 *
6 * GNU Zebra is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published
8 * by the Free Software Foundation; either version 2, or (at your
9 * option) any later version.
10 *
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with GNU Zebra; see the file COPYING.  If not, write to the
18 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
20 */
21
22#include <zebra.h>
23
24#include "hash.h"
25#include "memory.h"
26
27/* Allocate a new hash.  */
28struct hash *
29hash_create_size (unsigned int size,
30		  unsigned int (*hash_key) (), int (*hash_cmp) ())
31{
32  struct hash *hash;
33
34  hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
35  hash->index = XMALLOC (MTYPE_HASH_INDEX,
36			 sizeof (struct hash_backet *) * size);
37  memset (hash->index, 0, sizeof (struct hash_backet *) * size);
38  hash->size = size;
39  hash->hash_key = hash_key;
40  hash->hash_cmp = hash_cmp;
41  hash->count = 0;
42
43  return hash;
44}
45
46/* Allocate a new hash with default hash size.  */
47struct hash *
48hash_create (unsigned int (*hash_key) (), int (*hash_cmp) ())
49{
50  return hash_create_size (HASHTABSIZE, hash_key, hash_cmp);
51}
52
53/* Utility function for hash_get().  When this function is specified
54   as alloc_func, return arugment as it is.  This function is used for
55   intern already allocated value.  */
56void *
57hash_alloc_intern (void *arg)
58{
59  return arg;
60}
61
62/* Lookup and return hash backet in hash.  If there is no
63   corresponding hash backet and alloc_func is specified, create new
64   hash backet.  */
65void *
66hash_get (struct hash *hash, void *data, void * (*alloc_func) ())
67{
68  unsigned int key;
69  unsigned int index;
70  void *newdata;
71  struct hash_backet *backet;
72
73  key = (*hash->hash_key) (data);
74  index = key % hash->size;
75
76  for (backet = hash->index[index]; backet != NULL; backet = backet->next)
77    if (backet->key == key && (*hash->hash_cmp) (backet->data, data) == 1)
78      return backet->data;
79
80  if (alloc_func)
81    {
82      newdata = (*alloc_func) (data);
83      if (newdata == NULL)
84	return NULL;
85
86      backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
87      backet->data = newdata;
88      backet->key = key;
89      backet->next = hash->index[index];
90      hash->index[index] = backet;
91      hash->count++;
92      return backet->data;
93    }
94  return NULL;
95}
96
97/* Hash lookup.  */
98void *
99hash_lookup (struct hash *hash, void *data)
100{
101  return hash_get (hash, data, NULL);
102}
103
104/* This function release registered value from specified hash.  When
105   release is successfully finished, return the data pointer in the
106   hash backet.  */
107void *
108hash_release (struct hash *hash, void *data)
109{
110  void *ret;
111  unsigned int key;
112  unsigned int index;
113  struct hash_backet *backet;
114  struct hash_backet *pp;
115
116  key = (*hash->hash_key) (data);
117  index = key % hash->size;
118
119  for (backet = pp = hash->index[index]; backet; backet = backet->next)
120    {
121      if (backet->key == key && (*hash->hash_cmp) (backet->data, data) == 1)
122	{
123	  if (backet == pp)
124	    hash->index[index] = backet->next;
125	  else
126	    pp->next = backet->next;
127
128	  ret = backet->data;
129	  XFREE (MTYPE_HASH_BACKET, backet);
130	  hash->count--;
131	  return ret;
132	}
133      pp = backet;
134    }
135  return NULL;
136}
137
138/* Iterator function for hash.  */
139void
140hash_iterate (struct hash *hash,
141	      void (*func) (struct hash_backet *, void *), void *arg)
142{
143  int i;
144  struct hash_backet *hb;
145
146  for (i = 0; i < hash->size; i++)
147    for (hb = hash->index[i]; hb; hb = hb->next)
148      (*func) (hb, arg);
149}
150
151/* Clean up hash.  */
152void
153hash_clean (struct hash *hash, void (*free_func) (void *))
154{
155  int i;
156  struct hash_backet *hb;
157  struct hash_backet *next;
158
159  for (i = 0; i < hash->size; i++)
160    {
161      for (hb = hash->index[i]; hb; hb = next)
162	{
163	  next = hb->next;
164
165	  if (free_func)
166	    (*free_func) (hb->data);
167
168	  XFREE (MTYPE_HASH_BACKET, hb);
169	  hash->count--;
170	}
171      hash->index[i] = NULL;
172    }
173}
174
175/* Free hash memory.  You may call hash_clean before call this
176   function.  */
177void
178hash_free (struct hash *hash)
179{
180  XFREE (MTYPE_HASH_INDEX, hash->index);
181  XFREE (MTYPE_HASH, hash);
182}
183