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