#include "fontmisc.h"
typedef struct _AtomList {
char *name;
int len;
int hash;
Atom atom;
} AtomListRec, *AtomListPtr;
static AtomListPtr *hashTable;
static int hashSize, hashUsed;
static int hashMask;
static int rehash;
static AtomListPtr *reverseMap;
static int reverseMapSize;
static Atom lastAtom;
static int
Hash(char *string, int len)
{
int h;
h = 0;
while (len--)
h = (h << 3) ^ *string++;
if (h < 0)
return -h;
return h;
}
static int
ResizeHashTable (void)
{
int newHashSize;
int newHashMask;
AtomListPtr *newHashTable;
int i;
int h;
int newRehash;
int r;
if (hashSize == 0)
newHashSize = 1024;
else
newHashSize = hashSize * 2;
newHashTable = (AtomListPtr *) xalloc (newHashSize * sizeof (AtomListPtr));
if (!newHashTable) {
fprintf(stderr, "ResizeHashTable(): Error: Couldn't allocate"
" newHashTable (%ld)\n",
newHashSize * (unsigned long)sizeof (AtomListPtr));
return FALSE;
}
bzero ((char *) newHashTable, newHashSize * sizeof (AtomListPtr));
newHashMask = newHashSize - 1;
newRehash = (newHashMask - 2);
for (i = 0; i < hashSize; i++)
{
if (hashTable[i])
{
h = (hashTable[i]->hash) & newHashMask;
if (newHashTable[h])
{
r = hashTable[i]->hash % newRehash | 1;
do {
h += r;
if (h >= newHashSize)
h -= newHashSize;
} while (newHashTable[h]);
}
newHashTable[h] = hashTable[i];
}
}
xfree (hashTable);
hashTable = newHashTable;
hashSize = newHashSize;
hashMask = newHashMask;
rehash = newRehash;
return TRUE;
}
static int
ResizeReverseMap (void)
{
int ret = TRUE;
if (reverseMapSize == 0)
reverseMapSize = 1000;
else
reverseMapSize *= 2;
reverseMap = (AtomListPtr *) xrealloc (reverseMap, reverseMapSize * sizeof (AtomListPtr));
if (!reverseMap) {
fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
" reverseMap (%ld)\n",
reverseMapSize * (unsigned long)sizeof(AtomListPtr));
ret = FALSE;
}
return ret;
}
static int
NameEqual (const char *a, const char *b, int l)
{
while (l--)
if (*a++ != *b++)
return FALSE;
return TRUE;
}
Atom
MakeAtom(char *string, unsigned len, int makeit)
{
AtomListPtr a;
int hash;
int h = 0;
int r;
hash = Hash (string, len);
if (hashTable)
{
h = hash & hashMask;
if (hashTable[h])
{
if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
NameEqual (hashTable[h]->name, string, len))
{
return hashTable[h]->atom;
}
r = (hash % rehash) | 1;
for (;;)
{
h += r;
if (h >= hashSize)
h -= hashSize;
if (!hashTable[h])
break;
if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
NameEqual (hashTable[h]->name, string, len))
{
return hashTable[h]->atom;
}
}
}
}
if (!makeit)
return None;
a = (AtomListPtr) xalloc (sizeof (AtomListRec) + len + 1);
if (a == NULL) {
fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
" (%ld)\n", (unsigned long)sizeof (AtomListRec) + len + 1);
return None;
}
a->name = (char *) (a + 1);
a->len = len;
strncpy (a->name, string, len);
a->name[len] = '\0';
a->atom = ++lastAtom;
a->hash = hash;
if (hashUsed >= hashSize / 2)
{
ResizeHashTable ();
h = hash & hashMask;
if (hashTable[h])
{
r = (hash % rehash) | 1;
do {
h += r;
if (h >= hashSize)
h -= hashSize;
} while (hashTable[h]);
}
}
hashTable[h] = a;
hashUsed++;
if (reverseMapSize <= a->atom) {
if (!ResizeReverseMap())
return None;
}
reverseMap[a->atom] = a;
return a->atom;
}
int
ValidAtom(Atom atom)
{
return (atom != None) && (atom <= lastAtom);
}
char *
NameForAtom(Atom atom)
{
if (atom != None && atom <= lastAtom)
return reverseMap[atom]->name;
return NULL;
}