[Olsr-dev] [RFC] [PATCH v1 6/7] gateway: add gateway_list.{c,h}

Ferry Huberts (spam-protected)
Tue Nov 13 11:33:00 CET 2012


From: Ferry Huberts <(spam-protected)>

Signed-off-by: Ferry Huberts <(spam-protected)>
---
 src/gateway.c      |   7 +-
 src/gateway_list.c | 187 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/gateway_list.h | 152 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 340 insertions(+), 6 deletions(-)
 create mode 100644 src/gateway_list.c
 create mode 100644 src/gateway_list.h

diff --git a/src/gateway.c b/src/gateway.c
index 27b9341..e110a13 100644
--- a/src/gateway.c
+++ b/src/gateway.c
@@ -20,17 +20,12 @@
 #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
index 0000000..c84a789
--- /dev/null
+++ b/src/gateway_list.c
@@ -0,0 +1,187 @@
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004, Thomas Lopatic ((spam-protected))
+ * 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
index 0000000..e947b16
--- /dev/null
+++ b/src/gateway_list.h
@@ -0,0 +1,152 @@
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004, Thomas Lopatic ((spam-protected))
+ * 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 */
-- 
1.7.11.7





More information about the Olsr-dev mailing list