hash.c

   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
  33 static unsigned
  34 hash(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
  43 static void
  44 strcpy_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
  55 HashTablePtr
  56 makeHashTable(void)
  57 {
  58     return calloc(NUMBUCKETS, sizeof(HashBucketPtr));
  59 }
  60
  61 void
  62 destroyHashTable(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
  79 char *
  80 getHash(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
  91 int
  92 putHash(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
 138 int
 139 hashElements(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
 153 static int
 154 key_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
 162 static int
 163 value_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
 171 HashBucketPtr *
 172 hashArray(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
 197 void
 198 destroyHashArray(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 }