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