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 } 160