7 > Created (Julienne Walker): September 10, 2005
9 AVL balanced tree library
11 > Created (Julienne Walker): June 17, 2003
12 > Modified (Julienne Walker): September 24, 2005
14 Hash table library using separate chaining
16 > Created (Julienne Walker): August 7, 2005
17 > Modified (Julienne Walker): August 11, 2005
19 Red Black balanced tree library
21 > Created (Julienne Walker): August 23, 2003
22 > Modified (Julienne Walker): March 14, 2008
24 This code is in the public domain. Anyone may
25 use it or change it in any way that they see
26 fit. The author assumes no responsibility for
27 damages incurred through use of the original
28 code or any variations thereof.
30 It is requested, but not required, that due
31 credit is given to the original author and
32 anyone who has modified the code through
33 a header comment, such as this one.
36 /* code modified for inclusion in zpm */
40 /* User-defined item handling */
41 typedef int (*cmp_f) ( const void *p1, const void *p2 );
42 typedef void *(*dup_f) ( void *p );
43 typedef void (*rel_f) ( void *p );
50 typedef struct jsw_atree jsw_atree_t;
51 typedef struct jsw_atrav jsw_atrav_t;
53 /* Andersson tree functions */
54 jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel );
55 void jsw_adelete ( jsw_atree_t *tree );
56 void *jsw_afind ( jsw_atree_t *tree, void *data );
57 int jsw_ainsert ( jsw_atree_t *tree, void *data );
58 int jsw_aerase ( jsw_atree_t *tree, void *data );
59 size_t jsw_asize ( jsw_atree_t *tree );
61 /* Traversal functions */
62 jsw_atrav_t *jsw_atnew ( void );
63 void jsw_atdelete ( jsw_atrav_t *trav );
64 void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree );
65 void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree );
66 void *jsw_atnext ( jsw_atrav_t *trav );
67 void *jsw_atprev ( jsw_atrav_t *trav );
74 typedef struct jsw_avltree jsw_avltree_t;
75 typedef struct jsw_avltrav jsw_avltrav_t;
77 /* AVL tree functions */
78 jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel );
79 void jsw_avldelete ( jsw_avltree_t *tree );
80 void *jsw_avlfind ( jsw_avltree_t *tree, void *data );
81 int jsw_avlinsert ( jsw_avltree_t *tree, void *data );
82 int jsw_avlerase ( jsw_avltree_t *tree, void *data );
83 size_t jsw_avlsize ( jsw_avltree_t *tree );
85 /* Traversal functions */
86 jsw_avltrav_t *jsw_avltnew ( void );
87 void jsw_avltdelete ( jsw_avltrav_t *trav );
88 void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree );
89 void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree );
90 void *jsw_avltnext ( jsw_avltrav_t *trav );
91 void *jsw_avltprev ( jsw_avltrav_t *trav );
97 typedef struct jsw_hash jsw_hash_t;
99 /* Application specific hash function */
100 typedef unsigned (*hash_f) ( const void *key );
102 /* Application specific key copying function */
103 typedef void *(*keydup_f) ( const void *key );
105 /* Application specific data copying function */
106 typedef void *(*itemdup_f) ( const void *item );
108 /* Application specific key deletion function */
109 typedef void (*keyrel_f) ( void *key );
111 /* Application specific data deletion function */
112 typedef void (*itemrel_f) ( void *item );
114 typedef struct jsw_hstat {
115 double load; /* Table load factor: (M chains)/(table size) */
116 double achain; /* Average chain length */
117 size_t lchain; /* Longest chain */
118 size_t schain; /* Shortest non-empty chain */
122 Create a new hash table with a capacity of size, and
123 user defined functions for handling keys and items.
125 Returns: An empty hash table, or NULL on failure.
127 jsw_hash_t *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
128 keydup_f keydup, itemdup_f itemdup,
129 keyrel_f keyrel, itemrel_f itemrel );
131 /* Release all memory used by the hash table */
132 void jsw_hdelete ( jsw_hash_t *htab );
135 Find an item with the selected key
137 Returns: The item, or NULL if not found
139 void *jsw_hfind ( jsw_hash_t *htab, void *key );
142 Insert an item with the selected key
144 Returns: non-zero for success, zero for failure
146 int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item );
149 Remove an item with the selected key
151 Returns: non-zero for success, zero for failure
153 int jsw_herase ( jsw_hash_t *htab, void *key );
156 Grow or shrink the table, this is a slow operation
158 Returns: non-zero for success, zero for failure
160 int jsw_hresize ( jsw_hash_t *htab, size_t new_size );
162 /* Reset the traversal markers to the beginning */
163 void jsw_hreset ( jsw_hash_t *htab );
165 /* Traverse forward by one key */
166 int jsw_hnext ( jsw_hash_t *htab );
168 /* Get the current key */
169 const void *jsw_hkey ( jsw_hash_t *htab );
171 /* Get the current item */
172 void *jsw_hitem ( jsw_hash_t *htab );
174 /* Current number of items in the table */
175 size_t jsw_hsize ( jsw_hash_t *htab );
177 /* Total allowable number of items without resizing */
178 size_t jsw_hcapacity ( jsw_hash_t *htab );
180 /* Get statistics for the hash table */
181 jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab );
188 typedef struct jsw_rbtree jsw_rbtree_t;
189 typedef struct jsw_rbtrav jsw_rbtrav_t;
191 /* Red Black tree functions */
192 jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel );
193 void jsw_rbdelete ( jsw_rbtree_t *tree );
194 void *jsw_rbfind ( jsw_rbtree_t *tree, void *data );
195 int jsw_rbinsert ( jsw_rbtree_t *tree, void *data );
196 int jsw_rberase ( jsw_rbtree_t *tree, void *data );
197 size_t jsw_rbsize ( jsw_rbtree_t *tree );
199 /* Traversal functions */
200 jsw_rbtrav_t *jsw_rbtnew ( void );
201 void jsw_rbtdelete ( jsw_rbtrav_t *trav );
202 void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );
203 void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );
204 void *jsw_rbtnext ( jsw_rbtrav_t *trav );
205 void *jsw_rbtprev ( jsw_rbtrav_t *trav );