3684ff7113db790a4ce3d21d5f31b3f6b12915c1
4 typedef struct aatree aatree
;
5 typedef struct aatree_node aatree_node
;
7 typedef u32 aatree_ptr
;
8 #define AATREE_PTR_NIL 0xffffffff
12 u32 offset
, stride
; /* distance between elements */
15 int (*p_cmp
)( void *a
, void *b
);
16 int (*p_cmpv
)( void *a
, void *v
);
21 aatree_ptr left
, right
;
25 static void *aatree_get_data( aatree
*tree
, aatree_ptr t
)
27 return tree
->base
+ tree
->stride
*t
;
30 static aatree_node
*aatree_get_node( aatree
*tree
, aatree_ptr t
)
32 return tree
->base
+ tree
->stride
*t
+ tree
->offset
;
35 static void aatree_recount( aatree
*tree
, aatree_ptr n
)
37 aatree_node
*pnode
= aatree_get_node( tree
, n
);
40 if( pnode
->left
!= AATREE_PTR_NIL
)
41 pnode
->count
+= aatree_get_node( tree
, pnode
->left
)->count
;
43 if( pnode
->right
!= AATREE_PTR_NIL
)
44 pnode
->count
+= aatree_get_node( tree
, pnode
->right
)->count
;
53 static aatree_ptr
aatree_skew( aatree
*tree
, u32 t
)
55 if( t
== AATREE_PTR_NIL
) return t
;
57 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
58 if( ptnode
->left
== AATREE_PTR_NIL
) return t
;
60 aatree_node
*plnode
= aatree_get_node( tree
, ptnode
->left
);
61 if( plnode
->level
== ptnode
->level
)
63 aatree_ptr l
= ptnode
->left
;
64 ptnode
->left
= plnode
->right
;
67 aatree_recount( tree
, t
);
68 aatree_recount( tree
, l
);
84 static aatree_ptr
aatree_split( aatree
*tree
, aatree_ptr t
)
86 if( t
== AATREE_PTR_NIL
) return t
;
88 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
89 if( ptnode
->right
== AATREE_PTR_NIL
) return t
;
91 aatree_node
*prnode
= aatree_get_node( tree
, ptnode
->right
);
92 if( prnode
->right
== AATREE_PTR_NIL
) return t
;
94 aatree_node
*prrnode
= aatree_get_node( tree
, prnode
->right
);
95 if( ptnode
->level
== prrnode
->level
)
97 aatree_ptr r
= ptnode
->right
;
98 ptnode
->right
= prnode
->left
;
102 aatree_recount( tree
, t
);
103 aatree_recount( tree
, r
);
111 static aatree_ptr
aatree_insert( aatree
*tree
, aatree_ptr t
, aatree_ptr x
)
113 aatree_node
*pxnode
= aatree_get_node( tree
, x
);
115 if( t
== AATREE_PTR_NIL
)
117 pxnode
->left
= AATREE_PTR_NIL
;
118 pxnode
->right
= AATREE_PTR_NIL
;
124 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
125 int cmp_result
= tree
->p_cmp( aatree_get_data( tree
, t
),
126 aatree_get_data( tree
, x
) );
130 if( cmp_result
<= 0 )
131 ptnode
->left
= aatree_insert( tree
, ptnode
->left
, x
);
133 ptnode
->right
= aatree_insert( tree
, ptnode
->right
, x
);
135 t
= aatree_skew( tree
, t
);
136 t
= aatree_split( tree
, t
);
140 static aatree_ptr
aatree_del( aatree
*tree
, aatree_ptr t
, aatree_ptr x
)
142 if( t
== AATREE_PTR_NIL
) return t
;
143 return AATREE_PTR_NIL
; /*TODO*/
150 static aatree_ptr
aatree_kth( aatree
*tree
, aatree_ptr t
, u32 k
)
154 while( t
!= AATREE_PTR_NIL
)
156 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
159 if( ptnode
->left
!= AATREE_PTR_NIL
)
160 j
+= aatree_get_node( tree
, ptnode
->left
)->count
;
180 return AATREE_PTR_NIL
;
183 static aatree_ptr
aatree_ptrof( aatree
*tree
, aatree_ptr t
, void *value
)
185 while( t
!= AATREE_PTR_NIL
)
187 int cmp_result
= tree
->p_cmpv( aatree_get_data( tree
, t
), value
);
189 if( cmp_result
== 0 )
193 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
207 * =============================================================================
210 static void aatree_show_r( aatree
*tree
, aatree_ptr t
, int lvl
,
211 void(*p_show
)(void *data
) )
213 if( t
!= AATREE_PTR_NIL
)
215 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
216 aatree_show_r( tree
, ptnode
->left
, lvl
+1, p_show
);
218 void *data
= aatree_get_data( tree
, t
);
220 for( int i
=0; i
<lvl
; i
++ )
225 printf( " (%d) \n", t
);
227 aatree_show_r( tree
, ptnode
->right
, lvl
+1, p_show
);
231 static void aatree_show( aatree
*tree
, aatree_ptr t
, void(*p_show
)(void *data
))
233 if( t
!= AATREE_PTR_NIL
)
235 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
236 aatree_show( tree
, ptnode
->left
, p_show
);
237 void *data
= aatree_get_data( tree
, t
);
239 for( int i
=0; i
<ptnode
->level
; i
++ )
244 printf( " (%d) \n", t
);
246 aatree_show( tree
, ptnode
->right
, p_show
);
250 static void aatree_show_counts( aatree
*tree
, aatree_ptr t
, int lvl
, int *ln
,
251 void(*p_show
)(void *data
) )
253 if( t
== AATREE_PTR_NIL
) return;
255 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
256 void *data
= aatree_get_data( tree
, t
);
258 aatree_show_counts( tree
, ptnode
->left
, lvl
+1, ln
, p_show
);
260 printf( " %03d| ", *ln
);
263 for( int i
=0; i
<lvl
; i
++ )
269 printf( " (%d, %d) \n", t
, ptnode
->count
);
271 aatree_show_counts( tree
, ptnode
->right
, lvl
+1, ln
, p_show
);
274 #endif /* VG_STORE_H */
285 #include "vg/vg_platform.h"
286 #include "vg/vg_stdint.h"
287 #include "vg/vg_store.h"
288 #include "vg/vg_io.h"
291 typedef struct yoyo_t yoyo_t
;
298 static void yoyo_t_show( void *_data
)
300 yoyo_t
*data
= _data
;
301 printf( "%d ", data
->my_data
);
304 static int yoyo_t_cmpv( void *_a
, void *_v
)
308 return *b
- a
->my_data
;
311 static int yoyo_t_cmp( void *_a
, void *_b
)
313 yoyo_t
*a
= _a
, *b
= _b
;
314 return b
->my_data
- a
->my_data
;
317 int main(int argc
, const char *argv
[])
319 yoyo_t
*allsorts
= malloc( sizeof(yoyo_t
) * 10000 );
322 test
.base
= allsorts
;
323 test
.offset
= offsetof( yoyo_t
, anode
);
324 test
.stride
= sizeof( yoyo_t
);
325 test
.p_cmp
= yoyo_t_cmp
;
326 test
.p_cmpv
= yoyo_t_cmpv
;
328 aatree_ptr root
= AATREE_PTR_NIL
;
330 for( int i
=0; i
<20; i
++ )
332 yoyo_t
*rando
= &allsorts
[i
];
333 rando
->my_data
= vg_randf() * 10.0f
;
334 root
= aatree_insert( &test
, root
, i
);
338 aatree_show_counts( &test
, root
, 0, &ln
, yoyo_t_show
);
341 vg_info( "Ptr of %d: %u\n", value
, aatree_ptrof( &test
, root
, &value
) );
343 for( int i
=0; i
<20; i
++ )
345 yoyo_t
*v
= aatree_get_data(&test
,aatree_kth( &test
, root
, i
));
346 vg_info( "Value of [%d]: %d\n", i
, v
->my_data
);