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