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