]>
Commit | Line | Data |
---|---|---|
8f923be6 LDM |
1 | /* |
2 | * libkmod - interface to kernel module operations | |
3 | * | |
8f923be6 LDM |
4 | * Copyright (C) 2011 ProFUSION embedded systems |
5 | * | |
6 | * This library is free software; you can redistribute it and/or | |
7 | * modify it under the terms of the GNU Lesser General Public | |
cb451f35 LDM |
8 | * License as published by the Free Software Foundation; either |
9 | * version 2.1 of the License, or (at your option) any later version. | |
8f923be6 LDM |
10 | * |
11 | * This library is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * Lesser General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU Lesser General Public | |
17 | * License along with this library; if not, write to the Free Software | |
18 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
19 | */ | |
e8847fd2 | 20 | |
e71970ae LDM |
21 | #ifndef _LIBKMOD_INDEX_H |
22 | #define _LIBKMOD_INDEX_H | |
e8847fd2 LDM |
23 | |
24 | #include <stdint.h> | |
25 | ||
26 | /* Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first. | |
27 | All files start with a magic number. | |
28 | ||
29 | Magic spells "BOOTFAST". Second one used on newer versioned binary files. | |
30 | */ | |
31 | /* #define INDEX_MAGIC_OLD 0xB007FA57 */ | |
32 | #define INDEX_MAGIC 0xB007F457 | |
33 | ||
34 | /* We use a version string to keep track of changes to the binary format | |
35 | * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in | |
36 | * case we ever decide to have minor changes that are not incompatible. | |
37 | */ | |
38 | ||
39 | #define INDEX_VERSION_MAJOR 0x0002 | |
40 | #define INDEX_VERSION_MINOR 0x0001 | |
41 | #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR) | |
42 | ||
43 | /* The index file maps keys to values. Both keys and values are ASCII strings. | |
44 | Each key can have multiple values. Values are sorted by an integer priority. | |
45 | ||
46 | The reader also implements a wildcard search (including range expressions) | |
47 | where the keys in the index are treated as patterns. | |
48 | This feature is required for module aliases. | |
49 | */ | |
50 | ||
51 | /* Implementation is based on a radix tree, or "trie". | |
52 | Each arc from parent to child is labelled with a character. | |
53 | Each path from the root represents a string. | |
54 | ||
55 | == Example strings == | |
56 | ||
57 | ask | |
58 | ate | |
59 | on | |
60 | once | |
61 | one | |
62 | ||
63 | == Key == | |
64 | + Normal node | |
65 | * Marked node, representing a key and it's values. | |
66 | ||
67 | + | |
68 | |-a-+-s-+-k-* | |
69 | | | | |
70 | | `-t-+-e-* | |
71 | | | |
72 | `-o-+-n-*-c-+-e-* | |
73 | | | |
74 | `-e-* | |
75 | ||
76 | Naive implementations tend to be very space inefficient; child pointers | |
77 | are stored in arrays indexed by character, but most child pointers are null. | |
78 | ||
79 | Our implementation uses a scheme described by Wikipedia as a Patrica trie, | |
80 | ||
81 | "easiest to understand as a space-optimized trie where | |
82 | each node with only one child is merged with its child" | |
83 | ||
84 | + | |
85 | |-a-+-sk-* | |
86 | | | | |
87 | | `-te-* | |
88 | | | |
89 | `-on-*-ce-* | |
90 | | | |
91 | `-e-* | |
92 | ||
93 | We still use arrays of child pointers indexed by a single character; | |
94 | the remaining characters of the label are stored as a "prefix" in the child. | |
95 | ||
96 | The paper describing the original Patrica trie works on individiual bits - | |
97 | each node has a maximum of two children, which increases space efficiency. | |
98 | However for this application it is simpler to use the ASCII character set. | |
99 | Since the index file is read-only, it can be compressed by omitting null | |
100 | child pointers at the start and end of arrays. | |
101 | */ | |
102 | ||
103 | #define INDEX_PRIORITY_MIN UINT32_MAX | |
104 | ||
105 | struct index_value { | |
106 | struct index_value *next; | |
107 | unsigned int priority; | |
1433ba9e | 108 | unsigned int len; |
e8847fd2 LDM |
109 | char value[0]; |
110 | }; | |
111 | ||
112 | /* In-memory index (depmod only) */ | |
e8847fd2 | 113 | struct index_file; |
e8847fd2 | 114 | struct index_file *index_file_open(const char *filename); |
4a4876d6 LDM |
115 | void index_file_close(struct index_file *idx); |
116 | char *index_search(struct index_file *idx, const char *key); | |
117 | struct index_value *index_searchwild(struct index_file *idx, const char *key); | |
e8847fd2 LDM |
118 | |
119 | void index_values_free(struct index_value *values); | |
120 | ||
b471a6b4 LDM |
121 | /* Implementation using mmap */ |
122 | struct index_mm; | |
5109f2b4 | 123 | struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename, |
9fd58f30 | 124 | bool populate, unsigned long long *stamp); |
b471a6b4 | 125 | void index_mm_close(struct index_mm *index); |
b797b791 | 126 | char *index_mm_search(struct index_mm *idx, const char *key); |
bf89f70c | 127 | struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key); |
b471a6b4 | 128 | |
e71970ae | 129 | #endif |