diff options
author | Lucas De Marchi <lucas.demarchi@intel.com> | 2014-10-28 01:52:49 -0200 |
---|---|---|
committer | Lucas De Marchi <lucas.demarchi@intel.com> | 2014-10-28 01:54:23 -0200 |
commit | 414cb52b9a9211015cc6c604eb3893deaec6e07c (patch) | |
tree | d57540901ea22b44d13df0999c38e86f64389647 | |
parent | 2666377889b885c31393cb50df6541f67649d981 (diff) | |
download | kmod-414cb52b9a9211015cc6c604eb3893deaec6e07c.tar.gz |
depmod: point to documentation in libkmod
Instead of repeating all documentation, point to the documentation
available in libkmod-index.c
This also removes INDEX_PRIORITY_MIN that was never being used.
-rw-r--r-- | tools/depmod.c | 103 |
1 files changed, 2 insertions, 101 deletions
diff --git a/tools/depmod.c b/tools/depmod.c index fec458c..9669a61 100644 --- a/tools/depmod.c +++ b/tools/depmod.c @@ -142,84 +142,13 @@ static inline void _show(const char *fmt, ...) * along with these programs. If not, see <http://www.gnu.org/licenses/>. */ -/* Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first. - All files start with a magic number. +/* see documentation in libkmod/libkmod-index.c */ - Magic spells "BOOTFAST". Second one used on newer versioned binary files. - */ -/* #define INDEX_MAGIC_OLD 0xB007FA57 */ #define INDEX_MAGIC 0xB007F457 - -/* We use a version string to keep track of changes to the binary format - * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in - * case we ever decide to have minor changes that are not incompatible. - */ - #define INDEX_VERSION_MAJOR 0x0002 #define INDEX_VERSION_MINOR 0x0001 #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR) - -/* The index file maps keys to values. Both keys and values are ASCII strings. - Each key can have multiple values. Values are sorted by an integer priority. - - The reader also implements a wildcard search (including range expressions) - where the keys in the index are treated as patterns. - This feature is required for module aliases. -*/ - -/* Implementation is based on a radix tree, or "trie". - Each arc from parent to child is labelled with a character. - Each path from the root represents a string. - - == Example strings == - - ask - ate - on - once - one - - == Key == - + Normal node - * Marked node, representing a key and it's values. - - + - |-a-+-s-+-k-* - | | - | `-t-+-e-* - | - `-o-+-n-*-c-+-e-* - | - `-e-* - - Naive implementations tend to be very space inefficient; child pointers - are stored in arrays indexed by character, but most child pointers are null. - - Our implementation uses a scheme described by Wikipedia as a Patrica trie, - - "easiest to understand as a space-optimized trie where - each node with only one child is merged with its child" - - + - |-a-+-sk-* - | | - | `-te-* - | - `-on-*-ce-* - | - `-e-* - - We still use arrays of child pointers indexed by a single character; - the remaining characters of the label are stored as a "prefix" in the child. - - The paper describing the original Patrica trie works on individiual bits - - each node has a maximum of two children, which increases space efficiency. - However for this application it is simpler to use the ASCII character set. - Since the index file is read-only, it can be compressed by omitting null - child pointers at the start and end of arrays. -*/ - -#define INDEX_PRIORITY_MIN UINT32_MAX +#define INDEX_CHILDMAX 128 struct index_value { struct index_value *next; @@ -228,8 +157,6 @@ struct index_value { }; /* In-memory index (depmod only) */ - -#define INDEX_CHILDMAX 128 struct index_node { char *prefix; /* path compression */ struct index_value *values; @@ -238,32 +165,6 @@ struct index_node { struct index_node *children[INDEX_CHILDMAX]; /* indexed by character */ }; -/* Disk format: - - uint32_t magic = INDEX_MAGIC; - uint32_t version = INDEX_VERSION; - uint32_t root_offset; - - (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes: - - char[] prefix; // nul terminated - - char first; - char last; - uint32_t children[last - first + 1]; - - uint32_t value_count; - struct { - uint32_t priority; - char[] value; // nul terminated - } values[value_count]; - - (node_offset & INDEX_NODE_FLAGS) indicates which fields are present. - Empty prefixes are omitted, leaf nodes omit the three child-related fields. - - This could be optimised further by adding a sparse child format - (indicated using a new flag). - */ /* Format of node offsets within index file */ enum node_offset { |