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    unsigned u = 0;
41
42    for (int 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    for (int i = 0; i < NUMBUCKETS; i++) {
66        while (table[i]) {
67            HashBucketPtr bp = table[i];
68            table[i] = table[i]->next;
69            free(bp->key);
70            free(bp->value);
71            free(bp);
72        }
73    }
74    free(table);
75}
76
77char *
78getHash(HashTablePtr table, const char *key)
79{
80    unsigned int i = hash(key);
81
82    for (HashBucketPtr bp = table[i]; bp; bp = bp->next) {
83        if (strcasecmp(bp->key, key) == 0)
84            return bp->value;
85    }
86    return NULL;
87}
88
89int
90putHash(HashTablePtr table, char *key, char *value, int prio)
91{
92    unsigned int i = hash(key);
93    char *keycopy = NULL, *valuecopy = NULL;
94    HashBucketPtr bp;
95
96    for (bp = table[i]; bp; bp = bp->next) {
97        if (strcasecmp(bp->key, key) == 0) {
98            if (prio > bp->prio) {
99                keycopy = strdup(key);
100                if (keycopy == NULL)
101                    goto fail;
102                str_tolower(keycopy);
103                valuecopy = strdup(value);
104                if (valuecopy == NULL)
105                    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)
133        free(keycopy);
134    if (valuecopy)
135        free(valuecopy);
136    return -1;
137}
138
139int
140hashElements(HashTablePtr table)
141{
142    int n = 0;
143
144    for (int i = 0; i < NUMBUCKETS; i++) {
145        for (HashBucketPtr 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
158    if (c1 != 0)
159        return c1;
160    return strcmp((*b1)->value, (*b2)->value);
161}
162
163static int
164value_first_cmp(const void *v1, const void *v2)
165{
166    const HashBucketPtr *b1 = v1, *b2 = v2;
167    int c1 = strcmp((*b1)->value, (*b2)->value);
168
169    if (c1 != 0)
170        return c1;
171    return strcasecmp((*b1)->key, (*b2)->key);
172}
173
174HashBucketPtr *
175hashArray(HashTablePtr table, int value_first)
176{
177    unsigned int j;
178    int n = hashElements(table);
179    HashBucketPtr *dst = malloc((n + 1) * sizeof(HashBucketPtr));
180    if (dst == NULL)
181        return NULL;
182
183    j = 0;
184    for (unsigned int i = 0; i < NUMBUCKETS; i++) {
185        while (table[i]) {
186            dst[j++] = table[i];
187            table[i] = table[i]->next;
188        }
189    }
190    qsort(dst, j, sizeof(HashBucketPtr),
191          value_first ? value_first_cmp : key_first_cmp);
192    dst[j++] = NULL;
193    free(table);
194
195    return dst;
196}
197
198void
199destroyHashArray(HashBucketPtr *array)
200{
201    unsigned int i = 0;
202
203    while (array[i]) {
204        free(array[i]->key);
205        free(array[i]->value);
206        free(array[i]);
207        i++;
208    }
209    free(array);
210}
211