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