1 /*
2 * MXBT.C
3 *
4 * Written by Paul Edwards and released to the public domain.
5 *
6 * BTree functions that operate on an index file compatible with that
7 * used by Mix Database Toolchest (or something like that).
8 *
9 * The btree index file is comprised of three different record types,
10 *
11 * stored as a fixed length (e.g. 512 bytes), even though the record
12 *
13 * types may not require that full length.
14 *
15 * 1. A control record. This is the first record in the file, and
16 * contains important information such as the fixed length that all
17 * the other records are.
18 *
19 * 2. Leaf nodes. These are identified by having "-1" in the first
20 * field (a "long"). Every search key will be found in one of these
21 * records. The leaf nodes appear after the control record.
22 *
23 * 3. Index nodes. These are identified by not having "-1" in the
24 * first field. Some, but not all, of the keys will be found in
25 * one of these fields. The index nodes appear after the last leaf
26 * node.
27 *
28 * Note that if you wish to update records in this index file, you
29 * should update the leaf nodes before the index nodes.
30 *
31 * The objective of all this is to find a matching key, which will
32 * then have a corresponding "long" value. This long value can
33 * then be used as an offset into an appropriate data file.
34 *
35 * The basic structure of the index records goes like this. Each
36 * index record has several keys stored in it. If your key is
37 * lower than the first key, then the recType field doubles up as
38 * the *record number* of the left branch. Multiply that by the
39 * record size and you have your offset. Otherwise, go through
40 * the index entries until you find the an entry with a key greater
41 * than yours, or you reach the end. The previous entry to that
42 * one will have the left node for you to follow, in the "lower"
43 * variable. Again, this is a record number. The idea is that
44 * you keep following the appropriate left branch until you hit
45 * a leaf node, then you do a sequential search. Crikey, if
46 * you're a real loser you could even do a binary search of the
47 * leaf node.
48 *
49 */
50
51 /*
52 * The algorithm we employ is:
53 *
54 * 1. fetch the control record
55 *
56 * 2. Search the index nodes for our key until we reach a leaf
57 * node.
58 *
59 * 3. Search the leaf node for our key.
60 */
61
62 #include <stdio.h>
63 #include "mxbt.h"
64
65 static void mxbtInit(MXBT * mxbt);
66 static void mxbtOpen(MXBT * mxbt, char *indexFile);
67 static void mxbtClose(MXBT * mxbt);
68 static void mxbtFetchControl(MXBT * mxbt);
69 static void mxbtSetKey(MXBT * mxbt, void *searchKey);
70 static void mxbtSetCompare(MXBT * mxbt, int (*compare) (void *testKey, void *searchKey, int len));
71 static void mxbtReadRec(MXBT * mxbt);
72 static void mxbtFindLeaf(MXBT * mxbt);
73 static void mxbtSearchLeaf(MXBT * mxbt);
74
mxbtOneSearch(MXBT * mxbt,char * indexFile,void * searchKey,int (* compare)(void * testKey,void * searchKey,int len))75 long mxbtOneSearch(MXBT * mxbt, char *indexFile, void *searchKey, int (*compare) (void *testKey, void *searchKey, int len))
76 {
77 mxbt->error = 0;
78 mxbtInit(mxbt);
79 if (!mxbt->error)
80 {
81 mxbtOpen(mxbt, indexFile);
82 if (!mxbt->error)
83 {
84 mxbtFetchControl(mxbt);
85 if (!mxbt->error)
86 {
87 mxbtSetKey(mxbt, searchKey);
88 mxbtSetCompare(mxbt, compare);
89 mxbtFindLeaf(mxbt);
90 if (!mxbt->error)
91 {
92 mxbtSearchLeaf(mxbt);
93 }
94 }
95 mxbtClose(mxbt);
96 }
97 }
98 if (mxbt->error)
99 {
100 return -1L;
101 }
102 else
103 {
104 return mxbt->value;
105 }
106 }
107
mxbtInit(MXBT * mxbt)108 static void mxbtInit(MXBT * mxbt)
109 {
110 mxbt->buf = mxbt->myunion.intbuf;
111 mxbt->index = (struct mxbt_indexrec *)mxbt->buf;
112 mxbt->leaf = (struct mxbt_leafrec *)mxbt->buf;
113 }
114
mxbtOpen(MXBT * mxbt,char * indexFile)115 static void mxbtOpen(MXBT * mxbt, char *indexFile)
116 {
117 mxbt->fp = fopen(indexFile, "rb");
118 if (mxbt->fp == NULL)
119 {
120 mxbt->error = 1;
121 }
122 }
123
mxbtClose(MXBT * mxbt)124 static void mxbtClose(MXBT * mxbt)
125 {
126 if (fclose(mxbt->fp) != 0)
127 {
128 mxbt->error = 1;
129 }
130 }
131
mxbtFetchControl(MXBT * mxbt)132 static void mxbtFetchControl(MXBT * mxbt)
133 {
134 if (fread(&mxbt->recSize, sizeof(unsigned short), 1, mxbt->fp) != 1)
135 {
136 mxbt->error = 1;
137 }
138 else if (fread(&mxbt->control, sizeof mxbt->control, 1, mxbt->fp) != 1)
139 {
140 mxbt->error = 1;
141 }
142 }
143
mxbtSetKey(MXBT * mxbt,void * searchKey)144 static void mxbtSetKey(MXBT * mxbt, void *searchKey)
145 {
146 mxbt->searchK = searchKey;
147 }
148
mxbtSetCompare(MXBT * mxbt,int (* compare)(void * testKey,void * searchKey,int len))149 static void mxbtSetCompare(MXBT * mxbt, int (*compare) (void *testKey, void *searchKey, int len))
150 {
151 mxbt->compareF = compare;
152 }
153
mxbtReadRec(MXBT * mxbt)154 static void mxbtReadRec(MXBT * mxbt)
155 {
156 size_t x;
157 int y;
158 y = fseek(mxbt->fp, mxbt->recordNum * mxbt->recSize, SEEK_SET);
159 if (y != 0)
160 {
161 mxbt->error = 1;
162 }
163 else
164 {
165 x = fread(mxbt->buf, mxbt->recSize, 1, mxbt->fp);
166 if (x != 1)
167 {
168 mxbt->error = 1;
169 }
170 }
171 }
172
mxbtFindLeaf(MXBT * mxbt)173 static void mxbtFindLeaf(MXBT * mxbt)
174 {
175 int cnt, x;
176
177 mxbt->recordNum = mxbt->control.indexStart;
178 mxbtReadRec(mxbt);
179 while (!mxbt->error && (mxbt->index->recType != -1))
180 {
181 cnt = mxbt->index->keyCount;
182 if (cnt < 0)
183 {
184 mxbt->error = 1;
185 }
186 else
187 {
188 for (x = 0; x < cnt; x++)
189 {
190 if (mxbt->compareF((char *)mxbt->index +
191 mxbt->index->keys[x].offset, mxbt->searchK,
192 mxbt->index->keys[x].len) > 0)
193 {
194 break;
195 }
196 }
197 if (x == 0)
198 {
199 mxbt->recordNum = mxbt->index->recType;
200 }
201 else
202 {
203 mxbt->recordNum = mxbt->index->keys[x - 1].lower;
204 }
205 mxbtReadRec(mxbt);
206 }
207 }
208 }
209
mxbtSearchLeaf(MXBT * mxbt)210 static void mxbtSearchLeaf(MXBT * mxbt)
211 {
212 int cnt, x, ret;
213
214 cnt = mxbt->leaf->keyCount;
215 if (cnt <= 0)
216 {
217 mxbt->error = 1;
218 }
219 else
220 {
221 for (x = 0; x < cnt; x++)
222 {
223 ret = mxbt->compareF((char *)mxbt->leaf +
224 mxbt->leaf->keys[x].offset, mxbt->searchK,
225 mxbt->leaf->keys[x].len);
226 if (ret > 0)
227 {
228 mxbt->error = 1;
229 break;
230 }
231 else if (ret == 0)
232 {
233 mxbt->value = mxbt->leaf->keys[x].value;
234 break;
235 }
236 }
237 if (x == cnt)
238 {
239 mxbt->error = 1;
240 }
241 }
242 }
243