Debian Codegraph @

lib/base/bsearch.c

raw
1 /*
2 * Copyright (c) 2011, Secure Endpoints Inc.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * - Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
20 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
21 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
22 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
24 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
26 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
28 * OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 */
31
32 #include "baselocl.h"
33
34 #include <sys/types.h>
35 #include <sys/stat.h>
36 #ifdef HAVE_IO_H
37 #include <io.h>
38 #endif
39 #ifdef HAVE_UNISTD_H
40 #include <unistd.h>
41 #endif
42 #include <fcntl.h>
43 #include <ctype.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47 #ifdef HAVE_STRINGS_H
48 #include <strings.h>
49 #endif
50 #include <errno.h>
51 #include <assert.h>
52
53 /*
54 * This file contains functions for binary searching flat text in memory
55 * and in text files where each line is a [variable length] record.
56 * Each record has a key and an optional value separated from the key by
57 * unquoted whitespace. Whitespace in the key, and leading whitespace
58 * for the value, can be quoted with backslashes (but CR and LF must be
59 * quoted in such a way that they don't appear in the quoted result).
60 *
61 * Binary searching a tree are normally a dead simple algorithm. It
62 * turns out that binary searching flat text with *variable* length
63 * records is... tricky. There's no indexes to record beginning bytes,
64 * thus any index selected during the search is likely to fall in the
65 * middle of a record. When deciding to search a left sub-tree one
66 * might fail to find the last record in that sub-tree on account of the
67 * right boundary falling in the middle of it -- the chosen solution to
68 * this makes left sub-tree searches slightly less efficient than right
69 * sub-tree searches.
70 *
71 * If binary searching flat text in memory is tricky, using block-wise
72 * I/O instead is trickier! But it's necessary in order to support
73 * large files (which we either can't or wouldn't want to read or map
74 * into memory). Each block we read has to be large enough that the
75 * largest record can fit in it. And each block might start and/or end
76 * in the middle of a record. Here it is the right sub-tree searches
77 * that are less efficient than left sub-tree searches.
78 *
79 * bsearch_common() contains the common text block binary search code.
80 *
81 * _bsearch_text() is the interface for searching in-core text.
82 * _bsearch_file() is the interface for block-wise searching files.
83 */
84
85 struct bsearch_file_handle {
86 int fd; /* file descriptor */
87 char *cache; /* cache bytes */
88 char *page; /* one double-size page worth of bytes */
89 size_t file_sz; /* file size */
90 size_t cache_sz; /* cache size */
91 size_t page_sz; /* page size */
92 };
93
94 /* Find a new-line */
95 static const char *
96 find_line(const char *buf, size_t i, size_t right)
97 {
98 if (i == 0)
99 return &buf[i];
100 for (; i < right; i++) {
101 if (buf[i] == '\n') {
102 if ((i + 1) < right)
103 return &buf[i + 1];
104 return NULL;
105 }
106 }
107 return NULL;
108 }
109
110 /*
111 * Common routine for binary searching text in core.
112 *
113 * Perform a binary search of a char array containing a block from a
114 * text file where each line is a record (LF and CRLF supported). Each
115 * record consists of a key followed by an optional value separated from
116 * the key by whitespace. Whitespace can be quoted with backslashes.
117 * It's the caller's responsibility to encode/decode keys/values if
118 * quoting is desired; newlines should be encoded such that a newline
119 * does not appear in the result.
120 *
121 * All output arguments are optional.
122 *
123 * Returns 0 if key is found, -1 if not found, or an error code such as
124 * ENOMEM in case of error.
125 *
126 * Inputs:
127 *
128 * @buf String to search
129 * @sz Size of string to search
130 * @key Key string to search for
131 * @buf_is_start True if the buffer starts with a record, false if it
132 * starts in the middle of a record or if the caller
133 * doesn't know.
134 *
135 * Outputs:
136 *
137 * @value Location to store a copy of the value (caller must free)
138 * @location Record location if found else the location where the
139 * record should be inserted (index into @buf)
140 * @cmp Set to less than or greater than 0 to indicate that a
141 * key not found would have fit in an earlier or later
142 * part of a file. Callers should use this to decide
143 * whether to read a block to the left or to the right and
144 * search that.
145 * @loops Location to store a count of bisections required for
146 * search (useful for confirming logarithmic performance)
147 */
148 static int
149 bsearch_common(const char *buf, size_t sz, const char *key,
150 int buf_is_start, char **value, size_t *location,
151 int *cmp, size_t *loops)
152 {
153 const char *linep;
154 size_t key_start, key_len; /* key string in buf */
155 size_t val_start, val_len; /* value string in buf */
156 int key_cmp = -1;
157 size_t k;
158 size_t l; /* left side of buffer for binary search */
159 size_t r; /* right side of buffer for binary search */
160 size_t rmax; /* right side of buffer for binary search */
161 size_t i; /* index into buffer, typically in the middle of l and r */
162 size_t loop_count = 0;
163 int ret = -1;
164
165 if (value)
166 *value = NULL;
167 if (cmp)
168 *cmp = 0;
169 if (loops)
170 *loops = 0;
171
172 /* Binary search; file should be sorted */
173 for (l = 0, r = rmax = sz, i = sz >> 1; i >= l && i < rmax; loop_count++) {
174 heim_assert(i < sz, "invalid aname2lname db index");
175
176 /* buf[i] is likely in the middle of a line; find the next line */
177 linep = find_line(buf, i, rmax);
178 k = linep ? linep - buf : i;
179 if (linep == NULL || k >= rmax) {
180 /*
181 * No new line found to the right; search to the left then
182 * but don't change rmax (this isn't optimal, but it's
183 * simple).
184 */
185 if (i == l)
186 break;
187 r = i;
188 i = l + ((r - l) >> 1);
189 continue;
190 }
191 i = k;
192 heim_assert(i >= l && i < rmax, "invalid aname2lname db index");
193
194 /* Got a line; check it */
195
196 /* Search for and split on unquoted whitespace */
197 val_start = 0;
198 for (key_start = i, key_len = 0, val_len = 0, k = i; k < rmax; k++) {
199 if (buf[k] == '\\') {
200 k++;
201 continue;
202 }
203 if (buf[k] == '\r' || buf[k] == '\n') {
204 /* We now know where the key ends, and there's no value */
205 key_len = k - i;
206 break;
207 }
208 if (!isspace((unsigned char)buf[k]))
209 continue;
210
211 while (k < rmax && isspace((unsigned char)buf[k])) {
212 key_len = k - i;
213 k++;
214 }
215 if (k < rmax)
216 val_start = k;
217 /* Find end of value */
218 for (; k < rmax && buf[k] != '\0'; k++) {
219 if (buf[k] == '\r' || buf[k] == '\n') {
220 val_len = k - val_start;
221 break;
222 }
223 }
224 break;
225 }
226
227 /*
228 * The following logic is for dealing with partial buffers,
229 * which we use for block-wise binary searches of large files
230 */
231 if (key_start == 0 && !buf_is_start) {
232 /*
233 * We're at the beginning of a block that might have started
234 * in the middle of a record whose "key" might well compare
235 * as greater than the key we're looking for, so we don't
236 * bother comparing -- we know key_cmp must be -1 here.
237 */
238 key_cmp = -1;
239 break;
240 }
241 if ((val_len && buf[val_start + val_len] != '\n') ||
242 (!val_len && buf[key_start + key_len] != '\n')) {
243 /*
244 * We're at the end of a block that ends in the middle of a
245 * record whose "key" might well compare as less than the
246 * key we're looking for, so we don't bother comparing -- we
247 * know key_cmp must be >= 0 but we can't tell. Our caller
248 * will end up reading a double-size block to handle this.
249 */
250 key_cmp = 1;
251 break;
252 }
253
254 key_cmp = strncmp(key, &buf[key_start], key_len);
255 if (key_cmp == 0 && strlen(key) != key_len)
256 key_cmp = 1;
257 if (key_cmp < 0) {
258 /* search left */
259 r = rmax = (linep - buf);
260 i = l + ((r - l) >> 1);
261 if (location)
262 *location = key_start;
263 } else if (key_cmp > 0) {
264 /* search right */
265 if (l == i)
266 break; /* not found */
267 l = i;
268 i = l + ((r - l) >> 1);
269 if (location)
270 *location = val_start + val_len;
271 } else {
272 /* match! */
273 if (location)
274 *location = key_start;
275 ret = 0;
276 if (val_len && value) {
277 /* Avoid strndup() so we don't need libroken here yet */
278 if ((*value = malloc(val_len + 1))) {
279 (void) memcpy(*value, &buf[val_start], val_len);
280 (*value)[val_len] = '\0';
281 } else {
282 ret = errno;
283 }
284 }
285 break;
286 }
287 }
288
289 if (cmp)
290 *cmp = key_cmp;
291 if (loops)
292 *loops = loop_count;
293
294 return ret;
295 }
296
297 /*
298 * Binary search a char array containing sorted text records separated
299 * by new-lines (or CRLF). Each record consists of a key and an
300 * optional value following the key, separated from the key by unquoted
301 * whitespace.
302 *
303 * All output arguments are optional.
304 *
305 * Returns 0 if key is found, -1 if not found, or an error code such as
306 * ENOMEM in case of error.
307 *
308 * Inputs:
309 *
310 * @buf Char array pointer
311 * @buf_sz Size of buf
312 * @key Key to search for
313 *
314 * Outputs:
315 *
316 * @value Location where to put the value, if any (caller must free)
317 * @location Record location if found else the location where the record
318 * should be inserted (index into @buf)
319 * @loops Location where to put a number of loops (or comparisons)
320 * needed for the search (useful for benchmarking)
321 */
322 int
323 _bsearch_text(const char *buf, size_t buf_sz, const char *key,
324 char **value, size_t *location, size_t *loops)
325 {
326 return bsearch_common(buf, buf_sz, key, 1, value, location, NULL, loops);
327 }
328
329 #define MAX_BLOCK_SIZE (1024 * 1024)
330 #define DEFAULT_MAX_FILE_SIZE (1024 * 1024)
331 /*
332 * Open a file for binary searching. The file will be read in entirely
333 * if it is smaller than @max_sz, else a cache of @max_sz bytes will be
334 * allocated.
335 *
336 * Returns 0 on success, else an error number or -1 if the file is empty.
337 *
338 * Inputs:
339 *
340 * @fname Name of file to open
341 * @max_sz Maximum size of cache to allocate, in bytes (if zero, default)
342 * @page_sz Page size (must be a power of two, larger than 256, smaller
343 * than 1MB; if zero use default)
344 *
345 * Outputs:
346 *
347 * @bfh Handle for use with _bsearch_file() and _bsearch_file_close()
348 * @reads Number of reads performed
349 */
350 int
351 _bsearch_file_open(const char *fname, size_t max_sz, size_t page_sz,
352 bsearch_file_handle *bfh, size_t *reads)
353 {
354 bsearch_file_handle new_bfh = NULL;
355 struct stat st;
356 size_t i;
357 int fd;
358 int ret;
359
360 *bfh = NULL;
361
362 if (reads)
363 *reads = 0;
364
365 fd = open(fname, O_RDONLY);
366 if (fd == -1)
367 return errno;
368
369 if (fstat(fd, &st) == -1) {
370 ret = errno;
371 goto err;
372 }
373
374 if (st.st_size == 0) {
375 ret = -1; /* no data -> no binary search */
376 goto err;
377 }
378
379 /* Validate / default arguments */
380 if (max_sz == 0)
381 max_sz = DEFAULT_MAX_FILE_SIZE;
382 for (i = page_sz; i; i >>= 1) {
383 /* Make sure page_sz is a power of two */
384 if ((i % 2) && (i >> 1)) {
385 page_sz = 0;
386 break;
387 }
388 }
389 if (page_sz == 0)
390 #ifdef HAVE_STRUCT_STAT_ST_BLKSIZE
391 page_sz = st.st_blksize;
392 #else
393 page_sz = 4096;
394 #endif
395 for (i = page_sz; i; i >>= 1) {
396 /* Make sure page_sz is a power of two */
397 if ((i % 2) && (i >> 1)) {
398 /* Can't happen! Filesystems always use powers of two! */
399 page_sz = 4096;
400 break;
401 }
402 }
403 if (page_sz > MAX_BLOCK_SIZE)
404 page_sz = MAX_BLOCK_SIZE;
405
406 new_bfh = calloc(1, sizeof (*new_bfh));
407 if (new_bfh == NULL) {
408 ret = ENOMEM;
409 goto err;
410 }
411
412 new_bfh->fd = fd;
413 new_bfh->page_sz = page_sz;
414 new_bfh->file_sz = st.st_size;
415
416 if (max_sz >= st.st_size) {
417 /* Whole-file method */
418 new_bfh->cache = malloc(st.st_size + 1);
419 if (new_bfh->cache) {
420 new_bfh->cache[st.st_size] = '\0';
421 new_bfh->cache_sz = st.st_size;
422 ret = read(fd, new_bfh->cache, st.st_size);
423 if (ret < 0) {
424 ret = errno;
425 goto err;
426 }
427 if (ret != st.st_size) {
428 ret = EIO; /* XXX ??? */
429 goto err;
430 }
431 if (reads)
432 *reads = 1;
433 (void) close(fd);
434 new_bfh->fd = -1;
435 *bfh = new_bfh;
436 return 0;
437 }
438 }
439
440 /* Block-size method, or above malloc() failed */
441 new_bfh->page = malloc(new_bfh->page_sz << 1);
442 if (new_bfh->page == NULL) {
443 /* Can't even allocate a single double-size page! */
444 ret = ENOMEM;
445 goto err;
446 }
447
448 new_bfh->cache_sz = max_sz < st.st_size ? max_sz : st.st_size;
449 new_bfh->cache = malloc(new_bfh->cache_sz);
450 *bfh = new_bfh;
451
452 /*
453 * malloc() may have failed because we were asking for a lot of
454 * memory, but we may still be able to operate without a cache,
455 * so let's not fail.
456 */
457 if (new_bfh->cache == NULL) {
458 new_bfh->cache_sz = 0;
459 return 0;
460 }
461
462 /* Initialize cache */
463 for (i = 0; i < new_bfh->cache_sz; i += new_bfh->page_sz)
464 new_bfh->cache[i] = '\0';
465 return 0;
466
467 err:
468 (void) close(fd);
469 if (new_bfh) {
470 free(new_bfh->page);
471 free(new_bfh->cache);
472 free(new_bfh);
473 }
474 return ret;
475 }
476
477 /*
478 * Indicate whether the given binary search file handle will be searched
479 * with block-wise method.
480 */
481 void
482 _bsearch_file_info(bsearch_file_handle bfh,
483 size_t *page_sz, size_t *max_sz, int *blockwise)
484 {
485 if (page_sz)
486 *page_sz = bfh->page_sz;
487 if (max_sz)
488 *max_sz = bfh->cache_sz;
489 if (blockwise)
490 *blockwise = (bfh->file_sz != bfh->cache_sz);
491 }
492
493 /*
494 * Close the given binary file search handle.
495 *
496 * Inputs:
497 *
498 * @bfh Pointer to variable containing handle to close.
499 */
500 void
501 _bsearch_file_close(bsearch_file_handle *bfh)
502 {
503 if (!*bfh)
504 return;
505 if ((*bfh)->fd >= 0)
506 (void) close((*bfh)->fd);
507 if ((*bfh)->page)
508 free((*bfh)->page);
509 if ((*bfh)->cache)
510 free((*bfh)->cache);
511 free(*bfh);
512 *bfh = NULL;
513 }
514
515 /*
516 * Private function to get a page from a cache. The cache is a char
517 * array of 2^n - 1 double-size page worth of bytes, where n is the
518 * number of tree levels that the cache stores. The cache can be
519 * smaller than n implies.
520 *
521 * The page may or may not be valid. If the first byte of it is NUL
522 * then it's not valid, else it is.
523 *
524 * Returns 1 if page is in cache and valid, 0 if the cache is too small
525 * or the page is invalid. The page address is output in @buf if the
526 * cache is large enough to contain it regardless of whether the page is
527 * valid.
528 *
529 * Inputs:
530 *
531 * @bfh Binary search file handle
532 * @level Level in the tree that we want a page for
533 * @page_idx Page number in the given level (0..2^level - 1)
534 *
535 * Outputs:
536 *
537 * @buf Set to address of page if the cache is large enough
538 */
539 static int
540 get_page_from_cache(bsearch_file_handle bfh, size_t level, size_t page_idx,
541 char **buf)
542 {
543 size_t idx = 0;
544 size_t page_sz;
545
546 page_sz = bfh->page_sz << 1; /* we use double-size pages in the cache */
547
548 *buf = NULL;
549
550 /*
551 * Compute index into cache. The cache is basically an array of
552 * double-size pages. The first (zeroth) double-size page in the
553 * cache will be the middle page of the file -- the root of the
554 * tree. The next two double-size pages will be the left and right
555 * pages of the second level in the tree. The next four double-size
556 * pages will be the four pages at the next level. And so on for as
557 * many pages as fit in the cache.
558 *
559 * The page index is the number of the page at the given level. We
560 * then compute (2^level - 1 + page index) * 2page size, check that
561 * we have that in the cache, check that the page has been read (it
562 * doesn't start with NUL).
563 */
564 if (level)
565 idx = (1 << level) - 1 + page_idx;
566 if (((idx + 1) * page_sz * 2) > bfh->cache_sz)
567 return 0;
568
569 *buf = &bfh->cache[idx * page_sz * 2];
570 if (bfh->cache[idx * page_sz * 2] == '\0')
571 return 0; /* cache[idx] == NUL -> page not loaded in cache */
572 return 1;
573 }
574
575 /*
576 * Private function to read a page of @page_sz from @fd at offset @off
577 * into @buf, outputing the number of bytes read, which will be the same
578 * as @page_sz unless the page being read is the last page, in which
579 * case the number of remaining bytes in the file will be output.
580 *
581 * Returns 0 on success or an errno value otherwise (EIO if reads are
582 * short).
583 *
584 * Inputs:
585 *
586 * @bfh Binary search file handle
587 * @level Level in the binary search tree that we're at
588 * @page_idx Page "index" at the @level of the tree that we want
589 * @page Actual page number that we want
590 * want_double Whether we need a page or double page read
591 *
592 * Outputs:
593 *
594 * @buf Page read or cached
595 * @bytes Bytes read (may be less than page or double page size in
596 * the case of the last page, of course)
597 */
598 static int
599 read_page(bsearch_file_handle bfh, size_t level, size_t page_idx, size_t page,
600 int want_double, const char **buf, size_t *bytes)
601 {
602 int ret;
603 off_t off;
604 size_t expected;
605 size_t wanted;
606 char *page_buf;
607
608 /* Figure out where we're reading and how much */
609 off = page * bfh->page_sz;
610 if (off < 0)
611 return EOVERFLOW;
612
613 wanted = bfh->page_sz << want_double;
614 expected = ((bfh->file_sz - off) > wanted) ? wanted : bfh->file_sz - off;
615
616 if (get_page_from_cache(bfh, level, page_idx, &page_buf)) {
617 *buf = page_buf;
618 *bytes = expected;
619 return 0; /* found in cache */
620 }
621
622
623 *bytes = 0;
624 *buf = NULL;
625
626 /* OK, we have to read a page or double-size page */
627
628 if (page_buf)
629 want_double = 1; /* we'll be caching; we cache double-size pages */
630 else
631 page_buf = bfh->page; /* we won't cache this page */
632
633 wanted = bfh->page_sz << want_double;
634 expected = ((bfh->file_sz - off) > wanted) ? wanted : bfh->file_sz - off;
635
636 #ifdef HAVE_PREAD
637 ret = pread(bfh->fd, page_buf, expected, off);
638 #else
639 if (lseek(bfh->fd, off, SEEK_SET) == (off_t)-1)
640 return errno;
641 ret = read(bfh->fd, page_buf, expected);
642 #endif
643 if (ret < 0)
644 return errno;
645
646 if (ret != expected)
647 return EIO; /* XXX ??? */
648
649 *buf = page_buf;
650 *bytes = expected;
651 return 0;
652 }
653
654 /*
655 * Perform a binary search of a file where each line is a record (LF and
656 * CRLF supported). Each record consists of a key followed by an
657 * optional value separated from the key by whitespace. Whitespace can
658 * be quoted with backslashes. It's the caller's responsibility to
659 * encode/decode keys/values if quoting is desired; newlines should be
660 * encoded such that a newline does not appear in the result.
661 *
662 * The search is done with block-wise I/O (i.e., the whole file is not
663 * read into memory).
664 *
665 * All output arguments are optional.
666 *
667 * Returns 0 if key is found, -1 if not found, or an error code such as
668 * ENOMEM in case of error.
669 *
670 * NOTE: We could improve this by not freeing the buffer, instead
671 * requiring that the caller provide it. Further, we could cache
672 * the top N levels of [double-size] pages (2^N - 1 pages), which
673 * should speed up most searches by reducing the number of reads
674 * by N.
675 *
676 * Inputs:
677 *
678 * @fd File descriptor (file to search)
679 * @page_sz Page size (if zero then the file's st_blksize will be used)
680 * @key Key string to search for
681 *
682 * Outputs:
683 *
684 * @value Location to store a copy of the value (caller must free)
685 * @location Record location if found else the location where the
686 * record should be inserted (index into @buf)
687 * @loops Location to store a count of bisections required for
688 * search (useful for confirming logarithmic performance)
689 * @reads Location to store a count of pages read during search
690 * (useful for confirming logarithmic performance)
691 */
692 int
693 _bsearch_file(bsearch_file_handle bfh, const char *key,
694 char **value, size_t *location, size_t *loops, size_t *reads)
695 {
696 int ret;
697 const char *buf;
698 size_t buf_sz;
699 size_t page, l, r;
700 size_t my_reads = 0;
701 size_t my_loops_total = 0;
702 size_t my_loops;
703 size_t level; /* level in the tree */
704 size_t page_idx = 0; /* page number in the tree level */
705 size_t buf_location;
706 int cmp;
707 int buf_ends_in_eol = 0;
708 int buf_is_start = 0;
709
710 if (reads)
711 *reads = 0;
712 if (value)
713 *value = NULL;
714 if (loops)
715 *loops = 0;
716
717 /* If whole file is in memory then search that and we're done */
718 if (bfh->file_sz == bfh->cache_sz)
719 return _bsearch_text(bfh->cache, bfh->cache_sz, key, value, location, loops);
720
721 /* Else block-wise binary search */
722
723 l = 0;
724 r = (bfh->file_sz / bfh->page_sz) + 1;
725 for (level = 0, page = r >> 1; page >= l && page < r ; level++) {
726 ret = read_page(bfh, level, page_idx, page, 0, &buf, &buf_sz);
727 if (ret != 0)
728 return ret;
729 my_reads++;
730 if (buf[buf_sz - 1] == '\r' || buf[buf_sz - 1] == '\n')
731 buf_ends_in_eol = 1;
732 else
733 buf_ends_in_eol = 0;
734
735 buf_is_start = page == 0 ? 1 : 0;
736 ret = bsearch_common(buf, (size_t)buf_sz, key, buf_is_start,
737 value, &buf_location, &cmp, &my_loops);
738 if (ret > 0)
739 return ret;
740 /* Found or no we update stats */
741 my_loops_total += my_loops;
742 if (loops)
743 *loops = my_loops_total;
744 if (reads)
745 *reads = my_reads;
746 if (location)
747 *location = page * bfh->page_sz + buf_location;
748 if (ret == 0)
749 return 0; /* found! */
750 /* Not found */
751 if (cmp < 0) {
752 /* Search left */
753 page_idx <<= 1;
754 r = page;
755 page = l + ((r - l) >> 1);
756 continue;
757 } else {
758 /*
759 * Search right, but first search the current and next
760 * blocks in case that the record we're looking for either
761 * straddles the boundary between this and the next record,
762 * or in case the record starts exactly at the next page.
763 */
764 heim_assert(cmp > 0, "cmp > 0");
765
766 if (!buf_ends_in_eol || page == l || page == (r - 1)) {
767 ret = read_page(bfh, level, page_idx, page, 1, &buf, &buf_sz);
768 if (ret != 0)
769 return ret;
770 my_reads++;
771
772 buf_is_start = page == l ? 1 : 0;
773
774 ret = bsearch_common(buf, (size_t)buf_sz, key, buf_is_start,
775 value, &buf_location, &cmp, &my_loops);
776 if (ret > 0)
777 return ret;
778 my_loops_total += my_loops;
779 if (loops)
780 *loops = my_loops_total;
781 if (reads)
782 *reads = my_reads;
783 if (location)
784 *location = page * bfh->page_sz + buf_location;
785 if (ret == 0)
786 return 0;
787 }
788
789 /* Oh well, search right */
790 if (l == page && r == (l + 1))
791 break;
792 page_idx = (page_idx << 1) + 1;
793 l = page;
794 page = l + ((r - l) >> 1);
795 continue;
796 }
797 }
798 return -1;
799 }
800
801
802 static int
803 stdb_open(void *plug, const char *dbtype, const char *dbname,
804 heim_dict_t options, void **db, heim_error_t *error)
805 {
806 bsearch_file_handle bfh;
807 char *p;
808 int ret;
809
810 if (error)
811 *error = NULL;
812 if (dbname == NULL || *dbname == '\0') {
813 if (error)
814 *error = heim_error_create(EINVAL,
815 N_("DB name required for sorted-text DB "
816 "plugin", ""));
817 return EINVAL;
818 }
819 p = strrchr(dbname, '.');
820 if (p == NULL || strcmp(p, ".txt") != 0) {
821 if (error)
822 *error = heim_error_create(ENOTSUP,
823 N_("Text file (name ending in .txt) "
824 "required for sorted-text DB plugin",
825 ""));
826 return ENOTSUP;
827 }
828
829 ret = _bsearch_file_open(dbname, 0, 0, &bfh, NULL);
830 if (ret)
831 return ret;
832
833 *db = bfh;
834 return 0;
835 }
836
837 static int
838 stdb_close(void *db, heim_error_t *error)
839 {
840 bsearch_file_handle bfh = db;
841
842 if (error)
843 *error = NULL;
844 _bsearch_file_close(&bfh);
845 return 0;
846 }
847
848 static heim_data_t
849 stdb_copy_value(void *db, heim_string_t table, heim_data_t key,
850 heim_error_t *error)
851 {
852 bsearch_file_handle bfh = db;
853 const char *k;
854 char *v = NULL;
855 heim_data_t value;
856 int ret;
857
858 if (error)
859 *error = NULL;
860
861 if (table == NULL)
862 table = HSTR("");
863
864 if (table != HSTR(""))
865 return NULL;
866
867 if (heim_get_tid(key) == HEIM_TID_STRING)
868 k = heim_string_get_utf8((heim_string_t)key);
869 else
870 k = (const char *)heim_data_get_ptr(key);
871 ret = _bsearch_file(bfh, k, &v, NULL, NULL, NULL);
872 if (ret == 0 && v == NULL)
873 ret = -1; /* Quiet lint */
874 if (ret != 0) {
875 if (ret > 0 && error)
876 *error = heim_error_create(ret, "%s", strerror(ret));
877 return NULL;
878 }
879 value = heim_data_create(v, strlen(v));
880 free(v);
881 /* XXX Handle ENOMEM */
882 return value;
883 }
884
885 struct heim_db_type heim_sorted_text_file_dbtype = {
886 1, stdb_open, NULL, stdb_close, NULL, NULL, NULL, NULL, NULL, NULL,
887 stdb_copy_value, NULL, NULL, NULL
888 };