/*************************************************************************
 *  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.
 ************************************************************************/
/* $Id: search.h,v 35004.29 2007/01/13 23:12:39 kkeys Exp $ */

#ifndef SEARCH_H
#define SEARCH_H

/*************************************************************
 * trie, hash table, linked list, and binary search routines *
 *************************************************************/

/*
 * Trie.
 * Any type can be used in a trie.
 */
/*
 * Linked List.
 * Any type can be used in a linked list.
 */
/*
 * Circular Queue.
 * Any type can be used in a linked list.
 */
/*
 * Hash Table.
 * All structs used by hash table routines must have a string as the
 * first member.  This first string field is used as the hash key.
 */
/*
 * Binary Search.
 * Generic comparison functions gen[c]strcmp() are provided to perform
 * [c]strcmp() on any structure whose first field is a string; these are
 * useful with bsearch().
 */

/* Modulo arithmetic: remainder is positive, even if numerator is negative. */
#define nmod(n, d)   (((n) >= 0) ? ((n)%(d)) : ((d) - ((-(n)-1)%(d)) - 1))
#define ndiv(n, d)   (((n) >= 0) ? ((n)/(d)) : (-((-(n)-1)/(d))-1))


/* Resizable vector of pointers */
typedef struct Vector {
    int capacity;
    int size;
    void **ptrs;
} Vector;

#define vector_init(n)		{ (n)/2, 0, NULL }

#define vector_add(v, p) \
do { \
    if (!(v)->ptrs || (v)->size >= (v)->capacity) \
	(v)->ptrs = XREALLOC((v)->ptrs, ((v)->capacity *= 2) * sizeof(void*)); \
    (v)->ptrs[(v)->size++] = (p); \
} while (0)

#define vector_sort(v, cmp)	qsort((v)->ptrs, (v)->size, sizeof(void*), cmp)
#define vector_free(v)		do { if ((v)->ptrs) FREE((v)->ptrs); } while (0)


#define TRIE_SUB	(-1)
#define TRIE_SUPER	(-2)
#define TRIE_DUP	(-3)

typedef struct TrieNode {
    int children;
    union {
        struct TrieNode **child;
        void *datum;
    } u;
} TrieNode;

typedef int Cmp(const void *, const void *); /* generic compare */

typedef struct ListEntry {
    struct ListEntry *next, *prev;
    void *datum;
} ListEntry;

typedef struct List {
    ListEntry *head, *tail;
} List;

typedef struct HashTable {
    int size;			/* number of buckets */
    Cmp *cmp;
    List **bucket;
} HashTable;

typedef struct CQueue {		/* circular queue of data */
    void **data;		/* array of pointers to data */
    void (*free)(void*, const char*, int);	/* function to free a datum */
    int size;			/* actual number of data currently saved */
    int maxsize;		/* maximum number of data that can be saved */
    int first;			/* position of first datum in circular array */
    int last;			/* position of last datum in circular array */
    int index;			/* current position */
    int total;			/* total number of data ever saved */
} CQueue;

#define init_queue(Q)		(init_list(&(Q)->list))
#define dequeue(Q)		((conString*)((Q)->list.tail ? \
				(unlist((Q)->list.tail, &(Q)->list)) : NULL))
#define enqueue(Q, line)	(inlist((void *)(line), &(Q)->list, NULL))

#define inlist(datum, list, where) \
			inlist_fl((datum), (list), (where), __FILE__, __LINE__)

#define hash_find(name, table)	hashed_find(name, hash_string(name), table)
#define hash_insert(datum, table) \
    hashed_insert(datum, hash_string(*(char**)datum), table)

extern void init_list(List *list);
extern void *unlist(ListEntry *node, List *list);
extern ListEntry *inlist_fl(void *datum, List *list, ListEntry *where,
    const char *file, int line);
extern ListEntry *sinsert(void *datum, List *list, Cmp *cmp);
extern unsigned int hash_string(const char *str);
extern void hash_remove(ListEntry *node, HashTable *table);
extern ListEntry *hashed_insert(void *datum, unsigned int hash,
    HashTable *table);
extern void *hashed_find(const char *name, unsigned int hash,
    HashTable *table);
extern void init_hashtable(HashTable *table, int size, Cmp *cmp);

extern int strstructcmp(const void *key, const void *datum);
extern int cstrstructcmp(const void *key, const void *datum);
extern int strpppcmp(const void *a, const void *b);
extern int cstrpppcmp(const void *a, const void *b);

extern int intrie(TrieNode **root, void *datum,
    const unsigned char *key);
extern TrieNode *untrie(TrieNode **root, const unsigned char *s);
extern void *trie_find(TrieNode *root, const unsigned char *key);

struct CQueue *init_cqueue(CQueue *cq, int maxsize,
    void (*free_f)(void *, const char *, int));
void free_cqueue(CQueue *cq);
void encqueue(CQueue *cq, void *datum);
void cqueue_replace(CQueue *cq, void *datum, int idx);
int resize_cqueue(CQueue *cq, int maxsize);

#if USE_DMALLOC
extern void   free_search(void);
extern void   free_hash(HashTable *table);
#endif

#endif /* SEARCH_H */