sys/src/libhtml/strinttab.c

   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