]> pd.if.org Git - zpackage/blob - lib/jsw/jsw_atree.c
add zpm wrapper for checking if a db is readonly
[zpackage] / lib / jsw / jsw_atree.c
1 #define _POSIX_C_SOURCE 200809L
2 /*
3   Andersson tree library
4
5     > Created (Julienne Walker): September 10, 2005
6     > Corrections (James Bucanek): April 10, 2006
7       1) Typo in jsw_aerase:
8            up != 0 should be top != 0
9       2) Bug in jsw_aerase:
10            skew ( path[top] ) should be skew ( up )
11            split ( path[top] ) should be split ( up )
12       3) Bug in skew and split macros:
13            Condition should test for nil
14       4) Bug in jsw_aerase:
15            Search for successor should save the path
16 */
17 #include "jsw.h"
18
19 #include <stdlib.h>
20 #include <stdio.h>
21 #include <string.h>
22
23 #ifndef HEIGHT_LIMIT
24 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
25 #endif
26
27 typedef struct jsw_anode {
28   int               level;   /* Horizontal level for balance */
29   void             *data;    /* User-defined content */
30   struct jsw_anode *link[2]; /* Left (0) and right (1) links */
31 } jsw_anode_t;
32
33 struct jsw_atree {
34   jsw_anode_t *root; /* Top of the tree */
35   jsw_anode_t *nil;  /* End of tree sentinel */
36   cmp_f        cmp;  /* Compare two items */
37   dup_f        dup;  /* Clone an item (user-defined) */
38   rel_f        rel;  /* Destroy an item (user-defined) */
39   size_t       size; /* Number of items (user-defined) */
40 };
41
42 struct jsw_atrav {
43   jsw_atree_t *tree;               /* Paired tree */
44   jsw_anode_t *it;                 /* Current node */
45   jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */
46   size_t       top;                /* Top of stack */
47 };
48
49 /* Remove left horizontal links */
50 #define skew(t) do {                                      \
51   if ( t->link[0]->level == t->level && t->level != 0 ) { \
52     jsw_anode_t *save = t->link[0];                       \
53     t->link[0] = save->link[1];                           \
54     save->link[1] = t;                                    \
55     t = save;                                             \
56   }                                                       \
57 } while(0)
58
59 /* Remove consecutive horizontal links */
60 #define split(t) do {                                              \
61   if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \
62     jsw_anode_t *save = t->link[1];                                \
63     t->link[1] = save->link[0];                                    \
64     save->link[0] = t;                                             \
65     t = save;                                                      \
66     ++t->level;                                                    \
67   }                                                                \
68 } while(0)
69
70 int jsw_afind_strcmp(const void *a, const void *b) {
71         return strcmp(a, b);
72 }
73
74 static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )
75 {
76   jsw_anode_t *rn = malloc ( sizeof *rn );
77
78   if ( rn == NULL )
79     return tree->nil;
80
81   rn->level = 1;
82   rn->data = tree->dup ( data );
83   rn->link[0] = rn->link[1] = tree->nil;
84
85   return rn;
86 }
87
88 jsw_atree_t *jsw_anew_str(void) {
89         return jsw_anew(jsw_afind_strcmp, (dup_f)strdup, (rel_f)free);
90 }
91
92 jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )
93 {
94   jsw_atree_t *rt = malloc ( sizeof *rt );
95
96   if ( rt == NULL )
97     return NULL;
98
99   /* Initialize sentinel */
100   rt->nil = malloc ( sizeof *rt->nil );
101   if ( rt->nil == NULL ) {
102     free ( rt );
103     return NULL;
104   }
105
106   rt->nil->data = NULL; /* Simplifies some ops */
107   rt->nil->level = 0;
108   rt->nil->link[0] = rt->nil->link[1] = rt->nil;
109
110   /* Initialize tree */
111   rt->root = rt->nil;
112   rt->cmp = cmp;
113   rt->dup = dup;
114   rt->rel = rel;
115   rt->size = 0;
116
117   return rt;
118 }
119
120 void jsw_adelete(jsw_atree_t *tree) {
121         jsw_anode_t *it;
122         jsw_anode_t *save;
123
124         if (!tree) {
125                 return;
126         }
127
128         it = tree->root;
129
130
131   /* Destruction by rotation */
132   while ( it != tree->nil ) {
133     if ( it->link[0] == tree->nil ) {
134       /* Remove node */
135       save = it->link[1];
136       tree->rel ( it->data );
137       free ( it );
138     }
139     else {
140       /* Rotate right */
141       save = it->link[0];
142       it->link[0] = save->link[1];
143       save->link[1] = it;
144     }
145
146     it = save;
147   }
148
149   /* Finalize destruction */
150   free ( tree->nil );
151   free ( tree );
152 }
153
154 void *jsw_afind ( jsw_atree_t *tree, void *data) {
155   jsw_anode_t *it = tree->root;
156   int cmp = 0;
157
158   while ( it != tree->nil ) {
159     cmp = tree->cmp(it->data, data);
160
161     if ( cmp == 0 )
162       break;
163
164     it = it->link[cmp < 0];
165   }
166
167   /* nil->data == NULL */
168   return it->data;
169 }
170
171 int jsw_ainsert ( jsw_atree_t *tree, void *data )
172 {
173   if ( tree->root == tree->nil ) {
174     /* Empty tree case */
175     tree->root = new_node ( tree, data );
176     if ( tree->root == tree->nil )
177       return 0;
178   }
179   else {
180     jsw_anode_t *it = tree->root;
181     jsw_anode_t *path[HEIGHT_LIMIT];
182     int top = 0, dir;
183
184     /* Find a spot and save the path */
185     for ( ; ; ) {
186       path[top++] = it;
187       dir = tree->cmp ( it->data, data ) < 0;
188
189       if ( it->link[dir] == tree->nil )
190         break;
191
192       it = it->link[dir];
193     }
194
195     /* Create a new item */
196     it->link[dir] = new_node ( tree, data );
197     if ( it->link[dir] == tree->nil )
198       return 0;
199
200     /* Walk back and rebalance */
201     while ( --top >= 0 ) {
202       /* Which child? */
203       if ( top != 0 )
204         dir = path[top - 1]->link[1] == path[top];
205
206       skew ( path[top] );
207       split ( path[top] );
208
209       /* Fix the parent */
210       if ( top != 0 )
211         path[top - 1]->link[dir] = path[top];
212       else
213         tree->root = path[top];
214     }
215   }
216
217   ++tree->size;
218
219   return 1;
220 }
221
222 int jsw_aerase ( jsw_atree_t *tree, void *data )
223 {
224   if ( tree->root == tree->nil )
225     return 0;
226   else {
227     jsw_anode_t *it = tree->root;
228     jsw_anode_t *path[HEIGHT_LIMIT];
229     int top = 0, dir, cmp;
230
231     /* Find node to remove and save path */
232     for ( ; ; ) {
233       path[top++] = it;
234
235       if ( it == tree->nil )
236         return 0;
237
238       cmp = tree->cmp ( it->data, data );
239       if ( cmp == 0 )
240         break;
241
242       dir = cmp < 0;
243       it = it->link[dir];
244     }
245
246     /* Remove the found node */
247     if ( it->link[0] == tree->nil
248       || it->link[1] == tree->nil )
249     {
250       /* Single child case */
251       int dir2 = it->link[0] == tree->nil;
252
253       /* Unlink the item */
254       if ( --top != 0 )
255         path[top - 1]->link[dir] = it->link[dir2];
256       else
257         tree->root = it->link[1];
258
259       tree->rel ( it->data );
260       free ( it );
261     }
262     else {
263       /* Two child case */
264       jsw_anode_t *heir = it->link[1];
265       jsw_anode_t *prev = it;
266
267       while ( heir->link[0] != tree->nil ) {
268         path[top++] = prev = heir;
269         heir = heir->link[0];
270       }
271
272       /*
273         Order is important!
274         (free item, replace item, free heir)
275       */
276       tree->rel ( it->data );
277       it->data = heir->data;
278       prev->link[prev == it] = heir->link[1];
279       free ( heir );
280     }
281
282     /* Walk back up and rebalance */
283     while ( --top >= 0 ) {
284       jsw_anode_t *up = path[top];
285
286       if ( top != 0 )
287         dir = path[top - 1]->link[1] == up;
288
289       /* Rebalance (aka. black magic) */
290       if ( up->link[0]->level < up->level - 1
291         || up->link[1]->level < up->level - 1 )
292       {
293         if ( up->link[1]->level > --up->level )
294           up->link[1]->level = up->level;
295
296         /* Order is important! */
297         skew ( up );
298         skew ( up->link[1] );
299         skew ( up->link[1]->link[1] );
300         split ( up );
301         split ( up->link[1] );
302       }
303
304       /* Fix the parent */
305       if ( top != 0 )
306         path[top - 1]->link[dir] = up;
307       else
308         tree->root = up;
309     }
310   }
311
312   --tree->size;
313
314   return 1;
315 }
316
317 size_t jsw_asize ( jsw_atree_t *tree )
318 {
319   return tree->size;
320 }
321
322 jsw_atrav_t *jsw_atnew ( void )
323 {
324   return malloc ( sizeof ( jsw_atrav_t ) );
325 }
326
327 void jsw_atdelete ( jsw_atrav_t *trav )
328 {
329   free ( trav );
330 }
331
332 /*
333   First step in traversal,
334   handles min and max
335 */
336 static void *start ( jsw_atrav_t *trav,
337   jsw_atree_t *tree, int dir )
338 {
339   trav->tree = tree;
340   trav->it = tree->root;
341   trav->top = 0;
342
343   /* Build a path to work with */
344   if ( trav->it != tree->nil ) {
345     while ( trav->it->link[dir] != tree->nil ) {
346       trav->path[trav->top++] = trav->it;
347       trav->it = trav->it->link[dir];
348     }
349   }
350
351   /* Could be nil, but nil->data == NULL */
352   return trav->it->data;
353 }
354
355 /*
356   Subsequent traversal steps,
357   handles ascending and descending
358 */
359 static void *move ( jsw_atrav_t *trav, int dir )
360 {
361   jsw_anode_t *nil = trav->tree->nil;
362
363   if ( trav->it->link[dir] != nil ) {
364     /* Continue down this branch */
365     trav->path[trav->top++] = trav->it;
366     trav->it = trav->it->link[dir];
367
368     while ( trav->it->link[!dir] != nil ) {
369       trav->path[trav->top++] = trav->it;
370       trav->it = trav->it->link[!dir];
371     }
372   }
373   else {
374     /* Move to the next branch */
375     jsw_anode_t *last;
376
377     do {
378       if ( trav->top == 0 ) {
379         trav->it = nil;
380         break;
381       }
382
383       last = trav->it;
384       trav->it = trav->path[--trav->top];
385     } while ( last == trav->it->link[dir] );
386   }
387
388   /* Could be nil, but nil->data == NULL */
389   return trav->it->data;
390 }
391
392 void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )
393 {
394   return start ( trav, tree, 0 ); /* Min value */
395 }
396
397 void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )
398 {
399   return start ( trav, tree, 1 ); /* Max value */
400 }
401
402 void *jsw_atnext ( jsw_atrav_t *trav )
403 {
404   return move ( trav, 1 ); /* Toward larger items */
405 }
406
407 void *jsw_atprev ( jsw_atrav_t *trav )
408 {
409   return move ( trav, 0 ); /* Toward smaller items */
410 }