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