xref: /aosp_15_r20/external/kmod/libkmod/libkmod-index.c (revision cc4ad7da8cefe208cb129ac2aa9a357c7c72deb2)
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