| 1 | /*********************************************************** |
| 2 | |
| 3 | Copyright 1987, 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 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
| 26 | |
| 27 | All Rights Reserved |
| 28 | |
| 29 | Permission to use, copy, modify, and distribute this software and its |
| 30 | documentation for any purpose and without fee is hereby granted, |
| 31 | provided that the above copyright notice appear in all copies and that |
| 32 | both that copyright notice and this permission notice appear in |
| 33 | supporting documentation, and that the name of Digital not be |
| 34 | used in advertising or publicity pertaining to distribution of the |
| 35 | software without specific, written prior permission. |
| 36 | |
| 37 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
| 38 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
| 39 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
| 40 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
| 41 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
| 42 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
| 43 | SOFTWARE. |
| 44 | |
| 45 | ******************************************************************/ |
| 46 | |
| 47 | #ifdef HAVE_DIX_CONFIG_H |
| 48 | #include <dix-config.h> |
| 49 | #endif |
| 50 | |
| 51 | #include <X11/X.h> |
| 52 | #include <X11/Xatom.h> |
| 53 | #include <stdio.h> |
| 54 | #include <string.h> |
| 55 | #include "misc.h" |
| 56 | #include "resource.h" |
| 57 | #include "dix.h" |
| 58 | |
| 59 | #define InitialTableSize 100 |
| 60 | |
| 61 | typedef struct _Node { |
| 62 | struct _Node *left, *right; |
| 63 | Atom a; |
| 64 | unsigned int fingerPrint; |
| 65 | const char *string; |
| 66 | } NodeRec, *NodePtr; |
| 67 | |
| 68 | static Atom lastAtom = None; |
| 69 | static NodePtr atomRoot = NULL; |
| 70 | static unsigned long tableLength; |
| 71 | static NodePtr *nodeTable; |
| 72 | |
| 73 | void FreeAtom(NodePtr patom); |
| 74 | |
| 75 | Atom |
| 76 | MakeAtom(const char *string, unsigned len, Bool makeit) |
| 77 | { |
| 78 | NodePtr *np; |
| 79 | unsigned i; |
| 80 | int comp; |
| 81 | 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 != 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 | NodePtr nd; |
| 105 | |
| 106 | nd = malloc(sizeof(NodeRec)); |
| 107 | if (!nd) |
| 108 | return BAD_RESOURCE; |
| 109 | if (lastAtom < XA_LAST_PREDEFINED) { |
| 110 | nd->string = string; |
| 111 | } |
| 112 | else { |
| 113 | nd->string = strndup(string, len); |
| 114 | if (!nd->string) { |
| 115 | free(nd); |
| 116 | return BAD_RESOURCE; |
| 117 | } |
| 118 | } |
| 119 | if ((lastAtom + 1) >= tableLength) { |
| 120 | NodePtr *table; |
| 121 | |
| 122 | table = realloc(nodeTable, tableLength * (2 * sizeof(NodePtr))); |
| 123 | if (!table) { |
| 124 | if (nd->string != string) { |
| 125 | /* nd->string has been strdup'ed */ |
| 126 | free((char *) nd->string); |
| 127 | } |
| 128 | free(nd); |
| 129 | return BAD_RESOURCE; |
| 130 | } |
| 131 | tableLength <<= 1; |
| 132 | nodeTable = table; |
| 133 | } |
| 134 | *np = nd; |
| 135 | nd->left = nd->right = NULL; |
| 136 | nd->fingerPrint = fp; |
| 137 | nd->a = ++lastAtom; |
| 138 | nodeTable[lastAtom] = nd; |
| 139 | return nd->a; |
| 140 | } |
| 141 | else |
| 142 | return None; |
| 143 | } |
| 144 | |
| 145 | Bool |
| 146 | ValidAtom(Atom atom) |
| 147 | { |
| 148 | return (atom != None) && (atom <= lastAtom); |
| 149 | } |
| 150 | |
| 151 | const char * |
| 152 | NameForAtom(Atom atom) |
| 153 | { |
| 154 | NodePtr node; |
| 155 | |
| 156 | if (atom > lastAtom) |
| 157 | return 0; |
| 158 | if ((node = nodeTable[atom]) == NULL) |
| 159 | return 0; |
| 160 | return node->string; |
| 161 | } |
| 162 | |
| 163 | void |
| 164 | AtomError(void) |
| 165 | { |
| 166 | FatalError("initializing atoms"); |
| 167 | } |
| 168 | |
| 169 | void |
| 170 | FreeAtom(NodePtr patom) |
| 171 | { |
| 172 | if (patom->left) |
| 173 | FreeAtom(patom->left); |
| 174 | if (patom->right) |
| 175 | FreeAtom(patom->right); |
| 176 | if (patom->a > XA_LAST_PREDEFINED) { |
| 177 | /* |
| 178 | * All strings above XA_LAST_PREDEFINED are strdup'ed, so it's safe to |
| 179 | * cast here |
| 180 | */ |
| 181 | free((char *) patom->string); |
| 182 | } |
| 183 | free(patom); |
| 184 | } |
| 185 | |
| 186 | void |
| 187 | FreeAllAtoms(void) |
| 188 | { |
| 189 | if (atomRoot == NULL) |
| 190 | return; |
| 191 | FreeAtom(atomRoot); |
| 192 | atomRoot = NULL; |
| 193 | free(nodeTable); |
| 194 | nodeTable = NULL; |
| 195 | lastAtom = None; |
| 196 | } |
| 197 | |
| 198 | void |
| 199 | InitAtoms(void) |
| 200 | { |
| 201 | FreeAllAtoms(); |
| 202 | tableLength = InitialTableSize; |
| 203 | nodeTable = malloc(InitialTableSize * sizeof(NodePtr)); |
| 204 | if (!nodeTable) |
| 205 | AtomError(); |
| 206 | nodeTable[None] = NULL; |
| 207 | MakePredeclaredAtoms(); |
| 208 | if (lastAtom != XA_LAST_PREDEFINED) |
| 209 | AtomError(); |
| 210 | } |