1*cc4ad7daSAndroid Build Coastguard Worker /*
2*cc4ad7daSAndroid Build Coastguard Worker * libkmod - interface to kernel module operations
3*cc4ad7daSAndroid Build Coastguard Worker *
4*cc4ad7daSAndroid Build Coastguard Worker * Copyright (C) 2011-2013 ProFUSION embedded systems
5*cc4ad7daSAndroid Build Coastguard Worker *
6*cc4ad7daSAndroid Build Coastguard Worker * This library is free software; you can redistribute it and/or
7*cc4ad7daSAndroid Build Coastguard Worker * modify it under the terms of the GNU Lesser General Public
8*cc4ad7daSAndroid Build Coastguard Worker * License as published by the Free Software Foundation; either
9*cc4ad7daSAndroid Build Coastguard Worker * version 2.1 of the License, or (at your option) any later version.
10*cc4ad7daSAndroid Build Coastguard Worker *
11*cc4ad7daSAndroid Build Coastguard Worker * This library is distributed in the hope that it will be useful,
12*cc4ad7daSAndroid Build Coastguard Worker * but WITHOUT ANY WARRANTY; without even the implied warranty of
13*cc4ad7daSAndroid Build Coastguard Worker * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14*cc4ad7daSAndroid Build Coastguard Worker * Lesser General Public License for more details.
15*cc4ad7daSAndroid Build Coastguard Worker *
16*cc4ad7daSAndroid Build Coastguard Worker * You should have received a copy of the GNU Lesser General Public
17*cc4ad7daSAndroid Build Coastguard Worker * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18*cc4ad7daSAndroid Build Coastguard Worker */
19*cc4ad7daSAndroid Build Coastguard Worker
20*cc4ad7daSAndroid Build Coastguard Worker #include <arpa/inet.h>
21*cc4ad7daSAndroid Build Coastguard Worker #include <assert.h>
22*cc4ad7daSAndroid Build Coastguard Worker #include <errno.h>
23*cc4ad7daSAndroid Build Coastguard Worker #include <fnmatch.h>
24*cc4ad7daSAndroid Build Coastguard Worker #include <inttypes.h>
25*cc4ad7daSAndroid Build Coastguard Worker #include <stdio.h>
26*cc4ad7daSAndroid Build Coastguard Worker #include <stdlib.h>
27*cc4ad7daSAndroid Build Coastguard Worker #include <string.h>
28*cc4ad7daSAndroid Build Coastguard Worker
29*cc4ad7daSAndroid Build Coastguard Worker #include <shared/macro.h>
30*cc4ad7daSAndroid Build Coastguard Worker #include <shared/strbuf.h>
31*cc4ad7daSAndroid Build Coastguard Worker #include <shared/util.h>
32*cc4ad7daSAndroid Build Coastguard Worker
33*cc4ad7daSAndroid Build Coastguard Worker #include "libkmod-internal.h"
34*cc4ad7daSAndroid Build Coastguard Worker #include "libkmod-index.h"
35*cc4ad7daSAndroid Build Coastguard Worker
36*cc4ad7daSAndroid Build Coastguard Worker /* libkmod-index.c: module index file implementation
37*cc4ad7daSAndroid Build Coastguard Worker *
38*cc4ad7daSAndroid Build Coastguard Worker * Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
39*cc4ad7daSAndroid Build Coastguard Worker * All files start with a magic number.
40*cc4ad7daSAndroid Build Coastguard Worker *
41*cc4ad7daSAndroid Build Coastguard Worker * Magic spells "BOOTFAST". Second one used on newer versioned binary files.
42*cc4ad7daSAndroid Build Coastguard Worker * #define INDEX_MAGIC_OLD 0xB007FA57
43*cc4ad7daSAndroid Build Coastguard Worker *
44*cc4ad7daSAndroid Build Coastguard Worker * We use a version string to keep track of changes to the binary format
45*cc4ad7daSAndroid Build Coastguard Worker * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
46*cc4ad7daSAndroid Build Coastguard Worker * case we ever decide to have minor changes that are not incompatible.
47*cc4ad7daSAndroid Build Coastguard Worker */
48*cc4ad7daSAndroid Build Coastguard Worker #define INDEX_MAGIC 0xB007F457
49*cc4ad7daSAndroid Build Coastguard Worker #define INDEX_VERSION_MAJOR 0x0002
50*cc4ad7daSAndroid Build Coastguard Worker #define INDEX_VERSION_MINOR 0x0001
51*cc4ad7daSAndroid Build Coastguard Worker #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
52*cc4ad7daSAndroid Build Coastguard Worker
53*cc4ad7daSAndroid Build Coastguard Worker /* The index file maps keys to values. Both keys and values are ASCII strings.
54*cc4ad7daSAndroid Build Coastguard Worker * Each key can have multiple values. Values are sorted by an integer priority.
55*cc4ad7daSAndroid Build Coastguard Worker *
56*cc4ad7daSAndroid Build Coastguard Worker * The reader also implements a wildcard search (including range expressions)
57*cc4ad7daSAndroid Build Coastguard Worker * where the keys in the index are treated as patterns.
58*cc4ad7daSAndroid Build Coastguard Worker * This feature is required for module aliases.
59*cc4ad7daSAndroid Build Coastguard Worker */
60*cc4ad7daSAndroid Build Coastguard Worker #define INDEX_CHILDMAX 128
61*cc4ad7daSAndroid Build Coastguard Worker
62*cc4ad7daSAndroid Build Coastguard Worker /* Disk format:
63*cc4ad7daSAndroid Build Coastguard Worker *
64*cc4ad7daSAndroid Build Coastguard Worker * uint32_t magic = INDEX_MAGIC;
65*cc4ad7daSAndroid Build Coastguard Worker * uint32_t version = INDEX_VERSION;
66*cc4ad7daSAndroid Build Coastguard Worker * uint32_t root_offset;
67*cc4ad7daSAndroid Build Coastguard Worker *
68*cc4ad7daSAndroid Build Coastguard Worker * (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
69*cc4ad7daSAndroid Build Coastguard Worker *
70*cc4ad7daSAndroid Build Coastguard Worker * char[] prefix; // nul terminated
71*cc4ad7daSAndroid Build Coastguard Worker *
72*cc4ad7daSAndroid Build Coastguard Worker * char first;
73*cc4ad7daSAndroid Build Coastguard Worker * char last;
74*cc4ad7daSAndroid Build Coastguard Worker * uint32_t children[last - first + 1];
75*cc4ad7daSAndroid Build Coastguard Worker *
76*cc4ad7daSAndroid Build Coastguard Worker * uint32_t value_count;
77*cc4ad7daSAndroid Build Coastguard Worker * struct {
78*cc4ad7daSAndroid Build Coastguard Worker * uint32_t priority;
79*cc4ad7daSAndroid Build Coastguard Worker * char[] value; // nul terminated
80*cc4ad7daSAndroid Build Coastguard Worker * } values[value_count];
81*cc4ad7daSAndroid Build Coastguard Worker *
82*cc4ad7daSAndroid Build Coastguard Worker * (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
83*cc4ad7daSAndroid Build Coastguard Worker * Empty prefixes are omitted, leaf nodes omit the three child-related fields.
84*cc4ad7daSAndroid Build Coastguard Worker *
85*cc4ad7daSAndroid Build Coastguard Worker * This could be optimised further by adding a sparse child format
86*cc4ad7daSAndroid Build Coastguard Worker * (indicated using a new flag).
87*cc4ad7daSAndroid Build Coastguard Worker *
88*cc4ad7daSAndroid Build Coastguard Worker *
89*cc4ad7daSAndroid Build Coastguard Worker * Implementation is based on a radix tree, or "trie".
90*cc4ad7daSAndroid Build Coastguard Worker * Each arc from parent to child is labelled with a character.
91*cc4ad7daSAndroid Build Coastguard Worker * Each path from the root represents a string.
92*cc4ad7daSAndroid Build Coastguard Worker *
93*cc4ad7daSAndroid Build Coastguard Worker * == Example strings ==
94*cc4ad7daSAndroid Build Coastguard Worker *
95*cc4ad7daSAndroid Build Coastguard Worker * ask
96*cc4ad7daSAndroid Build Coastguard Worker * ate
97*cc4ad7daSAndroid Build Coastguard Worker * on
98*cc4ad7daSAndroid Build Coastguard Worker * once
99*cc4ad7daSAndroid Build Coastguard Worker * one
100*cc4ad7daSAndroid Build Coastguard Worker *
101*cc4ad7daSAndroid Build Coastguard Worker * == Key ==
102*cc4ad7daSAndroid Build Coastguard Worker * + Normal node
103*cc4ad7daSAndroid Build Coastguard Worker * * Marked node, representing a key and it's values.
104*cc4ad7daSAndroid Build Coastguard Worker *
105*cc4ad7daSAndroid Build Coastguard Worker * +
106*cc4ad7daSAndroid Build Coastguard Worker * |-a-+-s-+-k-*
107*cc4ad7daSAndroid Build Coastguard Worker * | |
108*cc4ad7daSAndroid Build Coastguard Worker * | `-t-+-e-*
109*cc4ad7daSAndroid Build Coastguard Worker * |
110*cc4ad7daSAndroid Build Coastguard Worker * `-o-+-n-*-c-+-e-*
111*cc4ad7daSAndroid Build Coastguard Worker * |
112*cc4ad7daSAndroid Build Coastguard Worker * `-e-*
113*cc4ad7daSAndroid Build Coastguard Worker *
114*cc4ad7daSAndroid Build Coastguard Worker * Naive implementations tend to be very space inefficient; child pointers
115*cc4ad7daSAndroid Build Coastguard Worker * are stored in arrays indexed by character, but most child pointers are null.
116*cc4ad7daSAndroid Build Coastguard Worker *
117*cc4ad7daSAndroid Build Coastguard Worker * Our implementation uses a scheme described by Wikipedia as a Patrica trie,
118*cc4ad7daSAndroid Build Coastguard Worker *
119*cc4ad7daSAndroid Build Coastguard Worker * "easiest to understand as a space-optimized trie where
120*cc4ad7daSAndroid Build Coastguard Worker * each node with only one child is merged with its child"
121*cc4ad7daSAndroid Build Coastguard Worker *
122*cc4ad7daSAndroid Build Coastguard Worker * +
123*cc4ad7daSAndroid Build Coastguard Worker * |-a-+-sk-*
124*cc4ad7daSAndroid Build Coastguard Worker * | |
125*cc4ad7daSAndroid Build Coastguard Worker * | `-te-*
126*cc4ad7daSAndroid Build Coastguard Worker * |
127*cc4ad7daSAndroid Build Coastguard Worker * `-on-*-ce-*
128*cc4ad7daSAndroid Build Coastguard Worker * |
129*cc4ad7daSAndroid Build Coastguard Worker * `-e-*
130*cc4ad7daSAndroid Build Coastguard Worker *
131*cc4ad7daSAndroid Build Coastguard Worker * We still use arrays of child pointers indexed by a single character;
132*cc4ad7daSAndroid Build Coastguard Worker * the remaining characters of the label are stored as a "prefix" in the child.
133*cc4ad7daSAndroid Build Coastguard Worker *
134*cc4ad7daSAndroid Build Coastguard Worker * The paper describing the original Patrica trie works on individiual bits -
135*cc4ad7daSAndroid Build Coastguard Worker * each node has a maximum of two children, which increases space efficiency.
136*cc4ad7daSAndroid Build Coastguard Worker * However for this application it is simpler to use the ASCII character set.
137*cc4ad7daSAndroid Build Coastguard Worker * Since the index file is read-only, it can be compressed by omitting null
138*cc4ad7daSAndroid Build Coastguard Worker * child pointers at the start and end of arrays.
139*cc4ad7daSAndroid Build Coastguard Worker */
140*cc4ad7daSAndroid Build Coastguard Worker
141*cc4ad7daSAndroid Build Coastguard Worker /* Format of node offsets within index file */
142*cc4ad7daSAndroid Build Coastguard Worker enum node_offset {
143*cc4ad7daSAndroid Build Coastguard Worker INDEX_NODE_FLAGS = 0xF0000000, /* Flags in high nibble */
144*cc4ad7daSAndroid Build Coastguard Worker INDEX_NODE_PREFIX = 0x80000000,
145*cc4ad7daSAndroid Build Coastguard Worker INDEX_NODE_VALUES = 0x40000000,
146*cc4ad7daSAndroid Build Coastguard Worker INDEX_NODE_CHILDS = 0x20000000,
147*cc4ad7daSAndroid Build Coastguard Worker
148*cc4ad7daSAndroid Build Coastguard Worker INDEX_NODE_MASK = 0x0FFFFFFF, /* Offset value */
149*cc4ad7daSAndroid Build Coastguard Worker };
150*cc4ad7daSAndroid Build Coastguard Worker
index_values_free(struct index_value * values)151*cc4ad7daSAndroid Build Coastguard Worker void index_values_free(struct index_value *values)
152*cc4ad7daSAndroid Build Coastguard Worker {
153*cc4ad7daSAndroid Build Coastguard Worker while (values) {
154*cc4ad7daSAndroid Build Coastguard Worker struct index_value *value = values;
155*cc4ad7daSAndroid Build Coastguard Worker
156*cc4ad7daSAndroid Build Coastguard Worker values = value->next;
157*cc4ad7daSAndroid Build Coastguard Worker free(value);
158*cc4ad7daSAndroid Build Coastguard Worker }
159*cc4ad7daSAndroid Build Coastguard Worker }
160*cc4ad7daSAndroid Build Coastguard Worker
add_value(struct index_value ** values,const char * value,unsigned len,unsigned int priority)161*cc4ad7daSAndroid Build Coastguard Worker static int add_value(struct index_value **values,
162*cc4ad7daSAndroid Build Coastguard Worker const char *value, unsigned len, unsigned int priority)
163*cc4ad7daSAndroid Build Coastguard Worker {
164*cc4ad7daSAndroid Build Coastguard Worker struct index_value *v;
165*cc4ad7daSAndroid Build Coastguard Worker
166*cc4ad7daSAndroid Build Coastguard Worker /* find position to insert value */
167*cc4ad7daSAndroid Build Coastguard Worker while (*values && (*values)->priority < priority)
168*cc4ad7daSAndroid Build Coastguard Worker values = &(*values)->next;
169*cc4ad7daSAndroid Build Coastguard Worker
170*cc4ad7daSAndroid Build Coastguard Worker v = malloc(sizeof(struct index_value) + len + 1);
171*cc4ad7daSAndroid Build Coastguard Worker if (!v)
172*cc4ad7daSAndroid Build Coastguard Worker return -1;
173*cc4ad7daSAndroid Build Coastguard Worker v->next = *values;
174*cc4ad7daSAndroid Build Coastguard Worker v->priority = priority;
175*cc4ad7daSAndroid Build Coastguard Worker v->len = len;
176*cc4ad7daSAndroid Build Coastguard Worker memcpy(v->value, value, len);
177*cc4ad7daSAndroid Build Coastguard Worker v->value[len] = '\0';
178*cc4ad7daSAndroid Build Coastguard Worker *values = v;
179*cc4ad7daSAndroid Build Coastguard Worker
180*cc4ad7daSAndroid Build Coastguard Worker return 0;
181*cc4ad7daSAndroid Build Coastguard Worker }
182*cc4ad7daSAndroid Build Coastguard Worker
read_error(void)183*cc4ad7daSAndroid Build Coastguard Worker static void read_error(void)
184*cc4ad7daSAndroid Build Coastguard Worker {
185*cc4ad7daSAndroid Build Coastguard Worker fatal("Module index: unexpected error: %s\n"
186*cc4ad7daSAndroid Build Coastguard Worker "Try re-running depmod\n", errno ? strerror(errno) : "EOF");
187*cc4ad7daSAndroid Build Coastguard Worker }
188*cc4ad7daSAndroid Build Coastguard Worker
read_char(FILE * in)189*cc4ad7daSAndroid Build Coastguard Worker static int read_char(FILE *in)
190*cc4ad7daSAndroid Build Coastguard Worker {
191*cc4ad7daSAndroid Build Coastguard Worker int ch;
192*cc4ad7daSAndroid Build Coastguard Worker
193*cc4ad7daSAndroid Build Coastguard Worker errno = 0;
194*cc4ad7daSAndroid Build Coastguard Worker ch = getc_unlocked(in);
195*cc4ad7daSAndroid Build Coastguard Worker if (ch == EOF)
196*cc4ad7daSAndroid Build Coastguard Worker read_error();
197*cc4ad7daSAndroid Build Coastguard Worker return ch;
198*cc4ad7daSAndroid Build Coastguard Worker }
199*cc4ad7daSAndroid Build Coastguard Worker
read_long(FILE * in)200*cc4ad7daSAndroid Build Coastguard Worker static uint32_t read_long(FILE *in)
201*cc4ad7daSAndroid Build Coastguard Worker {
202*cc4ad7daSAndroid Build Coastguard Worker uint32_t l;
203*cc4ad7daSAndroid Build Coastguard Worker
204*cc4ad7daSAndroid Build Coastguard Worker errno = 0;
205*cc4ad7daSAndroid Build Coastguard Worker if (fread(&l, sizeof(uint32_t), 1, in) != sizeof(uint32_t))
206*cc4ad7daSAndroid Build Coastguard Worker read_error();
207*cc4ad7daSAndroid Build Coastguard Worker return ntohl(l);
208*cc4ad7daSAndroid Build Coastguard Worker }
209*cc4ad7daSAndroid Build Coastguard Worker
buf_freadchars(struct strbuf * buf,FILE * in)210*cc4ad7daSAndroid Build Coastguard Worker static unsigned buf_freadchars(struct strbuf *buf, FILE *in)
211*cc4ad7daSAndroid Build Coastguard Worker {
212*cc4ad7daSAndroid Build Coastguard Worker unsigned i = 0;
213*cc4ad7daSAndroid Build Coastguard Worker int ch;
214*cc4ad7daSAndroid Build Coastguard Worker
215*cc4ad7daSAndroid Build Coastguard Worker while ((ch = read_char(in))) {
216*cc4ad7daSAndroid Build Coastguard Worker if (!strbuf_pushchar(buf, ch))
217*cc4ad7daSAndroid Build Coastguard Worker break;
218*cc4ad7daSAndroid Build Coastguard Worker i++;
219*cc4ad7daSAndroid Build Coastguard Worker }
220*cc4ad7daSAndroid Build Coastguard Worker
221*cc4ad7daSAndroid Build Coastguard Worker return i;
222*cc4ad7daSAndroid Build Coastguard Worker }
223*cc4ad7daSAndroid Build Coastguard Worker
224*cc4ad7daSAndroid Build Coastguard Worker /*
225*cc4ad7daSAndroid Build Coastguard Worker * Index file searching
226*cc4ad7daSAndroid Build Coastguard Worker */
227*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f {
228*cc4ad7daSAndroid Build Coastguard Worker FILE *file;
229*cc4ad7daSAndroid Build Coastguard Worker char *prefix; /* path compression */
230*cc4ad7daSAndroid Build Coastguard Worker struct index_value *values;
231*cc4ad7daSAndroid Build Coastguard Worker unsigned char first; /* range of child nodes */
232*cc4ad7daSAndroid Build Coastguard Worker unsigned char last;
233*cc4ad7daSAndroid Build Coastguard Worker uint32_t children[0];
234*cc4ad7daSAndroid Build Coastguard Worker };
235*cc4ad7daSAndroid Build Coastguard Worker
index_read(FILE * in,uint32_t offset)236*cc4ad7daSAndroid Build Coastguard Worker static struct index_node_f *index_read(FILE *in, uint32_t offset)
237*cc4ad7daSAndroid Build Coastguard Worker {
238*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *node;
239*cc4ad7daSAndroid Build Coastguard Worker char *prefix;
240*cc4ad7daSAndroid Build Coastguard Worker int i, child_count = 0;
241*cc4ad7daSAndroid Build Coastguard Worker
242*cc4ad7daSAndroid Build Coastguard Worker if ((offset & INDEX_NODE_MASK) == 0)
243*cc4ad7daSAndroid Build Coastguard Worker return NULL;
244*cc4ad7daSAndroid Build Coastguard Worker
245*cc4ad7daSAndroid Build Coastguard Worker if (fseek(in, offset & INDEX_NODE_MASK, SEEK_SET) < 0)
246*cc4ad7daSAndroid Build Coastguard Worker return NULL;
247*cc4ad7daSAndroid Build Coastguard Worker
248*cc4ad7daSAndroid Build Coastguard Worker if (offset & INDEX_NODE_PREFIX) {
249*cc4ad7daSAndroid Build Coastguard Worker struct strbuf buf;
250*cc4ad7daSAndroid Build Coastguard Worker strbuf_init(&buf);
251*cc4ad7daSAndroid Build Coastguard Worker buf_freadchars(&buf, in);
252*cc4ad7daSAndroid Build Coastguard Worker prefix = strbuf_steal(&buf);
253*cc4ad7daSAndroid Build Coastguard Worker } else
254*cc4ad7daSAndroid Build Coastguard Worker prefix = NOFAIL(strdup(""));
255*cc4ad7daSAndroid Build Coastguard Worker
256*cc4ad7daSAndroid Build Coastguard Worker if (offset & INDEX_NODE_CHILDS) {
257*cc4ad7daSAndroid Build Coastguard Worker char first = read_char(in);
258*cc4ad7daSAndroid Build Coastguard Worker char last = read_char(in);
259*cc4ad7daSAndroid Build Coastguard Worker child_count = last - first + 1;
260*cc4ad7daSAndroid Build Coastguard Worker
261*cc4ad7daSAndroid Build Coastguard Worker node = NOFAIL(malloc(sizeof(struct index_node_f) +
262*cc4ad7daSAndroid Build Coastguard Worker sizeof(uint32_t) * child_count));
263*cc4ad7daSAndroid Build Coastguard Worker
264*cc4ad7daSAndroid Build Coastguard Worker node->first = first;
265*cc4ad7daSAndroid Build Coastguard Worker node->last = last;
266*cc4ad7daSAndroid Build Coastguard Worker
267*cc4ad7daSAndroid Build Coastguard Worker for (i = 0; i < child_count; i++)
268*cc4ad7daSAndroid Build Coastguard Worker node->children[i] = read_long(in);
269*cc4ad7daSAndroid Build Coastguard Worker } else {
270*cc4ad7daSAndroid Build Coastguard Worker node = NOFAIL(malloc(sizeof(struct index_node_f)));
271*cc4ad7daSAndroid Build Coastguard Worker node->first = INDEX_CHILDMAX;
272*cc4ad7daSAndroid Build Coastguard Worker node->last = 0;
273*cc4ad7daSAndroid Build Coastguard Worker }
274*cc4ad7daSAndroid Build Coastguard Worker
275*cc4ad7daSAndroid Build Coastguard Worker node->values = NULL;
276*cc4ad7daSAndroid Build Coastguard Worker if (offset & INDEX_NODE_VALUES) {
277*cc4ad7daSAndroid Build Coastguard Worker int value_count;
278*cc4ad7daSAndroid Build Coastguard Worker struct strbuf buf;
279*cc4ad7daSAndroid Build Coastguard Worker const char *value;
280*cc4ad7daSAndroid Build Coastguard Worker unsigned int priority;
281*cc4ad7daSAndroid Build Coastguard Worker
282*cc4ad7daSAndroid Build Coastguard Worker value_count = read_long(in);
283*cc4ad7daSAndroid Build Coastguard Worker
284*cc4ad7daSAndroid Build Coastguard Worker strbuf_init(&buf);
285*cc4ad7daSAndroid Build Coastguard Worker while (value_count--) {
286*cc4ad7daSAndroid Build Coastguard Worker priority = read_long(in);
287*cc4ad7daSAndroid Build Coastguard Worker buf_freadchars(&buf, in);
288*cc4ad7daSAndroid Build Coastguard Worker value = strbuf_str(&buf);
289*cc4ad7daSAndroid Build Coastguard Worker add_value(&node->values, value, buf.used, priority);
290*cc4ad7daSAndroid Build Coastguard Worker strbuf_clear(&buf);
291*cc4ad7daSAndroid Build Coastguard Worker }
292*cc4ad7daSAndroid Build Coastguard Worker strbuf_release(&buf);
293*cc4ad7daSAndroid Build Coastguard Worker }
294*cc4ad7daSAndroid Build Coastguard Worker
295*cc4ad7daSAndroid Build Coastguard Worker node->prefix = prefix;
296*cc4ad7daSAndroid Build Coastguard Worker node->file = in;
297*cc4ad7daSAndroid Build Coastguard Worker return node;
298*cc4ad7daSAndroid Build Coastguard Worker }
299*cc4ad7daSAndroid Build Coastguard Worker
index_close(struct index_node_f * node)300*cc4ad7daSAndroid Build Coastguard Worker static void index_close(struct index_node_f *node)
301*cc4ad7daSAndroid Build Coastguard Worker {
302*cc4ad7daSAndroid Build Coastguard Worker free(node->prefix);
303*cc4ad7daSAndroid Build Coastguard Worker index_values_free(node->values);
304*cc4ad7daSAndroid Build Coastguard Worker free(node);
305*cc4ad7daSAndroid Build Coastguard Worker }
306*cc4ad7daSAndroid Build Coastguard Worker
307*cc4ad7daSAndroid Build Coastguard Worker struct index_file {
308*cc4ad7daSAndroid Build Coastguard Worker FILE *file;
309*cc4ad7daSAndroid Build Coastguard Worker uint32_t root_offset;
310*cc4ad7daSAndroid Build Coastguard Worker };
311*cc4ad7daSAndroid Build Coastguard Worker
index_file_open(const char * filename)312*cc4ad7daSAndroid Build Coastguard Worker struct index_file *index_file_open(const char *filename)
313*cc4ad7daSAndroid Build Coastguard Worker {
314*cc4ad7daSAndroid Build Coastguard Worker FILE *file;
315*cc4ad7daSAndroid Build Coastguard Worker uint32_t magic, version;
316*cc4ad7daSAndroid Build Coastguard Worker struct index_file *new;
317*cc4ad7daSAndroid Build Coastguard Worker
318*cc4ad7daSAndroid Build Coastguard Worker file = fopen(filename, "re");
319*cc4ad7daSAndroid Build Coastguard Worker if (!file)
320*cc4ad7daSAndroid Build Coastguard Worker return NULL;
321*cc4ad7daSAndroid Build Coastguard Worker errno = EINVAL;
322*cc4ad7daSAndroid Build Coastguard Worker
323*cc4ad7daSAndroid Build Coastguard Worker magic = read_long(file);
324*cc4ad7daSAndroid Build Coastguard Worker if (magic != INDEX_MAGIC) {
325*cc4ad7daSAndroid Build Coastguard Worker fclose(file);
326*cc4ad7daSAndroid Build Coastguard Worker return NULL;
327*cc4ad7daSAndroid Build Coastguard Worker }
328*cc4ad7daSAndroid Build Coastguard Worker
329*cc4ad7daSAndroid Build Coastguard Worker version = read_long(file);
330*cc4ad7daSAndroid Build Coastguard Worker if (version >> 16 != INDEX_VERSION_MAJOR) {
331*cc4ad7daSAndroid Build Coastguard Worker fclose(file);
332*cc4ad7daSAndroid Build Coastguard Worker return NULL;
333*cc4ad7daSAndroid Build Coastguard Worker }
334*cc4ad7daSAndroid Build Coastguard Worker
335*cc4ad7daSAndroid Build Coastguard Worker new = NOFAIL(malloc(sizeof(struct index_file)));
336*cc4ad7daSAndroid Build Coastguard Worker new->file = file;
337*cc4ad7daSAndroid Build Coastguard Worker new->root_offset = read_long(new->file);
338*cc4ad7daSAndroid Build Coastguard Worker
339*cc4ad7daSAndroid Build Coastguard Worker errno = 0;
340*cc4ad7daSAndroid Build Coastguard Worker return new;
341*cc4ad7daSAndroid Build Coastguard Worker }
342*cc4ad7daSAndroid Build Coastguard Worker
index_file_close(struct index_file * idx)343*cc4ad7daSAndroid Build Coastguard Worker void index_file_close(struct index_file *idx)
344*cc4ad7daSAndroid Build Coastguard Worker {
345*cc4ad7daSAndroid Build Coastguard Worker fclose(idx->file);
346*cc4ad7daSAndroid Build Coastguard Worker free(idx);
347*cc4ad7daSAndroid Build Coastguard Worker }
348*cc4ad7daSAndroid Build Coastguard Worker
index_readroot(struct index_file * in)349*cc4ad7daSAndroid Build Coastguard Worker static struct index_node_f *index_readroot(struct index_file *in)
350*cc4ad7daSAndroid Build Coastguard Worker {
351*cc4ad7daSAndroid Build Coastguard Worker return index_read(in->file, in->root_offset);
352*cc4ad7daSAndroid Build Coastguard Worker }
353*cc4ad7daSAndroid Build Coastguard Worker
index_readchild(const struct index_node_f * parent,int ch)354*cc4ad7daSAndroid Build Coastguard Worker static struct index_node_f *index_readchild(const struct index_node_f *parent,
355*cc4ad7daSAndroid Build Coastguard Worker int ch)
356*cc4ad7daSAndroid Build Coastguard Worker {
357*cc4ad7daSAndroid Build Coastguard Worker if (parent->first <= ch && ch <= parent->last) {
358*cc4ad7daSAndroid Build Coastguard Worker return index_read(parent->file,
359*cc4ad7daSAndroid Build Coastguard Worker parent->children[ch - parent->first]);
360*cc4ad7daSAndroid Build Coastguard Worker }
361*cc4ad7daSAndroid Build Coastguard Worker
362*cc4ad7daSAndroid Build Coastguard Worker return NULL;
363*cc4ad7daSAndroid Build Coastguard Worker }
364*cc4ad7daSAndroid Build Coastguard Worker
index_dump_node(struct index_node_f * node,struct strbuf * buf,int fd)365*cc4ad7daSAndroid Build Coastguard Worker static void index_dump_node(struct index_node_f *node, struct strbuf *buf,
366*cc4ad7daSAndroid Build Coastguard Worker int fd)
367*cc4ad7daSAndroid Build Coastguard Worker {
368*cc4ad7daSAndroid Build Coastguard Worker struct index_value *v;
369*cc4ad7daSAndroid Build Coastguard Worker int ch, pushed;
370*cc4ad7daSAndroid Build Coastguard Worker
371*cc4ad7daSAndroid Build Coastguard Worker pushed = strbuf_pushchars(buf, node->prefix);
372*cc4ad7daSAndroid Build Coastguard Worker
373*cc4ad7daSAndroid Build Coastguard Worker for (v = node->values; v != NULL; v = v->next) {
374*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, buf->bytes, buf->used);
375*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, " ", 1);
376*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, v->value, strlen(v->value));
377*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, "\n", 1);
378*cc4ad7daSAndroid Build Coastguard Worker }
379*cc4ad7daSAndroid Build Coastguard Worker
380*cc4ad7daSAndroid Build Coastguard Worker for (ch = node->first; ch <= node->last; ch++) {
381*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *child = index_readchild(node, ch);
382*cc4ad7daSAndroid Build Coastguard Worker
383*cc4ad7daSAndroid Build Coastguard Worker if (!child)
384*cc4ad7daSAndroid Build Coastguard Worker continue;
385*cc4ad7daSAndroid Build Coastguard Worker
386*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, ch);
387*cc4ad7daSAndroid Build Coastguard Worker index_dump_node(child, buf, fd);
388*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
389*cc4ad7daSAndroid Build Coastguard Worker }
390*cc4ad7daSAndroid Build Coastguard Worker
391*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchars(buf, pushed);
392*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
393*cc4ad7daSAndroid Build Coastguard Worker }
394*cc4ad7daSAndroid Build Coastguard Worker
index_dump(struct index_file * in,int fd,const char * prefix)395*cc4ad7daSAndroid Build Coastguard Worker void index_dump(struct index_file *in, int fd, const char *prefix)
396*cc4ad7daSAndroid Build Coastguard Worker {
397*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *root;
398*cc4ad7daSAndroid Build Coastguard Worker struct strbuf buf;
399*cc4ad7daSAndroid Build Coastguard Worker
400*cc4ad7daSAndroid Build Coastguard Worker root = index_readroot(in);
401*cc4ad7daSAndroid Build Coastguard Worker if (root == NULL)
402*cc4ad7daSAndroid Build Coastguard Worker return;
403*cc4ad7daSAndroid Build Coastguard Worker
404*cc4ad7daSAndroid Build Coastguard Worker strbuf_init(&buf);
405*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchars(&buf, prefix);
406*cc4ad7daSAndroid Build Coastguard Worker index_dump_node(root, &buf, fd);
407*cc4ad7daSAndroid Build Coastguard Worker strbuf_release(&buf);
408*cc4ad7daSAndroid Build Coastguard Worker }
409*cc4ad7daSAndroid Build Coastguard Worker
index_search__node(struct index_node_f * node,const char * key,int i)410*cc4ad7daSAndroid Build Coastguard Worker static char *index_search__node(struct index_node_f *node, const char *key, int i)
411*cc4ad7daSAndroid Build Coastguard Worker {
412*cc4ad7daSAndroid Build Coastguard Worker char *value;
413*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *child;
414*cc4ad7daSAndroid Build Coastguard Worker int ch;
415*cc4ad7daSAndroid Build Coastguard Worker int j;
416*cc4ad7daSAndroid Build Coastguard Worker
417*cc4ad7daSAndroid Build Coastguard Worker while(node) {
418*cc4ad7daSAndroid Build Coastguard Worker for (j = 0; node->prefix[j]; j++) {
419*cc4ad7daSAndroid Build Coastguard Worker ch = node->prefix[j];
420*cc4ad7daSAndroid Build Coastguard Worker
421*cc4ad7daSAndroid Build Coastguard Worker if (ch != key[i+j]) {
422*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
423*cc4ad7daSAndroid Build Coastguard Worker return NULL;
424*cc4ad7daSAndroid Build Coastguard Worker }
425*cc4ad7daSAndroid Build Coastguard Worker }
426*cc4ad7daSAndroid Build Coastguard Worker
427*cc4ad7daSAndroid Build Coastguard Worker i += j;
428*cc4ad7daSAndroid Build Coastguard Worker
429*cc4ad7daSAndroid Build Coastguard Worker if (key[i] == '\0') {
430*cc4ad7daSAndroid Build Coastguard Worker value = node->values != NULL
431*cc4ad7daSAndroid Build Coastguard Worker ? strdup(node->values[0].value)
432*cc4ad7daSAndroid Build Coastguard Worker : NULL;
433*cc4ad7daSAndroid Build Coastguard Worker
434*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
435*cc4ad7daSAndroid Build Coastguard Worker return value;
436*cc4ad7daSAndroid Build Coastguard Worker }
437*cc4ad7daSAndroid Build Coastguard Worker
438*cc4ad7daSAndroid Build Coastguard Worker child = index_readchild(node, key[i]);
439*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
440*cc4ad7daSAndroid Build Coastguard Worker node = child;
441*cc4ad7daSAndroid Build Coastguard Worker i++;
442*cc4ad7daSAndroid Build Coastguard Worker }
443*cc4ad7daSAndroid Build Coastguard Worker
444*cc4ad7daSAndroid Build Coastguard Worker return NULL;
445*cc4ad7daSAndroid Build Coastguard Worker }
446*cc4ad7daSAndroid Build Coastguard Worker
447*cc4ad7daSAndroid Build Coastguard Worker /*
448*cc4ad7daSAndroid Build Coastguard Worker * Search the index for a key
449*cc4ad7daSAndroid Build Coastguard Worker *
450*cc4ad7daSAndroid Build Coastguard Worker * Returns the value of the first match
451*cc4ad7daSAndroid Build Coastguard Worker *
452*cc4ad7daSAndroid Build Coastguard Worker * The recursive functions free their node argument (using index_close).
453*cc4ad7daSAndroid Build Coastguard Worker */
index_search(struct index_file * in,const char * key)454*cc4ad7daSAndroid Build Coastguard Worker char *index_search(struct index_file *in, const char *key)
455*cc4ad7daSAndroid Build Coastguard Worker {
456*cc4ad7daSAndroid Build Coastguard Worker // FIXME: return value by reference instead of strdup
457*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *root;
458*cc4ad7daSAndroid Build Coastguard Worker char *value;
459*cc4ad7daSAndroid Build Coastguard Worker
460*cc4ad7daSAndroid Build Coastguard Worker root = index_readroot(in);
461*cc4ad7daSAndroid Build Coastguard Worker value = index_search__node(root, key, 0);
462*cc4ad7daSAndroid Build Coastguard Worker
463*cc4ad7daSAndroid Build Coastguard Worker return value;
464*cc4ad7daSAndroid Build Coastguard Worker }
465*cc4ad7daSAndroid Build Coastguard Worker
466*cc4ad7daSAndroid Build Coastguard Worker
467*cc4ad7daSAndroid Build Coastguard Worker
468*cc4ad7daSAndroid Build Coastguard Worker /* Level 4: add all the values from a matching node */
index_searchwild__allvalues(struct index_node_f * node,struct index_value ** out)469*cc4ad7daSAndroid Build Coastguard Worker static void index_searchwild__allvalues(struct index_node_f *node,
470*cc4ad7daSAndroid Build Coastguard Worker struct index_value **out)
471*cc4ad7daSAndroid Build Coastguard Worker {
472*cc4ad7daSAndroid Build Coastguard Worker struct index_value *v;
473*cc4ad7daSAndroid Build Coastguard Worker
474*cc4ad7daSAndroid Build Coastguard Worker for (v = node->values; v != NULL; v = v->next)
475*cc4ad7daSAndroid Build Coastguard Worker add_value(out, v->value, v->len, v->priority);
476*cc4ad7daSAndroid Build Coastguard Worker
477*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
478*cc4ad7daSAndroid Build Coastguard Worker }
479*cc4ad7daSAndroid Build Coastguard Worker
480*cc4ad7daSAndroid Build Coastguard Worker /*
481*cc4ad7daSAndroid Build Coastguard Worker * Level 3: traverse a sub-keyspace which starts with a wildcard,
482*cc4ad7daSAndroid Build Coastguard Worker * looking for matches.
483*cc4ad7daSAndroid Build Coastguard Worker */
index_searchwild__all(struct index_node_f * node,int j,struct strbuf * buf,const char * subkey,struct index_value ** out)484*cc4ad7daSAndroid Build Coastguard Worker static void index_searchwild__all(struct index_node_f *node, int j,
485*cc4ad7daSAndroid Build Coastguard Worker struct strbuf *buf,
486*cc4ad7daSAndroid Build Coastguard Worker const char *subkey,
487*cc4ad7daSAndroid Build Coastguard Worker struct index_value **out)
488*cc4ad7daSAndroid Build Coastguard Worker {
489*cc4ad7daSAndroid Build Coastguard Worker int pushed = 0;
490*cc4ad7daSAndroid Build Coastguard Worker int ch;
491*cc4ad7daSAndroid Build Coastguard Worker
492*cc4ad7daSAndroid Build Coastguard Worker while (node->prefix[j]) {
493*cc4ad7daSAndroid Build Coastguard Worker ch = node->prefix[j];
494*cc4ad7daSAndroid Build Coastguard Worker
495*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, ch);
496*cc4ad7daSAndroid Build Coastguard Worker pushed++;
497*cc4ad7daSAndroid Build Coastguard Worker j++;
498*cc4ad7daSAndroid Build Coastguard Worker }
499*cc4ad7daSAndroid Build Coastguard Worker
500*cc4ad7daSAndroid Build Coastguard Worker for (ch = node->first; ch <= node->last; ch++) {
501*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *child = index_readchild(node, ch);
502*cc4ad7daSAndroid Build Coastguard Worker
503*cc4ad7daSAndroid Build Coastguard Worker if (!child)
504*cc4ad7daSAndroid Build Coastguard Worker continue;
505*cc4ad7daSAndroid Build Coastguard Worker
506*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, ch);
507*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__all(child, 0, buf, subkey, out);
508*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
509*cc4ad7daSAndroid Build Coastguard Worker }
510*cc4ad7daSAndroid Build Coastguard Worker
511*cc4ad7daSAndroid Build Coastguard Worker if (node->values) {
512*cc4ad7daSAndroid Build Coastguard Worker if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
513*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__allvalues(node, out);
514*cc4ad7daSAndroid Build Coastguard Worker else
515*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
516*cc4ad7daSAndroid Build Coastguard Worker } else {
517*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
518*cc4ad7daSAndroid Build Coastguard Worker }
519*cc4ad7daSAndroid Build Coastguard Worker
520*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchars(buf, pushed);
521*cc4ad7daSAndroid Build Coastguard Worker }
522*cc4ad7daSAndroid Build Coastguard Worker
523*cc4ad7daSAndroid Build Coastguard Worker /* Level 2: descend the tree (until we hit a wildcard) */
index_searchwild__node(struct index_node_f * node,struct strbuf * buf,const char * key,int i,struct index_value ** out)524*cc4ad7daSAndroid Build Coastguard Worker static void index_searchwild__node(struct index_node_f *node,
525*cc4ad7daSAndroid Build Coastguard Worker struct strbuf *buf,
526*cc4ad7daSAndroid Build Coastguard Worker const char *key, int i,
527*cc4ad7daSAndroid Build Coastguard Worker struct index_value **out)
528*cc4ad7daSAndroid Build Coastguard Worker {
529*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *child;
530*cc4ad7daSAndroid Build Coastguard Worker int j;
531*cc4ad7daSAndroid Build Coastguard Worker int ch;
532*cc4ad7daSAndroid Build Coastguard Worker
533*cc4ad7daSAndroid Build Coastguard Worker while(node) {
534*cc4ad7daSAndroid Build Coastguard Worker for (j = 0; node->prefix[j]; j++) {
535*cc4ad7daSAndroid Build Coastguard Worker ch = node->prefix[j];
536*cc4ad7daSAndroid Build Coastguard Worker
537*cc4ad7daSAndroid Build Coastguard Worker if (ch == '*' || ch == '?' || ch == '[') {
538*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__all(node, j, buf,
539*cc4ad7daSAndroid Build Coastguard Worker &key[i+j], out);
540*cc4ad7daSAndroid Build Coastguard Worker return;
541*cc4ad7daSAndroid Build Coastguard Worker }
542*cc4ad7daSAndroid Build Coastguard Worker
543*cc4ad7daSAndroid Build Coastguard Worker if (ch != key[i+j]) {
544*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
545*cc4ad7daSAndroid Build Coastguard Worker return;
546*cc4ad7daSAndroid Build Coastguard Worker }
547*cc4ad7daSAndroid Build Coastguard Worker }
548*cc4ad7daSAndroid Build Coastguard Worker
549*cc4ad7daSAndroid Build Coastguard Worker i += j;
550*cc4ad7daSAndroid Build Coastguard Worker
551*cc4ad7daSAndroid Build Coastguard Worker child = index_readchild(node, '*');
552*cc4ad7daSAndroid Build Coastguard Worker if (child) {
553*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, '*');
554*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__all(child, 0, buf, &key[i], out);
555*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
556*cc4ad7daSAndroid Build Coastguard Worker }
557*cc4ad7daSAndroid Build Coastguard Worker
558*cc4ad7daSAndroid Build Coastguard Worker child = index_readchild(node, '?');
559*cc4ad7daSAndroid Build Coastguard Worker if (child) {
560*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, '?');
561*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__all(child, 0, buf, &key[i], out);
562*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
563*cc4ad7daSAndroid Build Coastguard Worker }
564*cc4ad7daSAndroid Build Coastguard Worker
565*cc4ad7daSAndroid Build Coastguard Worker child = index_readchild(node, '[');
566*cc4ad7daSAndroid Build Coastguard Worker if (child) {
567*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, '[');
568*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__all(child, 0, buf, &key[i], out);
569*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
570*cc4ad7daSAndroid Build Coastguard Worker }
571*cc4ad7daSAndroid Build Coastguard Worker
572*cc4ad7daSAndroid Build Coastguard Worker if (key[i] == '\0') {
573*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__allvalues(node, out);
574*cc4ad7daSAndroid Build Coastguard Worker
575*cc4ad7daSAndroid Build Coastguard Worker return;
576*cc4ad7daSAndroid Build Coastguard Worker }
577*cc4ad7daSAndroid Build Coastguard Worker
578*cc4ad7daSAndroid Build Coastguard Worker child = index_readchild(node, key[i]);
579*cc4ad7daSAndroid Build Coastguard Worker index_close(node);
580*cc4ad7daSAndroid Build Coastguard Worker node = child;
581*cc4ad7daSAndroid Build Coastguard Worker i++;
582*cc4ad7daSAndroid Build Coastguard Worker }
583*cc4ad7daSAndroid Build Coastguard Worker }
584*cc4ad7daSAndroid Build Coastguard Worker
585*cc4ad7daSAndroid Build Coastguard Worker /*
586*cc4ad7daSAndroid Build Coastguard Worker * Search the index for a key. The index may contain wildcards.
587*cc4ad7daSAndroid Build Coastguard Worker *
588*cc4ad7daSAndroid Build Coastguard Worker * Returns a list of all the values of matching keys.
589*cc4ad7daSAndroid Build Coastguard Worker */
index_searchwild(struct index_file * in,const char * key)590*cc4ad7daSAndroid Build Coastguard Worker struct index_value *index_searchwild(struct index_file *in, const char *key)
591*cc4ad7daSAndroid Build Coastguard Worker {
592*cc4ad7daSAndroid Build Coastguard Worker struct index_node_f *root = index_readroot(in);
593*cc4ad7daSAndroid Build Coastguard Worker struct strbuf buf;
594*cc4ad7daSAndroid Build Coastguard Worker struct index_value *out = NULL;
595*cc4ad7daSAndroid Build Coastguard Worker
596*cc4ad7daSAndroid Build Coastguard Worker strbuf_init(&buf);
597*cc4ad7daSAndroid Build Coastguard Worker index_searchwild__node(root, &buf, key, 0, &out);
598*cc4ad7daSAndroid Build Coastguard Worker strbuf_release(&buf);
599*cc4ad7daSAndroid Build Coastguard Worker return out;
600*cc4ad7daSAndroid Build Coastguard Worker }
601*cc4ad7daSAndroid Build Coastguard Worker
602*cc4ad7daSAndroid Build Coastguard Worker /**************************************************************************/
603*cc4ad7daSAndroid Build Coastguard Worker /*
604*cc4ad7daSAndroid Build Coastguard Worker * Alternative implementation, using mmap to map all the file to memory when
605*cc4ad7daSAndroid Build Coastguard Worker * starting
606*cc4ad7daSAndroid Build Coastguard Worker */
607*cc4ad7daSAndroid Build Coastguard Worker #include <sys/mman.h>
608*cc4ad7daSAndroid Build Coastguard Worker #include <sys/stat.h>
609*cc4ad7daSAndroid Build Coastguard Worker #include <unistd.h>
610*cc4ad7daSAndroid Build Coastguard Worker
611*cc4ad7daSAndroid Build Coastguard Worker static const char _idx_empty_str[] = "";
612*cc4ad7daSAndroid Build Coastguard Worker
613*cc4ad7daSAndroid Build Coastguard Worker struct index_mm {
614*cc4ad7daSAndroid Build Coastguard Worker const struct kmod_ctx *ctx;
615*cc4ad7daSAndroid Build Coastguard Worker void *mm;
616*cc4ad7daSAndroid Build Coastguard Worker uint32_t root_offset;
617*cc4ad7daSAndroid Build Coastguard Worker size_t size;
618*cc4ad7daSAndroid Build Coastguard Worker };
619*cc4ad7daSAndroid Build Coastguard Worker
620*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_value {
621*cc4ad7daSAndroid Build Coastguard Worker unsigned int priority;
622*cc4ad7daSAndroid Build Coastguard Worker unsigned int len;
623*cc4ad7daSAndroid Build Coastguard Worker const char *value;
624*cc4ad7daSAndroid Build Coastguard Worker };
625*cc4ad7daSAndroid Build Coastguard Worker
626*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_value_array {
627*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_value *values;
628*cc4ad7daSAndroid Build Coastguard Worker unsigned int len;
629*cc4ad7daSAndroid Build Coastguard Worker };
630*cc4ad7daSAndroid Build Coastguard Worker
631*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node {
632*cc4ad7daSAndroid Build Coastguard Worker struct index_mm *idx;
633*cc4ad7daSAndroid Build Coastguard Worker const char *prefix; /* mmape'd value */
634*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_value_array values;
635*cc4ad7daSAndroid Build Coastguard Worker unsigned char first;
636*cc4ad7daSAndroid Build Coastguard Worker unsigned char last;
637*cc4ad7daSAndroid Build Coastguard Worker uint32_t children[];
638*cc4ad7daSAndroid Build Coastguard Worker };
639*cc4ad7daSAndroid Build Coastguard Worker
read_long_mm(void ** p)640*cc4ad7daSAndroid Build Coastguard Worker static inline uint32_t read_long_mm(void **p)
641*cc4ad7daSAndroid Build Coastguard Worker {
642*cc4ad7daSAndroid Build Coastguard Worker uint8_t *addr = *(uint8_t **)p;
643*cc4ad7daSAndroid Build Coastguard Worker uint32_t v;
644*cc4ad7daSAndroid Build Coastguard Worker
645*cc4ad7daSAndroid Build Coastguard Worker /* addr may be unalined to uint32_t */
646*cc4ad7daSAndroid Build Coastguard Worker v = get_unaligned((uint32_t *) addr);
647*cc4ad7daSAndroid Build Coastguard Worker
648*cc4ad7daSAndroid Build Coastguard Worker *p = addr + sizeof(uint32_t);
649*cc4ad7daSAndroid Build Coastguard Worker return ntohl(v);
650*cc4ad7daSAndroid Build Coastguard Worker }
651*cc4ad7daSAndroid Build Coastguard Worker
read_char_mm(void ** p)652*cc4ad7daSAndroid Build Coastguard Worker static inline uint8_t read_char_mm(void **p)
653*cc4ad7daSAndroid Build Coastguard Worker {
654*cc4ad7daSAndroid Build Coastguard Worker uint8_t *addr = *(uint8_t **)p;
655*cc4ad7daSAndroid Build Coastguard Worker uint8_t v = *addr;
656*cc4ad7daSAndroid Build Coastguard Worker *p = addr + sizeof(uint8_t);
657*cc4ad7daSAndroid Build Coastguard Worker return v;
658*cc4ad7daSAndroid Build Coastguard Worker }
659*cc4ad7daSAndroid Build Coastguard Worker
read_chars_mm(void ** p,unsigned * rlen)660*cc4ad7daSAndroid Build Coastguard Worker static inline char *read_chars_mm(void **p, unsigned *rlen)
661*cc4ad7daSAndroid Build Coastguard Worker {
662*cc4ad7daSAndroid Build Coastguard Worker char *addr = *(char **)p;
663*cc4ad7daSAndroid Build Coastguard Worker size_t len = *rlen = strlen(addr);
664*cc4ad7daSAndroid Build Coastguard Worker *p = addr + len + 1;
665*cc4ad7daSAndroid Build Coastguard Worker return addr;
666*cc4ad7daSAndroid Build Coastguard Worker }
667*cc4ad7daSAndroid Build Coastguard Worker
index_mm_read_node(struct index_mm * idx,uint32_t offset)668*cc4ad7daSAndroid Build Coastguard Worker static struct index_mm_node *index_mm_read_node(struct index_mm *idx,
669*cc4ad7daSAndroid Build Coastguard Worker uint32_t offset) {
670*cc4ad7daSAndroid Build Coastguard Worker void *p = idx->mm;
671*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *node;
672*cc4ad7daSAndroid Build Coastguard Worker const char *prefix;
673*cc4ad7daSAndroid Build Coastguard Worker int i, child_count, value_count, children_padding;
674*cc4ad7daSAndroid Build Coastguard Worker uint32_t children[INDEX_CHILDMAX];
675*cc4ad7daSAndroid Build Coastguard Worker char first, last;
676*cc4ad7daSAndroid Build Coastguard Worker
677*cc4ad7daSAndroid Build Coastguard Worker if ((offset & INDEX_NODE_MASK) == 0)
678*cc4ad7daSAndroid Build Coastguard Worker return NULL;
679*cc4ad7daSAndroid Build Coastguard Worker
680*cc4ad7daSAndroid Build Coastguard Worker p = (char *)p + (offset & INDEX_NODE_MASK);
681*cc4ad7daSAndroid Build Coastguard Worker
682*cc4ad7daSAndroid Build Coastguard Worker if (offset & INDEX_NODE_PREFIX) {
683*cc4ad7daSAndroid Build Coastguard Worker unsigned len;
684*cc4ad7daSAndroid Build Coastguard Worker prefix = read_chars_mm(&p, &len);
685*cc4ad7daSAndroid Build Coastguard Worker } else
686*cc4ad7daSAndroid Build Coastguard Worker prefix = _idx_empty_str;
687*cc4ad7daSAndroid Build Coastguard Worker
688*cc4ad7daSAndroid Build Coastguard Worker if (offset & INDEX_NODE_CHILDS) {
689*cc4ad7daSAndroid Build Coastguard Worker first = read_char_mm(&p);
690*cc4ad7daSAndroid Build Coastguard Worker last = read_char_mm(&p);
691*cc4ad7daSAndroid Build Coastguard Worker child_count = last - first + 1;
692*cc4ad7daSAndroid Build Coastguard Worker for (i = 0; i < child_count; i++)
693*cc4ad7daSAndroid Build Coastguard Worker children[i] = read_long_mm(&p);
694*cc4ad7daSAndroid Build Coastguard Worker } else {
695*cc4ad7daSAndroid Build Coastguard Worker first = (char)INDEX_CHILDMAX;
696*cc4ad7daSAndroid Build Coastguard Worker last = 0;
697*cc4ad7daSAndroid Build Coastguard Worker child_count = 0;
698*cc4ad7daSAndroid Build Coastguard Worker }
699*cc4ad7daSAndroid Build Coastguard Worker
700*cc4ad7daSAndroid Build Coastguard Worker children_padding = (sizeof(struct index_mm_node) +
701*cc4ad7daSAndroid Build Coastguard Worker (sizeof(uint32_t) * child_count)) % sizeof(void *);
702*cc4ad7daSAndroid Build Coastguard Worker
703*cc4ad7daSAndroid Build Coastguard Worker if (offset & INDEX_NODE_VALUES)
704*cc4ad7daSAndroid Build Coastguard Worker value_count = read_long_mm(&p);
705*cc4ad7daSAndroid Build Coastguard Worker else
706*cc4ad7daSAndroid Build Coastguard Worker value_count = 0;
707*cc4ad7daSAndroid Build Coastguard Worker
708*cc4ad7daSAndroid Build Coastguard Worker node = malloc(sizeof(struct index_mm_node)
709*cc4ad7daSAndroid Build Coastguard Worker + sizeof(uint32_t) * child_count + children_padding
710*cc4ad7daSAndroid Build Coastguard Worker + sizeof(struct index_mm_value) * value_count);
711*cc4ad7daSAndroid Build Coastguard Worker if (node == NULL)
712*cc4ad7daSAndroid Build Coastguard Worker return NULL;
713*cc4ad7daSAndroid Build Coastguard Worker
714*cc4ad7daSAndroid Build Coastguard Worker node->idx = idx;
715*cc4ad7daSAndroid Build Coastguard Worker node->prefix = prefix;
716*cc4ad7daSAndroid Build Coastguard Worker if (value_count == 0)
717*cc4ad7daSAndroid Build Coastguard Worker node->values.values = NULL;
718*cc4ad7daSAndroid Build Coastguard Worker else {
719*cc4ad7daSAndroid Build Coastguard Worker node->values.values = (struct index_mm_value *)
720*cc4ad7daSAndroid Build Coastguard Worker ((char *)node + sizeof(struct index_mm_node) +
721*cc4ad7daSAndroid Build Coastguard Worker sizeof(uint32_t) * child_count + children_padding);
722*cc4ad7daSAndroid Build Coastguard Worker }
723*cc4ad7daSAndroid Build Coastguard Worker node->values.len = value_count;
724*cc4ad7daSAndroid Build Coastguard Worker node->first = first;
725*cc4ad7daSAndroid Build Coastguard Worker node->last = last;
726*cc4ad7daSAndroid Build Coastguard Worker memcpy(node->children, children, sizeof(uint32_t) * child_count);
727*cc4ad7daSAndroid Build Coastguard Worker
728*cc4ad7daSAndroid Build Coastguard Worker for (i = 0; i < value_count; i++) {
729*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_value *v = node->values.values + i;
730*cc4ad7daSAndroid Build Coastguard Worker v->priority = read_long_mm(&p);
731*cc4ad7daSAndroid Build Coastguard Worker v->value = read_chars_mm(&p, &v->len);
732*cc4ad7daSAndroid Build Coastguard Worker }
733*cc4ad7daSAndroid Build Coastguard Worker
734*cc4ad7daSAndroid Build Coastguard Worker return node;
735*cc4ad7daSAndroid Build Coastguard Worker }
736*cc4ad7daSAndroid Build Coastguard Worker
index_mm_free_node(struct index_mm_node * node)737*cc4ad7daSAndroid Build Coastguard Worker static void index_mm_free_node(struct index_mm_node *node)
738*cc4ad7daSAndroid Build Coastguard Worker {
739*cc4ad7daSAndroid Build Coastguard Worker free(node);
740*cc4ad7daSAndroid Build Coastguard Worker }
741*cc4ad7daSAndroid Build Coastguard Worker
index_mm_open(const struct kmod_ctx * ctx,const char * filename,unsigned long long * stamp,struct index_mm ** pidx)742*cc4ad7daSAndroid Build Coastguard Worker int index_mm_open(const struct kmod_ctx *ctx, const char *filename,
743*cc4ad7daSAndroid Build Coastguard Worker unsigned long long *stamp, struct index_mm **pidx)
744*cc4ad7daSAndroid Build Coastguard Worker {
745*cc4ad7daSAndroid Build Coastguard Worker int fd, err;
746*cc4ad7daSAndroid Build Coastguard Worker struct stat st;
747*cc4ad7daSAndroid Build Coastguard Worker struct index_mm *idx;
748*cc4ad7daSAndroid Build Coastguard Worker struct {
749*cc4ad7daSAndroid Build Coastguard Worker uint32_t magic;
750*cc4ad7daSAndroid Build Coastguard Worker uint32_t version;
751*cc4ad7daSAndroid Build Coastguard Worker uint32_t root_offset;
752*cc4ad7daSAndroid Build Coastguard Worker } hdr;
753*cc4ad7daSAndroid Build Coastguard Worker void *p;
754*cc4ad7daSAndroid Build Coastguard Worker
755*cc4ad7daSAndroid Build Coastguard Worker assert(pidx != NULL);
756*cc4ad7daSAndroid Build Coastguard Worker
757*cc4ad7daSAndroid Build Coastguard Worker DBG(ctx, "file=%s\n", filename);
758*cc4ad7daSAndroid Build Coastguard Worker
759*cc4ad7daSAndroid Build Coastguard Worker idx = malloc(sizeof(*idx));
760*cc4ad7daSAndroid Build Coastguard Worker if (idx == NULL) {
761*cc4ad7daSAndroid Build Coastguard Worker ERR(ctx, "malloc: %m\n");
762*cc4ad7daSAndroid Build Coastguard Worker return -ENOMEM;
763*cc4ad7daSAndroid Build Coastguard Worker }
764*cc4ad7daSAndroid Build Coastguard Worker
765*cc4ad7daSAndroid Build Coastguard Worker if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
766*cc4ad7daSAndroid Build Coastguard Worker DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename);
767*cc4ad7daSAndroid Build Coastguard Worker err = -errno;
768*cc4ad7daSAndroid Build Coastguard Worker goto fail_open;
769*cc4ad7daSAndroid Build Coastguard Worker }
770*cc4ad7daSAndroid Build Coastguard Worker
771*cc4ad7daSAndroid Build Coastguard Worker if (fstat(fd, &st) < 0 || (size_t) st.st_size < sizeof(hdr)) {
772*cc4ad7daSAndroid Build Coastguard Worker err = -EINVAL;
773*cc4ad7daSAndroid Build Coastguard Worker goto fail_nommap;
774*cc4ad7daSAndroid Build Coastguard Worker }
775*cc4ad7daSAndroid Build Coastguard Worker
776*cc4ad7daSAndroid Build Coastguard Worker idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
777*cc4ad7daSAndroid Build Coastguard Worker if (idx->mm == MAP_FAILED) {
778*cc4ad7daSAndroid Build Coastguard Worker ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n",
779*cc4ad7daSAndroid Build Coastguard Worker st.st_size, fd);
780*cc4ad7daSAndroid Build Coastguard Worker err = -errno;
781*cc4ad7daSAndroid Build Coastguard Worker goto fail_nommap;
782*cc4ad7daSAndroid Build Coastguard Worker }
783*cc4ad7daSAndroid Build Coastguard Worker
784*cc4ad7daSAndroid Build Coastguard Worker p = idx->mm;
785*cc4ad7daSAndroid Build Coastguard Worker hdr.magic = read_long_mm(&p);
786*cc4ad7daSAndroid Build Coastguard Worker hdr.version = read_long_mm(&p);
787*cc4ad7daSAndroid Build Coastguard Worker hdr.root_offset = read_long_mm(&p);
788*cc4ad7daSAndroid Build Coastguard Worker
789*cc4ad7daSAndroid Build Coastguard Worker if (hdr.magic != INDEX_MAGIC) {
790*cc4ad7daSAndroid Build Coastguard Worker ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic,
791*cc4ad7daSAndroid Build Coastguard Worker INDEX_MAGIC);
792*cc4ad7daSAndroid Build Coastguard Worker err = -EINVAL;
793*cc4ad7daSAndroid Build Coastguard Worker goto fail;
794*cc4ad7daSAndroid Build Coastguard Worker }
795*cc4ad7daSAndroid Build Coastguard Worker
796*cc4ad7daSAndroid Build Coastguard Worker if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
797*cc4ad7daSAndroid Build Coastguard Worker ERR(ctx, "major version check fail: %u instead of %u\n",
798*cc4ad7daSAndroid Build Coastguard Worker hdr.version >> 16, INDEX_VERSION_MAJOR);
799*cc4ad7daSAndroid Build Coastguard Worker err = -EINVAL;
800*cc4ad7daSAndroid Build Coastguard Worker goto fail;
801*cc4ad7daSAndroid Build Coastguard Worker }
802*cc4ad7daSAndroid Build Coastguard Worker
803*cc4ad7daSAndroid Build Coastguard Worker idx->root_offset = hdr.root_offset;
804*cc4ad7daSAndroid Build Coastguard Worker idx->size = st.st_size;
805*cc4ad7daSAndroid Build Coastguard Worker idx->ctx = ctx;
806*cc4ad7daSAndroid Build Coastguard Worker close(fd);
807*cc4ad7daSAndroid Build Coastguard Worker
808*cc4ad7daSAndroid Build Coastguard Worker *stamp = stat_mstamp(&st);
809*cc4ad7daSAndroid Build Coastguard Worker *pidx = idx;
810*cc4ad7daSAndroid Build Coastguard Worker
811*cc4ad7daSAndroid Build Coastguard Worker return 0;
812*cc4ad7daSAndroid Build Coastguard Worker
813*cc4ad7daSAndroid Build Coastguard Worker fail:
814*cc4ad7daSAndroid Build Coastguard Worker munmap(idx->mm, st.st_size);
815*cc4ad7daSAndroid Build Coastguard Worker fail_nommap:
816*cc4ad7daSAndroid Build Coastguard Worker close(fd);
817*cc4ad7daSAndroid Build Coastguard Worker fail_open:
818*cc4ad7daSAndroid Build Coastguard Worker free(idx);
819*cc4ad7daSAndroid Build Coastguard Worker return err;
820*cc4ad7daSAndroid Build Coastguard Worker }
821*cc4ad7daSAndroid Build Coastguard Worker
index_mm_close(struct index_mm * idx)822*cc4ad7daSAndroid Build Coastguard Worker void index_mm_close(struct index_mm *idx)
823*cc4ad7daSAndroid Build Coastguard Worker {
824*cc4ad7daSAndroid Build Coastguard Worker munmap(idx->mm, idx->size);
825*cc4ad7daSAndroid Build Coastguard Worker free(idx);
826*cc4ad7daSAndroid Build Coastguard Worker }
827*cc4ad7daSAndroid Build Coastguard Worker
index_mm_readroot(struct index_mm * idx)828*cc4ad7daSAndroid Build Coastguard Worker static struct index_mm_node *index_mm_readroot(struct index_mm *idx)
829*cc4ad7daSAndroid Build Coastguard Worker {
830*cc4ad7daSAndroid Build Coastguard Worker return index_mm_read_node(idx, idx->root_offset);
831*cc4ad7daSAndroid Build Coastguard Worker }
832*cc4ad7daSAndroid Build Coastguard Worker
index_mm_readchild(const struct index_mm_node * parent,int ch)833*cc4ad7daSAndroid Build Coastguard Worker static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent,
834*cc4ad7daSAndroid Build Coastguard Worker int ch)
835*cc4ad7daSAndroid Build Coastguard Worker {
836*cc4ad7daSAndroid Build Coastguard Worker if (parent->first <= ch && ch <= parent->last) {
837*cc4ad7daSAndroid Build Coastguard Worker return index_mm_read_node(parent->idx,
838*cc4ad7daSAndroid Build Coastguard Worker parent->children[ch - parent->first]);
839*cc4ad7daSAndroid Build Coastguard Worker }
840*cc4ad7daSAndroid Build Coastguard Worker
841*cc4ad7daSAndroid Build Coastguard Worker return NULL;
842*cc4ad7daSAndroid Build Coastguard Worker }
843*cc4ad7daSAndroid Build Coastguard Worker
index_mm_dump_node(struct index_mm_node * node,struct strbuf * buf,int fd)844*cc4ad7daSAndroid Build Coastguard Worker static void index_mm_dump_node(struct index_mm_node *node, struct strbuf *buf,
845*cc4ad7daSAndroid Build Coastguard Worker int fd)
846*cc4ad7daSAndroid Build Coastguard Worker {
847*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_value *itr, *itr_end;
848*cc4ad7daSAndroid Build Coastguard Worker int ch, pushed;
849*cc4ad7daSAndroid Build Coastguard Worker
850*cc4ad7daSAndroid Build Coastguard Worker pushed = strbuf_pushchars(buf, node->prefix);
851*cc4ad7daSAndroid Build Coastguard Worker
852*cc4ad7daSAndroid Build Coastguard Worker itr = node->values.values;
853*cc4ad7daSAndroid Build Coastguard Worker itr_end = itr + node->values.len;
854*cc4ad7daSAndroid Build Coastguard Worker for (; itr < itr_end; itr++) {
855*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, buf->bytes, buf->used);
856*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, " ", 1);
857*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, itr->value, itr->len);
858*cc4ad7daSAndroid Build Coastguard Worker write_str_safe(fd, "\n", 1);
859*cc4ad7daSAndroid Build Coastguard Worker }
860*cc4ad7daSAndroid Build Coastguard Worker
861*cc4ad7daSAndroid Build Coastguard Worker for (ch = node->first; ch <= node->last; ch++) {
862*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *child = index_mm_readchild(node, ch);
863*cc4ad7daSAndroid Build Coastguard Worker
864*cc4ad7daSAndroid Build Coastguard Worker if (child == NULL)
865*cc4ad7daSAndroid Build Coastguard Worker continue;
866*cc4ad7daSAndroid Build Coastguard Worker
867*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, ch);
868*cc4ad7daSAndroid Build Coastguard Worker index_mm_dump_node(child, buf, fd);
869*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
870*cc4ad7daSAndroid Build Coastguard Worker }
871*cc4ad7daSAndroid Build Coastguard Worker
872*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchars(buf, pushed);
873*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
874*cc4ad7daSAndroid Build Coastguard Worker }
875*cc4ad7daSAndroid Build Coastguard Worker
index_mm_dump(struct index_mm * idx,int fd,const char * prefix)876*cc4ad7daSAndroid Build Coastguard Worker void index_mm_dump(struct index_mm *idx, int fd, const char *prefix)
877*cc4ad7daSAndroid Build Coastguard Worker {
878*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *root;
879*cc4ad7daSAndroid Build Coastguard Worker struct strbuf buf;
880*cc4ad7daSAndroid Build Coastguard Worker
881*cc4ad7daSAndroid Build Coastguard Worker root = index_mm_readroot(idx);
882*cc4ad7daSAndroid Build Coastguard Worker if (root == NULL)
883*cc4ad7daSAndroid Build Coastguard Worker return;
884*cc4ad7daSAndroid Build Coastguard Worker
885*cc4ad7daSAndroid Build Coastguard Worker strbuf_init(&buf);
886*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchars(&buf, prefix);
887*cc4ad7daSAndroid Build Coastguard Worker index_mm_dump_node(root, &buf, fd);
888*cc4ad7daSAndroid Build Coastguard Worker strbuf_release(&buf);
889*cc4ad7daSAndroid Build Coastguard Worker }
890*cc4ad7daSAndroid Build Coastguard Worker
index_mm_search_node(struct index_mm_node * node,const char * key,int i)891*cc4ad7daSAndroid Build Coastguard Worker static char *index_mm_search_node(struct index_mm_node *node, const char *key,
892*cc4ad7daSAndroid Build Coastguard Worker int i)
893*cc4ad7daSAndroid Build Coastguard Worker {
894*cc4ad7daSAndroid Build Coastguard Worker char *value;
895*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *child;
896*cc4ad7daSAndroid Build Coastguard Worker int ch;
897*cc4ad7daSAndroid Build Coastguard Worker int j;
898*cc4ad7daSAndroid Build Coastguard Worker
899*cc4ad7daSAndroid Build Coastguard Worker while(node) {
900*cc4ad7daSAndroid Build Coastguard Worker for (j = 0; node->prefix[j]; j++) {
901*cc4ad7daSAndroid Build Coastguard Worker ch = node->prefix[j];
902*cc4ad7daSAndroid Build Coastguard Worker
903*cc4ad7daSAndroid Build Coastguard Worker if (ch != key[i+j]) {
904*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
905*cc4ad7daSAndroid Build Coastguard Worker return NULL;
906*cc4ad7daSAndroid Build Coastguard Worker }
907*cc4ad7daSAndroid Build Coastguard Worker }
908*cc4ad7daSAndroid Build Coastguard Worker
909*cc4ad7daSAndroid Build Coastguard Worker i += j;
910*cc4ad7daSAndroid Build Coastguard Worker
911*cc4ad7daSAndroid Build Coastguard Worker if (key[i] == '\0') {
912*cc4ad7daSAndroid Build Coastguard Worker value = node->values.len > 0
913*cc4ad7daSAndroid Build Coastguard Worker ? strdup(node->values.values[0].value)
914*cc4ad7daSAndroid Build Coastguard Worker : NULL;
915*cc4ad7daSAndroid Build Coastguard Worker
916*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
917*cc4ad7daSAndroid Build Coastguard Worker return value;
918*cc4ad7daSAndroid Build Coastguard Worker }
919*cc4ad7daSAndroid Build Coastguard Worker
920*cc4ad7daSAndroid Build Coastguard Worker child = index_mm_readchild(node, key[i]);
921*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
922*cc4ad7daSAndroid Build Coastguard Worker node = child;
923*cc4ad7daSAndroid Build Coastguard Worker i++;
924*cc4ad7daSAndroid Build Coastguard Worker }
925*cc4ad7daSAndroid Build Coastguard Worker
926*cc4ad7daSAndroid Build Coastguard Worker return NULL;
927*cc4ad7daSAndroid Build Coastguard Worker }
928*cc4ad7daSAndroid Build Coastguard Worker
929*cc4ad7daSAndroid Build Coastguard Worker /*
930*cc4ad7daSAndroid Build Coastguard Worker * Search the index for a key
931*cc4ad7daSAndroid Build Coastguard Worker *
932*cc4ad7daSAndroid Build Coastguard Worker * Returns the value of the first match
933*cc4ad7daSAndroid Build Coastguard Worker *
934*cc4ad7daSAndroid Build Coastguard Worker * The recursive functions free their node argument (using index_close).
935*cc4ad7daSAndroid Build Coastguard Worker */
index_mm_search(struct index_mm * idx,const char * key)936*cc4ad7daSAndroid Build Coastguard Worker char *index_mm_search(struct index_mm *idx, const char *key)
937*cc4ad7daSAndroid Build Coastguard Worker {
938*cc4ad7daSAndroid Build Coastguard Worker // FIXME: return value by reference instead of strdup
939*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *root;
940*cc4ad7daSAndroid Build Coastguard Worker char *value;
941*cc4ad7daSAndroid Build Coastguard Worker
942*cc4ad7daSAndroid Build Coastguard Worker root = index_mm_readroot(idx);
943*cc4ad7daSAndroid Build Coastguard Worker value = index_mm_search_node(root, key, 0);
944*cc4ad7daSAndroid Build Coastguard Worker
945*cc4ad7daSAndroid Build Coastguard Worker return value;
946*cc4ad7daSAndroid Build Coastguard Worker }
947*cc4ad7daSAndroid Build Coastguard Worker
948*cc4ad7daSAndroid Build Coastguard Worker /* Level 4: add all the values from a matching node */
index_mm_searchwild_allvalues(struct index_mm_node * node,struct index_value ** out)949*cc4ad7daSAndroid Build Coastguard Worker static void index_mm_searchwild_allvalues(struct index_mm_node *node,
950*cc4ad7daSAndroid Build Coastguard Worker struct index_value **out)
951*cc4ad7daSAndroid Build Coastguard Worker {
952*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_value *itr, *itr_end;
953*cc4ad7daSAndroid Build Coastguard Worker
954*cc4ad7daSAndroid Build Coastguard Worker itr = node->values.values;
955*cc4ad7daSAndroid Build Coastguard Worker itr_end = itr + node->values.len;
956*cc4ad7daSAndroid Build Coastguard Worker for (; itr < itr_end; itr++)
957*cc4ad7daSAndroid Build Coastguard Worker add_value(out, itr->value, itr->len, itr->priority);
958*cc4ad7daSAndroid Build Coastguard Worker
959*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
960*cc4ad7daSAndroid Build Coastguard Worker }
961*cc4ad7daSAndroid Build Coastguard Worker
962*cc4ad7daSAndroid Build Coastguard Worker /*
963*cc4ad7daSAndroid Build Coastguard Worker * Level 3: traverse a sub-keyspace which starts with a wildcard,
964*cc4ad7daSAndroid Build Coastguard Worker * looking for matches.
965*cc4ad7daSAndroid Build Coastguard Worker */
index_mm_searchwild_all(struct index_mm_node * node,int j,struct strbuf * buf,const char * subkey,struct index_value ** out)966*cc4ad7daSAndroid Build Coastguard Worker static void index_mm_searchwild_all(struct index_mm_node *node, int j,
967*cc4ad7daSAndroid Build Coastguard Worker struct strbuf *buf,
968*cc4ad7daSAndroid Build Coastguard Worker const char *subkey,
969*cc4ad7daSAndroid Build Coastguard Worker struct index_value **out)
970*cc4ad7daSAndroid Build Coastguard Worker {
971*cc4ad7daSAndroid Build Coastguard Worker int pushed = 0;
972*cc4ad7daSAndroid Build Coastguard Worker int ch;
973*cc4ad7daSAndroid Build Coastguard Worker
974*cc4ad7daSAndroid Build Coastguard Worker while (node->prefix[j]) {
975*cc4ad7daSAndroid Build Coastguard Worker ch = node->prefix[j];
976*cc4ad7daSAndroid Build Coastguard Worker
977*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, ch);
978*cc4ad7daSAndroid Build Coastguard Worker pushed++;
979*cc4ad7daSAndroid Build Coastguard Worker j++;
980*cc4ad7daSAndroid Build Coastguard Worker }
981*cc4ad7daSAndroid Build Coastguard Worker
982*cc4ad7daSAndroid Build Coastguard Worker for (ch = node->first; ch <= node->last; ch++) {
983*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *child = index_mm_readchild(node, ch);
984*cc4ad7daSAndroid Build Coastguard Worker
985*cc4ad7daSAndroid Build Coastguard Worker if (!child)
986*cc4ad7daSAndroid Build Coastguard Worker continue;
987*cc4ad7daSAndroid Build Coastguard Worker
988*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, ch);
989*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_all(child, 0, buf, subkey, out);
990*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
991*cc4ad7daSAndroid Build Coastguard Worker }
992*cc4ad7daSAndroid Build Coastguard Worker
993*cc4ad7daSAndroid Build Coastguard Worker if (node->values.len > 0) {
994*cc4ad7daSAndroid Build Coastguard Worker if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
995*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_allvalues(node, out);
996*cc4ad7daSAndroid Build Coastguard Worker else
997*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
998*cc4ad7daSAndroid Build Coastguard Worker } else {
999*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
1000*cc4ad7daSAndroid Build Coastguard Worker }
1001*cc4ad7daSAndroid Build Coastguard Worker
1002*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchars(buf, pushed);
1003*cc4ad7daSAndroid Build Coastguard Worker }
1004*cc4ad7daSAndroid Build Coastguard Worker
1005*cc4ad7daSAndroid Build Coastguard Worker /* Level 2: descend the tree (until we hit a wildcard) */
index_mm_searchwild_node(struct index_mm_node * node,struct strbuf * buf,const char * key,int i,struct index_value ** out)1006*cc4ad7daSAndroid Build Coastguard Worker static void index_mm_searchwild_node(struct index_mm_node *node,
1007*cc4ad7daSAndroid Build Coastguard Worker struct strbuf *buf,
1008*cc4ad7daSAndroid Build Coastguard Worker const char *key, int i,
1009*cc4ad7daSAndroid Build Coastguard Worker struct index_value **out)
1010*cc4ad7daSAndroid Build Coastguard Worker {
1011*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *child;
1012*cc4ad7daSAndroid Build Coastguard Worker int j;
1013*cc4ad7daSAndroid Build Coastguard Worker int ch;
1014*cc4ad7daSAndroid Build Coastguard Worker
1015*cc4ad7daSAndroid Build Coastguard Worker while(node) {
1016*cc4ad7daSAndroid Build Coastguard Worker for (j = 0; node->prefix[j]; j++) {
1017*cc4ad7daSAndroid Build Coastguard Worker ch = node->prefix[j];
1018*cc4ad7daSAndroid Build Coastguard Worker
1019*cc4ad7daSAndroid Build Coastguard Worker if (ch == '*' || ch == '?' || ch == '[') {
1020*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_all(node, j, buf,
1021*cc4ad7daSAndroid Build Coastguard Worker &key[i+j], out);
1022*cc4ad7daSAndroid Build Coastguard Worker return;
1023*cc4ad7daSAndroid Build Coastguard Worker }
1024*cc4ad7daSAndroid Build Coastguard Worker
1025*cc4ad7daSAndroid Build Coastguard Worker if (ch != key[i+j]) {
1026*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
1027*cc4ad7daSAndroid Build Coastguard Worker return;
1028*cc4ad7daSAndroid Build Coastguard Worker }
1029*cc4ad7daSAndroid Build Coastguard Worker }
1030*cc4ad7daSAndroid Build Coastguard Worker
1031*cc4ad7daSAndroid Build Coastguard Worker i += j;
1032*cc4ad7daSAndroid Build Coastguard Worker
1033*cc4ad7daSAndroid Build Coastguard Worker child = index_mm_readchild(node, '*');
1034*cc4ad7daSAndroid Build Coastguard Worker if (child) {
1035*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, '*');
1036*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_all(child, 0, buf, &key[i], out);
1037*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
1038*cc4ad7daSAndroid Build Coastguard Worker }
1039*cc4ad7daSAndroid Build Coastguard Worker
1040*cc4ad7daSAndroid Build Coastguard Worker child = index_mm_readchild(node, '?');
1041*cc4ad7daSAndroid Build Coastguard Worker if (child) {
1042*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, '?');
1043*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_all(child, 0, buf, &key[i], out);
1044*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
1045*cc4ad7daSAndroid Build Coastguard Worker }
1046*cc4ad7daSAndroid Build Coastguard Worker
1047*cc4ad7daSAndroid Build Coastguard Worker child = index_mm_readchild(node, '[');
1048*cc4ad7daSAndroid Build Coastguard Worker if (child) {
1049*cc4ad7daSAndroid Build Coastguard Worker strbuf_pushchar(buf, '[');
1050*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_all(child, 0, buf, &key[i], out);
1051*cc4ad7daSAndroid Build Coastguard Worker strbuf_popchar(buf);
1052*cc4ad7daSAndroid Build Coastguard Worker }
1053*cc4ad7daSAndroid Build Coastguard Worker
1054*cc4ad7daSAndroid Build Coastguard Worker if (key[i] == '\0') {
1055*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_allvalues(node, out);
1056*cc4ad7daSAndroid Build Coastguard Worker
1057*cc4ad7daSAndroid Build Coastguard Worker return;
1058*cc4ad7daSAndroid Build Coastguard Worker }
1059*cc4ad7daSAndroid Build Coastguard Worker
1060*cc4ad7daSAndroid Build Coastguard Worker child = index_mm_readchild(node, key[i]);
1061*cc4ad7daSAndroid Build Coastguard Worker index_mm_free_node(node);
1062*cc4ad7daSAndroid Build Coastguard Worker node = child;
1063*cc4ad7daSAndroid Build Coastguard Worker i++;
1064*cc4ad7daSAndroid Build Coastguard Worker }
1065*cc4ad7daSAndroid Build Coastguard Worker }
1066*cc4ad7daSAndroid Build Coastguard Worker
1067*cc4ad7daSAndroid Build Coastguard Worker /*
1068*cc4ad7daSAndroid Build Coastguard Worker * Search the index for a key. The index may contain wildcards.
1069*cc4ad7daSAndroid Build Coastguard Worker *
1070*cc4ad7daSAndroid Build Coastguard Worker * Returns a list of all the values of matching keys.
1071*cc4ad7daSAndroid Build Coastguard Worker */
index_mm_searchwild(struct index_mm * idx,const char * key)1072*cc4ad7daSAndroid Build Coastguard Worker struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key)
1073*cc4ad7daSAndroid Build Coastguard Worker {
1074*cc4ad7daSAndroid Build Coastguard Worker struct index_mm_node *root = index_mm_readroot(idx);
1075*cc4ad7daSAndroid Build Coastguard Worker struct strbuf buf;
1076*cc4ad7daSAndroid Build Coastguard Worker struct index_value *out = NULL;
1077*cc4ad7daSAndroid Build Coastguard Worker
1078*cc4ad7daSAndroid Build Coastguard Worker strbuf_init(&buf);
1079*cc4ad7daSAndroid Build Coastguard Worker index_mm_searchwild_node(root, &buf, key, 0, &out);
1080*cc4ad7daSAndroid Build Coastguard Worker strbuf_release(&buf);
1081*cc4ad7daSAndroid Build Coastguard Worker return out;
1082*cc4ad7daSAndroid Build Coastguard Worker }
1083