From 8b4924d23ee8d51e78462ad00073a0ba3eee39af Mon Sep 17 00:00:00 2001 From: dufour Date: Mon, 5 Oct 2009 14:29:14 +0000 Subject: cesar/{cl,lib}: move cl/mac_lookup_table to lib directory (closes #606) Move mac_lookup_table module from the cl to the lib directory. Also correct a minor indentation problem. git-svn-id: svn+ssh://pessac/svn/cesar/trunk@5921 017c9cb6-072f-447c-8318-d5b54f68fe89 --- cesar/lib/inc/mac_lookup_table.h | 229 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 229 insertions(+) create mode 100644 cesar/lib/inc/mac_lookup_table.h (limited to 'cesar/lib/inc/mac_lookup_table.h') 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 + * + * <<>> + * + * }}} */ +/** + * \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 */ -- cgit v1.2.3