Use splay trees instead of AVL trees.

diff --git a/lib/Makefile.am b/lib/Makefile.am
index 57436fd..0f597bb 100644 (file)
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -5,11 +5,11 @@ noinst_LIBRARIES = libvpn.a
 
 INCLUDES = @INCLUDES@ -I. -I$(top_builddir)
 
-libvpn_a_SOURCES = xmalloc.c pidfile.c utils.c getopt.c getopt1.c list.c avl_tree.c dropin.c fake-getaddrinfo.c fake-getnameinfo.c
+libvpn_a_SOURCES = xmalloc.c pidfile.c utils.c getopt.c getopt1.c list.c splay_tree.c dropin.c fake-getaddrinfo.c fake-getnameinfo.c
 
 libvpn_a_LIBADD = @LIBOBJS@ @ALLOCA@
 libvpn_a_DEPENDENCIES = $(libvpn_a_LIBADD)
 
-noinst_HEADERS = xalloc.h pidfile.h utils.h getopt.h list.h avl_tree.h dropin.h fake-getaddrinfo.h fake-getnameinfo.h fake-gai-errnos.h gettext.h ipv6.h ipv4.h ethernet.h
+noinst_HEADERS = xalloc.h pidfile.h utils.h getopt.h list.h splay_tree.h dropin.h fake-getaddrinfo.h fake-getnameinfo.h fake-gai-errnos.h gettext.h ipv6.h ipv4.h ethernet.h
 
 EXTRA_DIST = 

diff --git a/src/conf.c b/src/conf.c
index 87e2ec5..49b78bb 100644 (file)
--- a/src/conf.c
+++ b/src/conf.c
@@ -24,14 +24,14 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "logger.h"
 #include "netutl.h"                            /* for str2address */
 #include "utils.h"                             /* for cp */
 #include "xalloc.h"
 
-avl_tree_t *config_tree;
+splay_tree_t *config_tree;
 
 int pinginterval = 0;                  /* seconds between pings */
 int pingtimeout = 0;                   /* seconds to wait for response */
@@ -54,16 +54,16 @@ static int config_compare(const config_t *a, const config_t *b) {
                return strcmp(a->file, b->file);
 }
 
