/*************************************************************************
* TinyFugue - programmable mud client
* Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2002, 2003, 2004, 2005, 2006-2007 Ken Keys
*
* TinyFugue (aka "tf") is protected under the terms of the GNU
* General Public License. See the file "COPYING" for details.
************************************************************************/
static const char RCSid[] = "$Id: search.c,v 35004.32 2007/01/13 23:12:39 kkeys Exp $";
/**********************************************
* trie, hash table, and linked list routines *
**********************************************/
#include "tfconfig.h"
#include "port.h"
#include "malloc.h"
#include "search.h"
static ListEntry *nodepool = NULL; /* freelist */
/********/
/* trie */
/********/
/* Find the datum in trie assosiated with the key. */
void *trie_find(TrieNode *root, const unsigned char *key)
{
TrieNode *n;
for (n = root; n && n->children && *key; n = n->u.child[*key++]);
return (n && !n->children && !*key) ? n->u.datum : NULL;
}
/* Insert a datum into the trie pointed to by root.
* If key is substring, superstring, or duplicate of an existing key, intrie()
* returns TRIE_SUB, TRIE_SUPER, or TRIE_DUP and does not insert.
* Otherwise, returns 1 for success.
*/
int intrie(TrieNode **root, void *datum, const unsigned char *key)
{
int i;
if (!*root) {
*root = (TrieNode *) XMALLOC(sizeof(TrieNode));
if (*key) {
(*root)->children = 1;
(*root)->u.child = (TrieNode**)XMALLOC(0x100 * sizeof(TrieNode *));
for (i = 0; i < 0x100; i++) (*root)->u.child[i] = NULL;
return intrie(&(*root)->u.child[*key], datum, key + 1);
} else {
(*root)->children = 0;
(*root)->u.datum = datum;
return 1;
}
} else {
if (*key) {
if ((*root)->children) {
if (!(*root)->u.child[*key]) (*root)->children++;
return intrie(&(*root)->u.child[*key], datum, key+1);
} else {
return TRIE_SUPER;
}
} else {
return ((*root)->children) ? TRIE_SUB : TRIE_DUP;
}
}
}
TrieNode *untrie(TrieNode **root, const unsigned char *s)
{
if (*s) {
if (untrie(&((*root)->u.child[*s]), s + 1)) return *root;
if (--(*root)->children) return *root;
FREE((*root)->u.child);
}
FREE(*root);
return *root = NULL;
}
/***************/
/* linked list */
/***************/
void init_list(List *list)
{
list->head = list->tail = NULL;
}
/* delete Node from linked list */
void *unlist(ListEntry *node, List *list)
{
void *result;
*(node->next ? &node->next->prev : &list->tail) = node->prev;
*(node->prev ? &node->prev->next : &list->head) = node->next;
result = node->datum;
pfree(node, nodepool, next);
return result;
}
/* Create new node for datum and insert into list in sorted order.
* <cmp> is a function that compares two data.
*/
ListEntry *sinsert(void *datum, List *list, Cmp *cmp)
{
ListEntry *node;
node = list->head;
while (node && (*cmp)(datum, node->datum) > 0) {
node = node->next;
}
return inlist(datum, list, node ? node->prev : list->tail);
}
/* Create new node for datum and insert into list.
* If where is non-null, insert after it; else, insert at beginning
*/
ListEntry *inlist_fl(void *datum, List *list, ListEntry *where,
const char *file, int line)
{
ListEntry *node;
palloc(node, ListEntry, nodepool, next, file, line);
node->datum = datum;
if (where) {
node->next = where->next;
where->next = node;
} else {
node->next = list->head;
list->head = node;
}
node->prev = where;
*(node->next ? &node->next->prev : &list->tail) = node;
return node;
}
/**************/
/* hash table */
/**************/
void init_hashtable(HashTable *table, int size, Cmp *cmp)
{
table->size = size;
table->cmp = cmp;
table->bucket = (List **)XMALLOC(sizeof(List *) * size);
while (size)
table->bucket[--size] = NULL;
}
/* find entry by name */
void *hashed_find(const char *name, unsigned int hash, HashTable *table)
{
List *bucket;
ListEntry *node;
bucket = table->bucket[hash % table->size];
if (bucket) {
for (node = bucket->head; node; node = node->next)
if ((*table->cmp)((void *)name, node->datum) == 0)
return node->datum;
}
return NULL;
}
unsigned int hash_string(const char *str)
{
unsigned int h;
for (h = 0; *str; str++)
h = (h << 5) + h + lcase(*str);
return h;
}
ListEntry *hashed_insert(void *datum, unsigned int hash, HashTable *table)
{
int indx = hash % table->size;
if (!table->bucket[indx]) {
table->bucket[indx] = (List *)XMALLOC(sizeof(List));
init_list(table->bucket[indx]);
}
return inlist(datum, table->bucket[indx], NULL);
}
void hash_remove(ListEntry *node, HashTable *tab)
{
unlist(node, tab->bucket[hash_string(*(char**)node->datum) % tab->size]);
}
/***************/
/* comparisons */
/***************/
/* strstructcmp - compares a string to the first field of a structure */
int strstructcmp(const void *key, const void *datum)
{
return strcmp((char *)key, *(char **)datum);
}
/* cstrstructcmp - compares string to first field of a struct, ignoring case */
int cstrstructcmp(const void *key, const void *datum)
{
return cstrcmp((char *)key, *(char **)datum);
}
/* strpppcmp - for qsort array of ptrs to structs whose 1st member is char* */
int strpppcmp(const void *a, const void *b)
{
return strcmp(**(char ***)a, **(char ***)b);
}
/* cstrpppcmp - for qsort array of ptrs to structs whose 1st member is char* */
int cstrpppcmp(const void *a, const void *b)
{
return cstrcmp(**(char ***)a, **(char ***)b);
}
/*******************/
/* circular queues */
/*******************/
static int alloc_cqueue(CQueue *cq, int maxsize)
{
cq->maxsize = maxsize;
if (maxsize) {
cq->data =
(void**)MALLOC(maxsize * sizeof(void*));
if (!cq->data) {
/*eprintf("not enough memory for %d lines.", maxsize); */ /* XXX */
cq->maxsize = 1;
cq->data = (void**)XMALLOC(1 * sizeof(void*));
return 0;
}
} else {
cq->data = NULL;
}
return 1;
}
struct CQueue *init_cqueue(CQueue *cq, int maxsize,
void (*free_f)(void*, const char *, int))
{
if (!cq) cq = (CQueue*)XMALLOC(sizeof(CQueue));
cq->free = free_f;
cq->last = cq->index = -1;
cq->first = cq->size = cq->total = 0;
alloc_cqueue(cq, maxsize);
return cq;
}
void free_cqueue(CQueue *cq)
{
if (cq->data) {
for ( ; cq->size; cq->size--) {
cq->free(cq->data[cq->first], __FILE__, __LINE__);
cq->first = nmod(cq->first + 1, cq->maxsize);
}
cq->first = 0;
cq->last = -1;
FREE(cq->data);
}
}
void encqueue(CQueue *cq, void *datum)
{
if (!cq->data)
alloc_cqueue(cq, cq->maxsize);
if (cq->size == cq->maxsize) {
cq->free(cq->data[cq->first], __FILE__, __LINE__);
cq->first = nmod(cq->first + 1, cq->maxsize);
} else {
cq->size++;
}
cq->last = nmod(cq->last + 1, cq->maxsize);
cq->data[cq->last] = datum;
cq->total++;
}
void cqueue_replace(CQueue *cq, void *datum, int idx)
{
cq->free(cq->data[idx], __FILE__, __LINE__);
cq->data[idx] = datum;
}
int resize_cqueue(CQueue *cq, int maxsize)
{
int first, last, size;
void **newdata;
/* XXX should use version of malloc without reserve */
if (!(newdata = (void**)MALLOC(maxsize * sizeof(void*))))
return 0;
first = nmod(cq->total, maxsize);
last = nmod(cq->total - 1, maxsize);
for (size = 0; cq->size; cq->size--) {
if (size < maxsize) {
first = nmod(first - 1, maxsize);
newdata[first] = cq->data[cq->last];
size++;
} else {
cq->free(cq->data[cq->last], __FILE__, __LINE__);
}
cq->last = nmod(cq->last - 1, cq->maxsize);
}
if (cq->data) FREE(cq->data);
cq->data = newdata;
cq->first = first;
cq->last = last;
cq->size = size;
cq->maxsize = maxsize;
cq->index = cq->last;
return cq->maxsize;
}
#if USE_DMALLOC
void free_search(void)
{
pfreepool(ListEntry, nodepool, next);
}
void free_hash(HashTable *table)
{
int i;
for (i = 0; i < table->size; i++) {
if (table->bucket[i]) FREE(table->bucket[i]);
}
FREE(table->bucket);
}
#endif
syntax highlighted by Code2HTML, v. 0.9.1