Author: axel Date: 2010-05-17 05:20:36 +0200 (Mon, 17 May 2010) New Revision: 1656
Modified: trunk/batman-experimental/avl.c trunk/batman-experimental/avl.h trunk/batman-experimental/batman.c trunk/batman-experimental/hna.c trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c trunk/batman-experimental/originator.c Log: avl.ch, hna.c batman.c originator.c gsf_map.c allow crawling upwards an avl tree, modify some avl_..() functions...
Modified: trunk/batman-experimental/avl.c =================================================================== --- trunk/batman-experimental/avl.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/avl.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -20,13 +20,14 @@ /* * avl code inspired by: * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx - * where Julienne Walker said ( 28. 2. 2010 12:55): + * where Julienne Walker said (web page from 28. 2. 2010 12:55): * ...Once again, all of the code in this tutorial is in the public domain. * You can do whatever you want with it, but I assume no responsibility * for any damages from improper use. ;-) */
+ #include <stdio.h> #include <string.h> #include <stdlib.h> @@ -38,61 +39,70 @@ #include "avl.h"
-void *avl_find( struct avl_tree *tree, void *key ) + +struct avl_node *avl_find( struct avl_tree *tree, void *key ) { - - struct avl_node *it = tree->root; + struct avl_node *an = tree->root; int cmp;
// Search for a dead path or a matching entry - while ( it && ( cmp = memcmp(it->key, key, tree->key_size) ) ) - it = it->link[ cmp < 0 ]; + while ( an && ( cmp = memcmp(an->key, key, tree->key_size) ) ) + an = an->link[ cmp < 0 ];
- - return it ? it->key : NULL; + return an; }
+struct avl_node *avl_next(struct avl_tree *tree, void *key) +{ + struct avl_node *an = tree->root; + struct avl_node *best = NULL; + int cmp;
-void *avl_next(struct avl_tree *tree, void *key) + while (an) { + + cmp = (memcmp(an->key, key, tree->key_size) <= 0); + + if (an->link[cmp]) { + best = cmp ? best : an; + an = an->link[cmp]; + } else { + return cmp ? best : an; + } + + } + return NULL; +} + +struct avl_node *avl_iterate(struct avl_tree *tree, struct avl_node *an ) { - struct avl_node *it = tree->root; - void *best = NULL;
- if ( !it ) - return NULL; + if ( !an || an->link[1] ) {
- while (it) { + an = an ? an->link[1] : tree->root;
- if ( memcmp(it->key, key, tree->key_size) <= 0 ) { + while ( an && an->link[0] ) + an = an->link[0];
- if (it->link[1]) { - it = it->link[1]; - continue; - } else { - return best; - } + return an; + }
- } else { + struct avl_node *prev = an;
- if (it->link[0]) { - best = it->key; - it = it->link[0]; - continue; - } else { - return it->key; - } + while ((an = an->up)) {
- } + if ( an->link[0] == prev ) + return an;
+ prev = an; }
- paranoia( -500177, 1 ); return NULL; }
+ static struct avl_node *avl_create_node(void *key) { struct avl_node *an = debugMalloc(sizeof (struct avl_node), 327); @@ -106,13 +116,22 @@
static struct avl_node *avl_rotate_single(struct avl_node *root, int dir) { - struct avl_node *save = root->link[!dir]; + struct avl_node *save; int rlh, rrh, slh;
/* Rotate */ - root->link[!dir] = save->link[dir]; + save = root->link[!dir]; + + root->link[!dir] = save->link[dir]; + + if (root->link[!dir]) + root->link[!dir]->up = root; + save->link[dir] = root;
+ if ( root ) + root->up = save; + /* Update balance factors */ rlh = avl_height(root->link[0]); rrh = avl_height(root->link[1]); @@ -127,12 +146,16 @@ static struct avl_node *avl_rotate_double(struct avl_node *root, int dir) { root->link[!dir] = avl_rotate_single(root->link[!dir], !dir); + + if (root->link[!dir]) + root->link[!dir]->up = root; + return avl_rotate_single(root, dir); }
void avl_insert(struct avl_tree *tree, void *key) { - + if (tree->root) {
struct avl_node *it = tree->root; @@ -143,7 +166,8 @@ /* Search for an empty link, save the path */ for (;;) { /* Push direction and node onto stack */ - upd[top] = memcmp(it->key, key, tree->key_size) < 0; +// upd[top] = memcmp(it->key, key, tree->key_size) < 0; + upd[top] = memcmp(it->key, key, tree->key_size) <= 0; up[top++] = it;
if (it->link[upd[top - 1]] == NULL) @@ -154,6 +178,7 @@
/* Insert a new node at the bottom of the tree */ it->link[upd[top - 1]] = avl_create_node(key); + it->link[upd[top - 1]]->up = it;
paranoia(-500178, (it->link[upd[top - 1]] == NULL));
@@ -178,11 +203,15 @@ up[top] = avl_rotate_double(up[top], !upd[top]);
/* Fix parent */ - if (top != 0) + if (top != 0) { up[top - 1]->link[upd[top - 1]] = up[top]; - else + up[top]->up = up[top - 1]; + } else { tree->root = up[0]; + up[0]->up = NULL;
+ } + done = 1; }
@@ -193,7 +222,7 @@
up[top]->balance = max + 1; } - + } else {
tree->root = avl_create_node(key); @@ -206,7 +235,7 @@
-void avl_remove(struct avl_tree *tree, void *key) +void *avl_remove(struct avl_tree *tree, void *key) { struct avl_node *it = tree->root; struct avl_node *up[AVL_MAX_HEIGHT]; @@ -214,29 +243,38 @@
paranoia(-500182, !it); // paranoia if not found
- while ((cmp = memcmp(it->key, key, tree->key_size))) { +// while ((cmp = memcmp(it->key, key, tree->key_size)) ) { + while ((cmp = memcmp(it->key, key, tree->key_size)) || (it->link[0] && !memcmp(it->link[0]->key, key, tree->key_size))) {
// Push direction and node onto stack upd[top] = (cmp < 0); up[top] = it; + top++;
- it = it->link[(cmp < 0)]; - top++; - paranoia(-500180, !it); // paranoia if not found + if (!(it = it->link[(cmp < 0)])) + return NULL; + }
+ // remember and return the found key. It might have been another one than intended + key = it->key; + // Remove the node: if (!(it->link[0] && it->link[1])) { // at least one child is NULL: - + // Which child is not null? int dir = !(it->link[0]);
/* Fix parent */ - if (top) + if (top) { up[top - 1]->link[upd[top - 1]] = it->link[dir]; - else + if (it->link[dir]) + it->link[dir]->up = up[top - 1]; + } else { tree->root = it->link[dir]; - + if (tree->root) + tree->root->up = NULL; + } debugFree(it, 1327);
} else { // both childs NOT NULL: @@ -262,6 +300,9 @@ // Unlink successor and fix parent up[top - 1]->link[ (up[top - 1] == it) ] = heir->link[1];
+ if ( heir->link[1]) + heir->link[1]->up = up[top - 1]; + debugFree(heir, 2327); }
@@ -306,11 +347,292 @@ up[top] = avl_rotate_double(up[top], upd[top]);
// Fix parent: - if (top) + if (top) { up[top - 1]->link[upd[top - 1]] = up[top]; - else + up[top]->up = up[top - 1]; + } else { tree->root = up[0]; + tree->root->up = NULL; + } }
+ return key; + }
+#ifdef AVL_DEBUG + +struct avl_node *_avl_iter_down(int dir, struct avl_node *an, struct avl_iterator *it ) { + + for (; an; it->top++) { + /* Push direction and node onto stack */ + it->up[it->top] = an; + it->upd[it->top] = dir; + + an = an->link[dir]; + } + it->top--; + return it->up[it->top]; +} + +struct avl_node *avl_iter(struct avl_tree *tree, struct avl_iterator *it ) { + + struct avl_node *an = tree->root; + if ( !an ) + return NULL; + + if (!it->up[0]) { + // Get initial element and fill stack: + // go left... + it->top=0; + return _avl_iter_down( 0/*left*/, an, it ); + } + + if ((an = it->up[(it->top)]->link[1])) { + //go one right, then left... + it->upd[it->top] = 1; + it->top++; + return _avl_iter_down(0, an, it); + } + + while (it->top > 0 && it->upd[(it->top) - 1] == 1 /*was: down right*/) { + //so go one back up (up-left = opposite of down right) + it->top--; + } + + if (it->top > 0 && it->upd[(it->top) - 1] == 0 /*was: down left*/) { + //so go one back up (up-right = opposite of down left)): + it->top--; + return it->up[it->top]; + } + + it->up[0] = NULL; + return NULL; +} + +void avl_debug( struct avl_tree *tree ) { + + #define AVL_DBG_COL_CHARS 6 + + int i,j; + + int depth_min = 0; + + struct avl_node *an; + for (an = tree->root; an; an = an->link[0]) + depth_min++; + + int depth_max = depth_min+2; + int width = 1<<depth_max; + + char * dbg_mem = malloc( depth_max * width * AVL_DBG_COL_CHARS + 1); + memset( dbg_mem, ' ', depth_max * width * AVL_DBG_COL_CHARS + 1 ); + + for( i=1; i<=depth_max; i++ ) + dbg_mem[(i*width*AVL_DBG_COL_CHARS)-1] = '\n'; + + dbg_mem[ depth_max * width * AVL_DBG_COL_CHARS ] = 0; + + struct avl_iterator it; + memset ( &it, 0, sizeof( struct avl_iterator ) ); + + while( (an = avl_iter( tree, &it )) ) { + + j = (width - 1) * AVL_DBG_COL_CHARS / 2; + + for (i = 0; i < it.top; i++) { + + int k = ((width - 1) * AVL_DBG_COL_CHARS ); + int l = 4<<i; + int m = ( it.upd[i]?1:-1); + + j = j + (m * k / l); + } + +// dbg_mem[((i * width * AVL_DBG_COL_CHARS) + j)] = 'x'; + + snprintf(&dbg_mem[((i * width * AVL_DBG_COL_CHARS) + j)], AVL_DBG_COL_CHARS, + "%3d/%1d", ((int*) (an->key))[0], ((int*) (an->key))[1]); + + dbg_mem[((i * width * AVL_DBG_COL_CHARS) + j + (AVL_DBG_COL_CHARS-1))] = ' '; + + + printf("%3d/%1d ", ((int*) (an->key))[0], ((int*) (an->key))[1]); + } + + + dbg_mem[ depth_max * width * AVL_DBG_COL_CHARS ] = 0; + + printf("\n-----\n%s\n-----\n", dbg_mem ); + +} +#endif + + +#ifdef AVL_TEST +static void avl_test() +{ + + + struct avl_node *an = NULL; + AVL_TREE(t, sizeof (int)); + + int i; + + struct p { + int i; + int v; + }; + struct p * p; + + + for (i = 0; i <= 19; i++) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 0; + avl_insert(&t, p); + } + + + for (i = 19; i >= 10; i--) { + p = avl_remove(&t, &i); + printf(" removed %d/%d\n", p->i, p->v ); + debugFree( p, 1999 ); + } + + for (i = 9; i >= 0; i--) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 1; + avl_insert(&t, p); + } + + for (i = 5; i <= 15; i++) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 2; + avl_insert(&t, p); + } + + for (i = 3; i <= 9; i++) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = 2; + p->v = i; + avl_insert(&t, p); + } + + printf("\navl_iterate():\n"); + i=0; + an = NULL; + while( (an = avl_iterate( &t, an ) ) ) { + p = ((struct p*)(an->key)); + if ( i > p->i) + printf("\nERROR %d > %d \n", i, p->i); + i = p->i; + printf( "%3d/%1d ", p->i, p->v ); + } + printf("\n"); + +#ifdef AVL_DEBUG + printf("avl_debug():\n"); + avl_debug( &t ); +#endif + + + for (i = 9; i >= 3; i--) { + int v = 2; + if ((p = avl_remove(&t, &v)) ) { + printf(" removed %d/%d\n", p->i, p->v); + debugFree(p, 1999); + } + } + + + for (i = 9; i >= 0; i--) { + if ( (p = avl_remove(&t, &i) ) ) { + printf(" removed %d/%d\n", p->i, p->v); + debugFree(p, 1999); + } + } + + for (i = 0; i <= 19; i++) { + if ((p = avl_remove(&t, &i))) { + printf(" removed %d/%d\n", p->i, p->v); + debugFree(p, 1999); + } else { + printf(" failed rm %d\n", i); + } + } + + + + + + + +/* for (i = 20; i >= 0; i--) { + + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 5; + avl_insert(&t, p); + } +*/ + + i = 0; + + printf("\n"); + + + printf("\navl_next():\n"); + + int32_t j = 0; + while( (an = avl_next( &t, &j )) ) { + p = ((struct p*)(an->key)); + j = p->i; + if ( i > p->i) + printf("\nERROR %d > %d \n", i, p->i); + + i = p->i; + + printf( "N%4d/%1d ", p->i, p->v ); + + if ( i%10 == 0 ) + printf("\n"); + + } + + + printf("\navl_iterate():\n"); + i=0; + while( (an = avl_iterate( &t, an ) ) ) { + p = ((struct p*)(an->key)); + if ( i > p->i) + printf("\nERROR %d > %d \n", i, p->i); + i = p->i; + printf( "%3d/%1d ", p->i, p->v ); + } + printf("\n"); + +#ifdef AVL_DEBUG + printf("avl_debug():\n"); + avl_debug( &t ); +#endif + + + + while( t.root ) { + p = (struct p*)t.root->key; + p = avl_remove( &t, p ); + printf(" removed %d/%d\n", p->i, p->v ); + debugFree( p, 1999 ); + + } + + printf("\n"); + + cleanup_all(CLEANUP_SUCCESS); + + +} +#endif
Modified: trunk/batman-experimental/avl.h =================================================================== --- trunk/batman-experimental/avl.h 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/avl.h 2010-05-17 03:20:36 UTC (rev 1656) @@ -18,24 +18,26 @@ */
/* - * avl code based on: + * avl code inspired by: * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx - * where Julienne Walker said ( 28. 2. 2010 12:55): + * where Julienne Walker said (web page from 28. 2. 2010 12:55): * ...Once again, all of the code in this tutorial is in the public domain. * You can do whatever you want with it, but I assume no responsibility * for any damages from improper use. ;-) */ - #ifndef _AVL_H #define _AVL_H
#include <stdint.h>
+#define AVL_MAX_HEIGHT 128 + struct avl_node { void *key; int balance; - struct avl_node * link[2]; + struct avl_node * up; + struct avl_node * link[2]; };
struct avl_tree { @@ -47,17 +49,27 @@ #define AVL_INIT_TREE(tree, size) do { tree.root = NULL; tree.key_size = (size); } while (0) #define AVL_TREE(tree, size) struct avl_tree (tree) = { (size), NULL }
- -#define AVL_MAX_HEIGHT 128 - #define avl_height(p) ((p) == NULL ? -1 : (p)->balance) #define avl_max(a,b) ((a) > (b) ? (a) : (b))
-void *avl_find( struct avl_tree *tree, void *key ); -void *avl_next( struct avl_tree *tree, void *key ); + +struct avl_node *avl_find( struct avl_tree *tree, void *key ); +struct avl_node *avl_next( struct avl_tree *tree, void *key ); +struct avl_node *avl_iterate(struct avl_tree *tree, struct avl_node *it ); + void avl_insert(struct avl_tree *tree, void *key); -void avl_remove(struct avl_tree *tree, void *key); +void *avl_remove(struct avl_tree *tree, void *key);
+#ifdef AVL_DEBUG +struct avl_iterator { + struct avl_node * up[AVL_MAX_HEIGHT]; + int upd[AVL_MAX_HEIGHT]; + int top; +};
+struct avl_node *avl_iter(struct avl_tree *tree, struct avl_iterator *it ); +void avl_debug( struct avl_tree *tree ); +#endif
-#endif \ No newline at end of file + +#endif
Modified: trunk/batman-experimental/batman.c =================================================================== --- trunk/batman-experimental/batman.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/batman.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -554,6 +554,7 @@ int dbg_ogm_out = 0; static char dbg_ogm_str[MAX_DBG_STR_SIZE + 1]; // TBD: must be checked for overflow when struct orig_node *on; + struct avl_node *an; uint16_t srv_count = 0;
if ( cmd != OPT_APPLY ) @@ -563,7 +564,7 @@
uint32_t orig_ip = 0;
- while ((on = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((on = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) {
orig_ip = on->orig;
Modified: trunk/batman-experimental/hna.c =================================================================== --- trunk/batman-experimental/hna.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/hna.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -47,8 +47,8 @@ // an hna entry for the given hna address, anetmask, and atype static struct hna_node *get_hna_node( struct hna_key *hk, uint8_t create ) { - struct hna_node *hn; - hn = ((struct hna_node *)avl_find( &hna_avl, hk )); + struct avl_node *an = avl_find( &hna_avl, hk ); + struct hna_node *hn = an ? (struct hna_node*) an->key : NULL; if ( hn ) { @@ -198,7 +198,8 @@ uint16_t array_len = 0;
struct hna_key hk = {0,{0,0}}; - while ( (hn = avl_next( &hna_avl, &hk))) { + struct avl_node *an; + while ((hn = ((an = avl_next(&hna_avl, &hk)) ? an->key : NULL))) { hk = hn->key; if ( hn->status == HNA_HASH_NODE_MYONE ) { @@ -386,6 +387,7 @@ struct hna_key key; struct hna_node *hn; struct orig_node *orig_node; + struct avl_node *an; if ( cmd == OPT_APPLY ) { @@ -393,7 +395,7 @@
uint32_t orig_ip = 0;
- while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) {
orig_ip = orig_node->orig;
Modified: trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c =================================================================== --- trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -145,13 +145,14 @@ if ( cmd == OPT_APPLY && cn ) { struct orig_node *orig_node; + struct avl_node *an; uint32_t count=0;
dbg_printf( cn, "\nall_nodes = {\n" " '%s' : {\n", ipStr(primary_addr) );
uint32_t orig_ip = 0;
- while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an=avl_next(&orig_avl, &orig_ip)) ? an->key : NULL ))) {
orig_ip = orig_node->orig;
Modified: trunk/batman-experimental/originator.c =================================================================== --- trunk/batman-experimental/originator.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/originator.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -922,11 +922,11 @@ static int8_t validate_considered_order( struct orig_node *orig_node, SQ_TYPE seqno, uint32_t neigh, struct batman_if *iif ) {
- - struct neigh_node *nn; struct neigh_node_key key = {neigh, iif}; + struct avl_node *an = avl_find( &orig_node->neigh_avl, &key ); + struct neigh_node *nn = an ? (struct neigh_node*) an->key : NULL;
- if ( (nn = (struct neigh_node*)avl_find( &orig_node->neigh_avl, &key )) ) { + if (nn) {
paranoia( -500198, (nn->nnkey_addr != neigh || nn->nnkey_iif != iif ) );
@@ -960,8 +960,10 @@ struct orig_node *get_orig_node( uint32_t addr, uint8_t create ) { prof_start( PROF_get_orig_node ); - struct orig_node *orig_node = ((struct orig_node *)avl_find( &orig_avl, &addr)); + struct avl_node *an = avl_find( &orig_avl, &addr);
+ struct orig_node *orig_node = an ? (struct orig_node *) an->key : NULL; + if ( !create ) { prof_stop( PROF_get_orig_node ); return orig_node; @@ -1017,6 +1019,7 @@ prof_start( PROF_purge_originator ); struct list_head *neigh_pos, *neigh_temp, *neigh_prev; struct orig_node *orig_node = NULL; + struct avl_node *an; struct neigh_node *neigh_node; static char neigh_str[ADDR_STR_LEN]; @@ -1027,7 +1030,7 @@ /* for all origins... */ uint32_t orig_ip = 0;
- while ( (orig_node = (struct orig_node*)avl_next( &orig_avl, &orig_ip ) ) ) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) {
orig_ip = orig_node->orig;
@@ -1512,6 +1515,7 @@ int32_t opt_show_origs ( uint8_t cmd, uint8_t _save, struct opt_type *opt, struct opt_parent *patch, struct ctrl_node *cn ) { struct orig_node *orig_node; + struct avl_node *an; uint16_t batman_count = 0; int dbg_ogm_out = 0, rq, tq, rtq; @@ -1530,7 +1534,7 @@ "knownSince lsqn(diff) lvld pws ~ogi cpu hop\n"); uint32_t orig_ip = 0;
- while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) {
orig_ip = orig_node->orig;
@@ -1612,9 +1616,9 @@
uint32_t orig_ip = 0; struct link_node * ln; - - while ((ln = (struct link_node*) avl_next(&link_avl, &orig_ip))) {
+ while ((ln = (struct link_node*) ((an = avl_next(&link_avl, &orig_ip)) ? an->key : NULL))) { + orig_ip = ln->orig_addr;
/* @@ -1683,7 +1687,7 @@ uint32_t orig_ip = 0;
- while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) {
orig_ip = orig_node->orig;