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".  No duplicates found on google web or code search.
  28  */
  29 #define INDEX_MAGIC 0xB007FA57
  30
  31 /* The index file is simply a set of uninterpreted ASCII strings.
  32
  33    Key/value separation is handled by the reader.  The end of a key
  34    is indicated by the first space character in the string.
  35    Therefore duplicate keys are legal (which is necessary for module aliases).
  36    The writer code only warns on duplicates of an entire string (key+value).
  37
  38    The reader also implements a wildcard search (including range expressions)
  39    where the keys in the index are treated as patterns.
  40    This feature is required for module aliases.
  41 */
  42
  43 /* Implementation is based on a radix tree, or "trie".
  44    Each arc from parent to child is labelled with a character.
  45    Each path from the root represents a string.
  46
  47    == Example strings ==
  48
  49    ask
  50    ate
  51    on
  52    once
  53    one
  54
  55    == Key ==
  56     + Normal node
  57     * Marked node, representing a string in the index
  58
  59    +
  60    |-a-+-s-+-k-*
  61    |   |
  62    |   `-t-+-e-*
  63    |
  64    `-o-+-n-*-c-+-e-*
  65            |
  66            `-e-*
  67
  68    Naive implementations tend to be very space inefficient; child pointers
  69    are stored in arrays indexed by character, but most child pointers are null.
  70
  71    Our implementation uses a scheme described by Wikipedia as a Patrica trie,
  72
  73        "easiest to understand as a space-optimized trie where
  74         each node with only one child is merged with its child"
  75
  76    +
  77    |-a-+-sk-*
  78    |   |
  79    |   `-te-*
  80    |
  81    `-on-*-ce-*
  82         |
  83         `-e-*
  84
  85    We still use arrays of child pointers indexed by a single character;
  86    the remaining characters of the label are stored as a "prefix" in the child.
  87
  88    The paper describing the original Patrica trie works on individiual bits -
  89    each node has a maximum of two children, which increases space efficiency.
  90    However for this application it is simpler to use the ASCII character set.
  91    Since the index file is read-only, it can be compressed by omitting null
  92    child pointers at the start and end of arrays.
  93 */
  94
  95 /* In-memory structure (depmod only) */
  96
  97 #define INDEX_CHILDMAX 128
  98 struct index_node {
  99         char *prefix;           /* path compression */
 100         char isendpoint;        /* does this node represent a string? */
 101         unsigned char first;    /* range of child nodes */
 102         unsigned char last;
 103         struct index_node *children[INDEX_CHILDMAX]; /* indexed by character */
 104 };
 105
 106 /* Disk format:
 107
 108    uint32_t magic = INDEX_MAGIC;
 109    uint32_t root_offset;
 110
 111    (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
 112
 113         char[] prefix; // nul terminated
 114
 115         char first;
 116         char last;
 117         uint32_t children[last - first + 1];
 118
 119    (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
 120    Empty prefixes are ommitted, leaf nodes omit the three child-related fields.
 121
 122    This could be optimised further by adding a sparse child format
 123    (indicated using a new flag).
 124  */
 125
 126 /* Format of node offsets within index file */
 127 enum node_offset {
 128         INDEX_NODE_FLAGS    = 0xF0000000, /* Flags in high nibble */
 129         INDEX_NODE_PREFIX   = 0x80000000,
 130         INDEX_NODE_ENDPOINT = 0x40000000,
 131         INDEX_NODE_CHILDS   = 0x20000000,
 132
 133         INDEX_NODE_MASK     = 0x0FFFFFFF, /* Offset value */
 134 };
 135
 136 struct index_value {
 137         struct index_value *next;
 138         char value[0];
 139 };
 140
 141 struct index_node *index_create();
 142 void index_destroy(struct index_node *node);
 143 int index_insert(struct index_node *node, const char *str);
 144 void index_write(const struct index_node *node, FILE *out);
 145
 146 /* Dump all strings in index as lines in a plain text file
 147    (prefix is prepended to each line)
 148 */
 149 void index_dump(FILE *in, FILE *out, const char *prefix);
 150
 151 /* Return value for first matching key.
 152    Keys must be exactly equal to match - i.e. there are no wildcard patterns
 153 */
 154 char *index_search(FILE *in, const char *key);
 155
 156 /* Return values for all matching keys.
 157    The keys in the index are treated as wildcard patterns using fnmatch()
 158 */
 159 struct index_value *index_searchwild(FILE *in, const char *key);
 160
 161 #endif /* MODINITTOOLS_INDEX_H */