index.h

   1
   2 /* index.c: module index file shared functions for modprobe and depmod
   3     Copyright (C) 2008  Alan Jenkins <alan-jenkins@tuffmail.co.uk>.
   4
   5     These programs are free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with these programs.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 #ifndef MODINITTOOLS_INDEX_H
  20 #define MODINITTOOLS_INDEX_H
  21
  22 #include <arpa/inet.h> /* htonl */
  23
  24 /* Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
  25    All files start with a magic number.
  26
  27    Magic spells "BOOTFAST". Second one used on newer versioned binary files.
  28  */
  29 #define INDEX_MAGIC_OLD 0xB007FA57
  30 #define INDEX_MAGIC 0xB007F457
  31
  32 /* We use a version string to keep track of changes to the binary format
  33  * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
  34  * case we ever decide to have minor changes that are not incompatible.
  35  */
  36
  37 #define INDEX_VERSION_MAJOR 0x0001
  38 #define INDEX_VERSION_MINOR 0x0001
  39 #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
  40
  41 /* The index file is simply a set of uninterpreted ASCII strings.
  42
  43    Key/value separation is handled by the reader.  The end of a key
  44    is indicated by the first space character in the string.
  45    Therefore duplicate keys are legal (which is necessary for module aliases).
  46    The writer code only warns on duplicates of an entire string (key+value).
  47
  48    The reader also implements a wildcard search (including range expressions)
  49    where the keys in the index are treated as patterns.
  50    This feature is required for module aliases.
  51 */
  52
  53 /* Implementation is based on a radix tree, or "trie".
  54    Each arc from parent to child is labelled with a character.
  55    Each path from the root represents a string.
  56
  57    == Example strings ==
  58
  59    ask
  60    ate
  61    on
  62    once
  63    one
  64
  65    == Key ==
  66     + Normal node
  67     * Marked node, representing a string in the index
  68
  69    +
  70    |-a-+-s-+-k-*
  71    |   |
  72    |   `-t-+-e-*
  73    |
  74    `-o-+-n-*-c-+-e-*
  75            |
  76            `-e-*
  77
  78    Naive implementations tend to be very space inefficient; child pointers
  79    are stored in arrays indexed by character, but most child pointers are null.
  80
  81    Our implementation uses a scheme described by Wikipedia as a Patrica trie,
  82
  83        "easiest to understand as a space-optimized trie where
  84         each node with only one child is merged with its child"
  85
  86    +
  87    |-a-+-sk-*
  88    |   |
  89    |   `-te-*
  90    |
  91    `-on-*-ce-*
  92         |
  93         `-e-*
  94
  95    We still use arrays of child pointers indexed by a single character;
  96    the remaining characters of the label are stored as a "prefix" in the child.
  97
  98    The paper describing the original Patrica trie works on individiual bits -
  99    each node has a maximum of two children, which increases space efficiency.
 100    However for this application it is simpler to use the ASCII character set.
 101    Since the index file is read-only, it can be compressed by omitting null
 102    child pointers at the start and end of arrays.
 103 */
 104
 105 /* In-memory structure (depmod only) */
 106
 107 #define INDEX_CHILDMAX 128
 108 struct index_node {
 109         char *prefix;           /* path compression */
 110         char isendpoint;        /* does this node represent a string? */
 111         unsigned char first;    /* range of child nodes */
 112         unsigned char last;
 113         struct index_node *children[INDEX_CHILDMAX]; /* indexed by character */
 114 };
 115
 116 /* Disk format:
 117
 118    uint32_t magic = INDEX_MAGIC;
 119    uint32_t version = INDEX_VERSION;
 120    uint32_t root_offset;
 121
 122    (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
 123
 124         char[] prefix; // nul terminated
 125
 126         char first;
 127         char last;
 128         uint32_t children[last - first + 1];
 129
 130    (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
 131    Empty prefixes are ommitted, leaf nodes omit the three child-related fields.
 132
 133    This could be optimised further by adding a sparse child format
 134    (indicated using a new flag).
 135  */
 136
 137 /* Format of node offsets within index file */
 138 enum node_offset {
 139         INDEX_NODE_FLAGS    = 0xF0000000, /* Flags in high nibble */
 140         INDEX_NODE_PREFIX   = 0x80000000,
 141         INDEX_NODE_ENDPOINT = 0x40000000,
 142         INDEX_NODE_CHILDS   = 0x20000000,
 143
 144         INDEX_NODE_MASK     = 0x0FFFFFFF, /* Offset value */
 145 };
 146
 147 struct index_value {
 148         struct index_value *next;
 149         char value[0];
 150 };
 151
 152 struct index_node *index_create();
 153 void index_destroy(struct index_node *node);
 154 int index_insert(struct index_node *node, const char *str);
 155 void index_write(const struct index_node *node, FILE *out);
 156
 157 /* Dump all strings in index as lines in a plain text file
 158    (prefix is prepended to each line)
 159 */
 160 void index_dump(FILE *in, FILE *out, const char *prefix);
 161
 162 /* Return value for first matching key.
 163    Keys must be exactly equal to match - i.e. there are no wildcard patterns
 164 */
 165 char *index_search(FILE *in, const char *key);
 166
 167 /* Return values for all matching keys.
 168    The keys in the index are treated as wildcard patterns using fnmatch()
 169 */
 170 struct index_value *index_searchwild(FILE *in, const char *key);
 171
 172 #endif /* MODINITTOOLS_INDEX_H */