r1656 - in trunk/batman-experimental: . lib/bmx_gsf_map - commits - lists.open-mesh.org

17 May 2010

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;

    