URL
https://opencores.org/ocsvn/igor/igor/trunk
Subversion Repositories igor
[/] [igor/] [trunk/] [simulator/] [hash.c] - Rev 4
Compare with Previous | Blame | View Log
/* * Copyright (c) 2007 Eirik A. Nygaard <eirikald@pvv.ntnu.no> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to * deal in the Software without restriction, including without limitation the * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or * sell copies of the Software, and to permit persons to whom the Software is * furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included in * all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS * IN THE SOFTWARE. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "hash.h" #include "alloc.h" static void hash_grow(hash_t *h); hash_t * _hash_create(hash_cmp cmp, hash_hash hash, unsigned long size, float threshold) { hash_t *h; h = scalloc(sizeof(*h), 1); h->h_cmp = cmp; h->h_hash = hash; h->h_size = size; h->h_used = 0; h->h_bucket = scalloc(sizeof(*h->h_bucket), size); memset(h->h_bucket, '\0', sizeof(*h->h_bucket) * h->h_size); h->h_threshold = threshold; return h; } int _hash_insert_do(hash_t *h, void *key, void *value, hash realhash) { hash hash, i; hash = realhash % h->h_size; for (i = hash; h->h_bucket[i].key != NULL && !(h->h_cmp)(key, h->h_bucket[i].key); i = (i + 1) % h->h_size) ; if (h->h_bucket[i].key != NULL) free(h->h_bucket[i].key); h->h_bucket[i].key = key; h->h_bucket[i].value = value; h->h_bucket[i].hash = realhash; h->h_used++; return 1; } static void hash_grow(hash_t *h) { struct hash_bucket *old; hash oldsize, i; //printf("Growing, %lu -> %lu\n", h->h_size, h->h_size*2); oldsize = h->h_size; h->h_size *= 2; old = h->h_bucket; h->h_bucket = scalloc(sizeof(*h->h_bucket), h->h_size); memset(h->h_bucket, '\0', sizeof(*h->h_bucket) * h->h_size); h->h_used = 0; for (i = 0; i < oldsize; i++) { if (old[i].key != NULL) _hash_insert_do(h, old[i].key, old[i].value, old[i].hash); } } int _hash_insert(hash_t *h, void *key, void *value) { hash realhash; if (((float)h->h_used / (float)h->h_size) > h->h_threshold) hash_grow(h); realhash = (h->h_hash)(key); return _hash_insert_do(h, key, value, realhash); } int _hash_remove(hash_t *h, void *key, int freevalue) { hash hash, i, itr; hash = (h->h_hash)(key) % h->h_size; for (i = hash, itr = 0; itr < h->h_size && !(h->h_cmp)(h->h_bucket[i].key, key); i = (i + 1) % h->h_size, itr++) ; if (itr == h->h_size) return 0; if (freevalue) free(h->h_bucket[i].value); free(h->h_bucket[i].key); h->h_bucket[i].key = NULL; return 1; } void * _hash_lookup(hash_t *h, const void *key) { hash hash, i, itr; hash = (h->h_hash)(key) % h->h_size; for (i = hash, itr = 0; itr < h->h_size && h->h_bucket[i].key != NULL && !(h->h_cmp)(h->h_bucket[i].key, key); i = (i + 1) % h->h_size, itr++) ; if (itr == h->h_size || h->h_bucket[i].key == NULL) return NULL; return h->h_bucket[i].value; } void hash_destroy(hash_t *h, int freevalue) { hash i; for(i = 0; i < h->h_size; i++) { if (h->h_bucket[i].key == NULL) continue; if (freevalue) free(h->h_bucket[i].value); free(h->h_bucket[i].key); } free(h->h_bucket); free(h); }