]> pd.if.org Git - zpackage/blob - lib/jsw/jsw.h
update for repository installing support
[zpackage] / lib / jsw / jsw.h
1 #ifndef JSW_H
2 #define JSW_H
3
4 /*
5   Andersson tree library
6
7     > Created (Julienne Walker): September 10, 2005
8
9   AVL balanced tree library
10
11     > Created (Julienne Walker): June 17, 2003
12     > Modified (Julienne Walker): September 24, 2005
13
14   Hash table library using separate chaining
15
16     > Created (Julienne Walker): August 7, 2005
17     > Modified (Julienne Walker): August 11, 2005
18
19   Red Black balanced tree library
20
21     > Created (Julienne Walker): August 23, 2003
22     > Modified (Julienne Walker): March 14, 2008
23
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.
29
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.
34 */
35
36 /* code modified for inclusion in zpm */
37
38 #include <stddef.h>
39
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 );
44
45 /*
46  * Andersson tree
47  */
48
49 /* Opaque types */
50 typedef struct jsw_atree jsw_atree_t;
51 typedef struct jsw_atrav jsw_atrav_t;
52
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 );
60
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 );
68
69 /*
70  * AVL tree
71  */
72
73 /* Opaque types */
74 typedef struct jsw_avltree jsw_avltree_t;
75 typedef struct jsw_avltrav jsw_avltrav_t;
76
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 );
84
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 );
92
93 /*
94  * hash table
95  */
96
97 typedef struct jsw_hash jsw_hash_t;
98
99 /* Application specific hash function */
100 typedef unsigned (*hash_f) ( const void *key );
101
102 /* Application specific key copying function */
103 typedef void    *(*keydup_f) ( const void *key );
104
105 /* Application specific data copying function */
106 typedef void    *(*itemdup_f) ( const void *item );
107
108 /* Application specific key deletion function */
109 typedef void     (*keyrel_f) ( void *key );
110
111 /* Application specific data deletion function */
112 typedef void     (*itemrel_f) ( void *item );
113
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 */
119 } jsw_hstat_t;
120
121 /*
122   Create a new hash table with a capacity of size, and
123   user defined functions for handling keys and items.
124
125   Returns: An empty hash table, or NULL on failure.
126 */
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 );
130
131 /* Release all memory used by the hash table */
132 void         jsw_hdelete ( jsw_hash_t *htab );
133
134 /*
135   Find an item with the selected key
136
137   Returns: The item, or NULL if not found
138 */
139 void        *jsw_hfind ( jsw_hash_t *htab, void *key );
140
141 /*
142   Insert an item with the selected key
143
144   Returns: non-zero for success, zero for failure
145 */
146 int          jsw_hinsert ( jsw_hash_t *htab, void *key, void *item );
147
148 /*
149   Remove an item with the selected key
150
151   Returns: non-zero for success, zero for failure
152 */
153 int          jsw_herase ( jsw_hash_t *htab, void *key );
154
155 /*
156   Grow or shrink the table, this is a slow operation
157   
158   Returns: non-zero for success, zero for failure
159 */
160 int          jsw_hresize ( jsw_hash_t *htab, size_t new_size );
161
162 /* Reset the traversal markers to the beginning */
163 void         jsw_hreset ( jsw_hash_t *htab );
164
165 /* Traverse forward by one key */
166 int          jsw_hnext ( jsw_hash_t *htab );
167
168 /* Get the current key */
169 const void  *jsw_hkey ( jsw_hash_t *htab );
170
171 /* Get the current item */
172 void        *jsw_hitem ( jsw_hash_t *htab );
173
174 /* Current number of items in the table */
175 size_t       jsw_hsize ( jsw_hash_t *htab );
176
177 /* Total allowable number of items without resizing */
178 size_t       jsw_hcapacity ( jsw_hash_t *htab );
179
180 /* Get statistics for the hash table */
181 jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab );
182
183 /*
184  * red black tree
185  */
186
187 /* Opaque types */
188 typedef struct jsw_rbtree jsw_rbtree_t;
189 typedef struct jsw_rbtrav jsw_rbtrav_t;
190
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 );
198
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 );
206
207 #endif