#ifdef HAVE_DIX_CONFIG_H
#include <dix-config.h>
#endif
#include <X11/X.h>
#include <X11/Xatom.h>
#include <stdio.h>
#include <string.h>
#include "misc.h"
#include "resource.h"
#include "dix.h"
#define InitialTableSize 100
typedef struct _Node {
struct _Node *left, *right;
Atom a;
unsigned int fingerPrint;
char *string;
} NodeRec, *NodePtr;
static Atom lastAtom = None;
static NodePtr atomRoot = (NodePtr)NULL;
static unsigned long tableLength;
static NodePtr *nodeTable;
void FreeAtom(NodePtr patom);
_X_EXPORT Atom
MakeAtom(char *string, unsigned len, Bool makeit)
{
NodePtr * np;
unsigned i;
int comp;
unsigned int fp = 0;
np = &atomRoot;
for (i = 0; i < (len+1)/2; i++)
{
fp = fp * 27 + string[i];
fp = fp * 27 + string[len - 1 - i];
}
while (*np != (NodePtr) NULL)
{
if (fp < (*np)->fingerPrint)
np = &((*np)->left);
else if (fp > (*np)->fingerPrint)
np = &((*np)->right);
else
{
comp = strncmp(string, (*np)->string, (int)len);
if ((comp < 0) || ((comp == 0) && (len < strlen((*np)->string))))
np = &((*np)->left);
else if (comp > 0)
np = &((*np)->right);
else
return(*np)->a;
}
}
if (makeit)
{
NodePtr nd;
nd = (NodePtr) xalloc(sizeof(NodeRec));
if (!nd)
return BAD_RESOURCE;
if (lastAtom < XA_LAST_PREDEFINED)
{
nd->string = string;
}
else
{
nd->string = (char *) xalloc(len + 1);
if (!nd->string) {
xfree(nd);
return BAD_RESOURCE;
}
strncpy(nd->string, string, (int)len);
nd->string[len] = 0;
}
if ((lastAtom + 1) >= tableLength) {
NodePtr *table;
table = (NodePtr *) xrealloc(nodeTable,
tableLength * (2 * sizeof(NodePtr)));
if (!table) {
if (nd->string != string)
xfree(nd->string);
xfree(nd);
return BAD_RESOURCE;
}
tableLength <<= 1;
nodeTable = table;
}
*np = nd;
nd->left = nd->right = (NodePtr) NULL;
nd->fingerPrint = fp;
nd->a = (++lastAtom);
*(nodeTable+lastAtom) = nd;
return nd->a;
}
else
return None;
}
_X_EXPORT Bool
ValidAtom(Atom atom)
{
return (atom != None) && (atom <= lastAtom);
}
_X_EXPORT char *
NameForAtom(Atom atom)
{
NodePtr node;
if (atom > lastAtom) return 0;
if ((node = nodeTable[atom]) == (NodePtr)NULL) return 0;
return node->string;
}
void
AtomError(void)
{
FatalError("initializing atoms");
}
void
FreeAtom(NodePtr patom)
{
if(patom->left)
FreeAtom(patom->left);
if(patom->right)
FreeAtom(patom->right);
if (patom->a > XA_LAST_PREDEFINED)
xfree(patom->string);
xfree(patom);
}
void
FreeAllAtoms(void)
{
if(atomRoot == (NodePtr)NULL)
return;
FreeAtom(atomRoot);
atomRoot = (NodePtr)NULL;
xfree(nodeTable);
nodeTable = (NodePtr *)NULL;
lastAtom = None;
}
void
InitAtoms(void)
{
FreeAllAtoms();
tableLength = InitialTableSize;
nodeTable = (NodePtr *)xalloc(InitialTableSize*sizeof(NodePtr));
if (!nodeTable)
AtomError();
nodeTable[None] = (NodePtr)NULL;
MakePredeclaredAtoms();
if (lastAtom != XA_LAST_PREDEFINED)
AtomError ();
}