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
new_itemlist(void)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
item_add(itemlist l,char * s)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
item_add_list(itemlist l,char ** s,int n,int alloc)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
item_addfile(itemlist l,const char * fname)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
xcmp(const void * s1,const void * s2)122 xcmp(const void *s1, const void *s2)
123 {
124 return (strcmp(*(char **)s1, *(char **)s2));
125 }
126
127 int
item_search(itemlist l,const char * s)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
item_get(itemlist l,int i)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