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