atom.c revision c7b4381a 
1/*
2
3  Copyright 1990, 1994, 1998  The Open Group
4
5  Permission to use, copy, modify, distribute, and sell this software and its
6  documentation for any purpose is hereby granted without fee, provided that
7  the above copyright notice appear in all copies and that both that
8  copyright notice and this permission notice appear in supporting
9  documentation.
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  OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18  AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21  Except as contained in this notice, the name of The Open Group shall not be
22  used in advertising or otherwise to promote the sale, use or other dealings
23  in this Software without prior written authorization from The Open Group.
24
25*/
26
27/*
28 * Author:  Keith Packard, MIT X Consortium
29 */
30
31/* lame atom replacement routines for font applications */
32
33#ifdef HAVE_CONFIG_H
34#include <config.h>
35#endif
36#include "libxfontint.h"
37#include "src/util/replace.h"
38#include <X11/fonts/fontmisc.h>
39
40typedef struct _AtomList {
41    char *name;
42    int len;
43    int hash;
44    Atom atom;
45} AtomListRec, *AtomListPtr;
46
47static AtomListPtr *hashTable;
48
49static int hashSize, hashUsed;
50static int hashMask;
51static int rehash;
52
53static AtomListPtr *reverseMap;
54static int reverseMapSize;
55static Atom lastAtom;
56
57static int
58Hash(const char *string, int len)
59{
60    int h;
61
62    h = 0;
63    while (len--)
64        h = (h << 3) ^ *string++;
65    if (h < 0)
66        return -h;
67    return h;
68}
69
70static int
71ResizeHashTable(void)
72{
73    int newHashSize;
74    int newHashMask;
75    AtomListPtr *newHashTable;
76    int i;
77    int h;
78    int newRehash;
79    int r;
80
81    if (hashSize == 0)
82        newHashSize = 1024;
83    else
84        newHashSize = hashSize * 2;
85    newHashTable = calloc(newHashSize, sizeof(AtomListPtr));
86    if (!newHashTable) {
87        fprintf(stderr, "ResizeHashTable(): Error: Couldn't allocate"
88                " newHashTable (%ld)\n",
89                newHashSize * (unsigned long) sizeof(AtomListPtr));
90        return FALSE;
91    }
92    newHashMask = newHashSize - 1;
93    newRehash = (newHashMask - 2);
94    for (i = 0; i < hashSize; i++) {
95        if (hashTable[i]) {
96            h = (hashTable[i]->hash) & newHashMask;
97            if (newHashTable[h]) {
98                r = hashTable[i]->hash % newRehash | 1;
99                do {
100                    h += r;
101                    if (h >= newHashSize)
102                        h -= newHashSize;
103                } while (newHashTable[h]);
104            }
105            newHashTable[h] = hashTable[i];
106        }
107    }
108    free(hashTable);
109    hashTable = newHashTable;
110    hashSize = newHashSize;
111    hashMask = newHashMask;
112    rehash = newRehash;
113    return TRUE;
114}
115
116static int
117ResizeReverseMap(void)
118{
119    AtomListPtr *newMap;
120    int newMapSize;
121
122    if (reverseMapSize == 0)
123        newMapSize = 1000;
124    else
125        newMapSize = reverseMapSize * 2;
126    newMap = reallocarray(reverseMap, newMapSize, sizeof(AtomListPtr));
127    if (newMap == NULL) {
128        fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
129                " reverseMap (%ld)\n",
130                newMapSize * (unsigned long) sizeof(AtomListPtr));
131        return FALSE;
132    }
133    reverseMap = newMap;
134    reverseMapSize = newMapSize;
135    return TRUE;
136}
137
138static int
139NameEqual(const char *a, const char *b, int l)
140{
141    while (l--)
142        if (*a++ != *b++)
143            return FALSE;
144    return TRUE;
145}
146
147Atom
148__libxfont_internal__MakeAtom(const char *string, unsigned len, int makeit)
149{
150    AtomListPtr a;
151    int hash;
152    int h = 0;
153    int r;
154
155    hash = Hash(string, len);
156    if (hashTable) {
157        h = hash & hashMask;
158        if (hashTable[h]) {
159            if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
160                NameEqual(hashTable[h]->name, string, len)) {
161                return hashTable[h]->atom;
162            }
163            r = (hash % rehash) | 1;
164            for (;;) {
165                h += r;
166                if (h >= hashSize)
167                    h -= hashSize;
168                if (!hashTable[h])
169                    break;
170                if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
171                    NameEqual(hashTable[h]->name, string, len)) {
172                    return hashTable[h]->atom;
173                }
174            }
175        }
176    }
177    if (!makeit)
178        return None;
179    a = malloc(sizeof(AtomListRec) + len + 1);
180    if (a == NULL) {
181        fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
182                " (%ld)\n", (unsigned long) sizeof(AtomListRec) + len + 1);
183        return None;
184    }
185    a->name = (char *) (a + 1);
186    a->len = len;
187    strncpy(a->name, string, len);
188    a->name[len] = '\0';
189    a->atom = ++lastAtom;
190    a->hash = hash;
191    if (hashUsed >= hashSize / 2) {
192        if ((ResizeHashTable() == FALSE) &&
193	    ((hashTable == NULL) || (hashUsed == hashSize)))
194	    return None;
195        h = hash & hashMask;
196        if (hashTable[h]) {
197            r = (hash % rehash) | 1;
198            do {
199                h += r;
200                if (h >= hashSize)
201                    h -= hashSize;
202            } while (hashTable[h]);
203        }
204    }
205    hashTable[h] = a;
206    hashUsed++;
207    if (reverseMapSize <= a->atom) {
208        if (!ResizeReverseMap())
209            return None;
210    }
211    reverseMap[a->atom] = a;
212    return a->atom;
213}
214
215int
216__libxfont_internal__ValidAtom(Atom atom)
217{
218    return (atom != None) && (atom <= lastAtom);
219}
220
221const char *
222__libxfont_internal__NameForAtom(Atom atom)
223{
224    if (atom != None && atom <= lastAtom)
225        return reverseMap[atom]->name;
226    return NULL;
227}
228