summaryrefslogtreecommitdiff
path: root/cesar/lib/inc/mac_lookup_table.h
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/lib/inc/mac_lookup_table.h')
-rw-r--r--cesar/lib/inc/mac_lookup_table.h229
1 files changed, 229 insertions, 0 deletions
diff --git a/cesar/lib/inc/mac_lookup_table.h b/cesar/lib/inc/mac_lookup_table.h
new file mode 100644
index 0000000000..c235bcfd9a
--- /dev/null
+++ b/cesar/lib/inc/mac_lookup_table.h
@@ -0,0 +1,229 @@
+#ifndef lib_inc_mac_lookup_table_h
+#define lib_inc_mac_lookup_table_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2009 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/inc/mac_lookup_table.h
+ * \brief MAC lookup table private header.
+ * \ingroup lib
+ *
+ * The MAC lookup table relies on the 512 bytes block allocator module. In
+ * fact, all entries are stored on those blocks.
+ *
+ * An entry is 8 bytes long:
+ * - 48 bits for the MAC address field,
+ * - 16 bits for the extra information field.
+ *
+ * A block can contain, at most, 64 entries.
+ *
+ * The non-sorted format simply stored all the new entries in the blocks,
+ * adding more blocks if needed. But this format is not optimized to find a
+ * MAC address in all the entries.
+ *
+ * The indexed format use the same data structure as the non-sorted one with
+ * some enhancements. First, it sorts the table. Then it present the whole
+ * linked blocks as a big table. To achieve this, it create a small index
+ * table on the last block (sometimes it creates a new block to store it):
+ * each entry of this index contains the first entry of each linked blocks.
+ * The dichotomy search algorithm can be used on this index to have an
+ * optimized search on the table.
+ */
+
+#include "lib/blk.h"
+
+/**
+ * A data entry of the MAC lookup table.
+ * The entry contains the MAC address (stored on 48 bits) field and the extra
+ * information field (stored on 16 bits).
+ */
+struct mac_lookup_data_entry_t
+{
+ /** The MAC address. */
+ u64 mac_address: 48;
+ /** The extra informations. */
+ u64 extra_info: 16;
+};
+typedef struct mac_lookup_data_entry_t mac_lookup_data_entry_t;
+
+/**
+ * Maximum number of entries per block.
+ */
+#define MAX_ENTRIES_PER_BLOCK (BLK_SIZE / sizeof (mac_lookup_data_entry_t))
+
+/**
+ * Maximum number of entries of the whole table.
+ * It is limited by the size of indexed table which must fit on a 512 bytes
+ * block.
+ */
+#define MAX_ENTRIES_PER_TABLE \
+ ((BLK_SIZE - sizeof (mac_lookup_block_header_t *) - sizeof (uint)) \
+ / sizeof (mac_lookup_data_entry_t *) * MAX_ENTRIES_PER_BLOCK)
+
+
+/**
+ * Data block header of the lookup table.
+ * If you use this header, you are accessing the non-sorted version of the MAC
+ * lookup table.
+ * This header is repeated at the beginning of each linked block (512 bytes
+ * long) of data. The header of the first block contains some additional
+ * informations for optimization purpose (those informations are not reported
+ * on the other block header entries!). It must respect \c blk_t structure.
+ * The block of data contains some \c mac_lookup_data_entry_t.
+ */
+struct mac_lookup_block_header_t
+{
+ /** The next data block header. */
+ struct mac_lookup_block_header_t *next;
+ /** The beginning of the entries of data of this block. */
+ struct mac_lookup_data_entry_t *data;
+ /** Total count of entries in all the linked blocks. It is used to compute
+ * the position of the next entry to add to the table. It is only filed in
+ * the first block. */
+ uint total_entry_count;
+ /** Last allocated block of data. It is used to prevent scanning the whole
+ * table to access the last allocated block.It is only filed in the first
+ * block. */
+ struct mac_lookup_block_header_t *last_allocated_header;
+};
+
+/**
+ * The indexed MAC lookup table.
+ * If you use this structure, you are accessing the indexed version of the MAC
+ * lookup table and you can not change the MAC address of the entries anymore.
+ * This table tries to hide the way data are stored (on linked blocks).
+ * Instead, it presents them as a one dimensional array (of one line and one
+ * column for each entry).
+ * This table is stored on the last linked block. It may required to add a
+ * block to have enough space to store it.
+ */
+struct mac_lookup_table_t
+{
+ /** A pointer to the first block header. It is useful to access the \a
+ * total_entry_count to know the number of entries in the whole table. */
+ mac_lookup_block_header_t *first;
+ /** The size of the \a data_entry table (not the count of entries of the
+ * whole indexed table). */
+ uint data_entry_size;
+ /** A table containing pointers to the first data entry of each block of
+ * the MAC lookup table. */
+ mac_lookup_data_entry_t *data_entry[];
+};
+
+BEGIN_DECLS
+
+/**
+ * Swap two data entries in the indexed MAC lookup table.
+ * \param table an indexed MAC lookup table.
+ * \param pos1 the first position of a data entry to swap.
+ * \param pos2 the second position of a data entry to swap.
+ *
+ * This function is used to sort the indexed table.
+ */
+void
+mac_lookup_table_swap (mac_lookup_table_t* table, uint pos1, uint pos2);
+
+/**
+ * Find an entry corresponding to the MAC address into the MAC lookup table.
+ * \param table the MAC lookup table in which to search the MAC address.
+ * \param mac_address the MAC address of the entry to lookup for.
+ * \return a pointer to the data entry if found, otherwise, returns NULL.
+ *
+ * This function is internal because it returns a pointer for a direct access
+ * to the data entry.
+ */
+mac_lookup_data_entry_t *
+mac_lookup_table_find (mac_lookup_table_t *table, mac_t mac_address);
+
+/**
+ * Copy entries with or without specific extra information from an indexed
+ * table to a non-sorted one.
+ * \param indexed_table the indexed MAC lookup table.
+ * \param non_sorted_table the non-sorted MAC lookup table.
+ * \param mask the mask to apply to the extra information for matching only
+ * part of the extra information (useful if you have stored more than one
+ * information in the extra information field).
+ * \param value the value to match against a part of the extra information.
+ * \param negate negate matching condition:
+ * - true will negate the matching condition (by adding a !),
+ * - false will not negate the matching condition.
+ * \return the count of copied entries to \a non_sorted_table.
+ */
+uint
+mac_lookup_table_copy_conditional
+ (mac_lookup_table_t *indexed_table,
+ mac_lookup_block_header_t *non_sorted_table,
+ u16 mask, u16 value, bool negate);
+
+/**
+ * Get the data entry at a desired position of a MAC lookup table.
+ * \param table the indexed MAC lookup table.
+ * \param position the position to get.
+ * \return the data entry located at \a position.
+ */
+static inline mac_lookup_data_entry_t *
+mac_lookup_get_data_entry (mac_lookup_table_t *table, uint position)
+{
+ /* Check parameters. */
+ dbg_assert (table);
+ dbg_assert (table->first);
+ dbg_assert (table->data_entry);
+ dbg_assert (position < table->first->total_entry_count);
+
+ /* Get corresponding block position. */
+ uint block_position = position / MAX_ENTRIES_PER_BLOCK;
+ dbg_assert (block_position < table->data_entry_size);
+ dbg_assert (table->data_entry[block_position]);
+
+ /* Return entry. */
+ return &(table->data_entry[block_position]
+ [position % MAX_ENTRIES_PER_BLOCK]);
+}
+
+/**
+ * Get MAC address at a desired position of a MAC lookup table.
+ * \param table the indexed MAC lookup table.
+ * \param position the position to get.
+ * \return the MAC address located at \a position.
+ */
+static inline mac_t
+mac_lookup_get_mac__ (mac_lookup_table_t *table, uint position)
+{
+ /* Get entry. */
+ mac_lookup_data_entry_t *result
+ = mac_lookup_get_data_entry (table, position);
+ dbg_assert (result);
+
+ /* Return MAC address field. */
+ return result->mac_address;
+}
+
+/**
+ * Compare two MAC addresses of the indexed MAC lookup table.
+ * \param table an indexed MAC lookup table.
+ * \param pos1 the first position of a data entry to compare.
+ * \param pos2 the second position of a data entry to compare.
+ * \return true if the MAC address of the data entry at \c pos1 is less than the
+ * one at \c pos2, otherwise, it returns false.
+ */
+static inline bool
+mac_lookup_table_compare (mac_lookup_table_t* table, uint pos1, uint pos2)
+{
+ /* Check parameter. */
+ dbg_assert (table);
+
+ /* Compare MAC values. */
+ if (mac_lookup_get_mac__ (table, pos1)
+ < mac_lookup_get_mac__ (table, pos2))
+ return true;
+ else
+ return false;
+}
+
+END_DECLS
+
+#endif /* lib_inc_mac_lookup_table_h */