maskmap/maskmap.c

   1 /*
   2  */
   3
   4 #include <string.h>
   5
   6 #include "tables.h"
   7 #include "hbytes.h"
   8
   9 typedef struct {
  10   int prefixlen; /* there may be some empty slots with prefixlen==-1 at end */
  11   Byte *prefix; /* ceil(prefixlen/8) bytes */
  12   Tcl_Obj *data;
  13 } MaskMap_Entry;
  14
  15 struct MaskMap_Value {
  16   int allocd;
  17   MaskMap_Entry *entries;
  18 }; /* overlays internalRep */
  19
  20 /*---------- useful stuff ----------*/
  21
  22 static int prefix_bytes (int prefixlen) {
  23   return (prefixlen + 7)/8;
  24 }
  25
  26 /*---------- operations on MaskMap_Entry ----------*/
  27
  28 static void mme_init(MaskMap_Entry *mme) {
  29   mme->prefix= 0;
  30   mme->data= 0;
  31 }
  32
  33 static void mme_free(MaskMap_Entry *mme) {
  34   TFREE(mme->prefix);  mme->prefix=0;
  35   if (mme->data) { Tcl_DecrRefCount(mme->data); mme->data=0; }
  36 }
  37
  38 static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
  39                         Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
  40                         int inmap) {
  41  /* *mme should be blank entry; after exit (even error exit) it will be valid
  42   * - on errors, it will be blank.  inmap is 1 if we're parsing an existing
  43   * map or 0 if it's an entry to be added or modified. */
  44   HBytes_Value prefix;
  45   int suppliedprefixbytes, prefixbits, wantprefixbytes, sparebits;
  46   const Byte *data;
  47   int rc;
  48
  49   hbytes_empty(&prefix);
  50
  51   rc= pat_hb(ip,prefixo,&prefix);  if (rc) goto x_rc;
  52   rc= pat_int(ip,prefixbitso,&prefixbits);  if (rc) goto x_rc;
  53
  54   wantprefixbytes= prefix_bytes(prefixbits);
  55   suppliedprefixbytes= hbytes_len(&prefix);
  56
  57   if (suppliedprefixbytes < wantprefixbytes) {
  58     rc= staticerr(ip, "mask-map entry PREFIX too short for PREFIX-LEN",
  59                   "HBYTES MASKMAP SYNTAX UNDERRUN");
  60     goto x_rc;
  61   }
  62   if (inmap && suppliedprefixbytes > wantprefixbytes) {
  63     rc= staticerr(ip, "mask-map existing entry PREFIX too long for PREFIX-LEN",
  64                   "HBYTES MASKMAP SYNTAX OVERRUN");
  65     goto x_rc;
  66   }
  67   sparebits= wantprefixbytes*8 - prefixbits;
  68   data= hbytes_data(&prefix);
  69   if (sparebits && (data[wantprefixbytes-1] & ((1u << sparebits)-1))) {
  70     rc= staticerr(ip, "mask-map entry PREFIX contains bits excluded"
  71                   " by PREFIX-LEN", "HBYTES MASKMAP SYNTAX EXCLBITS");
  72     goto x_rc;
  73   }
  74
  75   mme->prefixlen= prefixbits;
  76   mme->prefix= TALLOC(wantprefixbytes);  assert(mme->prefix);
  77   memcpy(mme->prefix, data, wantprefixbytes);
  78   return TCL_OK;
  79
  80  x_rc:
  81   mme_free(mme);
  82   return rc;
  83 }
  84
  85 static int mme_ordercompare(MaskMap_Entry *a, MaskMap_Entry *b) {
  86   if (a->prefixlen != b->prefixlen)
  87     return a->prefixlen - b->prefixlen;
  88   else
  89     return memcmp(b->prefix, a->prefix, prefix_bytes(a->prefixlen));
  90 }
  91
  92 /*---------- useful operations on MaskMap_Value etc. ----------*/
  93
  94 static int mm_count(const MaskMap_Value *mm) {
  95   int i;
  96   for (i=0; i<mm->allocd && mm->entries[i].prefixlen != -1; i++);
  97   return i;
  98 }
  99
 100 static void mm_init(MaskMap_Value *mm) {
 101   mm->allocd= 0;
 102   mm->entries= 0;
 103 }
 104
 105 static void mm_reallocentries(MaskMap_Value *mm, int len) {
 106   int i;
 107   MaskMap_Entry *newentries, *clear;
 108
 109   newentries= TREALLOC(mm->entries, sizeof(*newentries)*len);
 110   assert(!len || newentries);
 111
 112   for (i=mm->allocd, clear=&mm->entries[mm->allocd];
 113        i < len;
 114        i++, clear++)
 115     mme_init(clear);
 116
 117   mm->allocd= len;
 118   mm->entries= newentries;
 119 }
 120
 121 /*---------- substantial operations on mask maps ----------*/
 122
 123 int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
 124                      MaskMap_Var map, Tcl_Obj *prefix,
 125                      Tcl_Obj *preflen, Tcl_Obj *data) {
 126   MaskMap_Value *mm= map.mm;
 127   MaskMap_Entry mme, *search;
 128   int rc, insertat, findend, cmp;
 129
 130   mme_init(&mme);
 131
 132   rc= mme_parsekey(ip,&mme,prefix,preflen,0);  if (rc) goto x_rc;
 133
 134   for (insertat=0, search=mm->entries;
 135        insertat < mm->allocd &&
 136          search->prefixlen != -1;
 137        insertat++, search++) {
 138     cmp= mme_ordercompare(&mme,search);
 139     if (!cmp) {
 140       mme_free(&mme);
 141       Tcl_DecrRefCount(search->data);
 142       goto put_here;
 143     }
 144     if (cmp>0)
 145       /* the new one sorts later, insert it here */
 146       break;
 147   }
 148
 149   /* we're adding an entry, make room for it */
 150   findend= mm_count(mm);
 151   if (findend == mm->allocd) mm_reallocentries(mm, mm->allocd*2 + 1);
 152   if (findend > insertat)
 153     memmove(&mm->entries[insertat+1],
 154             &mm->entries[insertat],
 155             sizeof(mm->entries[0]) * (findend - insertat));
 156   *search= mme;
 157
 158  put_here:
 159   Tcl_IncrRefCount(data);
 160   search->data= data;
 161   return TCL_OK;
 162
 163  x_rc:
 164   mme_free(&mme);
 165   return rc;
 166 }
 167
 168 int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip,
 169                       Tcl_Obj *mapo, HBytes_Value addr, Tcl_Obj *def,
 170                       Tcl_Obj **result) {
 171   /*MaskMap_Var *map= (void*)&mapo->internalRep;*/
 172   *result= Tcl_NewIntObj(42);
 173   return TCL_OK; /*fixme*/
 174 }
 175
 176 /*---------- Tcl type and arg parsing functions ----------*/
 177
 178 int pat_maskmapv(Tcl_Interp *ip, Tcl_Obj *var, MaskMap_Var *agg) {
 179   int rc;
 180   rc= pat_somethingv(ip,var,&agg->sth,&maskmap_type);  if (rc) return rc;
 181   agg->mm= (void*)&agg->sth.obj->internalRep;
 182   return TCL_OK;
 183 }
 184
 185 static void maskmap_t_free(Tcl_Obj *o) {
 186   MaskMap_Value *mm= (void*)&o->internalRep;
 187   MaskMap_Entry *mme;
 188   int i;
 189
 190   for (i=0, mme=mm->entries; i<mm->allocd; i++, mme++) {
 191     if (mme->prefixlen==-1) break;
 192     mme_free(mme);
 193   }
 194 }
 195
 196 static void maskmap_t_dup(Tcl_Obj *sob, Tcl_Obj *dob) {
 197   MaskMap_Value *sm= (void*)&sob->internalRep;
 198   MaskMap_Value *dm= (void*)&dob->internalRep;
 199   MaskMap_Entry *sme, *dme;
 200   int l, i, nbytes;
 201
 202   assert(sob->typePtr == &maskmap_type);
 203   objfreeir(dob);
 204   l= mm_count(sm);
 205
 206   mm_init(dm);
 207   mm_reallocentries(dm,l);
 208   for (i=0, sme=sm->entries, dme=dm->entries;
 209        i<dm->allocd;
 210        i++, sme++, dme++) {
 211     *dme= *sme;
 212     nbytes= prefix_bytes(sme->prefixlen);
 213     dme->prefix= TALLOC(nbytes);  assert(dme->prefix);
 214     memcpy(dme->prefix, sme->prefix, nbytes);
 215     Tcl_IncrRefCount(dme->data);
 216   }
 217   dob->typePtr= &maskmap_type;
 218 }
 219
 220 static void maskmap_t_ustr(Tcl_Obj *so) {
 221   MaskMap_Value *sm= (void*)&so->internalRep;
 222   Tcl_Obj **mainlobjsl, *mainobj;
 223   int i, l;
 224
 225   assert(so->typePtr == &maskmap_type);
 226   l= mm_count(sm);
 227   mainlobjsl= TALLOC(sizeof(*mainlobjsl) * l);  assert(mainlobjsl);
 228
 229   for (i=0; i<l; i++) {
 230     MaskMap_Entry *sme= &sm->entries[i];
 231     HBytes_Value hb;
 232     Tcl_Obj *subl[3], *sublo;
 233
 234     hbytes_array(&hb, sme->prefix, prefix_bytes(sme->prefixlen));
 235     subl[0]= ret_hb(0, hb);  assert(subl[0]);
 236     subl[1]= Tcl_NewIntObj(sme->prefixlen);  assert(subl[1]);
 237     subl[2]= sme->data;
 238
 239     sublo= Tcl_NewListObj(3,subl);  assert(sublo);
 240     mainlobjsl[i]= sublo;
 241   }
 242
 243   mainobj= Tcl_NewListObj(l,mainlobjsl);  assert(mainobj);
 244   so->bytes= Tcl_GetStringFromObj(mainobj, &so->length);  assert(so->bytes);
 245   mainobj->bytes= 0; mainobj->length= 0; /* we stole it */
 246 }
 247
 248 static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
 249   int rc, len, eol, i;
 250   MaskMap_Value mm;
 251   Tcl_Obj *eo, *prefixo, *prefixleno;
 252
 253   mm_init(&mm);
 254
 255   rc= Tcl_ListObjLength(ip,o,&len);  if (rc) goto x_rc;
 256   mm_reallocentries(&mm, len);
 257
 258   for (i=0; i<len; i++) {
 259     rc= Tcl_ListObjIndex(ip,o,i,&eo);  if (rc) goto x_rc;
 260     rc= Tcl_ListObjLength(ip,eo,&eol);  if (rc) goto x_rc;
 261     if (eol != 3) {
 262       rc= staticerr(ip, "mask-map entry length != 3",
 263                     "HBYTES MASKMAP SYNTAX LLENGTH");
 264       goto x_rc;
 265     }
 266     rc= Tcl_ListObjIndex(ip,eo,0,&prefixo);  if (rc) goto x_rc;
 267     rc= Tcl_ListObjIndex(ip,eo,1,&prefixleno);  if (rc) goto x_rc;
 268     rc= Tcl_ListObjIndex(ip,eo,2,&mm.entries[i].data);  if (rc) goto x_rc;
 269     Tcl_IncrRefCount(mm.entries[i].data);
 270
 271     rc= mme_parsekey(ip, &mm.entries[i], prefixo, prefixleno, 1);
 272     if (rc) goto x_rc;
 273
 274     if (i>0) {
 275       if (mme_ordercompare(&mm.entries[i-1], &mm.entries[i]) <= 0) {
 276         rc= staticerr(ip, "mask-map entries out of order",
 277                       "HBYTES MASKMAP SYNTAX ORDER");
 278         goto x_rc;
 279       }
 280     }
 281   }
 282
 283   /* we commit now */
 284   assert(sizeof(mm) <= sizeof(o->internalRep));
 285   objfreeir(o);
 286   memcpy(&o->internalRep, &mm, sizeof(mm));
 287   o->typePtr= &maskmap_type;
 288   return TCL_OK;
 289
 290 x_rc:
 291   if (mm.entries) {
 292     for (i=0; i<len; i++)
 293       mme_free(&mm.entries[i]);
 294     TFREE(mm.entries);
 295   }
 296   return rc;
 297 }
 298
 299 Tcl_ObjType maskmap_type = {
 300   "mask-map",
 301   maskmap_t_free, maskmap_t_dup, maskmap_t_ustr, maskmap_t_sfa
 302 };