iset.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "post.h"
   4
   5 #define ALIGN(n, a)     (((n) + (a) - 1) & ~((a) - 1))
   6 #define CNTMIN          (1 << 10)
   7 #define CNTMAX          (1 << 20)
   8
   9 /* iset structure to map integers to sets */
  10 struct iset {
  11         int **set;
  12         int *sz;
  13         int *len;
  14         int cnt;
  15 };
  16
  17 static void iset_extend(struct iset *iset, int cnt)
  18 {
  19         iset->set = mextend(iset->set, iset->cnt, cnt, sizeof(iset->set[0]));
  20         iset->sz = mextend(iset->sz, iset->cnt, cnt, sizeof(iset->sz[0]));
  21         iset->len = mextend(iset->len, iset->cnt, cnt, sizeof(iset->len[0]));
  22         iset->cnt = cnt;
  23 }
  24
  25 struct iset *iset_make(void)
  26 {
  27         struct iset *iset = malloc(sizeof(*iset));
  28         memset(iset, 0, sizeof(*iset));
  29         iset_extend(iset, CNTMIN);
  30         return iset;
  31 }
  32
  33 void iset_free(struct iset *iset)
  34 {
  35         int i;
  36         for (i = 0; i < iset->cnt; i++)
  37                 free(iset->set[i]);
  38         free(iset->set);
  39         free(iset->len);
  40         free(iset->sz);
  41         free(iset);
  42 }
  43
  44 int *iset_get(struct iset *iset, int key)
  45 {
  46         return key >= 0 && key < iset->cnt ? iset->set[key] : NULL;
  47 }
  48
  49 int iset_len(struct iset *iset, int key)
  50 {
  51         return key >= 0 && key < iset->cnt ? iset->len[key] : 0;
  52 }
  53
  54 void iset_put(struct iset *iset, int key, int ent)
  55 {
  56         if (key < 0 || key >= CNTMAX)
  57                 return;
  58         if (key >= iset->cnt)
  59                 iset_extend(iset, ALIGN(key + 1, CNTMIN));
  60         if (key >= 0 && key < iset->cnt && iset->len[key] + 1 >= iset->sz[key]) {
  61                 int olen = iset->sz[key];
  62                 int nlen = iset->sz[key] * 2 + 8;
  63                 void *nset = malloc(nlen * sizeof(iset->set[key][0]));
  64                 if (iset->set[key]) {
  65                         memcpy(nset, iset->set[key],
  66                                 olen * sizeof(iset->set[key][0]));
  67                         free(iset->set[key]);
  68                 }
  69                 iset->sz[key] = nlen;
  70                 iset->set[key] = nset;
  71         }
  72         iset->set[key][iset->len[key]++] = ent;
  73         iset->set[key][iset->len[key]] = -1;
  74 }