diff options
Diffstat (limited to 'dvi/mdvi-lib/hash.c')
| -rw-r--r-- | dvi/mdvi-lib/hash.c | 223 |
1 files changed, 0 insertions, 223 deletions
diff --git a/dvi/mdvi-lib/hash.c b/dvi/mdvi-lib/hash.c deleted file mode 100644 index d030650..0000000 --- a/dvi/mdvi-lib/hash.c +++ /dev/null @@ -1,223 +0,0 @@ -/* - * Copyright (C) 2000, Matias Atria - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include "mdvi.h" - -/* simple hash tables for MDVI */ - - -struct _DviHashBucket { - DviHashBucket *next; - DviHashKey key; - Ulong hvalue; - void *data; -}; - -static Ulong hash_string(DviHashKey key) -{ - Uchar *p; - Ulong h, g; - - for(h = 0, p = (Uchar *)key; *p; p++) { - h = (h << 4UL) + *p; - if((g = h & 0xf0000000L) != 0) { - h ^= (g >> 24UL); - h ^= g; - } - } - - return h; -} - -static int hash_compare(DviHashKey k1, DviHashKey k2) -{ - return strcmp((char *)k1, (char *)k2); -} - -void mdvi_hash_init(DviHashTable *hash) -{ - hash->buckets = NULL; - hash->nbucks = 0; - hash->nkeys = 0; - hash->hash_func = NULL; - hash->hash_comp = NULL; - hash->hash_free = NULL; -} - -void mdvi_hash_create(DviHashTable *hash, int size) -{ - int i; - - hash->nbucks = size; - hash->buckets = xnalloc(DviHashBucket *, size); - for(i = 0; i < size; i++) - hash->buckets[i] = NULL; - hash->hash_func = hash_string; - hash->hash_comp = hash_compare; - hash->hash_free = NULL; - hash->nkeys = 0; -} - -static DviHashBucket *hash_find(DviHashTable *hash, DviHashKey key) -{ - Ulong hval; - DviHashBucket *buck; - - hval = (hash->hash_func(key) % hash->nbucks); - - for(buck = hash->buckets[hval]; buck; buck = buck->next) - if(hash->hash_comp(buck->key, key) == 0) - break; - return buck; -} - -/* Neither keys nor data are duplicated */ -int mdvi_hash_add(DviHashTable *hash, DviHashKey key, void *data, int rep) -{ - DviHashBucket *buck = NULL; - Ulong hval; - - if(rep != MDVI_HASH_UNCHECKED) { - buck = hash_find(hash, key); - if(buck != NULL) { - if(buck->data == data) - return 0; - if(rep == MDVI_HASH_UNIQUE) - return -1; - if(hash->hash_free != NULL) - hash->hash_free(buck->key, buck->data); - } - } - if(buck == NULL) { - buck = xalloc(DviHashBucket); - buck->hvalue = hash->hash_func(key); - hval = (buck->hvalue % hash->nbucks); - buck->next = hash->buckets[hval]; - hash->buckets[hval] = buck; - hash->nkeys++; - } - - /* save key and data */ - buck->key = key; - buck->data = data; - - return 0; -} - -void *mdvi_hash_lookup(DviHashTable *hash, DviHashKey key) -{ - DviHashBucket *buck = hash_find(hash, key); - - return buck ? buck->data : NULL; -} - -static DviHashBucket *hash_remove(DviHashTable *hash, DviHashKey key) -{ - DviHashBucket *buck, *last; - Ulong hval; - - hval = hash->hash_func(key); - hval %= hash->nbucks; - - for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) { - if(hash->hash_comp(buck->key, key) == 0) - break; - last = buck; - } - if(buck == NULL) - return NULL; - if(last) - last->next = buck->next; - else - hash->buckets[hval] = buck->next; - hash->nkeys--; - return buck; -} - -void *mdvi_hash_remove(DviHashTable *hash, DviHashKey key) -{ - DviHashBucket *buck = hash_remove(hash, key); - void *data = NULL; - - if(buck) { - data = buck->data; - mdvi_free(buck); - } - return data; -} - -void *mdvi_hash_remove_ptr(DviHashTable *hash, DviHashKey key) -{ - DviHashBucket *buck, *last; - Ulong hval; - void *ptr; - - hval = hash->hash_func(key); - hval %= hash->nbucks; - - for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) { - if(buck->key == key) - break; - last = buck; - } - if(buck == NULL) - return NULL; - if(last) - last->next = buck->next; - else - hash->buckets[hval] = buck->next; - hash->nkeys--; - /* destroy the bucket */ - ptr = buck->data; - mdvi_free(buck); - return ptr; -} - -int mdvi_hash_destroy_key(DviHashTable *hash, DviHashKey key) -{ - DviHashBucket *buck = hash_remove(hash, key); - - if(buck == NULL) - return -1; - if(hash->hash_free) - hash->hash_free(buck->key, buck->data); - mdvi_free(buck); - return 0; -} - -void mdvi_hash_reset(DviHashTable *hash, int reuse) -{ - int i; - DviHashBucket *buck; - - /* remove all keys in the hash table */ - for(i = 0; i < hash->nbucks; i++) { - for(; (buck = hash->buckets[i]); ) { - hash->buckets[i] = buck->next; - if(hash->hash_free) - hash->hash_free(buck->key, buck->data); - mdvi_free(buck); - } - } - hash->nkeys = 0; - if(!reuse && hash->buckets) { - mdvi_free(hash->buckets); - hash->buckets = NULL; - hash->nbucks = 0; - } /* otherwise, it is left empty, ready to be reused */ -} |