appl/dbutils/bsearch.c

   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 <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include <strings.h>
  36 #include <errno.h>
  37 #include <roken.h>
  38 #include <heimbase.h>
  39 #include <getarg.h>
  40 #include <vers.h>
  41
  42 int help_flag;
  43 int version_flag;
  44 int verbose_flag;
  45 int print_keys_flag;
  46 int no_values_flag;
  47 int block_size_int;
  48 int max_size_int;
  49
  50 struct getargs args[] = {
  51     { "print-keys",     'K',  arg_flag, &print_keys_flag,
  52         "print keys", NULL },
  53     { "no-values",      'V',  arg_flag, &no_values_flag,
  54         "don't print values", NULL },
  55     { "verbose",        'v',  arg_flag, &verbose_flag,
  56         "print statistics and informative messages", NULL },
  57     { "help",           'h',  arg_flag, &help_flag,
  58         "print usage message", NULL },
  59     { "block-size",     'b',  arg_integer, &block_size_int,
  60         "block size", "integer" },
  61     { "max-cache-size", 'm',  arg_integer, &max_size_int,
  62         "maximum cache size", "integer" },
  63     { "version",        '\0', arg_flag, &version_flag, NULL, NULL }
  64 };
  65
  66 static int num_args = sizeof(args) / sizeof(args[0]);
  67
  68 static void
  69 usage(int status)
  70 {
  71     arg_printusage(args, num_args, NULL, "file [key ...]");
  72     exit(status);
  73 }
  74
  75 #define MAX_BLOCK_SIZE (1024 * 1024)
  76 #define DEFAULT_MAX_FILE_SIZE (1024 * 1024)
  77
  78 int
  79 main(int argc, char **argv)
  80 {
  81     char keybuf[1024];
  82     char *fname;
  83     char *key = keybuf;
  84     char *value;
  85     char *p;
  86     bsearch_file_handle bfh = NULL;
  87     size_t num;
  88     size_t loc;           /* index where record is located or to be inserted */
  89     size_t loops;         /* number of loops/comparisons needed for lookup */
  90     size_t reads = 0;     /* number of reads needed for a lookup */
  91     size_t failures = 0;  /* number of lookup failures -- for exit status */
  92     size_t block_size = 0;
  93     size_t max_size = 0;
  94     int optidx = 0;
  95     int blockwise;
  96     int ret = 0;
  97
  98     setprogname(argv[0]);
  99     if (getarg(args, num_args, argc, argv, &optidx))
 100         usage(1);
 101
 102     if (version_flag) {
 103         print_version(NULL);
 104         return 0;
 105     }
 106
 107     if (help_flag)
 108         usage(0);
 109
 110     if (block_size_int != 0 && block_size_int < 512) {
 111         fprintf(stderr, "Invalid block size: too small\n");
 112         return 1;
 113     }
 114     if (block_size_int > 0) {
 115         /* Check that block_size is a power of 2 */
 116         num = block_size_int;
 117         while (num) {
 118             if ((num % 2) && (num >> 1)) {
 119                 fprintf(stderr, "Invalid block size: must be power "
 120                         "of two\n");
 121                 return 1;
 122             }
 123             num >>= 1;
 124         }
 125         if (block_size_int > MAX_BLOCK_SIZE)
 126             fprintf(stderr, "Invalid block size: too large\n");
 127         block_size = block_size_int;
 128     }
 129     if (max_size_int < 0)
 130         usage(1);
 131     max_size = max_size_int;
 132
 133     argc -= optind;
 134     argv += optind;
 135
 136     if (argc == 0)
 137         usage(1);
 138
 139     fname = argv[0];
 140     argc--;
 141     argv++;
 142
 143     ret = _bsearch_file_open(fname, max_size, block_size, &bfh, &reads);
 144     if (ret != 0) {
 145         perror("bsearch_file_open");
 146         return 1;
 147     }
 148
 149     _bsearch_file_info(bfh, &block_size, &max_size, &blockwise);
 150     if (verbose_flag && blockwise) {
 151         fprintf(stderr, "Using block-wise method with block size %lu and "
 152                 "cache size %lu\n",
 153                 (long unsigned)block_size, (long unsigned)max_size);
 154     } else if (verbose_flag) {
 155         fprintf(stderr, "Using whole-file method\n");
 156     }
 157
 158     for (;;) {
 159         loops = 0; /* reset stats */
 160         /* Eww */
 161         if (argc) {
 162             key = *(argv++);
 163             if (!key)
 164                 break;
 165         } else {
 166             if (!fgets(keybuf, sizeof (keybuf), stdin))
 167                 break;
 168             p = strchr(key, '\n');
 169             if (!p)
 170                 break;
 171             *p = '\0';
 172             if (!*key)
 173                 continue;
 174         }
 175         ret = _bsearch_file(bfh, key, &value, &loc, &loops, &reads);
 176         if (ret != 0) {
 177             if (ret > 0) {
 178                 fprintf(stderr, "Error: %s\n", strerror(ret));
 179                 _bsearch_file_close(&bfh);
 180                 return 1;
 181             }
 182             if (verbose_flag)
 183                 fprintf(stderr, "Key %s not found in %lu loops and %lu reads; "
 184                         "insert at %lu\n", key, (long unsigned)loops,
 185                         (long unsigned)reads, (long unsigned)loc);
 186             failures++;
 187             continue;
 188         }
 189         if (verbose_flag)
 190             fprintf(stderr, "Key %s found at offset %lu in %lu loops and "
 191                     "%lu reads\n", key, (long unsigned)loc,
 192                     (long unsigned)loops, (long unsigned)reads);
 193         if (print_keys_flag && !no_values_flag && value)
 194             printf("%s %s\n", key, value);
 195         else if (print_keys_flag)
 196             printf("%s\n", key);
 197         else if (no_values_flag && value)
 198             printf("%s\n", value);
 199         free(value);
 200     }
 201     if (failures)
 202         return 2;
 203     _bsearch_file_close(&bfh);
 204     return 0;
 205 }