[Olsr-cvs] olsrd-current/src lq_avl.c, 1.9, 1.10 lq_avl.h, 1.8, 1.9 lq_route.c, 1.46, 1.47 lq_route.h, 1.3, 1.4 net_olsr.c, 1.23, 1.24 olsr.c, 1.54, 1.55
Bernd Petrovitsch
(spam-protected)
Fri Jul 6 00:43:49 CEST 2007
Update of /cvsroot/olsrd/olsrd-current/src
In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv28283/src
Modified Files:
lq_avl.c lq_avl.h lq_route.c lq_route.h net_olsr.c olsr.c
Log Message:
added the SPF refactoring from Hannes Gredler <(spam-protected)>:
1. use of an AVL tree as a min-heap implementation
as a means for efficient sorting.
(the etx metric is used as the key in the candidate tree)
2. next-hop propagation
rather than tracking the previous node in olsr_relax()
i have changed that model and pre-populate all one-hop neighbors
with their own IP adress as 'next-hop' and pull that
pointer up once new paths are explored.
as a result no walker for counting hops and extracting next-hops
is required - it turns out at this is slighly more efficient
than the existing behaviour (even with the cache applied).
Index: lq_route.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.c,v
retrieving revision 1.46
retrieving revision 1.47
diff -C2 -d -r1.46 -r1.47
*** lq_route.c 25 Apr 2007 22:08:09 -0000 1.46
--- lq_route.c 5 Jul 2007 22:43:46 -0000 1.47
***************
*** 3,6 ****
--- 3,7 ----
* Copyright (c) 2004, Thomas Lopatic ((spam-protected))
* IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
+ * SPF implementation (c) 2007, Hannes Gredler ((spam-protected))
* All rights reserved.
*
***************
*** 54,124 ****
#include "lq_route.h"
[...1059 lines suppressed...]
! free_everything(&vertex_list);
// move the route changes into the kernel
--- 755,759 ----
// free the graph
! olsr_free_everything(&vertex_tree);
// move the route changes into the kernel
***************
*** 796,797 ****
--- 767,774 ----
olsr_free_routing_table(old_hna);
}
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: lq_avl.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.h,v
retrieving revision 1.8
retrieving revision 1.9
diff -C2 -d -r1.8 -r1.9
*** lq_avl.h 29 Mar 2007 00:05:50 -0000 1.8
--- lq_avl.h 5 Jul 2007 22:43:46 -0000 1.9
***************
*** 68,72 ****
--- 68,78 ----
void avl_delete(struct avl_tree *, struct avl_node *);
struct avl_node *avl_walk_first(struct avl_tree *);
+ struct avl_node *avl_walk_last(struct avl_tree *);
struct avl_node *avl_walk_next(struct avl_node *);
+ struct avl_node *avl_walk_prev(struct avl_node *);
+
+ extern int (*avl_comp_default)(void *, void *);
+ extern int avl_comp_ipv4(void *, void *);
+ extern int avl_comp_ipv6(void *, void *);
#define inline_avl_comp_ipv4(ip1, ip2) \
***************
*** 75,76 ****
--- 81,88 ----
#endif
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: lq_route.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** lq_route.h 28 Nov 2004 13:43:59 -0000 1.3
--- lq_route.h 5 Jul 2007 22:43:47 -0000 1.4
***************
*** 44,47 ****
--- 44,48 ----
#define INFINITE_ETX ((float)(1 << 30))
+ #define ZERO_ETX 0.0
#define MIN_LINK_QUALITY 0.01
Index: net_olsr.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/net_olsr.c,v
retrieving revision 1.23
retrieving revision 1.24
diff -C2 -d -r1.23 -r1.24
*** net_olsr.c 13 May 2007 22:23:55 -0000 1.23
--- net_olsr.c 5 Jul 2007 22:43:47 -0000 1.24
***************
*** 616,619 ****
--- 616,623 ----
static char buff[4][INET6_ADDRSTRLEN > INET_ADDRSTRLEN ? INET6_ADDRSTRLEN : INET_ADDRSTRLEN];
const char *ret;
+
+ if (!addr) {
+ return "null";
+ }
if(olsr_cnf->ip_version == AF_INET)
Index: lq_avl.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.c,v
retrieving revision 1.9
retrieving revision 1.10
diff -C2 -d -r1.9 -r1.10
*** lq_avl.c 20 Apr 2007 14:23:41 -0000 1.9
--- lq_avl.c 5 Jul 2007 22:43:46 -0000 1.10
***************
*** 43,46 ****
--- 43,47 ----
#include <stddef.h>
#include <time.h>
+ #include <string.h>
#include "lq_avl.h"
***************
*** 49,52 ****
--- 50,70 ----
#define AVLMIN(x, y) ((x < y) ? x : y)
+ /*
+ * dummy comparison pointer
+ * set to zero for a fast inline ipv4 comparison
+ */
+ int (*avl_comp_default)(void *, void *) = 0;
+
+ int avl_comp_ipv4(void *ip1, void *ip2)
+ {
+ return(*(unsigned int *)ip1 == *(unsigned int *)ip2 ? 0 : \
+ *(unsigned int *)ip1 < *(unsigned int *)ip2 ? -1 : +1);
+ }
+
+ int avl_comp_ipv6(void *ip1, void *ip2)
+ {
+ return memcmp(ip1, ip2, 16);
+ }
+
void avl_init(struct avl_tree *tree, int (*comp)(void *, void *))
{
***************
*** 55,64 ****
}
! static struct avl_node *find_rec_ipv4(struct avl_node *node, void *key)
{
if (*(unsigned int *)key < *(unsigned int *)node->key)
{
if (node->left != NULL)
! return find_rec_ipv4(node->left, key);
}
--- 73,82 ----
}
! static struct avl_node *avl_find_rec_ipv4(struct avl_node *node, void *key)
{
if (*(unsigned int *)key < *(unsigned int *)node->key)
{
if (node->left != NULL)
! return avl_find_rec_ipv4(node->left, key);
}
***************
*** 66,70 ****
{
if (node->right != NULL)
! return find_rec_ipv4(node->right, key);
}
--- 84,88 ----
{
if (node->right != NULL)
! return avl_find_rec_ipv4(node->right, key);
}
***************
*** 72,82 ****
}
! static struct avl_node *find_rec(struct avl_node *node, void *key,
! int (*comp)(void *, void *))
{
int diff;
if (0 == comp)
! return find_rec_ipv4(node, key);
diff = (*comp)(key, node->key);
--- 90,100 ----
}
! static struct avl_node *avl_find_rec(struct avl_node *node, void *key,
! int (*comp)(void *, void *))
{
int diff;
if (0 == comp)
! return avl_find_rec_ipv4(node, key);
diff = (*comp)(key, node->key);
***************
*** 85,89 ****
{
if (node->left != NULL)
! return find_rec(node->left, key, comp);
return node;
--- 103,107 ----
{
if (node->left != NULL)
! return avl_find_rec(node->left, key, comp);
return node;
***************
*** 93,97 ****
{
if (node->right != NULL)
! return find_rec(node->right, key, comp);
return node;
--- 111,115 ----
{
if (node->right != NULL)
! return avl_find_rec(node->right, key, comp);
return node;
***************
*** 108,112 ****
return NULL;
! node = find_rec(tree->root, key, tree->comp);
if (0 == tree->comp)
--- 126,130 ----
return NULL;
! node = avl_find_rec(tree->root, key, tree->comp);
if (0 == tree->comp)
***************
*** 125,129 ****
}
! static void rotate_right(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *left, *parent;
--- 143,147 ----
}
! static void avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *left, *parent;
***************
*** 157,161 ****
}
! static void rotate_left(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *right, *parent;
--- 175,179 ----
}
! static void avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *right, *parent;
***************
*** 211,220 ****
if (node->balance == -1)
{
! rotate_right(tree, parent);
return;
}
! rotate_left(tree, node);
! rotate_right(tree, node->parent->parent);
return;
}
--- 229,238 ----
if (node->balance == -1)
{
! avl_rotate_right(tree, parent);
return;
}
! avl_rotate_left(tree, node);
! avl_rotate_right(tree, node->parent->parent);
return;
}
***************
*** 233,246 ****
if (node->balance == 1)
{
! rotate_left(tree, parent);
return;
}
! rotate_right(tree, node);
! rotate_left(tree, node->parent->parent);
return;
}
! static void insert_before(struct avl_node *pos_node, struct avl_node *node)
{
if (pos_node->prev != NULL)
--- 251,264 ----
if (node->balance == 1)
{
! avl_rotate_left(tree, parent);
return;
}
! avl_rotate_right(tree, node);
! avl_rotate_left(tree, node->parent->parent);
return;
}
! static void avl_insert_before(struct avl_node *pos_node, struct avl_node *node)
{
if (pos_node->prev != NULL)
***************
*** 253,257 ****
}
! static void insert_after(struct avl_node *pos_node, struct avl_node *node)
{
if (pos_node->next != NULL)
--- 271,275 ----
}
! static void avl_insert_after(struct avl_node *pos_node, struct avl_node *node)
{
if (pos_node->next != NULL)
***************
*** 264,268 ****
}
! static void remove(struct avl_node *node)
{
if (node->prev != NULL)
--- 282,286 ----
}
! static void avl_remove(struct avl_node *node)
{
if (node->prev != NULL)
***************
*** 296,300 ****
}
! node = find_rec(tree->root, new->key, tree->comp);
last = node;
--- 314,318 ----
}
! node = avl_find_rec(tree->root, new->key, tree->comp);
last = node;
***************
*** 316,320 ****
new->leader = 0;
! insert_after(last, new);
return 0;
}
--- 334,338 ----
new->leader = 0;
! avl_insert_after(last, new);
return 0;
}
***************
*** 322,326 ****
if (node->balance == 1)
{
! insert_before(node, new);
node->balance = 0;
--- 340,344 ----
if (node->balance == 1)
{
! avl_insert_before(node, new);
node->balance = 0;
***************
*** 332,336 ****
if (node->balance == -1)
{
! insert_after(last, new);
node->balance = 0;
--- 350,354 ----
if (node->balance == -1)
{
! avl_insert_after(last, new);
node->balance = 0;
***************
*** 342,346 ****
if (diff < 0)
{
! insert_before(node, new);
node->balance = -1;
--- 360,364 ----
if (diff < 0)
{
! avl_insert_before(node, new);
node->balance = -1;
***************
*** 351,355 ****
}
! insert_after(last, new);
node->balance = 1;
--- 369,373 ----
}
! avl_insert_after(last, new);
node->balance = 1;
***************
*** 360,364 ****
}
! static void post_delete(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *parent;
--- 378,382 ----
}
! static void avl_post_delete(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *parent;
***************
*** 373,377 ****
if (parent->balance == 0)
{
! post_delete(tree, parent);
return;
}
--- 391,395 ----
if (parent->balance == 0)
{
! avl_post_delete(tree, parent);
return;
}
***************
*** 382,386 ****
if (parent->right->balance == 0)
{
! rotate_left(tree, parent);
return;
}
--- 400,404 ----
if (parent->right->balance == 0)
{
! avl_rotate_left(tree, parent);
return;
}
***************
*** 388,399 ****
if (parent->right->balance == 1)
{
! rotate_left(tree, parent);
! post_delete(tree, parent->parent);
return;
}
! rotate_right(tree, parent->right);
! rotate_left(tree, parent);
! post_delete(tree, parent->parent);
return;
}
--- 406,417 ----
if (parent->right->balance == 1)
{
! avl_rotate_left(tree, parent);
! avl_post_delete(tree, parent->parent);
return;
}
! avl_rotate_right(tree, parent->right);
! avl_rotate_left(tree, parent);
! avl_post_delete(tree, parent->parent);
return;
}
***************
*** 403,407 ****
if (parent->balance == 0)
{
! post_delete(tree, parent);
return;
}
--- 421,425 ----
if (parent->balance == 0)
{
! avl_post_delete(tree, parent);
return;
}
***************
*** 412,416 ****
if (parent->left->balance == 0)
{
! rotate_right(tree, parent);
return;
}
--- 430,434 ----
if (parent->left->balance == 0)
{
! avl_rotate_right(tree, parent);
return;
}
***************
*** 418,432 ****
if (parent->left->balance == -1)
{
! rotate_right(tree, parent);
! post_delete(tree, parent->parent);
return;
}
! rotate_left(tree, parent->left);
! rotate_right(tree, parent);
! post_delete(tree, parent->parent);
}
! static struct avl_node *local_min(struct avl_node *node)
{
while (node->left != NULL)
--- 436,450 ----
if (parent->left->balance == -1)
{
! avl_rotate_right(tree, parent);
! avl_post_delete(tree, parent->parent);
return;
}
! avl_rotate_left(tree, parent->left);
! avl_rotate_right(tree, parent);
! avl_post_delete(tree, parent->parent);
}
! static struct avl_node *avl_local_min(struct avl_node *node)
{
while (node->left != NULL)
***************
*** 436,440 ****
}
! static void delete_worker(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *parent, *min;
--- 454,466 ----
}
! static struct avl_node *avl_local_max(struct avl_node *node)
! {
! while (node->right != NULL)
! node = node->right;
!
! return node;
! }
!
! static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
{
struct avl_node *parent, *min;
***************
*** 460,464 ****
if (parent->balance == 0)
{
! post_delete(tree, parent);
return;
}
--- 486,490 ----
if (parent->balance == 0)
{
! avl_post_delete(tree, parent);
return;
}
***************
*** 466,470 ****
if (parent->right->balance == 0)
{
! rotate_left(tree, parent);
return;
}
--- 492,496 ----
if (parent->right->balance == 0)
{
! avl_rotate_left(tree, parent);
return;
}
***************
*** 472,483 ****
if (parent->right->balance == 1)
{
! rotate_left(tree, parent);
! post_delete(tree, parent->parent);
return;
}
! rotate_right(tree, parent->right);
! rotate_left(tree, parent);
! post_delete(tree, parent->parent);
return;
}
--- 498,509 ----
if (parent->right->balance == 1)
{
! avl_rotate_left(tree, parent);
! avl_post_delete(tree, parent->parent);
return;
}
! avl_rotate_right(tree, parent->right);
! avl_rotate_left(tree, parent);
! avl_post_delete(tree, parent->parent);
return;
}
***************
*** 493,497 ****
if (parent->balance == 0)
{
! post_delete(tree, parent);
return;
}
--- 519,523 ----
if (parent->balance == 0)
{
! avl_post_delete(tree, parent);
return;
}
***************
*** 499,503 ****
if (parent->left->balance == 0)
{
! rotate_right(tree, parent);
return;
}
--- 525,529 ----
if (parent->left->balance == 0)
{
! avl_rotate_right(tree, parent);
return;
}
***************
*** 505,516 ****
if (parent->left->balance == -1)
{
! rotate_right(tree, parent);
! post_delete(tree, parent->parent);
return;
}
! rotate_left(tree, parent->left);
! rotate_right(tree, parent);
! post_delete(tree, parent->parent);
return;
}
--- 531,542 ----
if (parent->left->balance == -1)
{
! avl_rotate_right(tree, parent);
! avl_post_delete(tree, parent->parent);
return;
}
! avl_rotate_left(tree, parent->left);
! avl_rotate_right(tree, parent);
! avl_post_delete(tree, parent->parent);
return;
}
***************
*** 534,538 ****
parent->right = node->right;
! post_delete(tree, node->right);
return;
}
--- 560,564 ----
parent->right = node->right;
! avl_post_delete(tree, node->right);
return;
}
***************
*** 555,564 ****
parent->right = node->left;
! post_delete(tree, node->left);
return;
}
! min = local_min(node->right);
! delete_worker(tree, min);
parent = node->parent;
--- 581,590 ----
parent->right = node->left;
! avl_post_delete(tree, node->left);
return;
}
! min = avl_local_min(node->right);
! avl_delete_worker(tree, min);
parent = node->parent;
***************
*** 633,640 ****
else
! delete_worker(tree, node);
}
! remove(node);
}
--- 659,666 ----
else
! avl_delete_worker(tree, node);
}
! avl_remove(node);
}
***************
*** 646,650 ****
return NULL;
! return local_min(node);
}
--- 672,686 ----
return NULL;
! return avl_local_min(node);
! }
!
! struct avl_node *avl_walk_last(struct avl_tree *tree)
! {
! struct avl_node *node = tree->root;
!
! if (node == NULL)
! return NULL;
!
! return avl_local_max(node);
}
***************
*** 653,654 ****
--- 689,701 ----
return node->next;
}
+
+ struct avl_node *avl_walk_prev(struct avl_node *node)
+ {
+ return node->prev;
+ }
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: olsr.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/olsr.c,v
retrieving revision 1.54
retrieving revision 1.55
diff -C2 -d -r1.54 -r1.55
*** olsr.c 25 Apr 2007 22:08:09 -0000 1.54
--- olsr.c 5 Jul 2007 22:43:47 -0000 1.55
***************
*** 61,64 ****
--- 61,65 ----
#include "log.h"
#include "lq_packet.h"
+ #include "lq_avl.h"
#include <stdarg.h>
***************
*** 261,264 ****
--- 262,272 ----
changes_hna = OLSR_FALSE;
+ /* Set avl tree comparator */
+ if (olsr_cnf->ipsize == 4) {
+ avl_comp_default = 0;
+ } else {
+ avl_comp_default = avl_comp_ipv6;
+ }
+
/* Initialize link set */
olsr_init_link_set();
More information about the Olsr-cvs
mailing list