xref: /titanic_50/usr/src/tools/pmodes/binsearch.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
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