1 /* hash.c - hash tables for opkg 2 3 Steven M. Ayer, Jamey Hicks 4 5 Copyright (C) 2002 Compaq Computer Corporation 6 7 This program is free software; you can redistribute it and/or 8 modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 2, or (at 10 your option) any later version. 11 12 This program is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 General Public License for more details. 16 */ 17 18 #include <stdio.h> 19 #include <stdlib.h> 20 #include <string.h> 21 #include "hash_table.h" 22 #include "opkg_message.h" 23 #include "libbb/libbb.h" 24 25 static unsigned long djb2_hash(const unsigned char *str) 26 { 27 unsigned long hash = 5381; 28 int c; 29 while ((c = *str++)) 30 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 31 return hash; 32 } 33 34 static int hash_index(hash_table_t * hash, const char *key) 35 { 36 return djb2_hash((const unsigned char *)key) % hash->n_buckets; 37 } 38 39 /* 40 * this is an open table keyed by strings 41 */ 42 void hash_table_init(const char *name, hash_table_t * hash, int len) 43 { 44 if (hash->entries != NULL) { 45 opkg_msg(ERROR, "Internal error: non empty hash table.\n"); 46 return; 47 } 48 49 memset(hash, 0, sizeof(hash_table_t)); 50 51 hash->name = name; 52 hash->n_buckets = len; 53 hash->entries = xcalloc(hash->n_buckets, sizeof(hash_entry_t)); 54 } 55 56 void hash_print_stats(hash_table_t * hash) 57 { 58 printf("hash_table: %s, %d bytes\n" 59 "\tn_buckets=%d, n_elements=%d, n_collisions=%d\n" 60 "\tmax_bucket_len=%d, n_used_buckets=%d, ave_bucket_len=%.2f\n" 61 "\tn_hits=%d, n_misses=%d\n", 62 hash->name, 63 hash->n_buckets * (int)sizeof(hash_entry_t), 64 hash->n_buckets, 65 hash->n_elements, 66 hash->n_collisions, 67 hash->max_bucket_len, 68 hash->n_used_buckets, 69 (hash->n_used_buckets ? 70 ((float)hash->n_elements) / hash->n_used_buckets : 0.0f), 71 hash->n_hits, hash->n_misses); 72 } 73 74 void hash_table_deinit(hash_table_t * hash) 75 { 76 int i; 77 if (!hash) 78 return; 79 80 /* free the reminaing entries */ 81 for (i = 0; i < hash->n_buckets; i++) { 82 hash_entry_t *hash_entry = (hash->entries + i); 83 free(hash_entry->key); 84 /* skip the first entry as this is part of the array */ 85 hash_entry = hash_entry->next; 86 while (hash_entry) { 87 hash_entry_t *old = hash_entry; 88 hash_entry = hash_entry->next; 89 free(old->key); 90 free(old); 91 } 92 } 93 94 free(hash->entries); 95 96 hash->entries = NULL; 97 hash->n_buckets = 0; 98 } 99 100 void *hash_table_get(hash_table_t * hash, const char *key) 101 { 102 int ndx = hash_index(hash, key); 103 hash_entry_t *hash_entry = hash->entries + ndx; 104 while (hash_entry) { 105 if (hash_entry->key) { 106 if (strcmp(key, hash_entry->key) == 0) { 107 hash->n_hits++; 108 return hash_entry->data; 109 } 110 } 111 hash_entry = hash_entry->next; 112 } 113 hash->n_misses++; 114 return NULL; 115 } 116 117 int hash_table_insert(hash_table_t * hash, const char *key, void *value) 118 { 119 int bucket_len = 0; 120 int ndx = hash_index(hash, key); 121 hash_entry_t *hash_entry = hash->entries + ndx; 122 if (hash_entry->key) { 123 if (strcmp(hash_entry->key, key) == 0) { 124 /* alread in table, update the value */ 125 hash_entry->data = value; 126 return 0; 127 } else { 128 /* 129 * if this is a collision, we have to go to the end of the ll, 130 * then add a new entry 131 * before we can hook up the value 132 */ 133 while (hash_entry->next) { 134 hash_entry = hash_entry->next; 135 if (strcmp(hash_entry->key, key) == 0) { 136 hash_entry->data = value; 137 return 0; 138 } 139 bucket_len++; 140 } 141 hash_entry->next = xcalloc(1, sizeof(hash_entry_t)); 142 hash_entry = hash_entry->next; 143 hash_entry->next = NULL; 144 145 hash->n_collisions++; 146 if (++bucket_len > hash->max_bucket_len) 147 hash->max_bucket_len = bucket_len; 148 } 149 } else 150 hash->n_used_buckets++; 151 152 hash->n_elements++; 153 hash_entry->key = xstrdup(key); 154 hash_entry->data = value; 155 156 return 0; 157 } 158 159 int hash_table_remove(hash_table_t * hash, const char *key) 160 { 161 int ndx = hash_index(hash, key); 162 hash_entry_t *hash_entry = hash->entries + ndx; 163 hash_entry_t *next_entry = NULL, *last_entry = NULL; 164 while (hash_entry) { 165 if (hash_entry->key) { 166 if (strcmp(key, hash_entry->key) == 0) { 167 free(hash_entry->key); 168 if (last_entry) { 169 last_entry->next = hash_entry->next; 170 free(hash_entry); 171 } else { 172 next_entry = hash_entry->next; 173 if (next_entry) { 174 memmove(hash_entry, next_entry, 175 sizeof(hash_entry_t)); 176 free(next_entry); 177 } else { 178 memset(hash_entry, 0, 179 sizeof(hash_entry_t)); 180 } 181 } 182 return 1; 183 } 184 } 185 last_entry = hash_entry; 186 hash_entry = hash_entry->next; 187 } 188 return 0; 189 } 190 191 void hash_table_foreach(hash_table_t * hash, 192 void (*f) (const char *key, void *entry, void *data), 193 void *data) 194 { 195 int i; 196 if (!hash || !f) 197 return; 198 199 for (i = 0; i < hash->n_buckets; i++) { 200 hash_entry_t *hash_entry = (hash->entries + i); 201 do { 202 if (hash_entry->key) { 203 f(hash_entry->key, hash_entry->data, data); 204 } 205 } while ((hash_entry = hash_entry->next)); 206 } 207 } 208
This page was automatically generated by LXR 0.3.1. • OpenWrt