rpmdb/rpmhash.c

Go to the documentation of this file.

#include "system.h"
#include <rpmlib.h>
#include "rpmhash.h"
#include "debug.h"

typedef /*@owned@*/ const void * voidptr;

typedef struct hashBucket_s * hashBucket;

struct hashBucket_s {
    voidptr key;                        
/*@owned@*/ voidptr * data;             
    int dataCount;                      
/*@dependent@*/hashBucket next;         
};

struct hashTable_s {
    int numBuckets;                     
    int keySize;                        
    int freeData;       
    hashBucket * buckets;               
    hashFunctionType fn;                
    hashEqualityType eq;                
};

static /*@shared@*/ /*@null@*/
hashBucket findEntry(hashTable ht, const void * key)
        /*@*/
{
    unsigned int hash;
    hashBucket b;

    /*@-modunconnomods@*/
    hash = ht->fn(key) % ht->numBuckets;
/*@-boundsread@*/
    b = ht->buckets[hash];
/*@=boundsread@*/

    while (b && b->key && ht->eq(b->key, key))
        b = b->next;
    /*@=modunconnomods@*/

    return b;
}

int hashEqualityString(const void * key1, const void * key2)
{
    const char *k1 = (const char *)key1;
    const char *k2 = (const char *)key2;
    return strcmp(k1, k2);
}

unsigned int hashFunctionString(const void * string)
{
    char xorValue = 0;
    char sum = 0;
    short len;
    int i;
    const char * chp = string;

    len = strlen(string);
/*@-boundsread@*/
    for (i = 0; i < len; i++, chp++) {
        xorValue ^= *chp;
        sum += *chp;
    }
/*@=boundsread@*/

    return ((((unsigned)len) << 16) + (((unsigned)sum) << 8) + xorValue);
}

hashTable htCreate(int numBuckets, int keySize, int freeData,
                hashFunctionType fn, hashEqualityType eq)
{
    hashTable ht;

    ht = xmalloc(sizeof(*ht));
    ht->numBuckets = numBuckets;
    ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
    ht->keySize = keySize;
    ht->freeData = freeData;
    /*@-assignexpose@*/
    ht->fn = fn;
    ht->eq = eq;
    /*@=assignexpose@*/

    return ht;
}

/*@-boundswrite@*/
void htAddEntry(hashTable ht, const void * key, const void * data)
{
    unsigned int hash;
    hashBucket b;

    hash = ht->fn(key) % ht->numBuckets;
    b = ht->buckets[hash];

    while (b && b->key && ht->eq(b->key, key))
        b = b->next;

    /*@-branchstate@*/
    if (b == NULL) {
        b = xmalloc(sizeof(*b));
        if (ht->keySize) {
            char *k = xmalloc(ht->keySize);
            memcpy(k, key, ht->keySize);
            b->key = k;
        } else {
            b->key = key;
        }
        b->dataCount = 0;
        b->next = ht->buckets[hash];
        b->data = NULL;
        ht->buckets[hash] = b;
    }
    /*@=branchstate@*/

    b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
    b->data[b->dataCount++] = data;
}
/*@=boundswrite@*/

hashTable htFree(hashTable ht)
{
    hashBucket b, n;
    int i;

    for (i = 0; i < ht->numBuckets; i++) {
/*@-boundsread@*/
        b = ht->buckets[i];
/*@=boundsread@*/
        if (b == NULL)
            continue;
/*@-boundswrite@*/
        ht->buckets[i] = NULL;
/*@=boundswrite@*/
        if (ht->keySize > 0)
            b->key = _free(b->key);
        do {
            n = b->next;
            /*@-branchstate@*/
            if (b->data) {
/*@-boundswrite@*/
                if (ht->freeData)
                    *b->data = _free(*b->data);
/*@=boundswrite@*/
                b->data = _free(b->data);
            }
            /*@=branchstate@*/
            b = _free(b);
        } while ((b = n) != NULL);
    }

    ht->buckets = _free(ht->buckets);
    ht = _free(ht);
    return NULL;
}

int htHasEntry(hashTable ht, const void * key)
{
    hashBucket b;

    if (!(b = findEntry(ht, key))) return 0; else return 1;
}

int htGetEntry(hashTable ht, const void * key, const void *** data,
               int * dataCount, const void ** tableKey)
{
    hashBucket b;

    if ((b = findEntry(ht, key)) == NULL)
        return 1;

/*@-boundswrite@*/
    if (data)
        *data = (const void **) b->data;
    if (dataCount)
        *dataCount = b->dataCount;
    if (tableKey)
        *tableKey = b->key;
/*@=boundswrite@*/

    return 0;
}

---