gateway: add gateway_list.{c,h}
authorFerry Huberts <ferry.huberts@pelagic.nl>
Mon, 5 Nov 2012 12:12:48 +0000 (13:12 +0100)
committerFerry Huberts <ferry.huberts@pelagic.nl>
Mon, 10 Dec 2012 14:18:24 +0000 (15:18 +0100)
Signed-off-by: Ferry Huberts <ferry.huberts@pelagic.nl>
Reviewed-by: Henning Rogge <hrogge@googlemail.com>
src/gateway.c
src/gateway_list.c [new file with mode: 0644]
src/gateway_list.h [new file with mode: 0644]

index 7aa09ba..9c740c3 100644 (file)
 #include "duplicate_set.h"
 #include "log.h"
 #include "gateway_default_handler.h"
+#include "gateway_list.h"
 #include "gateway.h"
 
 #include <assert.h>
 #include <net/if.h>
 
-/** A container for a gateway and its tunnel */
-struct gw_container_entry {
-               struct gateway_entry * gw; /**< the gateway entry */
-               struct olsr_iptunnel_entry * tunnel; /**< the gateway tunnel */
-};
-
 /** the gateway tree */
 struct avl_tree gateway_tree;
 
diff --git a/src/gateway_list.c b/src/gateway_list.c
new file mode 100644 (file)
index 0000000..c84a789
--- /dev/null
@@ -0,0 +1,187 @@
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ *
+ */
+
+#ifdef __linux__
+
+#include "gateway_list.h"
+
+#include "gateway.h"
+#include "common/list.h"
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <assert.h>
+
+/*
+ * Exported functions
+ */
+
+/**
+ * Initialization
+ *
+ * @param list a pointer to the list
+ * @param count the maximum number of entries to be kept in the list. Must be
+ * larger than zero
+ */
+void olsr_gw_list_init(struct gw_list * list, uint8_t count) {
+       assert(list);
+       assert(count > 0);
+
+       list_head_init(&list->head);
+       list->count_max = count;
+       list->count = 0;
+}
+
+/**
+ * Cleanup
+ *
+ * @param list a pointer to the list
+ */
+void olsr_gw_list_cleanup(struct gw_list * list __attribute__((unused))) {
+       /* nothing to do */
+}
+
+/**
+ * Find an entry on the list
+ *
+ * @param list a pointer to the list
+ * @param entry a pointer to the entry to find
+ * @return a pointer to the entry, or NULL when not found
+ */
+struct gw_container_entry * olsr_gw_list_find(struct gw_list * list, struct gateway_entry * entry) {
+       struct gw_container_entry * gw;
+
+       assert(list);
+       assert(entry);
+
+       OLSR_FOR_ALL_GWS(&list->head, gw) {
+               if (gw && gw->gw && (gw->gw == entry)) {
+                       return gw;
+               }
+       }
+       OLSR_FOR_ALL_GWS_END(gw);
+
+       return NULL;
+}
+
+/**
+ * Add an entry to the list.
+ *
+ * The list is ordered on costs with the lowest costs (best) first and the
+ * highest costs (worst) last. In case of equal costs, the entry is added
+ * _before_ the one(s) that is(are) already in the list.
+ *
+ * @param list a pointer to the list
+ * @param entry a pointer to the entry
+ * @return a pointer to the added entry
+ */
+struct gw_container_entry * olsr_gw_list_add(struct gw_list * list, struct gw_container_entry * entry) {
+       struct gw_container_entry * gw;
+
+       assert(list);
+       assert(entry);
+       assert(!olsr_gw_list_full(list));
+
+       list_node_init(&entry->list_node);
+
+       OLSR_FOR_ALL_GWS(&list->head, gw) {
+               if (gw && (entry->path_cost <= gw->path_cost)) {
+                       /* add before the iterated list entry: the gateway to insert has lower
+                        * costs or has equal costs but is newer (since we insert it) */
+                       list_add_before(&gw->list_node, &entry->list_node);
+                       list->count++;
+                       return entry;
+               }
+       }
+       OLSR_FOR_ALL_GWS_END(gw);
+
+       /* add at the end */
+       list_add_after(list->head.prev, &entry->list_node);
+       list->count++;
+       return entry;
+}
+
+/**
+ * Update an entry on the list.
+ *
+ * @param list a pointer to the list
+ * @param entry a pointer to the entry
+ * @param path_cost the costs of the entry
+ * @return a pointer to the updated entry
+ */
+struct gw_container_entry * olsr_gw_list_update(struct gw_list * list, struct gw_container_entry * entry,
+               uint64_t path_cost) {
+       assert(list);
+       assert(entry);
+       assert(!olsr_gw_list_empty(list));
+
+       if (entry->path_cost == path_cost) {
+               return entry;
+       }
+
+       /* don't touch gw */
+       /* don't touch tunnel */
+       entry->path_cost = path_cost;
+       /* don't touch list_node */
+
+       list_remove(&entry->list_node);
+       list->count--;
+       return olsr_gw_list_add(list, entry);
+}
+
+/**
+ * Remove a gateway from the list (but do not free it's memory)
+ *
+ * @param list a pointer to the list
+ * @param entry a pointer to the gateway
+ * @return a pointer to the removed entry
+ */
+struct gw_container_entry * olsr_gw_list_remove(struct gw_list * list, struct gw_container_entry * entry) {
+       assert(list);
+       assert(entry);
+       assert(!olsr_gw_list_empty(list));
+
+       list_remove(&entry->list_node);
+       list->count--;
+       return entry;
+}
+
+#endif /* __linux__ */
diff --git a/src/gateway_list.h b/src/gateway_list.h
new file mode 100644 (file)
index 0000000..e947b16
--- /dev/null
@@ -0,0 +1,152 @@
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ *
+ */
+
+#ifndef _GW_LIST_H
+#define _GW_LIST_H
+
+#ifdef __linux__
+
+#include "gateway.h"
+#include "common/list.h"
+#include "kernel_tunnel.h"
+#include <stdint.h>
+#include <stdbool.h>
+#include <assert.h>
+
+/** Holds the list head and list administration */
+struct gw_list {
+               struct list_node head; /**< The (ordered) list of entries */
+               uint8_t count_max; /**< The maximum number of entries in the list */
+               uint8_t count; /**< The number of entries in the list */
+};
+
+/** A container for a gateway and its tunnel */
+struct gw_container_entry {
+               struct gateway_entry * gw; /**< the gateway entry */
+               struct olsr_iptunnel_entry * tunnel; /**< the gateway tunnel */
+               uint64_t path_cost; /**< the gateway path costs */
+               struct list_node list_node; /**< the list node */
+};
+
+/** Cast from list_node to gw_container_entry */
+LISTNODE2STRUCT(olsr_gw_list_node2entry, struct gw_container_entry, list_node);
+
+/** Deletion safe macro for gateway list traversal (do not delete the previous or next node, current node is ok) */
+#define OLSR_FOR_ALL_GWS(head, gw) {\
+  struct list_node * _list_node; \
+  struct list_node * _next_list_node; \
+  for (_list_node = (head)->next; _list_node != (head); _list_node = _next_list_node) { \
+    _next_list_node = _list_node->next; \
+    gw = olsr_gw_list_node2entry(_list_node);
+#define OLSR_FOR_ALL_GWS_END(gw) }}
+
+/**
+ * @param list a pointer to the list
+ * @return true when multiple gateways mode is enabled
+ */
+static inline bool olsr_gw_list_isModeMulti(struct gw_list * list) {
+       assert(list);
+       return (list->count_max > 1);
+}
+
+void olsr_gw_list_init(struct gw_list * list, uint8_t count);
+void olsr_gw_list_cleanup(struct gw_list * list);
+
+/**
+ * @param list a pointer to the list
+ * @return true if the list is empty
+ */
+static inline bool olsr_gw_list_empty(struct gw_list * list) {
+       assert(list);
+       return (list->count == 0);
+}
+
+/**
+ * @param list a pointer to the list
+ * @return true if the list is full
+ */
+static inline bool olsr_gw_list_full(struct gw_list * list) {
+       assert(list);
+       return (list->count >= list->count_max);
+}
+
+/**
+ * Get the best entry that is on the list
+ *
+ * @param list a pointer to the list
+ * @return a pointer to the best entry, or NULL when the list is empty
+ */
+static inline struct gw_container_entry * olsr_gw_list_get_best_entry(struct gw_list * list) {
+       assert(list);
+
+       if (olsr_gw_list_empty(list)) {
+               return NULL;
+       }
+
+       /* get the best (first) entry of the list */
+       return olsr_gw_list_node2entry(list->head.next);
+}
+
+/**
+ * Get the worst entry that is on the list
+ *
+ * @param list a pointer to the list
+ * @return a pointer to the worst entry
+ */
+static inline struct gw_container_entry * olsr_gw_list_get_worst_entry(struct gw_list * list) {
+       assert(list);
+
+       if (olsr_gw_list_empty(list)) {
+               return NULL;
+       }
+
+       /* get the worst (last) entry of the list */
+       return olsr_gw_list_node2entry(list->head.prev);
+}
+
+struct gw_container_entry * olsr_gw_list_find(struct gw_list * list, struct gateway_entry * entry);
+struct gw_container_entry * olsr_gw_list_add(struct gw_list * list, struct gw_container_entry * entry);
+struct gw_container_entry * olsr_gw_list_update(struct gw_list * list, struct gw_container_entry * entry,
+               uint64_t gw_path_cost);
+struct gw_container_entry * olsr_gw_list_remove(struct gw_list * list, struct gw_container_entry * entry);
+
+#endif /* __linux__ */
+#endif /* _GW_LIST_H */