1 7cf289ca 2004-04-06 devnull #include <u.h>
 2 7cf289ca 2004-04-06 devnull #include <libc.h>
 3 7cf289ca 2004-04-06 devnull #include <draw.h>
 4 7cf289ca 2004-04-06 devnull #include <html.h>
 5 7cf289ca 2004-04-06 devnull #include "impl.h"
 6 7cf289ca 2004-04-06 devnull 
 7 cbeb0b26 2006-04-01 devnull /* Do case-insensitive lookup of key[0:keylen] in t[0:n] (key part), */
 8 cbeb0b26 2006-04-01 devnull /* returning 1 if found, 0 if not. */
 9 cbeb0b26 2006-04-01 devnull /* Array t must be sorted in increasing lexicographic order of key. */
10 cbeb0b26 2006-04-01 devnull /* If found, return corresponding val in *pans. */
11 7cf289ca 2004-04-06 devnull int
12 7cf289ca 2004-04-06 devnull _lookup(StringInt* t, int n, Rune* key, int keylen, int* pans)
13 7cf289ca 2004-04-06 devnull {
14 7cf289ca 2004-04-06 devnull 	int	min;
15 7cf289ca 2004-04-06 devnull 	int	max;
16 7cf289ca 2004-04-06 devnull 	int	try;
17 7cf289ca 2004-04-06 devnull 	int	cmpresult;
18 7cf289ca 2004-04-06 devnull 
19 7cf289ca 2004-04-06 devnull 	min = 0;
20 7cf289ca 2004-04-06 devnull 	max = n - 1;
21 7cf289ca 2004-04-06 devnull 	while(min <= max) {
22 7cf289ca 2004-04-06 devnull 		try = (min + max)/2;
23 7cf289ca 2004-04-06 devnull 		cmpresult = _Strncmpci(key, keylen, t[try].key);
24 7cf289ca 2004-04-06 devnull 		if(cmpresult > 0)
25 7cf289ca 2004-04-06 devnull 			min = try + 1;
26 7cf289ca 2004-04-06 devnull 		else if(cmpresult < 0)
27 7cf289ca 2004-04-06 devnull 			max = try - 1;
28 7cf289ca 2004-04-06 devnull 		else {
29 7cf289ca 2004-04-06 devnull 			*pans = t[try].val;
30 7cf289ca 2004-04-06 devnull 			return 1;
31 7cf289ca 2004-04-06 devnull 		}
32 7cf289ca 2004-04-06 devnull 	}
33 7cf289ca 2004-04-06 devnull 	return 0;
34 7cf289ca 2004-04-06 devnull }
35 7cf289ca 2004-04-06 devnull 
36 cbeb0b26 2006-04-01 devnull /* Return first key in t[0:n] that corresponds to val, */
37 cbeb0b26 2006-04-01 devnull /* nil if none. */
38 7cf289ca 2004-04-06 devnull Rune*
39 7cf289ca 2004-04-06 devnull _revlookup(StringInt* t, int n, int val)
40 7cf289ca 2004-04-06 devnull {
41 7cf289ca 2004-04-06 devnull 	int	i;
42 7cf289ca 2004-04-06 devnull 
43 7cf289ca 2004-04-06 devnull 	for(i = 0; i < n; i++)
44 7cf289ca 2004-04-06 devnull 		if(t[i].val == val)
45 7cf289ca 2004-04-06 devnull 			return t[i].key;
46 7cf289ca 2004-04-06 devnull 	return nil;
47 7cf289ca 2004-04-06 devnull }
48 7cf289ca 2004-04-06 devnull 
49 cbeb0b26 2006-04-01 devnull /* Make a StringInt table out of a[0:n], mapping each string */
50 cbeb0b26 2006-04-01 devnull /* to its index.  Check that entries are in alphabetical order. */
51 7cf289ca 2004-04-06 devnull StringInt*
52 7cf289ca 2004-04-06 devnull _makestrinttab(Rune** a, int n)
53 7cf289ca 2004-04-06 devnull {
54 7cf289ca 2004-04-06 devnull 	StringInt*	ans;
55 7cf289ca 2004-04-06 devnull 	int	i;
56 7cf289ca 2004-04-06 devnull 
57 7cf289ca 2004-04-06 devnull 	ans = (StringInt*)emalloc(n * sizeof(StringInt));
58 7cf289ca 2004-04-06 devnull 	for(i = 0; i < n; i++) {
59 7cf289ca 2004-04-06 devnull 		ans[i].key = a[i];
60 7cf289ca 2004-04-06 devnull 		ans[i].val = i;
61 7cf289ca 2004-04-06 devnull 		assert(i == 0 || runestrcmp(a[i], a[i - 1]) >= 0);
62 7cf289ca 2004-04-06 devnull 	}
63 7cf289ca 2004-04-06 devnull 	return ans;
64 7cf289ca 2004-04-06 devnull }