atom.c revision bbe1b32b 
1/* $Xorg: atom.c,v 1.4 2001/02/09 02:05:42 xorgcvs Exp $ */
2/*
3 * font server atom manipulations
4 */
5/*
6Copyright 1987, 1998  The Open Group
7
8Permission to use, copy, modify, distribute, and sell this software and its
9documentation for any purpose is hereby granted without fee, provided that
10the above copyright notice appear in all copies and that both that
11copyright notice and this permission notice appear in supporting
12documentation.
13
14The above copyright notice and this permission notice shall be included in
15all copies or substantial portions of the Software.
16
17THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
20OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
21AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23
24Except as contained in this notice, the name of The Open Group shall not be
25used in advertising or otherwise to promote the sale, use or other dealings
26in this Software without prior written authorization from The Open Group.
27 * Copyright 1990, 1991 Network Computing Devices;
28 * Portions Copyright 1987 by Digital Equipment Corporation
29 *
30 * Permission to use, copy, modify, distribute, and sell this software and its
31 * documentation for any purpose is hereby granted without fee, provided that
32 * the above copyright notice appear in all copies and that both that
33 * copyright notice and this permission notice appear in supporting
34 * documentation, and that the names of Network Computing Devices,
35 * or Digital not be used in advertising or
36 * publicity pertaining to distribution of the software without specific,
37 * written prior permission.  Network Computing Devices, or Digital
38 * make no representations about the
39 * suitability of this software for any purpose.  It is provided "as is"
40 * without express or implied warranty.
41 *
42 * NETWORK COMPUTING DEVICES, AND DIGITAL DISCLAIM ALL WARRANTIES WITH
43 * REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
44 * AND FITNESS, IN NO EVENT SHALL NETWORK COMPUTING DEVICES, OR DIGITAL BE
45 * LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
46 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
47 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
48 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
49 *
50 * @(#)atom.c	4.1	5/2/91
51 *
52 */
53/* $XFree86: xc/programs/xfs/difs/atom.c,v 3.4tsi Exp $ */
54
55#include "misc.h"
56#include "fsresource.h"
57#include "difs.h"
58
59#define InitialTableSize 100
60#define	FSA_LAST_PREDEFINED	0 /* only None is predefined */
61
62typedef struct _Node {
63    struct _Node *left,
64               *right;
65    Atom        a;
66    unsigned int fingerPrint;
67    char       *string;
68}           NodeRec, *NodePtr;
69
70static Atom lastAtom = None;
71static NodePtr atomRoot = (NodePtr) NULL;
72static unsigned long tableLength;
73static NodePtr *nodeTable;
74
75Atom
76MakeAtom(char *string, unsigned int len, Bool makeit)
77{
78    register NodePtr *np;
79    unsigned    i;
80    int         comp;
81    register unsigned int fp = 0;
82
83    np = &atomRoot;
84    for (i = 0; i < (len + 1) / 2; i++) {
85	fp = fp * 27 + string[i];
86	fp = fp * 27 + string[len - 1 - i];
87    }
88    while (*np != (NodePtr) NULL) {
89	if (fp < (*np)->fingerPrint)
90	    np = &((*np)->left);
91	else if (fp > (*np)->fingerPrint)
92	    np = &((*np)->right);
93	else {			/* now start testing the strings */
94	    comp = strncmp(string, (*np)->string, (int) len);
95	    if ((comp < 0) || ((comp == 0) && (len < strlen((*np)->string))))
96		np = &((*np)->left);
97	    else if (comp > 0)
98		np = &((*np)->right);
99	    else
100		return (*np)->a;
101	}
102    }
103    if (makeit) {
104	register NodePtr nd;
105
106	nd = (NodePtr) fsalloc(sizeof(NodeRec));
107	if (!nd)
108	    return BAD_RESOURCE;
109#if FSA_LAST_PREDEFINED > 0
110	if (lastAtom < FSA_LAST_PREDEFINED) {
111	    nd->string = string;
112	} else
113#endif
114	{
115	    nd->string = (char *) fsalloc(len + 1);
116	    if (!nd->string) {
117		fsfree(nd);
118		return BAD_RESOURCE;
119	    }
120	    strncpy(nd->string, string, (int) len);
121	    nd->string[len] = 0;
122	}
123	if ((lastAtom + 1) >= tableLength) {
124	    NodePtr    *table;
125
126	    table = (NodePtr *) fsrealloc(nodeTable,
127					tableLength * (2 * sizeof(NodePtr)));
128	    if (!table) {
129		if (nd->string != string)
130		    fsfree(nd->string);
131		fsfree(nd);
132		return BAD_RESOURCE;
133	    }
134	    tableLength <<= 1;
135	    nodeTable = table;
136	}
137	*np = nd;
138	nd->left = nd->right = (NodePtr) NULL;
139	nd->fingerPrint = fp;
140	nd->a = (++lastAtom);
141	*(nodeTable + lastAtom) = nd;
142	return nd->a;
143    } else
144	return None;
145}
146
147int
148ValidAtom(Atom atom)
149{
150    return (atom != None) && (atom <= lastAtom);
151}
152
153char       *
154NameForAtom(Atom atom)
155{
156    NodePtr     node;
157
158    if (atom > lastAtom)
159	return 0;
160    if ((node = nodeTable[atom]) == (NodePtr) NULL)
161	return 0;
162    return node->string;
163}
164
165static void
166atom_error(void)
167{
168    FatalError("initializing atoms\n");
169}
170
171static void
172free_atom(NodePtr patom)
173{
174    if (patom->left)
175	free_atom(patom->left);
176    if (patom->right)
177	free_atom(patom->right);
178    if (patom->a > FSA_LAST_PREDEFINED)
179	fsfree(patom->string);
180    fsfree(patom);
181}
182
183static void
184free_all_atoms(void)
185{
186    if (atomRoot == (NodePtr) NULL)
187	return;
188    free_atom(atomRoot);
189    atomRoot = (NodePtr) NULL;
190    fsfree(nodeTable);
191    nodeTable = (NodePtr *) NULL;
192    lastAtom = None;
193}
194
195void
196InitAtoms(void)
197{
198    free_all_atoms();
199    tableLength = InitialTableSize;
200    nodeTable = (NodePtr *) fsalloc(InitialTableSize * sizeof(NodePtr));
201    if (!nodeTable)
202	atom_error();
203    nodeTable[None] = (NodePtr) NULL;
204    lastAtom = FSA_LAST_PREDEFINED;
205}
206