usr/src/tools/pmodes/binsearch.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright (c) 2000-2001 by Sun Microsystems, Inc.
  24  * All rights reserved.
  25  */
  26
  27 #pragma ident   "%Z%%M% %I%     %E% SMI"
  28
  29 /*
  30  * String list maintenance and binary search routines
  31  */
  32
  33
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <string.h>
  37
  38 #define ALLOCCHUNK      128
  39
  40 struct itemlist  {
  41     char **items;
  42     int nallocated;
  43     int nused;
  44     int sorted;
  45 };
  46
  47 #include "binsearch.h"
  48
  49 itemlist
  50 new_itemlist(void)
  51 {
  52         itemlist x = malloc(sizeof (struct itemlist));
  53
  54         x->nallocated = x->nused = 0;
  55         x->sorted = 1;
  56         x->items = 0;
  57
  58         return (x);
  59 }
  60
  61 void
  62 item_add(itemlist l, char *s)
  63 {
  64         if (l->nallocated < 0) {
  65                 char **new;
  66                 l->nallocated = l->nused + ALLOCCHUNK;
  67                 new = malloc(sizeof (char *) * l->nused);
  68                 memcpy(new, l->items, l->nused * sizeof (char *));
  69                 l->items = new;
  70         } else if (l->nallocated == l->nused) {
  71                 if (l->nallocated)
  72                         l->nallocated *= 2;
  73                 else
  74                         l->nallocated = ALLOCCHUNK;
  75                 l->items = reallocarray(l->items, l->nallocated,
  76                    sizeof (char *));
  77         }
  78         l->items[l->nused++] = s;
  79         l->sorted = l->nused <= 1;
  80 }
  81
  82 void
  83 item_add_list(itemlist l, char **s, int n, int alloc)
  84 {
  85         if (l->nallocated == 0) {
  86                 l->items = s;
  87                 l->nallocated = alloc ? n : -1;
  88                 l->nused = n;
  89                 l->sorted = 0;
  90         } else {
  91                 int i;
  92
  93                 for (i = 0; i < n; i++)
  94                         item_add(l, s[i]);
  95
  96                 if (alloc)
  97                         free(s);
  98         }
  99 }
 100
 101 int
 102 item_addfile(itemlist l, const char *fname)
 103 {
 104         FILE *f = fopen(fname, "r");
 105         char buf[10240];
 106
 107         if (f == NULL)
 108                 return (-1);
 109
 110         while (fgets(buf, sizeof (buf), f) != NULL) {
 111                 if (buf[0] == '#' || buf[0] == '\n')
 112                         continue;
 113
 114                 buf[strlen(buf)-1] = '\0';
 115                 item_add(l, strdup(buf));
 116         }
 117         fclose(f);
 118
 119         return (0);
 120 }
 121
 122 static int
 123 xcmp(const void *s1, const void *s2)
 124 {
 125         return (strcmp(*(char **)s1, *(char **)s2));
 126 }
 127
 128 int
 129 item_search(itemlist l, const char *s)
 130 {
 131         int lo = 0;
 132         int hi = l->nused - 1;
 133
 134         if (!l->sorted) {
 135                 qsort(l->items, l->nused, sizeof (char *), xcmp);
 136                 l->sorted = 1;
 137         }
 138
 139         while (lo <= hi) {
 140                 int mid = (lo + hi) / 2;
 141                 int res = strcmp(s, l->items[mid]);
 142
 143                 if (res == 0)
 144                         return (mid);
 145                 else if (res < 0)
 146                         hi = mid - 1;
 147                 else
 148                         lo = mid + 1;
 149         }
 150         return (-1);
 151 }
 152
 153 char
 154 *item_get(itemlist l, int i)
 155 {
 156         if (i >= l->nused || i < 0)
 157                 return (NULL);
 158         else
 159                 return (l->items[i]);
 160 }