2 * Copyright (c) 2011, Secure Endpoints Inc.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
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
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.
34 #include <sys/types.h>
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).
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
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.
79 * bsearch_common() contains the common text block binary search code.
81 * _bsearch_text() is the interface for searching in-core text.
82 * _bsearch_file() is the interface for block-wise searching files.
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 */
96 find_line(const char *buf, size_t i, size_t right)
100 for (; i < right; i++) {
101 if (buf[i] == '\n') {
111 * Common routine for binary searching text in core.
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.
121 * All output arguments are optional.
123 * Returns 0 if key is found, -1 if not found, or an error code such as
124 * ENOMEM in case of error.
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
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
145 * @loops Location to store a count of bisections required for
146 * search (useful for confirming logarithmic performance)
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)
154 size_t key_start, key_len; /* key string in buf */
155 size_t val_start, val_len; /* value string in buf */
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;
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");
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) {
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
188 i = l + ((r - l) >> 1);
192 heim_assert(i >= l && i < rmax, "invalid aname2lname db index");
194 /* Got a line; check it */
196 /* Search for and split on unquoted whitespace */
198 for (key_start = i, key_len = 0, val_len = 0, k = i; k < rmax; k++) {
199 if (buf[k] == '\\') {
203 if (buf[k] == '\r' || buf[k] == '\n') {
204 /* We now know where the key ends, and there's no value */
208 if (!isspace((unsigned char)buf[k]))
211 while (k < rmax && isspace((unsigned char)buf[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;
228 * The following logic is for dealing with partial buffers,
229 * which we use for block-wise binary searches of large files
231 if (key_start == 0 && !buf_is_start) {
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.
241 if ((val_len && buf[val_start + val_len] != '\n') ||
242 (!val_len && buf[key_start + key_len] != '\n')) {
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.
254 key_cmp = strncmp(key, &buf[key_start], key_len);
255 if (key_cmp == 0 && strlen(key) != key_len)
259 r = rmax = (linep - buf);
260 i = l + ((r - l) >> 1);
262 *location = key_start;
263 } else if (key_cmp > 0) {
266 break; /* not found */
268 i = l + ((r - l) >> 1);
270 *location = val_start + val_len;
274 *location = key_start;
276 if (val_len && value) {
277 /* Avoid strndup() so we don't need libroken here yet */
278 *value = malloc(val_len + 1);
281 (void) memcpy(*value, &buf[val_start], val_len);
282 (*value)[val_len] = '\0';
297 * Binary search a char array containing sorted text records separated
298 * by new-lines (or CRLF). Each record consists of a key and an
299 * optional value following the key, separated from the key by unquoted
302 * All output arguments are optional.
304 * Returns 0 if key is found, -1 if not found, or an error code such as
305 * ENOMEM in case of error.
309 * @buf Char array pointer
310 * @buf_sz Size of buf
311 * @key Key to search for
315 * @value Location where to put the value, if any (caller must free)
316 * @location Record location if found else the location where the record
317 * should be inserted (index into @buf)
318 * @loops Location where to put a number of loops (or comparisons)
319 * needed for the search (useful for benchmarking)
322 _bsearch_text(const char *buf, size_t buf_sz, const char *key,
323 char **value, size_t *location, size_t *loops)
325 return bsearch_common(buf, buf_sz, key, 1, value, location, NULL, loops);
328 #define MAX_BLOCK_SIZE (1024 * 1024)
329 #define DEFAULT_MAX_FILE_SIZE (1024 * 1024)
331 * Open a file for binary searching. The file will be read in entirely
332 * if it is smaller than @max_sz, else a cache of @max_sz bytes will be
335 * Returns 0 on success, else an error number or -1 if the file is empty.
339 * @fname Name of file to open
340 * @max_sz Maximum size of cache to allocate, in bytes (if zero, default)
341 * @page_sz Page size (must be a power of two, larger than 256, smaller
342 * than 1MB; if zero use default)
346 * @bfh Handle for use with _bsearch_file() and _bsearch_file_close()
347 * @reads Number of reads performed
350 _bsearch_file_open(const char *fname, size_t max_sz, size_t page_sz,
351 bsearch_file_handle *bfh, size_t *reads)
353 bsearch_file_handle new_bfh = NULL;
364 fd = open(fname, O_RDONLY);
368 if (fstat(fd, &st) == -1) {
373 if (st.st_size == 0) {
374 ret = -1; /* no data -> no binary search */
378 /* Validate / default arguments */
380 max_sz = DEFAULT_MAX_FILE_SIZE;
381 for (i = page_sz; i; i >>= 1) {
382 /* Make sure page_sz is a power of two */
383 if ((i % 2) && (i >> 1)) {
389 #ifdef HAVE_STRUCT_STAT_ST_BLKSIZE
390 page_sz = st.st_blksize;
394 for (i = page_sz; i; i >>= 1) {
395 /* Make sure page_sz is a power of two */
396 if ((i % 2) && (i >> 1)) {
397 /* Can't happen! Filesystems always use powers of two! */
402 if (page_sz > MAX_BLOCK_SIZE)
403 page_sz = MAX_BLOCK_SIZE;
405 new_bfh = calloc(1, sizeof (*new_bfh));
406 if (new_bfh == NULL) {
412 new_bfh->page_sz = page_sz;
413 new_bfh->file_sz = st.st_size;
415 if (max_sz >= st.st_size) {
416 /* Whole-file method */
417 new_bfh->cache = malloc(st.st_size + 1);
418 if (new_bfh->cache) {
419 new_bfh->cache[st.st_size] = '\0';
420 new_bfh->cache_sz = st.st_size;
421 ret = read(fd, new_bfh->cache, st.st_size);
426 if (ret != st.st_size) {
427 ret = EIO; /* XXX ??? */
439 /* Block-size method, or above malloc() failed */
440 new_bfh->page = malloc(new_bfh->page_sz << 1);
441 if (new_bfh->page == NULL) {
442 /* Can't even allocate a single double-size page! */
447 new_bfh->cache_sz = max_sz < st.st_size ? max_sz : st.st_size;
448 new_bfh->cache = malloc(new_bfh->cache_sz);
452 * malloc() may have failed because we were asking for a lot of
453 * memory, but we may still be able to operate without a cache,
456 if (new_bfh->cache == NULL) {
457 new_bfh->cache_sz = 0;
461 /* Initialize cache */
462 for (i = 0; i < new_bfh->cache_sz; i += new_bfh->page_sz)
463 new_bfh->cache[i] = '\0';
470 free(new_bfh->cache);
477 * Indicate whether the given binary search file handle will be searched
478 * with block-wise method.
481 _bsearch_file_info(bsearch_file_handle bfh,
482 size_t *page_sz, size_t *max_sz, int *blockwise)
485 *page_sz = bfh->page_sz;
487 *max_sz = bfh->cache_sz;
489 *blockwise = (bfh->file_sz != bfh->cache_sz);
493 * Close the given binary file search handle.
497 * @bfh Pointer to variable containing handle to close.
500 _bsearch_file_close(bsearch_file_handle *bfh)
505 (void) close((*bfh)->fd);
515 * Private function to get a page from a cache. The cache is a char
516 * array of 2^n - 1 double-size page worth of bytes, where n is the
517 * number of tree levels that the cache stores. The cache can be
518 * smaller than n implies.
520 * The page may or may not be valid. If the first byte of it is NUL
521 * then it's not valid, else it is.
523 * Returns 1 if page is in cache and valid, 0 if the cache is too small
524 * or the page is invalid. The page address is output in @buf if the
525 * cache is large enough to contain it regardless of whether the page is
530 * @bfh Binary search file handle
531 * @level Level in the tree that we want a page for
532 * @page_idx Page number in the given level (0..2^level - 1)
536 * @buf Set to address of page if the cache is large enough
539 get_page_from_cache(bsearch_file_handle bfh, size_t level, size_t page_idx,
545 page_sz = bfh->page_sz << 1; /* we use double-size pages in the cache */
550 * Compute index into cache. The cache is basically an array of
551 * double-size pages. The first (zeroth) double-size page in the
552 * cache will be the middle page of the file -- the root of the
553 * tree. The next two double-size pages will be the left and right
554 * pages of the second level in the tree. The next four double-size
555 * pages will be the four pages at the next level. And so on for as
556 * many pages as fit in the cache.
558 * The page index is the number of the page at the given level. We
559 * then compute (2^level - 1 + page index) * 2page size, check that
560 * we have that in the cache, check that the page has been read (it
561 * doesn't start with NUL).
564 idx = (1 << level) - 1 + page_idx;
565 if (((idx + 1) * page_sz * 2) > bfh->cache_sz)
568 *buf = &bfh->cache[idx * page_sz * 2];
569 if (bfh->cache[idx * page_sz * 2] == '\0')
570 return 0; /* cache[idx] == NUL -> page not loaded in cache */
575 * Private function to read a page of @page_sz from @fd at offset @off
576 * into @buf, outputing the number of bytes read, which will be the same
577 * as @page_sz unless the page being read is the last page, in which
578 * case the number of remaining bytes in the file will be output.
580 * Returns 0 on success or an errno value otherwise (EIO if reads are
585 * @bfh Binary search file handle
586 * @level Level in the binary search tree that we're at
587 * @page_idx Page "index" at the @level of the tree that we want
588 * @page Actual page number that we want
589 * want_double Whether we need a page or double page read
593 * @buf Page read or cached
594 * @bytes Bytes read (may be less than page or double page size in
595 * the case of the last page, of course)
598 read_page(bsearch_file_handle bfh, size_t level, size_t page_idx, size_t page,
599 int want_double, const char **buf, size_t *bytes)
607 /* Figure out where we're reading and how much */
608 off = page * bfh->page_sz;
612 wanted = bfh->page_sz << want_double;
613 expected = ((bfh->file_sz - off) > wanted) ? wanted : bfh->file_sz - off;
615 if (get_page_from_cache(bfh, level, page_idx, &page_buf)) {
618 return 0; /* found in cache */
625 /* OK, we have to read a page or double-size page */
628 want_double = 1; /* we'll be caching; we cache double-size pages */
630 page_buf = bfh->page; /* we won't cache this page */
632 wanted = bfh->page_sz << want_double;
633 expected = ((bfh->file_sz - off) > wanted) ? wanted : bfh->file_sz - off;
636 ret = pread(bfh->fd, page_buf, expected, off);
638 if (lseek(bfh->fd, off, SEEK_SET) == (off_t)-1)
640 ret = read(bfh->fd, page_buf, expected);
646 return EIO; /* XXX ??? */
654 * Perform a binary search of a file where each line is a record (LF and
655 * CRLF supported). Each record consists of a key followed by an
656 * optional value separated from the key by whitespace. Whitespace can
657 * be quoted with backslashes. It's the caller's responsibility to
658 * encode/decode keys/values if quoting is desired; newlines should be
659 * encoded such that a newline does not appear in the result.
661 * The search is done with block-wise I/O (i.e., the whole file is not
664 * All output arguments are optional.
666 * Returns 0 if key is found, -1 if not found, or an error code such as
667 * ENOMEM in case of error.
669 * NOTE: We could improve this by not freeing the buffer, instead
670 * requiring that the caller provide it. Further, we could cache
671 * the top N levels of [double-size] pages (2^N - 1 pages), which
672 * should speed up most searches by reducing the number of reads
677 * @fd File descriptor (file to search)
678 * @page_sz Page size (if zero then the file's st_blksize will be used)
679 * @key Key string to search for
683 * @value Location to store a copy of the value (caller must free)
684 * @location Record location if found else the location where the
685 * record should be inserted (index into @buf)
686 * @loops Location to store a count of bisections required for
687 * search (useful for confirming logarithmic performance)
688 * @reads Location to store a count of pages read during search
689 * (useful for confirming logarithmic performance)
692 _bsearch_file(bsearch_file_handle bfh, const char *key,
693 char **value, size_t *location, size_t *loops, size_t *reads)
700 size_t my_loops_total = 0;
702 size_t level; /* level in the tree */
703 size_t page_idx = 0; /* page number in the tree level */
706 int buf_ends_in_eol = 0;
707 int buf_is_start = 0;
712 /* If whole file is in memory then search that and we're done */
713 if (bfh->file_sz == bfh->cache_sz)
714 return _bsearch_text(bfh->cache, bfh->cache_sz, key, value, location, loops);
716 /* Else block-wise binary search */
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);
730 if (buf[buf_sz - 1] == '\r' || buf[buf_sz - 1] == '\n')
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);
740 /* Found or no we update stats */
741 my_loops_total += my_loops;
743 *loops = my_loops_total;
747 *location = page * bfh->page_sz + buf_location;
749 return 0; /* found! */
755 page = l + ((r - l) >> 1);
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.
764 heim_assert(cmp > 0, "cmp > 0");
766 if (!buf_ends_in_eol || page == l || page == (r - 1)) {
767 ret = read_page(bfh, level, page_idx, page, 1, &buf, &buf_sz);
772 buf_is_start = page == l ? 1 : 0;
774 ret = bsearch_common(buf, (size_t)buf_sz, key, buf_is_start,
775 value, &buf_location, &cmp, &my_loops);
778 my_loops_total += my_loops;
780 *loops = my_loops_total;
784 *location = page * bfh->page_sz + buf_location;
789 /* Oh well, search right */
790 if (l == page && r == (l + 1))
792 page_idx = (page_idx << 1) + 1;
794 page = l + ((r - l) >> 1);
803 stdb_open(void *plug, const char *dbtype, const char *dbname,
804 heim_dict_t options, void **db, heim_error_t *error)
806 bsearch_file_handle bfh;
812 if (dbname == NULL || *dbname == '\0') {
814 *error = heim_error_create(EINVAL,
815 N_("DB name required for sorted-text DB "
819 p = strrchr(dbname, '.');
820 if (p == NULL || strcmp(p, ".txt") != 0) {
822 *error = heim_error_create(ENOTSUP,
823 N_("Text file (name ending in .txt) "
824 "required for sorted-text DB plugin",
829 ret = _bsearch_file_open(dbname, 0, 0, &bfh, NULL);
838 stdb_close(void *db, heim_error_t *error)
840 bsearch_file_handle bfh = db;
844 _bsearch_file_close(&bfh);
849 stdb_copy_value(void *db, heim_string_t table, heim_data_t key,
852 bsearch_file_handle bfh = db;
864 if (table != HSTR(""))
867 if (heim_get_tid(key) == HEIM_TID_STRING)
868 k = heim_string_get_utf8((heim_string_t)key);
870 k = (const char *)heim_data_get_ptr(key);
871 ret = _bsearch_file(bfh, k, &v, NULL, NULL, NULL);
873 if (ret > 0 && error)
874 *error = heim_error_create(ret, "%s", strerror(ret));
877 value = heim_data_create(v, strlen(v));
879 /* XXX Handle ENOMEM */
883 struct heim_db_type heim_sorted_text_file_dbtype = {
884 1, stdb_open, NULL, stdb_close, NULL, NULL, NULL, NULL, NULL, NULL,
885 stdb_copy_value, NULL, NULL, NULL