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 = realloc(l->items, sizeof (char *) * l->nallocated);
  76         }
  77         l->items[l->nused++] = s;
  78         l->sorted = l->nused <= 1;
  79 }
  80
  81 void
  82 item_add_list(itemlist l, char **s, int n, int alloc)
  83 {
  84         if (l->nallocated == 0) {
  85                 l->items = s;
  86                 l->nallocated = alloc ? n : -1;
  87                 l->nused = n;
  88                 l->sorted = 0;
  89         } else {
  90                 int i;
  91
  92                 for (i = 0; i < n; i++)
  93                         item_add(l, s[i]);
  94
  95                 if (alloc)
  96                         free(s);
  97         }
  98 }
  99
 100 int
 101 item_addfile(itemlist l, const char *fname)
 102 {
 103         FILE *f = fopen(fname, "r");
 104         char buf[10240];
 105
 106         if (f == NULL)
 107                 return (-1);
 108
 109         while (fgets(buf, sizeof (buf), f) != NULL) {
 110                 if (buf[0] == '#' || buf[0] == '\n')
 111                         continue;
 112
 113                 buf[strlen(buf)-1] = '\0';
 114                 item_add(l, strdup(buf));
 115         }
 116         fclose(f);
 117
 118         return (0);
 119 }
 120
 121 static int
 122 xcmp(const void *s1, const void *s2)
 123 {
 124         return (strcmp(*(char **)s1, *(char **)s2));
 125 }
 126
 127 int
 128 item_search(itemlist l, const char *s)
 129 {
 130         int lo = 0;
 131         int hi = l->nused - 1;
 132
 133         if (!l->sorted) {
 134                 qsort(l->items, l->nused, sizeof (char *), xcmp);
 135                 l->sorted = 1;
 136         }
 137
 138         while (lo <= hi) {
 139                 int mid = (lo + hi) / 2;
 140                 int res = strcmp(s, l->items[mid]);
 141
 142                 if (res == 0)
 143                         return (mid);
 144                 else if (res < 0)
 145                         hi = mid - 1;
 146                 else
 147                         lo = mid + 1;
 148         }
 149         return (-1);
 150 }
 151
 152 char
 153 *item_get(itemlist l, int i)
 154 {
 155         if (i >= l->nused || i < 0)
 156                 return (NULL);
 157         else
 158                 return (l->items[i]);
 159 }