root/trunk/fl_hash.c

/*
  +----------------------------------------------------------------------+
  | PHP Version 4                                                        |
  +----------------------------------------------------------------------+
  | Copyright (c) 1997-2003 The PHP Group                                |
  +----------------------------------------------------------------------+
  | This source file is subject to version 2.02 of the PHP license,      |
  | that is bundled with this package in the file LICENSE, and is        |
  | available at through the world-wide-web at                           |
  | http://www.php.net/license/2_02.txt.                                 |
  | If you did not receive a copy of the PHP license and are unable to   |
  | obtain it through the world-wide-web, please send a note to          |
  | license@php.net so we can mail you a copy immediately.               |
  +----------------------------------------------------------------------+
  | Author: Thies C. Arntzen <thies@php.net>                             |
  |         Sterling Hughes <sterling@php.net>                           |
  +----------------------------------------------------------------------+

  $Id: fl_hash.c,v 1.1.1.1 2004/02/17 23:31:44 sterling Exp $
*/

#include <stdlib.h>
#include <string.h>
#include "php_fastxsl.h"
#include "fl_hash.h"

FL_Hash *fl_hash_new(FL_Allocator *mems, FL_HashDtor dtor)
{
        FL_Hash *table;

        table = mems->calloc_func(1, sizeof(FL_Hash));
        table->dtor = dtor;
        table->mems = mems;

        return table;
}

void fl_hash_free(FL_Hash *table) 
{
        FL_Bucket *cur;
        FL_Bucket *next;
        FL_Allocator *mems;
        int     i;

        mems = table->mems;
        
        for (i = 0; i < FL_HASH_SIZE; i++) {
                cur = table->buckets[i];
                while (cur) {
                        next = cur->next;

                        if (table->dtor) table->dtor(cur->data);
                        mems->free_func(cur->key);
                        mems->free_func(cur);

                        cur = next;
                }
        }
        mems->free_func(table);
}

static unsigned int hash_hash(const char *key, int length)
{
        unsigned int hash = 0;

        while (--length)
                hash = hash * 65599 + *key++;

        return hash;
}

void *fl_hash_find(FL_Hash *table, const void *key, int length)
{
        FL_Bucket       *b;
        unsigned int  hash = hash_hash(key, length) % FL_HASH_SIZE;
        for (b = table->buckets[ hash ]; b; b = b->next) {
                if (hash != b->hash) continue;
                if (length != b->length) continue;
                if (memcmp(key, b->key, length)) continue;
                return b->data;
        }

        return NULL;
}

int fl_hash_add(FL_Hash *table, char *key, int length, void *data)
{
        FL_Bucket       *b, *ptr;
        unsigned int  hash;
        
        hash = hash_hash(key, length) % FL_HASH_SIZE;
        /* check hash for dupes */
        ptr = table->buckets[ hash ];
        while(ptr) {
                if(!strcmp(ptr->key, key)) {
                        return 0;
                }
                ptr = ptr->next;
        }

        b = table->mems->malloc_func(sizeof(FL_Bucket));
        b->key = table->mems->malloc_func(length + 1);
        memcpy(b->key, key, length);
        b->key[length] = 0;
        b->length = length;
        b->hash = hash;
        b->data = data;
        b->next = table->buckets[ hash ];

        table->buckets[ hash ] = b;
        table->nElements++;
        return 1;
}

void fl_hash_delete(FL_Hash *table, char *key, int length)
{
        FL_Bucket       *b; 
        FL_Bucket       *prev = NULL;
        unsigned int  hash;

        hash = hash_hash(key, length) % FL_HASH_SIZE;
        for (b = table->buckets[ hash ]; b; b = b->next) {
                if (hash != b->hash || length != b->length || memcmp(key, b->key, length)) {
                        prev = b;
                        continue;
                }

                /* unlink */
                if (prev) {
                        prev->next = b->next;
                } else {
                        table->buckets[hash] = b->next;
                }
                
                if (table->dtor) table->dtor(b->data);
                table->mems->free_func(b->key);
                table->mems->free_func(b);

                break;
        }
}

/*
Local variables:
tab-width: 4
c-basic-offset: 4
End:
vim600: noet sw=4 ts=4 fdm=marker
vim<600: noet sw=4 ts=4
*/