← Back to branch summary

~ubuntu-branches/ubuntu/precise/xfonts-utils/precise

« back to all changes in this revision

Viewing changes to mkfontscale/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Daniel T Chen
  • Date: 2006-12-18 17:10:27 UTC
  • mfrom: (1.1.1 upstream) (0.1.2 etch)
  • Revision ID: james.westby@ubuntu.com-20061218171027-ayzuv41s4ufth700
Tags: 1:1.0.1-1ubuntu1
* Merge from Debian unstable, remaining Ubuntu change:
  - debian/control: Replace/Conflict bdftopcf to smooth upgrades
    from 6.06 LTS.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mkfontscale/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
/* $XFree86$ */
 
23
 
 
24
#include <stdlib.h>
 
25
#include <stdio.h>
 
26
#include <string.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(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 char
 
44
lwr(char a)
 
45
{
 
46
    if(a >= 'A' && a <= 'Z')
 
47
        return a | 0x20;
 
48
    else
 
49
        return a;
 
50
}
 
51
 
 
52
static void
 
53
strcpy_lwr(char *dst, char *src)
 
54
{
 
55
    while(1) {
 
56
        *dst = lwr(*src);
 
57
        if(*src == '\0')
 
58
            break;
 
59
        src++;
 
60
        dst++;
 
61
    }
 
62
}
 
63
 
 
64
static int
 
65
strcmp_lwr(char *a, char *b)
 
66
{
 
67
    while(*a != '\0' && *b != '\0') {
 
68
        if(lwr(*a) != lwr(*b)) {
 
69
            if(lwr(*a) < lwr(*b))
 
70
                return -1;
 
71
            if(lwr(*a) > lwr(*b))
 
72
                return 1;
 
73
        }
 
74
        a++;
 
75
        b++;
 
76
    }
 
77
    if (*a != '\0')
 
78
        return -1;
 
79
    else if(*b == '\0')
 
80
        return 1;
 
81
    else
 
82
        return 0;
 
83
}
 
84
 
 
85
HashTablePtr
 
86
makeHashTable()
 
87
{
 
88
    return calloc(NUMBUCKETS, sizeof(HashBucketPtr));
 
89
}
 
90
 
 
91
void
 
92
destroyHashTable(HashTablePtr table)
 
93
{
 
94
    int i;
 
95
    HashBucketPtr bp;
 
96
 
 
97
    for(i = 0; i < NUMBUCKETS; i++) {
 
98
        while(table[i]) {
 
99
            bp = table[i];
 
100
            table[i] = table[i]->next;
 
101
            free(bp->key);
 
102
            free(bp->value);
 
103
            free(bp);
 
104
        }
 
105
    }
 
106
    free(table);
 
107
}
 
108
 
 
109
char *
 
110
getHash(HashTablePtr table, char *key)
 
111
{
 
112
    int i = hash(key);
 
113
    HashBucketPtr bp;
 
114
    for(bp = table[i]; bp; bp = bp->next) {
 
115
        if(strcmp_lwr(bp->key, key) == 0)
 
116
            return bp->value;
 
117
    }
 
118
    return NULL;
 
119
}
 
120
 
 
121
int
 
122
putHash(HashTablePtr table, char *key, char *value, int prio)
 
123
{
 
124
    int i = hash(key);
 
125
    char *keycopy = NULL, *valuecopy = NULL;
 
126
    HashBucketPtr bp;
 
127
    for(bp = table[i]; bp; bp = bp->next) {
 
128
        if(strcmp_lwr(bp->key, key) == 0) {
 
129
            if(prio > bp->prio) {
 
130
                keycopy = malloc(strlen(key) + 1);
 
131
                if(keycopy == NULL) goto fail;
 
132
                strcpy_lwr(keycopy, key);
 
133
                valuecopy = malloc(strlen(value) + 1);
 
134
                if(valuecopy == NULL) goto fail;
 
135
                strcpy(valuecopy, value);
 
136
                free(bp->key);
 
137
                free(bp->value);
 
138
                bp->key = keycopy;
 
139
                bp->value = valuecopy;
 
140
            }
 
141
            return 1;
 
142
        }
 
143
    }
 
144
    keycopy = malloc(strlen(key) + 1);
 
145
    if(keycopy == NULL)
 
146
        goto fail;
 
147
    strcpy_lwr(keycopy, key);
 
148
    valuecopy = malloc(strlen(value) + 1);
 
149
    if(valuecopy == NULL)
 
150
        goto fail;
 
151
    strcpy(valuecopy, value);
 
152
    bp = malloc(sizeof(HashBucketRec));
 
153
    if(bp == NULL)
 
154
        goto fail;
 
155
    bp->key = keycopy;
 
156
    bp->value = valuecopy;
 
157
    bp->prio = prio;
 
158
    bp->next = table[i];
 
159
    table[i] = bp;
 
160
    return 1;
 
161
 
 
162
 fail:
 
163
    if(keycopy) free(keycopy);
 
164
    if(valuecopy) free(valuecopy);
 
165
    return -1;
 
166
}
 
167
 
 
168
int
 
169
hashElements(HashTablePtr table)
 
170
{
 
171
    int i, n;
 
172
    HashBucketPtr bp;
 
173
 
 
174
    n = 0;
 
175
    for(i = 0; i < NUMBUCKETS; i++) {
 
176
        for(bp = table[i]; bp; bp = bp->next) {
 
177
            n++;
 
178
        }
 
179
    }
 
180
    return n;
 
181
}
 
182
 
 
183
static int
 
184
key_first_cmp(const void *v1, const void *v2)
 
185
{
 
186
    const HashBucketPtr *b1 = v1, *b2 = v2;
 
187
    int c1 = strcmp_lwr((*b1)->key, (*b2)->key);
 
188
    if(c1 != 0) return c1;
 
189
    return strcmp((*b1)->value, (*b2)->value);
 
190
}
 
191
 
 
192
static int
 
193
value_first_cmp(const void *v1, const void *v2)
 
194
{
 
195
    const HashBucketPtr *b1 = v1, *b2 = v2;
 
196
    int c1 = strcmp((*b1)->value, (*b2)->value);
 
197
    if(c1 != 0) return c1;
 
198
    return strcmp_lwr((*b1)->key, (*b2)->key);
 
199
}
 
200
 
 
201
HashBucketPtr *
 
202
hashArray(HashTablePtr table, int value_first)
 
203
{
 
204
    int i, j, n;
 
205
    HashBucketPtr *dst;
 
206
    
 
207
    n = hashElements(table);
 
208
    dst = malloc((n + 1) * sizeof(HashBucketPtr));
 
209
    if(dst == NULL)
 
210
        return NULL;
 
211
 
 
212
    j = 0;
 
213
    for(i = 0; i < NUMBUCKETS; i++) {
 
214
        while(table[i]) {
 
215
            dst[j++] = table[i];
 
216
            table[i] = table[i]->next;
 
217
        }
 
218
    }
 
219
    qsort(dst, j, sizeof(HashBucketPtr),
 
220
          value_first ? value_first_cmp : key_first_cmp);
 
221
    dst[j++] = NULL;
 
222
    free(table);
 
223
 
 
224
    return dst;
 
225
}
 
226
 
 
227
void
 
228
destroyHashArray(HashBucketPtr *array)
 
229
{
 
230
    int i = 0;
 
231
    while(array[i]) {
 
232
        free(array[i]->key);
 
233
        free(array[i]->value);
 
234
        free(array[i]);
 
235
        i++;
 
236
    }
 
237
    free(array);
 
238
}