diff options
Diffstat (limited to 'backend/dvi/mdvi-lib/hash.c')
| -rw-r--r-- | backend/dvi/mdvi-lib/hash.c | 224 |
1 files changed, 224 insertions, 0 deletions
diff --git a/backend/dvi/mdvi-lib/hash.c b/backend/dvi/mdvi-lib/hash.c new file mode 100644 index 00000000..d359e3c8 --- /dev/null +++ b/backend/dvi/mdvi-lib/hash.c @@ -0,0 +1,224 @@ +/* + * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include <config.h> +#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 */ +} |