-void init_configuration(avl_tree_t ** config_tree) {
+void init_configuration(splay_tree_t ** config_tree) {
        cp();
 
-       *config_tree = avl_alloc_tree((avl_compare_t) config_compare, (avl_action_t) free_config);
+       *config_tree = splay_alloc_tree((splay_compare_t) config_compare, (splay_action_t) free_config);
 }
 
-void exit_configuration(avl_tree_t ** config_tree) {
+void exit_configuration(splay_tree_t ** config_tree) {
        cp();
 
-       avl_delete_tree(*config_tree);
+       splay_delete_tree(*config_tree);
        *config_tree = NULL;
 }
 
@@ -88,13 +88,13 @@ void free_config(config_t *cfg) {
        free(cfg);
 }
 
-void config_add(avl_tree_t *config_tree, config_t *cfg) {
+void config_add(splay_tree_t *config_tree, config_t *cfg) {
        cp();
 
-       avl_insert(config_tree, cfg);
+       splay_insert(config_tree, cfg);
 }
 
-config_t *lookup_config(avl_tree_t *config_tree, char *variable) {
+config_t *lookup_config(splay_tree_t *config_tree, char *variable) {
        config_t cfg, *found;
 
        cp();
@@ -103,7 +103,7 @@ config_t *lookup_config(avl_tree_t *config_tree, char *variable) {
        cfg.file = "";
        cfg.line = 0;
 
-       found = avl_search_closest_greater(config_tree, &cfg);
+       found = splay_search_closest_greater(config_tree, &cfg);
 
        if(!found)
                return NULL;
@@ -114,13 +114,13 @@ config_t *lookup_config(avl_tree_t *config_tree, char *variable) {
        return found;
 }
 
-config_t *lookup_config_next(avl_tree_t *config_tree, const config_t *cfg) {
-       avl_node_t *node;
+config_t *lookup_config_next(splay_tree_t *config_tree, const config_t *cfg) {
+       splay_node_t *node;
        config_t *found;
 
        cp();
 
-       node = avl_search_node(config_tree, cfg);
+       node = splay_search_node(config_tree, cfg);
 
        if(node) {
                if(node->next) {
@@ -303,7 +303,7 @@ static char *readline(FILE * fp, char **buf, size_t *buflen) {
   Parse a configuration file and put the results in the configuration tree
   starting at *base.
 */
-int read_config_file(avl_tree_t *config_tree, const char *fname) {
+int read_config_file(splay_tree_t *config_tree, const char *fname) {
        int err = -2;                           /* Parse error */
        FILE *fp;
        char *buffer, *line;

diff --git a/src/conf.h b/src/conf.h
index 1494e96..ee20c29 100644 (file)
--- a/src/conf.h
+++ b/src/conf.h
@@ -23,7 +23,7 @@
 #ifndef __TINC_CONF_H__
 #define __TINC_CONF_H__
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 
 typedef struct config_t {
        char *variable;
@@ -34,7 +34,7 @@ typedef struct config_t {
 
 #include "subnet.h"
 
-extern avl_tree_t *config_tree;
+extern splay_tree_t *config_tree;
 
 extern int pinginterval;
 extern int pingtimeout;
@@ -43,20 +43,20 @@ extern bool bypass_security;
 extern char *confbase;
 extern char *netname;
 
-extern void init_configuration(avl_tree_t **);
-extern void exit_configuration(avl_tree_t **);
+extern void init_configuration(splay_tree_t **);
+extern void exit_configuration(splay_tree_t **);
 extern config_t *new_config(void) __attribute__ ((__malloc__));
 extern void free_config(config_t *);
-extern void config_add(avl_tree_t *, config_t *);
-extern config_t *lookup_config(avl_tree_t *, char *);
-extern config_t *lookup_config_next(avl_tree_t *, const config_t *);
+extern void config_add(splay_tree_t *, config_t *);
+extern config_t *lookup_config(splay_tree_t *, char *);
+extern config_t *lookup_config_next(splay_tree_t *, const config_t *);
 extern bool get_config_bool(const config_t *, bool *);
 extern bool get_config_int(const config_t *, int *);
 extern bool get_config_string(const config_t *, char **);
 extern bool get_config_address(const config_t *, struct addrinfo **);
 extern bool get_config_subnet(const config_t *, struct subnet_t **);
 
-extern int read_config_file(avl_tree_t *, const char *);
+extern int read_config_file(splay_tree_t *, const char *);
 extern bool read_server_config(void);
 extern FILE *ask_and_open(const char *, const char *, const char *);
 extern bool is_safe_path(const char *);

diff --git a/src/connection.c b/src/connection.c
index 58e2d35..408ef6c 100644 (file)
--- a/src/connection.c
+++ b/src/connection.c
@@ -22,7 +22,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "list.h"
 #include "logger.h"
@@ -32,7 +32,7 @@
 #include "utils.h"
 #include "xalloc.h"
 
-avl_tree_t *connection_tree;   /* Meta connections */
+splay_tree_t *connection_tree; /* Meta connections */
 connection_t *broadcast;
 
 static int connection_compare(const connection_t *a, const connection_t *b) {
@@ -42,7 +42,7 @@ static int connection_compare(const connection_t *a, const connection_t *b) {
 void init_connections(void) {
        cp();
 
-       connection_tree = avl_alloc_tree((avl_compare_t) connection_compare, (avl_action_t) free_connection);
+       connection_tree = splay_alloc_tree((splay_compare_t) connection_compare, (splay_action_t) free_connection);
        broadcast = new_connection();
        broadcast->name = xstrdup(_("everyone"));
        broadcast->hostname = xstrdup(_("BROADCAST"));
@@ -51,7 +51,7 @@ void init_connections(void) {
 void exit_connections(void) {
        cp();
 
-       avl_delete_tree(connection_tree);
+       splay_delete_tree(connection_tree);
        free_connection(broadcast);
 }
 
@@ -102,17 +102,17 @@ void free_connection(connection_t *c) {
 void connection_add(connection_t *c) {
        cp();
 
-       avl_insert(connection_tree, c);
+       splay_insert(connection_tree, c);
 }
 
 void connection_del(connection_t *c) {
        cp();
 
-       avl_delete(connection_tree, c);
+       splay_delete(connection_tree, c);
 }
 
 void dump_connections(void) {
-       avl_node_t *node;
+       splay_node_t *node;
        connection_t *c;
 
        cp();

diff --git a/src/connection.h b/src/connection.h
index 92cd23b..9906f0d 100644 (file)
--- a/src/connection.h
+++ b/src/connection.h
@@ -28,7 +28,7 @@
 
 #include <event.h>
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 
 #define OPTION_INDIRECT                0x0001
 #define OPTION_TCPONLY         0x0002
@@ -105,10 +105,10 @@ typedef struct connection_t {
 
        time_t last_ping_time;          /* last time we saw some activity from the other end or pinged them */
 
-       avl_tree_t *config_tree;        /* Pointer to configuration tree belonging to him */
+       splay_tree_t *config_tree;      /* Pointer to configuration tree belonging to him */
 } connection_t;
 
-extern avl_tree_t *connection_tree;
+extern splay_tree_t *connection_tree;
 extern connection_t *broadcast;
 
 extern void init_connections(void);

diff --git a/src/edge.c b/src/edge.c
index 97a57a6..861b945 100644 (file)
--- a/src/edge.c
+++ b/src/edge.c
@@ -22,7 +22,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "edge.h"
 #include "logger.h"
 #include "netutl.h"
@@ -30,7 +30,7 @@
 #include "utils.h"
 #include "xalloc.h"
 
-avl_tree_t *edge_weight_tree;  /* Tree with all edges, sorted on weight */
+splay_tree_t *edge_weight_tree;        /* Tree with all edges, sorted on weight */
 
 static int edge_compare(const edge_t *a, const edge_t *b) {
        return strcmp(a->to->name, b->to->name);
@@ -55,25 +55,25 @@ static int edge_weight_compare(const edge_t *a, const edge_t *b) {
 void init_edges(void) {
        cp();
 
-       edge_weight_tree = avl_alloc_tree((avl_compare_t) edge_weight_compare, NULL);
+       edge_weight_tree = splay_alloc_tree((splay_compare_t) edge_weight_compare, NULL);
 }
 
-avl_tree_t *new_edge_tree(void) {
+splay_tree_t *new_edge_tree(void) {
        cp();
 
-       return avl_alloc_tree((avl_compare_t) edge_compare, (avl_action_t) free_edge);
+       return splay_alloc_tree((splay_compare_t) edge_compare, (splay_action_t) free_edge);
 }
 
-void free_edge_tree(avl_tree_t *edge_tree) {
+void free_edge_tree(splay_tree_t *edge_tree) {
        cp();
 
-       avl_delete_tree(edge_tree);
+       splay_delete_tree(edge_tree);
 }
 
 void exit_edges(void) {
        cp();
 
-       avl_delete_tree(edge_weight_tree);
+       splay_delete_tree(edge_weight_tree);
 }
 
 /* Creation and deletion of connection elements */
@@ -95,8 +95,8 @@ void free_edge(edge_t *e) {
 void edge_add(edge_t *e) {
        cp();
 
-       avl_insert(edge_weight_tree, e);
-       avl_insert(e->from->edge_tree, e);
+       splay_insert(edge_weight_tree, e);
+       splay_insert(e->from->edge_tree, e);
 
        e->reverse = lookup_edge(e->to, e->from);
 
@@ -110,8 +110,8 @@ void edge_del(edge_t *e) {
        if(e->reverse)
                e->reverse->reverse = NULL;
 
-       avl_delete(edge_weight_tree, e);
-       avl_delete(e->from->edge_tree, e);
+       splay_delete(edge_weight_tree, e);
+       splay_delete(e->from->edge_tree, e);
 }
 
 edge_t *lookup_edge(node_t *from, node_t *to) {
@@ -122,11 +122,11 @@ edge_t *lookup_edge(node_t *from, node_t *to) {
        v.from = from;
        v.to = to;
 
-       return avl_search(from->edge_tree, &v);
+       return splay_search(from->edge_tree, &v);
 }
 
 void dump_edges(void) {
-       avl_node_t *node, *node2;
+       splay_node_t *node, *node2;
        node_t *n;
        edge_t *e;
        char *address;

diff --git a/src/edge.h b/src/edge.h
index 8375920..082ea5d 100644 (file)
--- a/src/edge.h
+++ b/src/edge.h
@@ -23,7 +23,7 @@
 #ifndef __TINC_EDGE_H__
 #define __TINC_EDGE_H__
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "connection.h"
 #include "net.h"
 #include "node.h"
@@ -40,14 +40,14 @@ typedef struct edge_t {
        struct edge_t *reverse;         /* edge in the opposite direction, if available */
 } edge_t;
 
-extern avl_tree_t *edge_weight_tree;   /* Tree with all known edges sorted on weight */
+extern splay_tree_t *edge_weight_tree; /* Tree with all known edges sorted on weight */
 
 extern void init_edges(void);
 extern void exit_edges(void);
 extern edge_t *new_edge(void) __attribute__ ((__malloc__));
 extern void free_edge(edge_t *);
-extern avl_tree_t *new_edge_tree(void) __attribute__ ((__malloc__));
-extern void free_edge_tree(avl_tree_t *);
+extern splay_tree_t *new_edge_tree(void) __attribute__ ((__malloc__));
+extern void free_edge_tree(splay_tree_t *);
 extern void edge_add(edge_t *);
 extern void edge_del(edge_t *);
 extern edge_t *lookup_edge(struct node_t *, struct node_t *);

diff --git a/src/graph.c b/src/graph.c
index c04cef4..5bf6361 100644 (file)
--- a/src/graph.c
+++ b/src/graph.c
@@ -46,7 +46,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "config.h"
 #include "connection.h"
 #include "device.h"
@@ -64,7 +64,7 @@
 */
 
 void mst_kruskal(void) {
-       avl_node_t *node, *next;
+       splay_node_t *node, *next;
        edge_t *e;
        node_t *n;
        connection_t *c;
@@ -147,7 +147,7 @@ void mst_kruskal(void) {
 */
 
 void sssp_bfs(void) {
-       avl_node_t *node, *next, *to;
+       splay_node_t *node, *next, *to;
        edge_t *e;
        node_t *n;
        list_t *todo_list;
@@ -223,7 +223,7 @@ void sssp_bfs(void) {
                        e->to->options = e->options;
 
                        if(sockaddrcmp(&e->to->address, &e->address)) {
-                               node = avl_unlink(node_udp_tree, e->to);
+                               node = splay_unlink(node_udp_tree, e->to);
                                sockaddrfree(&e->to->address);
                                sockaddrcpy(&e->to->address, &e->address);
 
@@ -233,7 +233,7 @@ void sssp_bfs(void) {
                                e->to->hostname = sockaddr2hostname(&e->to->address);
 
                                if(node)
-                                       avl_insert_node(node_udp_tree, node);
+                                       splay_insert_node(node_udp_tree, node);
 
                                if(e->to->options & OPTION_PMTU_DISCOVERY) {
                                        e->to->mtuprobes = 0;
@@ -265,11 +265,11 @@ void sssp_bfs(void) {
                        if(n->status.reachable) {
                                ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became reachable"),
                                           n->name, n->hostname);
-                               avl_insert(node_udp_tree, n);
+                               splay_insert(node_udp_tree, n);
                        } else {
                                ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became unreachable"),
                                           n->name, n->hostname);
-                               avl_delete(node_udp_tree, n);
+                               splay_delete(node_udp_tree, n);
                        }
 
                        n->status.validkey = false;
@@ -314,7 +314,7 @@ void sssp_bfs(void) {
 */
 
 static void dump_graph(int fd, short events, void *data) {
-       avl_node_t *node;
+       splay_node_t *node;
        node_t *n;
        edge_t *e;
        char *filename = NULL, *tmpname = NULL;

diff --git a/src/meta.c b/src/meta.c
index 4ed1384..af37d01 100644 (file)
--- a/src/meta.c
+++ b/src/meta.c
@@ -25,7 +25,7 @@
 #include <openssl/err.h>
 #include <openssl/evp.h>
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "connection.h"
 #include "logger.h"
 #include "meta.h"
@@ -122,7 +122,7 @@ void flush_meta(int fd, short events, void *data) {
 }
 
 void broadcast_meta(connection_t *from, const char *buffer, int length) {
-       avl_node_t *node;
+       splay_node_t *node;
        connection_t *c;
 
        cp();

diff --git a/src/net.c b/src/net.c
index 33d90da..469f10f 100644 (file)
--- a/src/net.c
+++ b/src/net.c
@@ -25,7 +25,7 @@
 #include <openssl/rand.h>
 
 #include "utils.h"
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "device.h"
@@ -42,7 +42,7 @@
 /* Purge edges and subnets of unreachable nodes. Use carefully. */
 
 static void purge(void) {
-       avl_node_t *nnode, *nnext, *enode, *enext, *snode, *snext;
+       splay_node_t *nnode, *nnext, *enode, *enext, *snode, *snext;
        node_t *n;
        edge_t *e;
        subnet_t *s;
@@ -105,7 +105,7 @@ static void purge(void) {
   While we're at it, purge stuf that needs to be removed.
 */
 static int build_fdset(void) {
-       avl_node_t *node, *next;
+       splay_node_t *node, *next;
        connection_t *c;
        int i, max = 0;
 
@@ -198,7 +198,7 @@ void terminate_connection(connection_t *c, bool report) {
   and close the connection.
 */
 static void timeout_handler(int fd, short events, void *event) {
-       avl_node_t *node, *next;
+       splay_node_t *node, *next;
        connection_t *c;
        time_t now = time(NULL);
 
@@ -315,7 +315,7 @@ static void sigwinch_handler(int signal, short events, void *data) {
 
 static void sighup_handler(int signal, short events, void *data) {
        connection_t *c;
-       avl_node_t *node;
+       splay_node_t *node;
        char *fname;
        struct stat s;
        static time_t last_config_check = 0;
@@ -363,7 +363,7 @@ static void sigalrm_handler(int signal, short events, void *data) {
        logger(LOG_NOTICE, _("Got %s signal"), strsignal(signal));
 
        connection_t *c;
-       avl_node_t *node;
+       splay_node_t *node;
 
        for(node = connection_tree->head; node; node = node->next) {
                c = node->data;

diff --git a/src/net_packet.c b/src/net_packet.c
index 4269d42..2a86d65 100644 (file)
--- a/src/net_packet.c
+++ b/src/net_packet.c
@@ -31,7 +31,7 @@
 #include <zlib.h>
 #include LZO1X_H
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "device.h"
@@ -438,7 +438,7 @@ void send_packet(const node_t *n, vpn_packet_t *packet) {
 /* Broadcast a packet using the minimum spanning tree */
 
 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
-       avl_node_t *node;
+       splay_node_t *node;
        connection_t *c;
 
        cp();

diff --git a/src/net_setup.c b/src/net_setup.c
index 327cdcc..c5f776a 100644 (file)
--- a/src/net_setup.c
+++ b/src/net_setup.c
@@ -28,7 +28,7 @@
 #include <openssl/err.h>
 #include <openssl/evp.h>
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "device.h"
@@ -609,7 +609,7 @@ bool setup_network_connections(void) {
   close all open network connections
 */
 void close_network_connections(void) {
-       avl_node_t *node, *next;
+       splay_node_t *node, *next;
        connection_t *c;
        char *envp[5];
        int i;

diff --git a/src/net_socket.c b/src/net_socket.c
index 9c8ef05..ec774f6 100644 (file)
--- a/src/net_socket.c
+++ b/src/net_socket.c
@@ -22,7 +22,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "logger.h"

diff --git a/src/node.c b/src/node.c
index 9d4d2f4..cbafe71 100644 (file)
--- a/src/node.c
+++ b/src/node.c
@@ -22,7 +22,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "logger.h"
 #include "net.h"
 #include "netutl.h"
@@ -30,8 +30,8 @@
 #include "utils.h"
 #include "xalloc.h"
 
-avl_tree_t *node_tree;                 /* Known nodes, sorted by name */
-avl_tree_t *node_udp_tree;             /* Known nodes, sorted by address and port */
+splay_tree_t *node_tree;                       /* Known nodes, sorted by name */
+splay_tree_t *node_udp_tree;           /* Known nodes, sorted by address and port */
 
 node_t *myself;
 
@@ -55,15 +55,15 @@ static int node_udp_compare(const node_t *a, const node_t *b) {
 void init_nodes(void) {
        cp();
 
-       node_tree = avl_alloc_tree((avl_compare_t) node_compare, (avl_action_t) free_node);
-       node_udp_tree = avl_alloc_tree((avl_compare_t) node_udp_compare, NULL);
+       node_tree = splay_alloc_tree((splay_compare_t) node_compare, (splay_action_t) free_node);
+       node_udp_tree = splay_alloc_tree((splay_compare_t) node_udp_compare, NULL);
 }
 
 void exit_nodes(void) {
        cp();
 
-       avl_delete_tree(node_udp_tree);
-       avl_delete_tree(node_tree);
+       splay_delete_tree(node_udp_tree);
+       splay_delete_tree(node_tree);
 }
 
 node_t *new_node(void) {
@@ -114,11 +114,11 @@ void free_node(node_t *n) {
 void node_add(node_t *n) {
        cp();
 
-       avl_insert(node_tree, n);
+       splay_insert(node_tree, n);
 }
 
 void node_del(node_t *n) {
-       avl_node_t *node, *next;
+       splay_node_t *node, *next;
        edge_t *e;
        subnet_t *s;
 
@@ -136,7 +136,7 @@ void node_del(node_t *n) {
                edge_del(e);
        }
 
-       avl_delete(node_tree, n);
+       splay_delete(node_tree, n);
 }
 
 node_t *lookup_node(char *name) {
@@ -146,7 +146,7 @@ node_t *lookup_node(char *name) {
        
        n.name = name;
 
-       return avl_search(node_tree, &n);
+       return splay_search(node_tree, &n);
 }
 
 node_t *lookup_node_udp(const sockaddr_t *sa) {
@@ -157,11 +157,11 @@ node_t *lookup_node_udp(const sockaddr_t *sa) {
        n.address = *sa;
        n.name = NULL;
 
-       return avl_search(node_udp_tree, &n);
+       return splay_search(node_udp_tree, &n);
 }
 
 void dump_nodes(void) {
-       avl_node_t *node;
+       splay_node_t *node;
        node_t *n;
 
        cp();

diff --git a/src/node.h b/src/node.h
index 5b5cc25..83af5e3 100644 (file)
--- a/src/node.h
+++ b/src/node.h
@@ -23,7 +23,7 @@
 #ifndef __TINC_NODE_H__
 #define __TINC_NODE_H__
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "connection.h"
 #include "list.h"
 #include "subnet.h"
@@ -65,9 +65,9 @@ typedef struct node_t {
        struct node_t *nexthop;                 /* nearest node from us to him */
        struct node_t *via;                     /* next hop for UDP packets */
 
-       avl_tree_t *subnet_tree;                /* Pointer to a tree of subnets belonging to this node */
+       splay_tree_t *subnet_tree;              /* Pointer to a tree of subnets belonging to this node */
 
-       avl_tree_t *edge_tree;                  /* Edges with this node as one of the endpoints */
+       splay_tree_t *edge_tree;                        /* Edges with this node as one of the endpoints */
 
        struct connection_t *connection;        /* Connection associated with this node (if a direct connection exists) */
 
@@ -83,8 +83,8 @@ typedef struct node_t {
 } node_t;
 
 extern struct node_t *myself;
-extern avl_tree_t *node_tree;
-extern avl_tree_t *node_udp_tree;
+extern splay_tree_t *node_tree;
+extern splay_tree_t *node_udp_tree;
 
 extern void init_nodes(void);
 extern void exit_nodes(void);

diff --git a/src/protocol.c b/src/protocol.c
index 0fbf2a9..c3fe6f3 100644 (file)
--- a/src/protocol.c
+++ b/src/protocol.c
@@ -53,7 +53,7 @@ static char (*request_name[]) = {
                "ADD_EDGE", "DEL_EDGE", "KEY_CHANGED", "REQ_KEY", "ANS_KEY", "PACKET",
 };
 
-static avl_tree_t *past_request_tree;
+static splay_tree_t *past_request_tree;
 
 bool check_id(const char *id) {
        for(; *id; id++)
@@ -198,21 +198,21 @@ bool seen_request(char *request) {
 
        p.request = request;
 
-       if(avl_search(past_request_tree, &p)) {
+       if(splay_search(past_request_tree, &p)) {
                ifdebug(SCARY_THINGS) logger(LOG_DEBUG, _("Already seen request"));
                return true;
        } else {
                new = xmalloc(sizeof(*new));
                new->request = xstrdup(request);
                new->firstseen = time(NULL);
-               avl_insert(past_request_tree, new);
+               splay_insert(past_request_tree, new);
                event_add(&past_request_event, &(struct timeval){10, 0});
                return false;
        }
 }
 
 void age_past_requests(int fd, short events, void *data) {
-       avl_node_t *node, *next;
+       splay_node_t *node, *next;
        past_request_t *p;
        int left = 0, deleted = 0;
        time_t now = time(NULL);
@@ -224,7 +224,7 @@ void age_past_requests(int fd, short events, void *data) {
                p = node->data;
 
                if(p->firstseen + pinginterval < now)
-                       avl_delete_node(past_request_tree, node), deleted++;
+                       splay_delete_node(past_request_tree, node), deleted++;
                else
                        left++;
        }
@@ -240,7 +240,7 @@ void age_past_requests(int fd, short events, void *data) {
 void init_requests(void) {
        cp();
 
-       past_request_tree = avl_alloc_tree((avl_compare_t) past_request_compare, (avl_action_t) free_past_request);
+       past_request_tree = splay_alloc_tree((splay_compare_t) past_request_compare, (splay_action_t) free_past_request);
 
        timeout_set(&past_request_event, age_past_requests, NULL);
 }
@@ -248,7 +248,7 @@ void init_requests(void) {
 void exit_requests(void) {
        cp();
 
-       avl_delete_tree(past_request_tree);
+       splay_delete_tree(past_request_tree);
 
        event_del(&past_request_event);
 }

diff --git a/src/protocol_auth.c b/src/protocol_auth.c
index f7e9252..70ccda1 100644 (file)
--- a/src/protocol_auth.c
+++ b/src/protocol_auth.c
@@ -27,7 +27,7 @@
 #include <openssl/err.h>
 #include <openssl/evp.h>
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "edge.h"
@@ -483,7 +483,7 @@ bool send_ack(connection_t *c) {
 }
 
 static void send_everything(connection_t *c) {
-       avl_node_t *node, *node2;
+       splay_node_t *node, *node2;
        node_t *n;
        subnet_t *s;
        edge_t *e;

diff --git a/src/protocol_edge.c b/src/protocol_edge.c
index df39bb9..8f8d092 100644 (file)
--- a/src/protocol_edge.c
+++ b/src/protocol_edge.c
@@ -22,7 +22,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "edge.h"

diff --git a/src/protocol_key.c b/src/protocol_key.c
index 0cf33d7..9ab1743 100644 (file)
--- a/src/protocol_key.c
+++ b/src/protocol_key.c
@@ -25,7 +25,7 @@
 #include <openssl/evp.h>
 #include <openssl/err.h>
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "connection.h"
 #include "logger.h"
 #include "net.h"

diff --git a/src/route.c b/src/route.c
index 5ccf9bd..dbe38df 100644 (file)
--- a/src/route.c
+++ b/src/route.c
@@ -22,7 +22,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "connection.h"
 #include "ethernet.h"
 #include "ipv4.h"
@@ -102,7 +102,7 @@ static void age_subnets(int fd, short events, void *data)
 {
        subnet_t *s;
        connection_t *c;
-       avl_node_t *node, *next, *node2;
+       splay_node_t *node, *next, *node2;
        bool left = false;
        time_t now = time(NULL);
 
@@ -138,7 +138,7 @@ static void age_subnets(int fd, short events, void *data)
 static void learn_mac(mac_t *address)
 {
        subnet_t *subnet;
-       avl_node_t *node;
+       splay_node_t *node;
        connection_t *c;
 
        cp();

diff --git a/src/subnet.c b/src/subnet.c
index a4ec2b3..bbf4edd 100644 (file)
--- a/src/subnet.c
+++ b/src/subnet.c
@@ -22,7 +22,7 @@
 
 #include "system.h"
 
-#include "avl_tree.h"
+#include "splay_tree.h"
 #include "device.h"
 #include "logger.h"
 #include "net.h"
@@ -35,7 +35,7 @@
 
 /* lists type of subnet */
 
-avl_tree_t *subnet_tree;
+splay_tree_t *subnet_tree;
 
 /* Subnet comparison */
 
@@ -117,28 +117,28 @@ void init_subnets(void)
 {
        cp();
 
-       subnet_tree = avl_alloc_tree((avl_compare_t) subnet_compare, (avl_action_t) free_subnet);
+       subnet_tree = splay_alloc_tree((splay_compare_t) subnet_compare, (splay_action_t) free_subnet);
 }
 
 void exit_subnets(void)
 {
        cp();
 
-       avl_delete_tree(subnet_tree);
+       splay_delete_tree(subnet_tree);
 }
 
-avl_tree_t *new_subnet_tree(void)
+splay_tree_t *new_subnet_tree(void)
 {
        cp();
 
-       return avl_alloc_tree((avl_compare_t) subnet_compare, NULL);
+       return splay_alloc_tree((splay_compare_t) subnet_compare, NULL);
 }
 
-void free_subnet_tree(avl_tree_t *subnet_tree)
+void free_subnet_tree(splay_tree_t *subnet_tree)
 {
        cp();
 
-       avl_delete_tree(subnet_tree);
+       splay_delete_tree(subnet_tree);
 }
 
 /* Allocating and freeing space for subnets */
@@ -165,16 +165,16 @@ void subnet_add(node_t *n, subnet_t *subnet)
 
        subnet->owner = n;
 
-       avl_insert(subnet_tree, subnet);
-       avl_insert(n->subnet_tree, subnet);
+       splay_insert(subnet_tree, subnet);
+       splay_insert(n->subnet_tree, subnet);
 }
 
 void subnet_del(node_t *n, subnet_t *subnet)
 {
        cp();
 
-       avl_delete(n->subnet_tree, subnet);
-       avl_delete(subnet_tree, subnet);
+       splay_delete(n->subnet_tree, subnet);
+       splay_delete(subnet_tree, subnet);
 }
 
 /* Ascii representation of subnets */
@@ -300,7 +300,7 @@ subnet_t *lookup_subnet(const node_t *owner, const subnet_t *subnet)
 {
        cp();
 
-       return avl_search(owner->subnet_tree, subnet);
+       return splay_search(owner->subnet_tree, subnet);
 }
 
 subnet_t *lookup_subnet_mac(const mac_t *address)
@@ -313,7 +313,7 @@ subnet_t *lookup_subnet_mac(const mac_t *address)
        subnet.net.mac.address = *address;
        subnet.owner = NULL;
 
-       p = avl_search(subnet_tree, &subnet);
+       p = splay_search(subnet_tree, &subnet);
 
        return p;
 }
@@ -332,7 +332,7 @@ subnet_t *lookup_subnet_ipv4(const ipv4_t *address)
        do {
                /* Go find subnet */
 
-               p = avl_search_closest_smaller(subnet_tree, &subnet);
+               p = splay_search_closest_smaller(subnet_tree, &subnet);
 
                /* Check if the found subnet REALLY matches */
 
@@ -370,7 +370,7 @@ subnet_t *lookup_subnet_ipv6(const ipv6_t *address)
        do {
                /* Go find subnet */
 
-               p = avl_search_closest_smaller(subnet_tree, &subnet);
+               p = splay_search_closest_smaller(subnet_tree, &subnet);
 
                /* Check if the found subnet REALLY matches */
 
@@ -393,7 +393,7 @@ subnet_t *lookup_subnet_ipv6(const ipv6_t *address)
 }
 
 void subnet_update(node_t *owner, subnet_t *subnet, bool up) {
-       avl_node_t *node;
+       splay_node_t *node;
        int i;
        char *envp[8];
        char netstr[MAXNETSTR + 7] = "SUBNET=";
@@ -442,7 +442,7 @@ void dump_subnets(void)
 {
        char netstr[MAXNETSTR];
        subnet_t *subnet;
-       avl_node_t *node;
+       splay_node_t *node;
 
        cp();
 

diff --git a/src/subnet.h b/src/subnet.h
index c50ac6c..f73aaf9 100644 (file)
--- a/src/subnet.h
+++ b/src/subnet.h
@@ -70,8 +70,8 @@ extern subnet_t *new_subnet(void) __attribute__ ((__malloc__));
 extern void free_subnet(subnet_t *);
 extern void init_subnets(void);
 extern void exit_subnets(void);
-extern avl_tree_t *new_subnet_tree(void) __attribute__ ((__malloc__));
-extern void free_subnet_tree(avl_tree_t *);
+extern splay_tree_t *new_subnet_tree(void) __attribute__ ((__malloc__));
+extern void free_subnet_tree(splay_tree_t *);
 extern void subnet_add(struct node_t *, subnet_t *);
 extern void subnet_del(struct node_t *, subnet_t *);
 extern void subnet_update(struct node_t *, subnet_t *, bool);