chiark - git - mdw - fastforward/blob - strset.c

   1 #include "strset.h"
   2 #include "str.h"
   3 #include "byte.h"
   4
   5 uint32 strset_hash(s)
   6 char *s;
   7 {
   8  unsigned char ch;
   9  uint32 h;
  10  h = 5381;
  11  while (ch = *s)
  12   {
  13    h = ((h << 5) + h) ^ ch;
  14    ++s;
  15   }
  16  return h;
  17 }
  18
  19 int strset_init(set)
  20 strset *set;
  21 {
  22  int h;
  23  set->mask = 15;
  24  set->n = 0;
  25  set->a = 10;
  26
  27  set->first = (int *) alloc(sizeof(int) * (set->mask + 1));
  28  if (!set->first) return 0;
  29  set->p = (strset_list *) alloc(sizeof(strset_list) * set->a);
  30  if (!set->p) { alloc_free(set->first); return 0; }
  31  set->x = (char **) alloc(sizeof(char *) * set->a);
  32  if (!set->x) { alloc_free(set->p); alloc_free(set->first); return 0; }
  33
  34  for (h = 0;h <= set->mask;++h) set->first[h] = -1;
  35
  36  return 1;
  37 }
  38
  39 char *strset_in(set,s)
  40 strset *set;
  41 char *s;
  42 {
  43  uint32 h;
  44  strset_list *sl;
  45  int i;
  46  char *xi;
  47
  48  h = strset_hash(s);
  49  i = set->first[h & set->mask];
  50  while (i >= 0)
  51   {
  52    sl = set->p + i;
  53    if (sl->h == h)
  54     {
  55      xi = set->x[i];
  56      if (!str_diff(xi,s)) return xi;
  57     }
  58    i = sl->next;
  59   }
  60  return 0;
  61 }
  62
  63 int strset_add(set,s)
  64 strset *set;
  65 char *s;
  66 {
  67  uint32 h;
  68  int n;
  69  strset_list *sl;
  70
  71  n = set->n;
  72
  73  if (n == set->a)
  74   {
  75    int newa;
  76    strset_list *newp;
  77    char **newx;
  78
  79    newa = n + 10 + (n >> 3);
  80    newp = (strset_list *) alloc(sizeof(strset_list) * newa);
  81    if (!newp) return 0;
  82    newx = (char **) alloc(sizeof(char *) * newa);
  83    if (!newx) { alloc_free(newp); return 0; }
  84
  85    byte_copy(newp,sizeof(strset_list) * n,set->p);
  86    byte_copy(newx,sizeof(char *) * n,set->x);
  87    alloc_free(set->p);
  88    alloc_free(set->x);
  89    set->p = newp;
  90    set->x = newx;
  91    set->a = newa;
  92
  93    if (n + n + n > set->mask)
  94     {
  95      int newmask;
  96      int *newfirst;
  97      int i;
  98      uint32 h;
  99
 100      newmask = set->mask + set->mask + 1;
 101      newfirst = (int *) alloc(sizeof(int) * (newmask + 1));
 102      if (!newfirst) return 0;
 103
 104      for (h = 0;h <= newmask;++h) newfirst[h] = -1;
 105
 106      for (i = 0;i < n;++i)
 107       {
 108        sl = set->p + i;
 109        h = sl->h & newmask;
 110        sl->next = newfirst[h];
 111        newfirst[h] = i;
 112       }
 113
 114      alloc_free(set->first);
 115      set->first = newfirst;
 116      set->mask = newmask;
 117     }
 118   }
 119
 120  h = strset_hash(s);
 121
 122  sl = set->p + n;
 123  sl->h = h;
 124  h &= set->mask;
 125  sl->next = set->first[h];
 126  set->first[h] = n;
 127  set->x[n] = s;
 128  set->n = n + 1;
 129  return 1;
 130 }