File: hash.c

package info (click to toggle)
c-icap 1:0.5.3-2
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 3,600 kB
  • sloc: ansic: 27,220; sh: 4,415; makefile: 242; perl: 95; awk: 10
file content (132 lines) | stat: -rw-r--r-- 4,259 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*
 *  Copyright (C) 2004-2008 Christos Tsantilas
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 *  MA  02110-1301  USA.
 */

#include "common.h"
#include "hash.h"
#include "debug.h"
#include <assert.h>

unsigned int ci_hash_compute(unsigned long hash_max_value, const void *key, int len)
{
    unsigned long hash = 5381;
    const unsigned char *s = key;
    int i;

    if (len) {
        for (i = 0; i<len; i++, s++)
            hash = ((hash << 5) + hash) + *s;
    } else
        while (*s) {
            hash = ((hash << 5) + hash) + *s; /* hash * 33 + current char */
            s++;
        }

    if (hash == 0) hash++;
    hash = hash & hash_max_value; /*Keep only the bits we need*/
    return hash;
}

struct ci_hash_table * ci_hash_build(unsigned int hash_size,
                                     const ci_type_ops_t *ops, ci_mem_allocator_t *allocator)
{
    struct ci_hash_table *htable;
    unsigned int new_hash_size;
    htable = allocator->alloc(allocator, sizeof(struct ci_hash_table));

    if (!htable) {
        /*a debug message ....*/
        return NULL;
    }
    new_hash_size = 63;
    if (hash_size > 63) {
        while (new_hash_size<hash_size && new_hash_size < 0xFFFFFF) {
            new_hash_size++;
            new_hash_size = (new_hash_size << 1) -1;
        }
    }
    ci_debug_printf(5, "Build hash table of size: %u, memallocated:%u\n", (unsigned int)new_hash_size, (unsigned int)((new_hash_size+1)*sizeof(struct ci_hash_entry *)));
    htable->hash_table=allocator->alloc(allocator, (new_hash_size+1)*sizeof(struct ci_hash_entry *));
    if (!htable->hash_table) {
        allocator->free(allocator, htable);
        return NULL;
    }
    memset(htable->hash_table, 0, (new_hash_size + 1)*sizeof(struct ci_hash_entry *));

    htable->hash_table_size = new_hash_size;
    htable->ops = ops;
    htable->allocator = allocator;
    return htable;
}

void ci_hash_destroy(struct ci_hash_table *htable)
{
    int i;
    struct ci_hash_entry *e;
    ci_mem_allocator_t *allocator = htable->allocator;
    for (i=0; i<= htable->hash_table_size; i++) {
        while (htable->hash_table[i]) {
            e = htable->hash_table[i];
            htable->hash_table[i] = htable->hash_table[i]->hnext;
            allocator->free(allocator, e);
        }
    }
    htable->allocator->free(allocator,htable->hash_table );
    allocator->free(allocator, htable);
}

const void * ci_hash_search(struct ci_hash_table *htable,const void *key)
{
    struct ci_hash_entry *e;
    unsigned int hash=ci_hash_compute(htable->hash_table_size, key, htable->ops->size(key));

    assert(hash <= htable->hash_table_size); /*is it possible?*/

    e = htable->hash_table[hash];
    while (e != NULL) {
        if (htable->ops->compare(e->key, key) == 0)
            return e->val;
        e = e->hnext;
    }
    return NULL;
}

void * ci_hash_add(struct ci_hash_table *htable, const void *key, const void *val)
{
    struct ci_hash_entry *e;
    unsigned int hash = ci_hash_compute(htable->hash_table_size, key, htable->ops->size(key));
    assert(hash <= htable->hash_table_size);

    e = htable->allocator->alloc(htable->allocator, sizeof(struct ci_hash_entry));

    if (!e)
        return NULL;

    e->hnext = NULL;
    e->key = key;
    e->val = val;
    e->hash = hash;

//    if(htable->hash_table[hash])
//  ci_debug_printf(9, "ci_hash_update:::Found %s\n", htable->hash_table[hash]->val);

    /*Make it the first entry in the current hash entry*/
    e->hnext=htable->hash_table[hash];
    htable->hash_table[hash] = e;
    return e;
}