1255e72915d4cbddceb435e13d81601755714e9fSE Android 2255e72915d4cbddceb435e13d81601755714e9fSE Android/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */ 3255e72915d4cbddceb435e13d81601755714e9fSE Android 4255e72915d4cbddceb435e13d81601755714e9fSE Android/* 5255e72915d4cbddceb435e13d81601755714e9fSE Android * Updated : Karl MacMillan <kmacmillan@mentalrootkit.com> 6255e72915d4cbddceb435e13d81601755714e9fSE Android * 7255e72915d4cbddceb435e13d81601755714e9fSE Android * Copyright (C) 2007 Red Hat, Inc. 8255e72915d4cbddceb435e13d81601755714e9fSE Android * 9255e72915d4cbddceb435e13d81601755714e9fSE Android * This library is free software; you can redistribute it and/or 10255e72915d4cbddceb435e13d81601755714e9fSE Android * modify it under the terms of the GNU Lesser General Public 11255e72915d4cbddceb435e13d81601755714e9fSE Android * License as published by the Free Software Foundation; either 12255e72915d4cbddceb435e13d81601755714e9fSE Android * version 2.1 of the License, or (at your option) any later version. 13255e72915d4cbddceb435e13d81601755714e9fSE Android * 14255e72915d4cbddceb435e13d81601755714e9fSE Android * This library is distributed in the hope that it will be useful, 15255e72915d4cbddceb435e13d81601755714e9fSE Android * but WITHOUT ANY WARRANTY; without even the implied warranty of 16255e72915d4cbddceb435e13d81601755714e9fSE Android * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17255e72915d4cbddceb435e13d81601755714e9fSE Android * Lesser General Public License for more details. 18255e72915d4cbddceb435e13d81601755714e9fSE Android * 19255e72915d4cbddceb435e13d81601755714e9fSE Android * You should have received a copy of the GNU Lesser General Public 20255e72915d4cbddceb435e13d81601755714e9fSE Android * License along with this library; if not, write to the Free Software 21255e72915d4cbddceb435e13d81601755714e9fSE Android * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 22255e72915d4cbddceb435e13d81601755714e9fSE Android */ 23255e72915d4cbddceb435e13d81601755714e9fSE Android 24255e72915d4cbddceb435e13d81601755714e9fSE Android 25255e72915d4cbddceb435e13d81601755714e9fSE Android/* FLASK */ 26255e72915d4cbddceb435e13d81601755714e9fSE Android 27255e72915d4cbddceb435e13d81601755714e9fSE Android/* 28255e72915d4cbddceb435e13d81601755714e9fSE Android * Implementation of the hash table type. 29255e72915d4cbddceb435e13d81601755714e9fSE Android */ 30255e72915d4cbddceb435e13d81601755714e9fSE Android 31255e72915d4cbddceb435e13d81601755714e9fSE Android#include <stdlib.h> 32255e72915d4cbddceb435e13d81601755714e9fSE Android#include <string.h> 33255e72915d4cbddceb435e13d81601755714e9fSE Android#include <sepol/policydb/hashtab.h> 34255e72915d4cbddceb435e13d81601755714e9fSE Android 35255e72915d4cbddceb435e13d81601755714e9fSE Androidhashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h, 36255e72915d4cbddceb435e13d81601755714e9fSE Android const hashtab_key_t key), 37255e72915d4cbddceb435e13d81601755714e9fSE Android int (*keycmp) (hashtab_t h, 38255e72915d4cbddceb435e13d81601755714e9fSE Android const hashtab_key_t key1, 39255e72915d4cbddceb435e13d81601755714e9fSE Android const hashtab_key_t key2), 40255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int size) 41255e72915d4cbddceb435e13d81601755714e9fSE Android{ 42255e72915d4cbddceb435e13d81601755714e9fSE Android 43255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_t p; 44255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int i; 45255e72915d4cbddceb435e13d81601755714e9fSE Android 46255e72915d4cbddceb435e13d81601755714e9fSE Android p = (hashtab_t) malloc(sizeof(hashtab_val_t)); 47255e72915d4cbddceb435e13d81601755714e9fSE Android if (p == NULL) 48255e72915d4cbddceb435e13d81601755714e9fSE Android return p; 49255e72915d4cbddceb435e13d81601755714e9fSE Android 50255e72915d4cbddceb435e13d81601755714e9fSE Android memset(p, 0, sizeof(hashtab_val_t)); 51255e72915d4cbddceb435e13d81601755714e9fSE Android p->size = size; 52255e72915d4cbddceb435e13d81601755714e9fSE Android p->nel = 0; 53255e72915d4cbddceb435e13d81601755714e9fSE Android p->hash_value = hash_value; 54255e72915d4cbddceb435e13d81601755714e9fSE Android p->keycmp = keycmp; 55255e72915d4cbddceb435e13d81601755714e9fSE Android p->htable = (hashtab_ptr_t *) malloc(sizeof(hashtab_ptr_t) * size); 56255e72915d4cbddceb435e13d81601755714e9fSE Android if (p->htable == NULL) { 57255e72915d4cbddceb435e13d81601755714e9fSE Android free(p); 58255e72915d4cbddceb435e13d81601755714e9fSE Android return NULL; 59255e72915d4cbddceb435e13d81601755714e9fSE Android } 60255e72915d4cbddceb435e13d81601755714e9fSE Android for (i = 0; i < size; i++) 61255e72915d4cbddceb435e13d81601755714e9fSE Android p->htable[i] = (hashtab_ptr_t) NULL; 62255e72915d4cbddceb435e13d81601755714e9fSE Android 63255e72915d4cbddceb435e13d81601755714e9fSE Android return p; 64255e72915d4cbddceb435e13d81601755714e9fSE Android} 65255e72915d4cbddceb435e13d81601755714e9fSE Android 66255e72915d4cbddceb435e13d81601755714e9fSE Androidint hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum) 67255e72915d4cbddceb435e13d81601755714e9fSE Android{ 68255e72915d4cbddceb435e13d81601755714e9fSE Android int hvalue; 69255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t prev, cur, newnode; 70255e72915d4cbddceb435e13d81601755714e9fSE Android 71255e72915d4cbddceb435e13d81601755714e9fSE Android if (!h) 72255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_ENOMEM; 73255e72915d4cbddceb435e13d81601755714e9fSE Android 74255e72915d4cbddceb435e13d81601755714e9fSE Android hvalue = h->hash_value(h, key); 75255e72915d4cbddceb435e13d81601755714e9fSE Android prev = NULL; 76255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[hvalue]; 77255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur && h->keycmp(h, key, cur->key) > 0) { 78255e72915d4cbddceb435e13d81601755714e9fSE Android prev = cur; 79255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 80255e72915d4cbddceb435e13d81601755714e9fSE Android } 81255e72915d4cbddceb435e13d81601755714e9fSE Android 82255e72915d4cbddceb435e13d81601755714e9fSE Android if (cur && (h->keycmp(h, key, cur->key) == 0)) 83255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_EEXIST; 84255e72915d4cbddceb435e13d81601755714e9fSE Android 85255e72915d4cbddceb435e13d81601755714e9fSE Android newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); 86255e72915d4cbddceb435e13d81601755714e9fSE Android if (newnode == NULL) 87255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_ENOMEM; 88255e72915d4cbddceb435e13d81601755714e9fSE Android memset(newnode, 0, sizeof(struct hashtab_node)); 89255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->key = key; 90255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->datum = datum; 91255e72915d4cbddceb435e13d81601755714e9fSE Android if (prev) { 92255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->next = prev->next; 93255e72915d4cbddceb435e13d81601755714e9fSE Android prev->next = newnode; 94255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 95255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->next = h->htable[hvalue]; 96255e72915d4cbddceb435e13d81601755714e9fSE Android h->htable[hvalue] = newnode; 97255e72915d4cbddceb435e13d81601755714e9fSE Android } 98255e72915d4cbddceb435e13d81601755714e9fSE Android 99255e72915d4cbddceb435e13d81601755714e9fSE Android h->nel++; 100255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_OK; 101255e72915d4cbddceb435e13d81601755714e9fSE Android} 102255e72915d4cbddceb435e13d81601755714e9fSE Android 103255e72915d4cbddceb435e13d81601755714e9fSE Androidint hashtab_remove(hashtab_t h, hashtab_key_t key, 104255e72915d4cbddceb435e13d81601755714e9fSE Android void (*destroy) (hashtab_key_t k, 105255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, void *args), void *args) 106255e72915d4cbddceb435e13d81601755714e9fSE Android{ 107255e72915d4cbddceb435e13d81601755714e9fSE Android int hvalue; 108255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t cur, last; 109255e72915d4cbddceb435e13d81601755714e9fSE Android 110255e72915d4cbddceb435e13d81601755714e9fSE Android if (!h) 111255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_ENOENT; 112255e72915d4cbddceb435e13d81601755714e9fSE Android 113255e72915d4cbddceb435e13d81601755714e9fSE Android hvalue = h->hash_value(h, key); 114255e72915d4cbddceb435e13d81601755714e9fSE Android last = NULL; 115255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[hvalue]; 116255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { 117255e72915d4cbddceb435e13d81601755714e9fSE Android last = cur; 118255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 119255e72915d4cbddceb435e13d81601755714e9fSE Android } 120255e72915d4cbddceb435e13d81601755714e9fSE Android 121255e72915d4cbddceb435e13d81601755714e9fSE Android if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) 122255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_ENOENT; 123255e72915d4cbddceb435e13d81601755714e9fSE Android 124255e72915d4cbddceb435e13d81601755714e9fSE Android if (last == NULL) 125255e72915d4cbddceb435e13d81601755714e9fSE Android h->htable[hvalue] = cur->next; 126255e72915d4cbddceb435e13d81601755714e9fSE Android else 127255e72915d4cbddceb435e13d81601755714e9fSE Android last->next = cur->next; 128255e72915d4cbddceb435e13d81601755714e9fSE Android 129255e72915d4cbddceb435e13d81601755714e9fSE Android if (destroy) 130255e72915d4cbddceb435e13d81601755714e9fSE Android destroy(cur->key, cur->datum, args); 131255e72915d4cbddceb435e13d81601755714e9fSE Android free(cur); 132255e72915d4cbddceb435e13d81601755714e9fSE Android h->nel--; 133255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_OK; 134255e72915d4cbddceb435e13d81601755714e9fSE Android} 135255e72915d4cbddceb435e13d81601755714e9fSE Android 136255e72915d4cbddceb435e13d81601755714e9fSE Androidint hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum, 137255e72915d4cbddceb435e13d81601755714e9fSE Android void (*destroy) (hashtab_key_t k, 138255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, void *args), void *args) 139255e72915d4cbddceb435e13d81601755714e9fSE Android{ 140255e72915d4cbddceb435e13d81601755714e9fSE Android int hvalue; 141255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t prev, cur, newnode; 142255e72915d4cbddceb435e13d81601755714e9fSE Android 143255e72915d4cbddceb435e13d81601755714e9fSE Android if (!h) 144255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_ENOMEM; 145255e72915d4cbddceb435e13d81601755714e9fSE Android 146255e72915d4cbddceb435e13d81601755714e9fSE Android hvalue = h->hash_value(h, key); 147255e72915d4cbddceb435e13d81601755714e9fSE Android prev = NULL; 148255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[hvalue]; 149255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { 150255e72915d4cbddceb435e13d81601755714e9fSE Android prev = cur; 151255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 152255e72915d4cbddceb435e13d81601755714e9fSE Android } 153255e72915d4cbddceb435e13d81601755714e9fSE Android 154255e72915d4cbddceb435e13d81601755714e9fSE Android if (cur && (h->keycmp(h, key, cur->key) == 0)) { 155255e72915d4cbddceb435e13d81601755714e9fSE Android if (destroy) 156255e72915d4cbddceb435e13d81601755714e9fSE Android destroy(cur->key, cur->datum, args); 157255e72915d4cbddceb435e13d81601755714e9fSE Android cur->key = key; 158255e72915d4cbddceb435e13d81601755714e9fSE Android cur->datum = datum; 159255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 160255e72915d4cbddceb435e13d81601755714e9fSE Android newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); 161255e72915d4cbddceb435e13d81601755714e9fSE Android if (newnode == NULL) 162255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_ENOMEM; 163255e72915d4cbddceb435e13d81601755714e9fSE Android memset(newnode, 0, sizeof(struct hashtab_node)); 164255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->key = key; 165255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->datum = datum; 166255e72915d4cbddceb435e13d81601755714e9fSE Android if (prev) { 167255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->next = prev->next; 168255e72915d4cbddceb435e13d81601755714e9fSE Android prev->next = newnode; 169255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 170255e72915d4cbddceb435e13d81601755714e9fSE Android newnode->next = h->htable[hvalue]; 171255e72915d4cbddceb435e13d81601755714e9fSE Android h->htable[hvalue] = newnode; 172255e72915d4cbddceb435e13d81601755714e9fSE Android } 173255e72915d4cbddceb435e13d81601755714e9fSE Android } 174255e72915d4cbddceb435e13d81601755714e9fSE Android 175255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_OK; 176255e72915d4cbddceb435e13d81601755714e9fSE Android} 177255e72915d4cbddceb435e13d81601755714e9fSE Android 178255e72915d4cbddceb435e13d81601755714e9fSE Androidhashtab_datum_t hashtab_search(hashtab_t h, const hashtab_key_t key) 179255e72915d4cbddceb435e13d81601755714e9fSE Android{ 180255e72915d4cbddceb435e13d81601755714e9fSE Android 181255e72915d4cbddceb435e13d81601755714e9fSE Android int hvalue; 182255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t cur; 183255e72915d4cbddceb435e13d81601755714e9fSE Android 184255e72915d4cbddceb435e13d81601755714e9fSE Android if (!h) 185255e72915d4cbddceb435e13d81601755714e9fSE Android return NULL; 186255e72915d4cbddceb435e13d81601755714e9fSE Android 187255e72915d4cbddceb435e13d81601755714e9fSE Android hvalue = h->hash_value(h, key); 188255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[hvalue]; 189255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur != NULL && h->keycmp(h, key, cur->key) > 0) 190255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 191255e72915d4cbddceb435e13d81601755714e9fSE Android 192255e72915d4cbddceb435e13d81601755714e9fSE Android if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) 193255e72915d4cbddceb435e13d81601755714e9fSE Android return NULL; 194255e72915d4cbddceb435e13d81601755714e9fSE Android 195255e72915d4cbddceb435e13d81601755714e9fSE Android return cur->datum; 196255e72915d4cbddceb435e13d81601755714e9fSE Android} 197255e72915d4cbddceb435e13d81601755714e9fSE Android 198255e72915d4cbddceb435e13d81601755714e9fSE Androidvoid hashtab_destroy(hashtab_t h) 199255e72915d4cbddceb435e13d81601755714e9fSE Android{ 200255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int i; 201255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t cur, temp; 202255e72915d4cbddceb435e13d81601755714e9fSE Android 203255e72915d4cbddceb435e13d81601755714e9fSE Android if (!h) 204255e72915d4cbddceb435e13d81601755714e9fSE Android return; 205255e72915d4cbddceb435e13d81601755714e9fSE Android 206255e72915d4cbddceb435e13d81601755714e9fSE Android for (i = 0; i < h->size; i++) { 207255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[i]; 208255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur != NULL) { 209255e72915d4cbddceb435e13d81601755714e9fSE Android temp = cur; 210255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 211255e72915d4cbddceb435e13d81601755714e9fSE Android free(temp); 212255e72915d4cbddceb435e13d81601755714e9fSE Android } 213255e72915d4cbddceb435e13d81601755714e9fSE Android h->htable[i] = NULL; 214255e72915d4cbddceb435e13d81601755714e9fSE Android } 215255e72915d4cbddceb435e13d81601755714e9fSE Android 216255e72915d4cbddceb435e13d81601755714e9fSE Android free(h->htable); 217255e72915d4cbddceb435e13d81601755714e9fSE Android h->htable = NULL; 218255e72915d4cbddceb435e13d81601755714e9fSE Android 219255e72915d4cbddceb435e13d81601755714e9fSE Android free(h); 220255e72915d4cbddceb435e13d81601755714e9fSE Android} 221255e72915d4cbddceb435e13d81601755714e9fSE Android 222255e72915d4cbddceb435e13d81601755714e9fSE Androidint hashtab_map(hashtab_t h, 223255e72915d4cbddceb435e13d81601755714e9fSE Android int (*apply) (hashtab_key_t k, 224255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, void *args), void *args) 225255e72915d4cbddceb435e13d81601755714e9fSE Android{ 226255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int i, ret; 227255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t cur; 228255e72915d4cbddceb435e13d81601755714e9fSE Android 229255e72915d4cbddceb435e13d81601755714e9fSE Android if (!h) 230255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_OK; 231255e72915d4cbddceb435e13d81601755714e9fSE Android 232255e72915d4cbddceb435e13d81601755714e9fSE Android for (i = 0; i < h->size; i++) { 233255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[i]; 234255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur != NULL) { 235255e72915d4cbddceb435e13d81601755714e9fSE Android ret = apply(cur->key, cur->datum, args); 236255e72915d4cbddceb435e13d81601755714e9fSE Android if (ret) 237255e72915d4cbddceb435e13d81601755714e9fSE Android return ret; 238255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 239255e72915d4cbddceb435e13d81601755714e9fSE Android } 240255e72915d4cbddceb435e13d81601755714e9fSE Android } 241255e72915d4cbddceb435e13d81601755714e9fSE Android return SEPOL_OK; 242255e72915d4cbddceb435e13d81601755714e9fSE Android} 243255e72915d4cbddceb435e13d81601755714e9fSE Android 244255e72915d4cbddceb435e13d81601755714e9fSE Androidvoid hashtab_map_remove_on_error(hashtab_t h, 245255e72915d4cbddceb435e13d81601755714e9fSE Android int (*apply) (hashtab_key_t k, 246255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, 247255e72915d4cbddceb435e13d81601755714e9fSE Android void *args), 248255e72915d4cbddceb435e13d81601755714e9fSE Android void (*destroy) (hashtab_key_t k, 249255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, 250255e72915d4cbddceb435e13d81601755714e9fSE Android void *args), void *args) 251255e72915d4cbddceb435e13d81601755714e9fSE Android{ 252255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int i; 253255e72915d4cbddceb435e13d81601755714e9fSE Android int ret; 254255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t last, cur, temp; 255255e72915d4cbddceb435e13d81601755714e9fSE Android 256255e72915d4cbddceb435e13d81601755714e9fSE Android if (!h) 257255e72915d4cbddceb435e13d81601755714e9fSE Android return; 258255e72915d4cbddceb435e13d81601755714e9fSE Android 259255e72915d4cbddceb435e13d81601755714e9fSE Android for (i = 0; i < h->size; i++) { 260255e72915d4cbddceb435e13d81601755714e9fSE Android last = NULL; 261255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[i]; 262255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur != NULL) { 263255e72915d4cbddceb435e13d81601755714e9fSE Android ret = apply(cur->key, cur->datum, args); 264255e72915d4cbddceb435e13d81601755714e9fSE Android if (ret) { 265255e72915d4cbddceb435e13d81601755714e9fSE Android if (last) { 266255e72915d4cbddceb435e13d81601755714e9fSE Android last->next = cur->next; 267255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 268255e72915d4cbddceb435e13d81601755714e9fSE Android h->htable[i] = cur->next; 269255e72915d4cbddceb435e13d81601755714e9fSE Android } 270255e72915d4cbddceb435e13d81601755714e9fSE Android 271255e72915d4cbddceb435e13d81601755714e9fSE Android temp = cur; 272255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 273255e72915d4cbddceb435e13d81601755714e9fSE Android if (destroy) 274255e72915d4cbddceb435e13d81601755714e9fSE Android destroy(temp->key, temp->datum, args); 275255e72915d4cbddceb435e13d81601755714e9fSE Android free(temp); 276255e72915d4cbddceb435e13d81601755714e9fSE Android h->nel--; 277255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 278255e72915d4cbddceb435e13d81601755714e9fSE Android last = cur; 279255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 280255e72915d4cbddceb435e13d81601755714e9fSE Android } 281255e72915d4cbddceb435e13d81601755714e9fSE Android } 282255e72915d4cbddceb435e13d81601755714e9fSE Android } 283255e72915d4cbddceb435e13d81601755714e9fSE Android 284255e72915d4cbddceb435e13d81601755714e9fSE Android return; 285255e72915d4cbddceb435e13d81601755714e9fSE Android} 286255e72915d4cbddceb435e13d81601755714e9fSE Android 287255e72915d4cbddceb435e13d81601755714e9fSE Androidvoid hashtab_hash_eval(hashtab_t h, char *tag) 288255e72915d4cbddceb435e13d81601755714e9fSE Android{ 289255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int i; 290255e72915d4cbddceb435e13d81601755714e9fSE Android int chain_len, slots_used, max_chain_len; 291255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t cur; 292255e72915d4cbddceb435e13d81601755714e9fSE Android 293255e72915d4cbddceb435e13d81601755714e9fSE Android slots_used = 0; 294255e72915d4cbddceb435e13d81601755714e9fSE Android max_chain_len = 0; 295255e72915d4cbddceb435e13d81601755714e9fSE Android for (i = 0; i < h->size; i++) { 296255e72915d4cbddceb435e13d81601755714e9fSE Android cur = h->htable[i]; 297255e72915d4cbddceb435e13d81601755714e9fSE Android if (cur) { 298255e72915d4cbddceb435e13d81601755714e9fSE Android slots_used++; 299255e72915d4cbddceb435e13d81601755714e9fSE Android chain_len = 0; 300255e72915d4cbddceb435e13d81601755714e9fSE Android while (cur) { 301255e72915d4cbddceb435e13d81601755714e9fSE Android chain_len++; 302255e72915d4cbddceb435e13d81601755714e9fSE Android cur = cur->next; 303255e72915d4cbddceb435e13d81601755714e9fSE Android } 304255e72915d4cbddceb435e13d81601755714e9fSE Android 305255e72915d4cbddceb435e13d81601755714e9fSE Android if (chain_len > max_chain_len) 306255e72915d4cbddceb435e13d81601755714e9fSE Android max_chain_len = chain_len; 307255e72915d4cbddceb435e13d81601755714e9fSE Android } 308255e72915d4cbddceb435e13d81601755714e9fSE Android } 309255e72915d4cbddceb435e13d81601755714e9fSE Android 310255e72915d4cbddceb435e13d81601755714e9fSE Android printf 311255e72915d4cbddceb435e13d81601755714e9fSE Android ("%s: %d entries and %d/%d buckets used, longest chain length %d\n", 312255e72915d4cbddceb435e13d81601755714e9fSE Android tag, h->nel, slots_used, h->size, max_chain_len); 313255e72915d4cbddceb435e13d81601755714e9fSE Android} 314