hash.c revision 40cc5db4 
1/*
2  Copyright (c) 2003 by Juliusz Chroboczek
3
4  Permission is hereby granted, free of charge, to any person obtaining a copy
5  of this software and associated documentation files (the "Software"), to deal
6  in the Software without restriction, including without limitation the rights
7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  copies of the Software, and to permit persons to whom the Software is
9  furnished to do so, subject to the following conditions:
10
11  The above copyright notice and this permission notice shall be included in
12  all copies or substantial portions of the Software.
13
14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20  THE SOFTWARE.
21*/
22
23#ifdef HAVE_CONFIG_H
24#include "config.h"
25#endif
26
27#include <stdlib.h>
28#include <stdio.h>
29#include <string.h>
30#include <ctype.h>
31#include "hash.h"
32#include "list.h"
33
34#define LOG2_NUMBUCKETS 10
35#define NUMBUCKETS (1 << LOG2_NUMBUCKETS)
36
37static unsigned
38hash(const char *string)
39{
40    int i;
41    unsigned u = 0;
42    for(i = 0; string[i] != '\0'; i++)
43        u = (u<<5) + (u >> (LOG2_NUMBUCKETS - 5)) + (unsigned char)string[i];
44    return (u & (NUMBUCKETS - 1));
45}
46
47static void
48str_tolower(char *s)
49{
50    while(*s != '\0') {
51        *s = tolower(*s);
52        s++;
53    }
54}
55
56HashTablePtr
57makeHashTable(void)
58{
59    return calloc(NUMBUCKETS, sizeof(HashBucketPtr));
60}
61
62void
63destroyHashTable(HashTablePtr table)
64{
65    int i;
66    HashBucketPtr bp;
67
68    for(i = 0; i < NUMBUCKETS; i++) {
69        while(table[i]) {
70            bp = table[i];
71            table[i] = table[i]->next;
72            free(bp->key);
73            free(bp->value);
74            free(bp);
75        }
76    }
77    free(table);
78}
79
80char *
81getHash(HashTablePtr table, const char *key)
82{
83    unsigned int i = hash(key);
84    HashBucketPtr bp;
85    for(bp = table[i]; bp; bp = bp->next) {
86        if(strcasecmp(bp->key, key) == 0)
87            return bp->value;
88    }
89    return NULL;
90}
91
92int
93putHash(HashTablePtr table, char *key, char *value, int prio)
94{
95    unsigned int i = hash(key);
96    char *keycopy = NULL, *valuecopy = NULL;
97    HashBucketPtr bp;
98    for(bp = table[i]; bp; bp = bp->next) {
99        if(strcasecmp(bp->key, key) == 0) {
100            if(prio > bp->prio) {
101                keycopy = strdup(key);
102                if(keycopy == NULL) goto fail;
103                str_tolower(keycopy);
104                valuecopy = strdup(value);
105                if(valuecopy == NULL) goto fail;
106                free(bp->key);
107                free(bp->value);
108                bp->key = keycopy;
109                bp->value = valuecopy;
110            }
111            return 1;
112        }
113    }
114    keycopy = strdup(key);
115    if(keycopy == NULL)
116        goto fail;
117    str_tolower(keycopy);
118    valuecopy = strdup(value);
119    if(valuecopy == NULL)
120        goto fail;
121    bp = malloc(sizeof(HashBucketRec));
122    if(bp == NULL)
123        goto fail;
124    bp->key = keycopy;
125    bp->value = valuecopy;
126    bp->prio = prio;
127    bp->next = table[i];
128    table[i] = bp;
129    return 1;
130
131 fail:
132    if(keycopy) free(keycopy);
133    if(valuecopy) free(valuecopy);
134    return -1;
135}
136
137int
138hashElements(HashTablePtr table)
139{
140    int i, n;
141    HashBucketPtr bp;
142
143    n = 0;
144    for(i = 0; i < NUMBUCKETS; i++) {
145        for(bp = table[i]; bp; bp = bp->next) {
146            n++;
147        }
148    }
149    return n;
150}
151
152static int
153key_first_cmp(const void *v1, const void *v2)
154{
155    const HashBucketPtr *b1 = v1, *b2 = v2;
156    int c1 = strcasecmp((*b1)->key, (*b2)->key);
157    if(c1 != 0) return c1;
158    return strcmp((*b1)->value, (*b2)->value);
159}
160
161static int
162value_first_cmp(const void *v1, const void *v2)
163{
164    const HashBucketPtr *b1 = v1, *b2 = v2;
165    int c1 = strcmp((*b1)->value, (*b2)->value);
166    if(c1 != 0) return c1;
167    return strcasecmp((*b1)->key, (*b2)->key);
168}
169
170HashBucketPtr *
171hashArray(HashTablePtr table, int value_first)
172{
173    int i, j, n;
174    HashBucketPtr *dst;
175
176    n = hashElements(table);
177    dst = malloc((n + 1) * sizeof(HashBucketPtr));
178    if(dst == NULL)
179        return NULL;
180
181    j = 0;
182    for(i = 0; i < NUMBUCKETS; i++) {
183        while(table[i]) {
184            dst[j++] = table[i];
185            table[i] = table[i]->next;
186        }
187    }
188    qsort(dst, j, sizeof(HashBucketPtr),
189          value_first ? value_first_cmp : key_first_cmp);
190    dst[j++] = NULL;
191    free(table);
192
193    return dst;
194}
195
196void
197destroyHashArray(HashBucketPtr *array)
198{
199    int i = 0;
200    while(array[i]) {
201        free(array[i]->key);
202        free(array[i]->value);
203        free(array[i]);
204        i++;
205    }
206    free(array);
207}
208