hash.c File Reference

#include <config.h>
#include "mdvi.h"

Include dependency graph for hash.c:

Go to the source code of this file.

Data Structures
struct	_DviHashBucket

Functions
static Ulong	hash_string (DviHashKey key)
static int	hash_compare (DviHashKey k1, DviHashKey k2)
void	mdvi_hash_init (DviHashTable *hash)
void	mdvi_hash_create (DviHashTable *hash, int size)
static DviHashBucket *	hash_find (DviHashTable *hash, DviHashKey key)
int	mdvi_hash_add (DviHashTable *hash, DviHashKey key, void *data, int rep)
void *	mdvi_hash_lookup (DviHashTable *hash, DviHashKey key)
static DviHashBucket *	hash_remove (DviHashTable *hash, DviHashKey key)
void *	mdvi_hash_remove (DviHashTable *hash, DviHashKey key)
void *	mdvi_hash_remove_ptr (DviHashTable *hash, DviHashKey key)
int	mdvi_hash_destroy_key (DviHashTable *hash, DviHashKey key)
void	mdvi_hash_reset (DviHashTable *hash, int reuse)

Function Documentation

static int hash_compare ( DviHashKey  k1, DviHashKey  k2  )

static

Definition at line 48 of file hash.c.

{
    return strcmp((char *)k1, (char *)k2);
}

Here is the caller graph for this function:

static DviHashBucket* hash_find ( DviHashTable *  hash, DviHashKey  key  )

static

Definition at line 77 of file hash.c.

{
    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;
}

Here is the caller graph for this function:

static DviHashBucket* hash_remove ( DviHashTable *  hash, DviHashKey  key  )

static

Definition at line 130 of file hash.c.

{
    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;
}

Here is the caller graph for this function:

static Ulong hash_string ( DviHashKey  key)

static

Definition at line 32 of file hash.c.

{
    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;
}

Here is the caller graph for this function:

int mdvi_hash_add	(	DviHashTable *	hash,
		DviHashKey	key,
		void *	data,
		int	rep
	)

Definition at line 91 of file hash.c.

{
    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;
}

Here is the caller graph for this function:

void mdvi_hash_create	(	DviHashTable *	hash,
		int	size
	)

Definition at line 63 of file hash.c.

{
    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;
}

Here is the caller graph for this function:

int mdvi_hash_destroy_key	(	DviHashTable *	hash,
		DviHashKey	key
	)

Definition at line 192 of file hash.c.

{
    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_init

(

DviHashTable *

hash)

Definition at line 53 of file hash.c.

{
    hash->buckets = NULL;
    hash->nbucks  = 0;
    hash->nkeys   = 0;
    hash->hash_func = NULL;
    hash->hash_comp = NULL;
    hash->hash_free = NULL;
}

Here is the caller graph for this function:

void* mdvi_hash_lookup	(	DviHashTable *	hash,
		DviHashKey	key
	)

Definition at line 123 of file hash.c.

{
    DviHashBucket *buck = hash_find(hash, key);

    return buck ? buck->data : NULL;
}

Here is the caller graph for this function:

void* mdvi_hash_remove	(	DviHashTable *	hash,
		DviHashKey	key
	)

Definition at line 153 of file hash.c.

{
    DviHashBucket *buck = hash_remove(hash, key);
    void    *data = NULL;

    if(buck) {
        data = buck->data;
        mdvi_free(buck);
    }
    return data;
}

Here is the caller graph for this function:

void* mdvi_hash_remove_ptr	(	DviHashTable *	hash,
		DviHashKey	key
	)

Definition at line 165 of file hash.c.

{
    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;
}

Here is the caller graph for this function:

void mdvi_hash_reset	(	DviHashTable *	hash,
		int	reuse
	)

Definition at line 204 of file hash.c.

{
    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 */
}

Here is the caller graph for this function: