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