1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
/*************************************************************************
* 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 */
|
