ee0e91acf04d3e94579b1f62c7dfafda8d322a9d
[vg.git] / vg_store.h
1 #ifndef VG_STORE_H
2 #define VG_STORE_H
3
4 #include "vg_stdint.h"
5 #include "vg_io.h"
6 #include "vg_log.h"
7
8 /*
9 * Anderson tree implementation with extensions:
10 * parents are kept track of
11 * duplicates are allowed
12 * data is never allocated or destroyed here
13 *
14 * TODO: seperate offset,stride,base into 'generic array', seperate pool
15 */
16
17 typedef struct aatree aatree;
18 typedef struct aatree_node aatree_node;
19 typedef struct aatree_pool_node aatree_pool_node;
20
21 typedef u32 aatree_ptr;
22 #define AATREE_PTR_NIL 0xffffffff
23
24 struct aatree
25 {
26 u32 offset, stride; /* distance between elements */
27 void *base;
28
29 int (*p_cmp)( void *a, void *b );
30 };
31
32 #pragma pack(push,1)
33 struct aatree_node
34 {
35 aatree_ptr left, right, parent;
36 u32 level, count;
37 };
38
39 struct aatree_pool_node
40 {
41 aatree_ptr next_free;
42 };
43 #pragma pack(pop)
44
45 /* api
46 * ===========================================================================*/
47
48 /* return a pointer to the start of the data referenced by t */
49 static void *aatree_get_data( aatree *tree, aatree_ptr t );
50
51 /* link node x into the tree with root t */
52 static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x );
53
54 /* delete node x from tree, does not free memory */
55 static aatree_ptr aatree_del( aatree *tree, aatree_ptr x );
56
57 /* get pointer to element in tree with index k */
58 static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k );
59
60 /* get pointer to the element above x */
61 static aatree_ptr aatree_next( aatree *tree, aatree_ptr x );
62
63 /* get pointer by value, returns NIL if not found.
64 *
65 * if duplicates values are present then the result is undefined, but it will be
66 * AN node with that value, just maybe not the first lexicographically
67 */
68 static aatree_ptr aatree_find( aatree *tree, aatree_ptr t, void *value );
69
70 /* implementation
71 * ===========================================================================*/
72
73 static void *aatree_get_data( aatree *tree, aatree_ptr t )
74 {
75 return (u8 *)tree->base + tree->stride*t;
76 }
77
78 static u8 *aatree_node_base( aatree *tree, aatree_ptr t )
79 {
80 return (u8 *)tree->base + tree->stride*t + tree->offset;
81 }
82
83 static aatree_pool_node *aatree_get_pool_node( aatree *tree, aatree_ptr t )
84 {
85 return (aatree_pool_node *)aatree_node_base( tree, t );
86 }
87
88 static aatree_node *aatree_get_node( aatree *tree, aatree_ptr t )
89 {
90 return (aatree_node *)aatree_node_base( tree, t );
91 }
92
93 static void aatree_recount( aatree *tree, aatree_ptr n )
94 {
95 aatree_node *pnode = aatree_get_node( tree, n );
96 pnode->count = 1;
97
98 if( pnode->left != AATREE_PTR_NIL )
99 pnode->count += aatree_get_node( tree, pnode->left )->count;
100
101 if( pnode->right != AATREE_PTR_NIL )
102 pnode->count += aatree_get_node( tree, pnode->right )->count;
103 }
104
105 /* . .
106 * | |
107 * L <- T L -> T
108 * / \ \ -> / / \
109 * A B R A B R
110 */
111 static aatree_ptr aatree_skew( aatree *tree, u32 t )
112 {
113 if( t == AATREE_PTR_NIL ) return t;
114
115 aatree_node *ptnode = aatree_get_node( tree, t );
116 if( ptnode->left == AATREE_PTR_NIL ) return t;
117
118 aatree_node *plnode = aatree_get_node( tree, ptnode->left );
119 if( plnode->level == ptnode->level )
120 {
121 aatree_ptr l = ptnode->left;
122 ptnode->left = plnode->right;
123 plnode->right = t;
124
125 aatree_recount( tree, t );
126 aatree_recount( tree, l );
127
128 plnode->parent = ptnode->parent;
129 ptnode->parent = l;
130 if( ptnode->left != AATREE_PTR_NIL )
131 aatree_get_node( tree, ptnode->left )->parent = t;
132
133 return l;
134 }
135
136 return t;
137 }
138
139 /* . .
140 * | |
141 * T -> R -> X -> R
142 * / / / \
143 * A B T X
144 * / \
145 * A B
146 */
147 static aatree_ptr aatree_split( aatree *tree, aatree_ptr t )
148 {
149 if( t == AATREE_PTR_NIL ) return t;
150
151 aatree_node *ptnode = aatree_get_node( tree, t );
152 if( ptnode->right == AATREE_PTR_NIL ) return t;
153
154 aatree_node *prnode = aatree_get_node( tree, ptnode->right );
155 if( prnode->right == AATREE_PTR_NIL ) return t;
156
157 aatree_node *prrnode = aatree_get_node( tree, prnode->right );
158 if( ptnode->level == prrnode->level )
159 {
160 aatree_ptr r = ptnode->right;
161 ptnode->right = prnode->left;
162 prnode->left = t;
163 prnode->level ++;
164
165 aatree_recount( tree, t );
166 aatree_recount( tree, r );
167
168 prnode->parent = ptnode->parent;
169 ptnode->parent = r;
170 if( ptnode->right != AATREE_PTR_NIL )
171 aatree_get_node( tree, ptnode->right )->parent = t;
172
173 return r;
174 }
175
176 return t;
177 }
178
179 static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x )
180 {
181 aatree_node *pxnode = aatree_get_node( tree, x );
182
183 if( t == AATREE_PTR_NIL )
184 {
185 pxnode->left = AATREE_PTR_NIL;
186 pxnode->right = AATREE_PTR_NIL;
187 pxnode->parent = AATREE_PTR_NIL;
188 pxnode->level = 0;
189 pxnode->count = 1;
190 return x;
191 }
192
193 aatree_node *ptnode = aatree_get_node( tree, t );
194 int cmp_result = tree->p_cmp( aatree_get_data( tree, t ),
195 aatree_get_data( tree, x ) );
196
197 ptnode->count ++;
198
199 if( cmp_result <= 0 )
200 {
201 ptnode->left = aatree_insert( tree, ptnode->left, x );
202 aatree_node *plnode = aatree_get_node( tree, ptnode->left );
203 plnode->parent = t;
204 }
205 else
206 {
207 ptnode->right = aatree_insert( tree, ptnode->right, x );
208 aatree_node *prnode = aatree_get_node( tree, ptnode->right );
209 prnode->parent = t;
210 }
211
212 t = aatree_skew( tree, t );
213 t = aatree_split( tree, t );
214 return t;
215 }
216
217 static void aatree_link_down( aatree *tree, aatree_ptr p, aatree_ptr *pl,
218 aatree_ptr l )
219 {
220 *pl = l;
221
222 if( *pl != AATREE_PTR_NIL )
223 aatree_get_node( tree, *pl )->parent = p;
224 }
225
226 static aatree_ptr aatree_copy_links( aatree *tree, aatree_ptr root,
227 aatree_ptr src, aatree_ptr dst )
228 {
229 aatree_node *pdst = aatree_get_node( tree, dst ),
230 *psrc = aatree_get_node( tree, src );
231
232 pdst->count = psrc->count;
233 pdst->level = psrc->level;
234 pdst->parent = psrc->parent;
235
236 aatree_link_down( tree, dst, &pdst->left, psrc->left );
237 aatree_link_down( tree, dst, &pdst->right, psrc->right );
238
239 if( pdst->parent != AATREE_PTR_NIL )
240 {
241 aatree_node *parent = aatree_get_node( tree, pdst->parent );
242
243 if( parent->left == src )
244 parent->left = dst;
245 else if( parent->right == src )
246 parent->right = dst;
247 }
248 else
249 return dst;
250
251 return root;
252 }
253
254 static aatree_ptr aatree_del( aatree *tree, aatree_ptr x )
255 {
256 aatree_ptr it = x,
257 up[32];
258
259 int count = 1, dir = 0;
260
261 /* TODO: maybe be a better way to do this, without counting back up */
262 for( aatree_node *s = aatree_get_node( tree, x );
263 s->parent != AATREE_PTR_NIL;
264 count ++ )
265 s = aatree_get_node( tree, s->parent );
266
267 int top=0;
268 while(1)
269 {
270 int index = count - (++top);
271
272 up[ index ] = it;
273 aatree_node *itnode = aatree_get_node( tree, it );
274 if( itnode->parent == AATREE_PTR_NIL )
275 break;
276 else
277 it = itnode->parent;
278 }
279
280 aatree_ptr _ptrswap_src = AATREE_PTR_NIL,
281 _ptrswap_dst = AATREE_PTR_NIL;
282
283 aatree_node *pxnode = aatree_get_node( tree, x );
284 aatree_ptr root = up[ count-1 ];
285 if( pxnode->left == AATREE_PTR_NIL || pxnode->right == AATREE_PTR_NIL )
286 {
287 if( --top != 0 )
288 {
289 aatree_node *pnode = aatree_get_node( tree, up[top-1] ),
290 *parent = aatree_get_node( tree, pxnode->parent );
291
292 aatree_ptr next = pxnode->left == AATREE_PTR_NIL?
293 pxnode->right:
294 pxnode->left;
295
296 if( parent->left == x ) pnode->left = next;
297 else pnode->right = next;
298
299 if( next != AATREE_PTR_NIL )
300 {
301 aatree_node *pnext = aatree_get_node( tree, next );
302 pnext->parent = up[top-1];
303 }
304 }
305 else
306 {
307 if( pxnode->right != AATREE_PTR_NIL ) root = pxnode->right;
308 else if( pxnode->left != AATREE_PTR_NIL ) root = pxnode->left;
309 else return AATREE_PTR_NIL;
310
311 aatree_node *newroot = aatree_get_node( tree, root );
312 newroot->parent = AATREE_PTR_NIL;
313 }
314 }
315 else
316 {
317 aatree_ptr heir = pxnode->right,
318 prev = x;
319
320 aatree_node *pheir = aatree_get_node( tree, heir );
321
322 while( pheir->left != AATREE_PTR_NIL )
323 {
324 up[top++] = prev = heir;
325 heir = pheir->left;
326 pheir = aatree_get_node( tree, heir );
327 }
328
329 _ptrswap_dst = heir;
330 _ptrswap_src = x;
331
332 aatree_node *pprev = aatree_get_node( tree, prev );
333
334 if( prev == x )
335 aatree_link_down( tree, prev, &pprev->right, pheir->right );
336 else
337 aatree_link_down( tree, prev, &pprev->left, pheir->right );
338 }
339
340 /* Tail */
341 while( --top >= 0 )
342 {
343 if( top != 0 )
344 {
345 aatree_node *above = aatree_get_node( tree, up[top-1] );
346 dir = above->right == up[top];
347 }
348
349 aatree_recount( tree, up[top] );
350 aatree_node *pntop = aatree_get_node( tree, up[top] );
351
352 if( !(pntop->left == AATREE_PTR_NIL || pntop->right == AATREE_PTR_NIL) )
353 {
354 aatree_node *pnl = aatree_get_node( tree, pntop->left ),
355 *pnr = aatree_get_node( tree, pntop->right );
356
357 if( pnl->level < pntop->level-1 || pnr->level < pntop->level-1 )
358 {
359 if( pnr->level > --pntop->level )
360 pnr->level = pntop->level;
361
362 up[top] = aatree_skew( tree, up[top] );
363
364 aatree_node *ut = aatree_get_node( tree, up[top] );
365 ut->right = aatree_skew( tree, ut->right );
366
367 aatree_node *utr = aatree_get_node( tree, ut->right );
368 utr->right = aatree_skew( tree, utr->right );
369
370 up[top] = aatree_split( tree, up[top] );
371 ut = aatree_get_node( tree, up[top] );
372
373 ut->right = aatree_split( tree, ut->right );
374 }
375 }
376
377 if( top != 0 )
378 {
379 aatree_node *ut1 = aatree_get_node( tree, up[top-1] );
380
381 if( dir == 1 )
382 aatree_link_down( tree, up[top-1], &ut1->right, up[top] );
383 else
384 aatree_link_down( tree, up[top-1], &ut1->left, up[top] );
385 }
386 else
387 {
388 root = up[top];
389 aatree_get_node( tree, root )->parent = AATREE_PTR_NIL;
390 }
391 }
392
393 /* This is our extension to the original non-recursive delete, so no data
394 * has to be moved */
395 if( _ptrswap_dst != AATREE_PTR_NIL )
396 root = aatree_copy_links( tree, root, _ptrswap_src, _ptrswap_dst );
397
398 return root;
399 }
400
401 static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k )
402 {
403 u32 i = 0;
404
405 while( t != AATREE_PTR_NIL )
406 {
407 aatree_node *ptnode = aatree_get_node( tree, t );
408
409 u32 j = i;
410 if( ptnode->left != AATREE_PTR_NIL )
411 j += aatree_get_node( tree, ptnode->left )->count;
412
413 if( j < k )
414 {
415 i = j+1;
416 t = ptnode->right;
417 }
418 else
419 {
420 if( j > k )
421 {
422 t = ptnode->left;
423 }
424 else
425 {
426 return t;
427 }
428 }
429 }
430
431 return AATREE_PTR_NIL;
432 }
433
434 static aatree_ptr aatree_next( aatree *tree, aatree_ptr x )
435 {
436 /* if can go left, go left then all the way right,
437 * else go up, if it was right link accept
438 */
439
440 aatree_node *pnode = aatree_get_node( tree, x );
441 if( pnode->right != AATREE_PTR_NIL )
442 {
443 aatree_ptr next = pnode->right;
444
445 while(1)
446 {
447 aatree_node *pnext = aatree_get_node( tree, next );
448
449 if( pnext->left != AATREE_PTR_NIL )
450 next = pnext->left;
451 else
452 return next;
453 }
454 }
455 else
456 {
457 aatree_ptr next = x;
458
459 while(1)
460 {
461 aatree_node *pnode = aatree_get_node( tree, next );
462
463 if( pnode->parent == AATREE_PTR_NIL )
464 return AATREE_PTR_NIL;
465
466 aatree_node *pabove = aatree_get_node( tree, pnode->parent );
467 if( pabove->left == next )
468 return pnode->parent;
469 else
470 next = pnode->parent;
471 }
472 }
473 }
474
475 static aatree_ptr aatree_find( aatree *tree, aatree_ptr t, void *value )
476 {
477 while( t != AATREE_PTR_NIL )
478 {
479 int cmp_result = tree->p_cmp( aatree_get_data( tree, t ), value );
480
481 if( cmp_result == 0 )
482 return t;
483 else
484 {
485 aatree_node *ptnode = aatree_get_node( tree, t );
486
487 if( cmp_result < 0 )
488 t = ptnode->left;
489 else
490 t = ptnode->right;
491 }
492 }
493 return t;
494 }
495
496 /*
497 * Debugging stuff, everything below is scaffholding and will be removed
498 * =============================================================================
499 */
500
501 static int aatree_verify_split( aatree *tree, aatree_ptr t )
502 {
503 if( t == AATREE_PTR_NIL ) return 1;
504
505 aatree_node *ptnode = aatree_get_node( tree, t );
506 if( ptnode->right == AATREE_PTR_NIL ) return 1;
507
508 aatree_node *prnode = aatree_get_node( tree, ptnode->right );
509 if( prnode->right == AATREE_PTR_NIL ) return 1;
510
511 aatree_node *prrnode = aatree_get_node( tree, prnode->right );
512 if( ptnode->level == prrnode->level )
513 return 0;
514
515 return 1;
516 }
517
518 static int aatree_verify_skew( aatree *tree, aatree_ptr t )
519 {
520 if( t == AATREE_PTR_NIL ) return 1;
521
522 aatree_node *ptnode = aatree_get_node( tree, t );
523 if( ptnode->left == AATREE_PTR_NIL ) return 1;
524
525 aatree_node *plnode = aatree_get_node( tree, ptnode->left );
526 if( plnode->level == ptnode->level )
527 return 0;
528
529 return 1;
530 }
531
532 static int aatree_verify( aatree *tree, aatree_ptr t )
533 {
534 aatree_node *ptnode = aatree_get_node( tree, t );
535 if( ptnode->parent != AATREE_PTR_NIL )
536 {
537 aatree_node *parent = aatree_get_node( tree, ptnode->parent );
538 if( !(parent->left == t || parent->right == t) )
539 return 0;
540 }
541
542 if( ptnode->left != AATREE_PTR_NIL )
543 if( aatree_get_node( tree, ptnode->left )->parent != t )
544 return 0;
545 if( ptnode->right != AATREE_PTR_NIL )
546 if( aatree_get_node( tree, ptnode->right )->parent != t )
547 return 0;
548
549 return aatree_verify_skew( tree, t ) &&
550 aatree_verify_split( tree, t );
551 }
552
553
554 static void aatree_show_r( aatree *tree, aatree_ptr t, int lvl,
555 void(*p_show)(void *data) )
556 {
557 if( t != AATREE_PTR_NIL )
558 {
559 aatree_node *ptnode = aatree_get_node( tree, t );
560 aatree_show_r( tree, ptnode->left, lvl+1, p_show );
561
562 void *data = aatree_get_data( tree, t );
563
564 for( int i=0; i<lvl; i++ )
565 {
566 vg_info( " " );
567 }
568 p_show( data );
569 vg_info( " (%d) \n", t );
570
571 aatree_show_r( tree, ptnode->right, lvl+1, p_show );
572 }
573 }
574
575 static void aatree_show( aatree *tree, aatree_ptr t, void(*p_show)(void *data))
576 {
577 if( t != AATREE_PTR_NIL )
578 {
579 aatree_node *ptnode = aatree_get_node( tree, t );
580 aatree_show( tree, ptnode->left, p_show );
581 void *data = aatree_get_data( tree, t );
582
583 for( int i=0; i<ptnode->level; i++ )
584 {
585 vg_info( " " );
586 }
587 p_show( data );
588 vg_info( " (%d) \n", t );
589
590 aatree_show( tree, ptnode->right, p_show );
591 }
592 }
593
594 static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln,
595 int *err,
596 void(*p_show)(void *data), int show )
597 {
598 if( lvl > 20 )
599 return;
600 if( t == AATREE_PTR_NIL ) return;
601
602 aatree_node *ptnode = aatree_get_node( tree, t );
603 void *data = aatree_get_data( tree, t );
604
605 aatree_show_counts( tree, ptnode->left, lvl+1, ln, err, p_show, show );
606
607 if( show ) vg_info( "%03d| ", *ln );
608 *ln = *ln +1;
609
610 if( show )
611 for( int i=0; i<lvl; i++ )
612 printf( " " );
613
614 if( show )
615 {
616 p_show( data );
617
618 if( ptnode->left != AATREE_PTR_NIL && ptnode->right != AATREE_PTR_NIL )
619 printf( "|" );
620 if( ptnode->left != AATREE_PTR_NIL && ptnode->right == AATREE_PTR_NIL )
621 printf( "/" );
622 if( ptnode->left == AATREE_PTR_NIL && ptnode->right != AATREE_PTR_NIL )
623 printf( "\\" );
624
625 printf( " (%d, %d, parent: %d. V: %d, level: %d) \n", t,
626 ptnode->count, ptnode->parent,
627 aatree_verify( tree, t ), ptnode->level);
628 }
629
630 if( !aatree_verify( tree, t ) )
631 {
632 if( show )
633 vg_info( "error\n" );
634 *err = 1;
635 }
636
637 aatree_show_counts( tree, ptnode->right, lvl+1, ln, err, p_show, show );
638 }
639
640 /*
641 * Pool allocator utility which can be placed in a union with regular aa nodes.
642 */
643
644 static aatree_ptr aatree_init_pool( aatree *info, u32 item_count )
645 {
646 for( aatree_ptr i=0; i<item_count; i++ )
647 {
648 aatree_pool_node *pn = aatree_get_pool_node( info, i );
649
650 if( i==item_count-1 )
651 pn->next_free = AATREE_PTR_NIL;
652 else
653 pn->next_free = i+1;
654 }
655
656 return 0;
657 }
658
659 static aatree_ptr aatree_pool_alloc( aatree *info, aatree_ptr *head )
660 {
661 if( *head == AATREE_PTR_NIL )
662 {
663 vg_error( "No nodes free in pool allocator!\n" );
664 return AATREE_PTR_NIL;
665 }
666 else
667 {
668 aatree_ptr gap = *head;
669 *head = aatree_get_pool_node( info, *head )->next_free;
670 return gap;
671 }
672 }
673
674 static void aatree_pool_free( aatree *info, aatree_ptr node, aatree_ptr *head )
675 {
676 aatree_pool_node *pn = aatree_get_pool_node( info, node );
677 pn->next_free = *head;
678 *head = node;
679 }
680
681 #endif /* VG_STORE_H */