hash.c revision 663cdc11 
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#include <stdlib.h>
24#include <stdio.h>
25#include <string.h>
26#include <ctype.h>
27#include "hash.h"
28#include "list.h"
29
30#define LOG2_NUMBUCKETS 10
31#define NUMBUCKETS (1 << LOG2_NUMBUCKETS)
32
33static unsigned
34hash(const char *string)
35{
36    int i;
37    unsigned u = 0;
38    for(i = 0; string[i] != '\0'; i++)
39        u = (u<<5) + (u >> (LOG2_NUMBUCKETS - 5)) + (unsigned char)string[i];
40    return (u & (NUMBUCKETS - 1));
41}
42
43static void
44strcpy_lwr(char *dst, const char *src)
45{
46    while(1) {
47        *dst = tolower(*src);
48        if(*src == '\0')
49            break;
50        src++;
51        dst++;
52    }
53}
54
55HashTablePtr
56makeHashTable(void)
57{
58    return calloc(NUMBUCKETS, sizeof(HashBucketPtr));
59}
60
61void
62destroyHashTable(HashTablePtr table)
63{
64    int i;
65    HashBucketPtr bp;
66
67    for(i = 0; i < NUMBUCKETS; i++) {
68        while(table[i]) {
69            bp = table[i];
70            table[i] = table[i]->next;
71            free(bp->key);
72            free(bp->value);
73            free(bp);
74        }
75    }
76    free(table);
77}
78
79char *
80getHash(HashTablePtr table, const char *key)
81{
82    int i = hash(key);
83    HashBucketPtr bp;
84    for(bp = table[i]; bp; bp = bp->next) {
85        if(strcasecmp(bp->key, key) == 0)
86            return bp->value;
87    }
88    return NULL;
89}
90
91int
92putHash(HashTablePtr table, char *key, char *value, int prio)
93{
94    int i = hash(key);
95    char *keycopy = NULL, *valuecopy = NULL;
96    HashBucketPtr bp;
97    for(bp = table[i]; bp; bp = bp->next) {
98        if(strcasecmp(bp->key, key) == 0) {
99            if(prio > bp->prio) {
100                keycopy = malloc(strlen(key) + 1);
101                if(keycopy == NULL) goto fail;
102                strcpy_lwr(keycopy, key);
103                valuecopy = malloc(strlen(value) + 1);
104                if(valuecopy == NULL) goto fail;
105                strcpy(valuecopy, value);
106                free(bp->key);
107                free(bp->value);
108                bp->key = keycopy;
109                bp->value = valuecopy;
110            }
111            return 1;
112        }
113    }
114    keycopy = malloc(strlen(key) + 1);
115    if(keycopy == NULL)
116        goto fail;
117    strcpy_lwr(keycopy, key);
118    valuecopy = malloc(strlen(value) + 1);
119    if(valuecopy == NULL)
120        goto fail;
121    strcpy(valuecopy, value);
122    bp = malloc(sizeof(HashBucketRec));
123    if(bp == NULL)
124        goto fail;
125    bp->key = keycopy;
126    bp->value = valuecopy;
127    bp->prio = prio;
128    bp->next = table[i];
129    table[i] = bp;
130    return 1;
131
132 fail:
133    if(keycopy) free(keycopy);
134    if(valuecopy) free(valuecopy);
135    return -1;
136}
137
138int
139hashElements(HashTablePtr table)
140{
141    int i, n;
142    HashBucketPtr bp;
143
144    n = 0;
145    for(i = 0; i < NUMBUCKETS; i++) {
146        for(bp = table[i]; bp; bp = bp->next) {
147            n++;
148        }
149    }
150    return n;
151}
152
153static int
154key_first_cmp(const void *v1, const void *v2)
155{
156    const HashBucketPtr *b1 = v1, *b2 = v2;
157    int c1 = strcasecmp((*b1)->key, (*b2)->key);
158    if(c1 != 0) return c1;
159    return strcmp((*b1)->value, (*b2)->value);
160}
161
162static int
163value_first_cmp(const void *v1, const void *v2)
164{
165    const HashBucketPtr *b1 = v1, *b2 = v2;
166    int c1 = strcmp((*b1)->value, (*b2)->value);
167    if(c1 != 0) return c1;
168    return strcasecmp((*b1)->key, (*b2)->key);
169}
170
171HashBucketPtr *
172hashArray(HashTablePtr table, int value_first)
173{
174    int i, j, n;
175    HashBucketPtr *dst;
176
177    n = hashElements(table);
178    dst = malloc((n + 1) * sizeof(HashBucketPtr));
179    if(dst == NULL)
180        return NULL;
181
182    j = 0;
183    for(i = 0; i < NUMBUCKETS; i++) {
184        while(table[i]) {
185            dst[j++] = table[i];
186            table[i] = table[i]->next;
187        }
188    }
189    qsort(dst, j, sizeof(HashBucketPtr),
190          value_first ? value_first_cmp : key_first_cmp);
191    dst[j++] = NULL;
192    free(table);
193
194    return dst;
195}
196
197void
198destroyHashArray(HashBucketPtr *array)
199{
200    int i = 0;
201    while(array[i]) {
202        free(array[i]->key);
203        free(array[i]->value);
204        free(array[i]);
205        i++;
206    }
207    free(array);
208}
209