-
Notifications
You must be signed in to change notification settings - Fork 11
/
index.h
185 lines (140 loc) · 5.58 KB
/
index.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/* index.c: module index file shared functions for modprobe and depmod
Copyright (C) 2008 Alan Jenkins <alan-jenkins@tuffmail.co.uk>.
These programs are free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with these programs. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef MODINITTOOLS_INDEX_H
#define MODINITTOOLS_INDEX_H
#include <stdint.h>
/* Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
All files start with a magic number.
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
struct index_value {
struct index_value *next;
unsigned int priority;
char value[0];
};
/* In-memory index (depmod only) */
#define INDEX_CHILDMAX 128
struct index_node {
char *prefix; /* path compression */
struct index_value *values;
unsigned char first; /* range of child nodes */
unsigned char last;
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 ommitted, 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 {
INDEX_NODE_FLAGS = 0xF0000000, /* Flags in high nibble */
INDEX_NODE_PREFIX = 0x80000000,
INDEX_NODE_VALUES = 0x40000000,
INDEX_NODE_CHILDS = 0x20000000,
INDEX_NODE_MASK = 0x0FFFFFFF, /* Offset value */
};
struct index_file;
struct index_node *index_create(void);
void index_destroy(struct index_node *node);
int index_insert(struct index_node *node, const char *key,
const char *value, unsigned int priority);
void index_write(const struct index_node *node, FILE *out);
struct index_file *index_file_open(const char *filename);
void index_file_close(struct index_file *index);
/* Dump all strings in index as lines in a plain text file
(prefix is prepended to each line)
*/
void index_dump(struct index_file *in, FILE *out, const char *prefix);
/* Return value for first matching key.
Keys must be exactly equal to match - i.e. there are no wildcard patterns
*/
char *index_search(struct index_file *index, const char *key);
/* Return values for all matching keys.
The keys in the index are treated as wildcard patterns using fnmatch()
*/
struct index_value *index_searchwild(struct index_file *index, const char *key);
void index_values_free(struct index_value *values);
#endif /* MODINITTOOLS_INDEX_H */