X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=chiark-tcl.git;a=blobdiff_plain;f=maskmap%2Fmaskmap.c;h=7e6bcf04f4c961518c39c8412aec14fd90d9d51f;hp=f51dba4b19cf587690b170174a9c933dd36b6150;hb=bf917064c5edc75fdd84371f53e7cef51ff05510;hpb=79afa3a523e92a1d552d46729b1e1d04db97f72c

diff --git a/maskmap/maskmap.c b/maskmap/maskmap.c
index f51dba4..7e6bcf0 100644
--- a/maskmap/maskmap.c
+++ b/maskmap/maskmap.c
@@ -13,7 +13,7 @@ typedef struct {
 } MaskMap_Entry;
 
 struct MaskMap_Value {
-  int allocd;
+  int used, space;
   MaskMap_Entry *entries;
 }; /* overlays internalRep */
 
@@ -36,6 +36,24 @@ static void mme_free(MaskMap_Entry *mme) {
   if (mme->data) { Tcl_DecrRefCount(mme->data); mme->data=0; }
 }
 
+static unsigned mme_clear_unwanted(MaskMap_Entry *mme, int bytes) {
+  /* returns non-0 iff some bits were cleared */
+  int sparebits;
+  unsigned result, sparemask;
+  Byte *datap;
+
+  sparebits= bytes * 8 - mme->prefixlen;
+  if (!sparebits) return 0;
+
+  sparemask= (1u << sparebits) - 1;
+  datap= &mme->prefix[bytes-1];
+
+  result= *datap & sparemask;
+  *datap &= ~sparemask;
+
+  return result;
+}
+
 static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
 			Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
 			int inmap) {
@@ -43,7 +61,7 @@ static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
   * - on errors, it will be blank.  inmap is 1 if we're parsing an existing
   * map or 0 if it's an entry to be added or modified. */
   HBytes_Value prefix;
-  int suppliedprefixbytes, prefixbits, wantprefixbytes, sparebits;
+  int suppliedprefixbytes, prefixbits, wantprefixbytes;
   const Byte *data;
   int rc;
 
@@ -65,17 +83,17 @@ static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
 		  "HBYTES MASKMAP SYNTAX OVERRUN");
     goto x_rc;
   }
-  sparebits= wantprefixbytes*8 - prefixbits;
-  data= hbytes_data(&prefix);
-  if (sparebits && (data[wantprefixbytes-1] & ((1u << sparebits)-1))) {
+
+  mme->prefixlen= prefixbits;
+  mme->prefix= TALLOC(wantprefixbytes);  assert(mme->prefix);
+  memcpy(mme->prefix, data, wantprefixbytes);
+
+  if (mme_clear_unwanted(mme, wantprefixbytes)) {
     rc= staticerr(ip, "mask-map entry PREFIX contains bits excluded"
 		  " by PREFIX-LEN", "HBYTES MASKMAP SYNTAX EXCLBITS");
     goto x_rc;
   }
 
-  mme->prefixlen= prefixbits;
-  mme->prefix= TALLOC(wantprefixbytes);  assert(mme->prefix);
-  memcpy(mme->prefix, data, wantprefixbytes);
   return TCL_OK;
 
  x_rc:
@@ -83,132 +101,315 @@ static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
   return rc;
 }
 
-static int mme_ordercompare(MaskMap_Entry *a, MaskMap_Entry *b) {
-  if (a->prefixlen != b->prefixlen)
-    return a->prefixlen - b->prefixlen;
-  else
-    return memcmp(b->prefix, a->prefix, prefix_bytes(a->prefixlen));
+static int mme_contains(const MaskMap_Entry *ref, const Byte *addr, int len) {
+  int directbytes, leftoverbits;
+  
+  assert(len >= ref->prefixlen);
+  
+  directbytes= ref->prefixlen / 8;
+  if (memcmp(ref->prefix, addr, directbytes)) return 0;
+
+  leftoverbits= ref->prefixlen % 8;
+  if (leftoverbits)
+    if ((addr[directbytes] & (0xffu << leftoverbits))
+	!= search->prefix[directbytes])
+      return 0;
+
+  return 1;
+}  
+
+static int mme_compare(const MaskMap_Entry *a, const MaskMap_Entry *b) {
+  /*    +2 =    a   covers later range of address space than  b
+   *    +1 =    a   wholly contains but is not equal to       b
+   *     0 =    a   is identical to                           b
+   *    -1 =    b   wholly contains but is not equal to       a
+   *    -2 =    b   covers later range of address space than  a
+   */
+  int al= a->prefixlen;
+  int bl= b->prefixlen;
+  int ml, d;
+
+  if (al==bl) { ml=al; }
+  else if (al<bl) { ml=al; if (mme_contains(a,b->prefix,bl)) return +1; }
+  else if (bl<al) { ml=bl; if (mme_contains(b,a->prefix,al)) return -1; }
+
+  d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
+  return (d > 0 ? +2 :
+	  d < 0 ? -2 :
+	  0);
 }
 
-/*---------- useful operations on MaskMap_Value etc. ----------*/
+/*---------- searching maps ----------*/
 
-static int mm_count(const MaskMap_Value *mm) {
-  int i;
-  for (i=0; i<mm->allocd && mm->entries[i].prefixlen != -1; i++);
-  return i;
+typedef enum {
+  sr_notfound,
+  sr_exact,
+  sr_inbig,
+  sr_aroundsmall
+} Search_Result;
+
+static int
+mm_binarychop(MaskMap_Value *mm, int low_oreq, int high_strict, void *u,
+	      int (*test)(MaskMap_Entry *mm, void *u) /* -ve => look left */,
+	      int *found_r) {
+  int mid, cmp;
+  
+  for (;;) {
+    if (high_strict <= low_oreq) {
+      assert(high_strict == low_oreq);
+      *found_r= 0;
+      return high_strict;
+    }
+
+    mid= (high_strict + low_oreq) / 2;
+    cmp= test(&mm->entries[mid], u);
+
+    if (!cmp) {
+      *found_r= 1;
+      return mid;
+    }
+
+    if (cmp < 0)
+      high_strict= mid;
+    else
+      low_oreq= mid+1;
+  }
 }
 
+struct mm_search_u {
+  int forbid_aroundsmall;
+  MaskMap_Entry proposed;
+  Search_Result sr;
+};
+
+static int
+mm_search_binchoptest(MaskMap_Entry *mme, void *u_v) {
+  struct mm_search_u *u= u_v;
+  int cmp;
+
+  cmp= mme_compare(&u.proposed, mme);
+  switch (cmp) {
+  case -1:  u->sr= sr_inbig;        return  0;
+  case  0:  u->sr= sr_exact;        return  0;
+  case +1:  u->sr= sr_aroundsmall;  return  0;
+  default:                          return cmp;
+  }
+}
+
+static Search_Result
+mm_search(MaskMap_Value *mm, const MaskMap_Entry *proposed, int *place_r) {
+  int place, found;
+  struct mm_search_u u;
+
+  u.forbid_aroundsmall= forbid_aroundsmall;
+  u.proposed= proposed;
+  u.sr= sr_notfound;
+
+  *place_r= mm_binarychop(mm, 0, mm.used, &u, mm_search_binchoptest, &found);
+
+  assert(!!found == (u.sr != sr_notfound));
+  return u.sr;
+}
+
+/*---------- useful operations on MaskMap_Value etc. ----------*/
+
 static void mm_init(MaskMap_Value *mm) {
-  mm->allocd= 0;
+  mm->used= 0;
+  mm->space= 0;
   mm->entries= 0;
 }
 
 static void mm_reallocentries(MaskMap_Value *mm, int len) {
-  int i;
-  MaskMap_Entry *newentries, *clear;
+  MaskMap_Entry *newentries;
 
-  assert(len >= mm->allocd);
+  assert(len >= mm->space);
   if (!len) return;
 
   newentries= TREALLOC(mm->entries, sizeof(*newentries)*len);
   assert(newentries);
   
-  for (i=mm->allocd, clear=newentries+mm->allocd;
-       i < len;
-       i++, clear++)
-    mme_init(clear);
-
-  mm->allocd= len;
+  mm->space= len;
   mm->entries= newentries;
 }
-  
-/*---------- substantial operations on mask maps ----------*/
+
+/*---------- amendment (complex algorithm) ----------*/
+
+struct mm_amend_aroundsmall_u {
+  MaskMap_Entry *new;
+  int sign;
+};
+
+
+static int
+mm_amend_aroundsmall_binchoptest(MaskMap_Entry *search, void *u_v) {
+  struct mm_amend_aroundsmall_u *u= u_v;
+
+  cmp= u->sign * mme_compare(search, u->new);
+
+  switch (cmp) {
+  case +2:  return -u->sign;
+  case +1:  return +u->sign;
+  default:  abort();
+  }
+}
 
 int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
 		     MaskMap_Var map, Tcl_Obj *prefix,
 		     Tcl_Obj *preflen, Tcl_Obj *data) {
   MaskMap_Value *mm= map.mm;
-  MaskMap_Entry mme, *search;
-  int rc, insertat, findend, cmp;
+  MaskMap_Entry new, *fragment;
+  MaskMap_Entry *breaking, *replacements;
+  int rc, insertat, findend, cmp, nreplacements, new_used;
+  struct mm_amend_aroundsmall_u u;
 
-  mme_init(&mme);
+  mme_init(&new);
   
-  rc= mme_parsekey(ip,&mme,prefix,preflen,0);  if (rc) goto x_rc;
-
-  for (insertat=0, search=mm->entries;
-       insertat < mm->allocd &&
-	 search->prefixlen != -1;
-       insertat++, search++) {
-    cmp= mme_ordercompare(&mme,search);
-    if (!cmp) {
-      mme_free(&mme);
-      Tcl_DecrRefCount(search->data);
-      goto put_here;
+  rc= mme_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
+
+  sr= mm_search(mm, &new, &searched);
+
+  replacements= &new;
+  nreplacements= 1;
+  replace_start= searched;
+  replace_end= searched;
+
+  switch (sr) {
+
+  case sr_notfound:
+    break;
+
+  case sr_exact:
+    replace_end= searched+1;
+    break;
+
+  case sr_aroundsmall:
+    u.mme= new;
+    u.sign= -1;
+    replace_start= mm_binarychop(mm, 0, searched, &u,
+				 mm_amend_aroundsmall_binchoptest, &dummy);
+    u.sign= +1;
+    replace_end= mm_binarychop(mm, searched+1, mm.used, &u,
+				 mm_amend_aroundsmall_binchoptest, &dummy);
+    break;
+
+  case sr_inbig:
+    /* Urgh, we need to break it up.  This produces
+     *   - innermost prefix (the new one) as specified
+     *   - one for each bitlength
+     *       <= innermost
+     *        > outermost (the existing one)
+     *     each one specifying the outermost prefix plus zero, one,
+     *     two, etc. bits of the innermost followed by one bit
+     *     opposite to the innermost, with the outermost's data
+     * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B
+     * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ...
+     * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
+     */
+
+    breaking= &mm.entries[searched];
+    nreplacements= new.prefix - breaking->prefixlen + 1;
+    replacements= TALLOC(sizeof(*replacements) * nreplacements);
+
+    for (fragmentlen= breaking->prefixlen + 1,
+	   left_insert= 0, right_insert= nreplacements;
+	 fragmentlen <= new.prefix;
+	 fragmentlen++) {
+      int fragmentbytes;
+
+      fragmentbytes= prefix_bytes(fragmentlen)
+      fragment->prefixlen= fragmentlen;
+      fragment->prefix= TALLOC(fragmentbytes);
+      memcpy(fragment->prefix, new.prefix, fragmentbytes);
+      mme_clear_unwanted(fragment, fragmentbytes);
+
+      fragment->prefix[fragmentbytes] ^=
+	0x80u >> ((fragmentlen+7) & 7);
+
+      switch (mme_compare(&fragment, &new)) {
+      case -2:  replacements[left_insert++]=  fragment;  break;
+      case +2:  replacements[--right_insert]= fragment;  break;
+      default: abort();
+      }
     }
-    if (cmp>0)
-      /* the new one sorts later, insert it here */
-      break;
+    assert(left_insert == right_insert-1);
+    replacements[left_insert]= new;
+    mme_init(&new);
+
+    replace_end= searched+1;
+    break;
+
   }
 
-  /* we're adding an entry, make room for it */
-  findend= mm_count(mm);
-  if (findend == mm->allocd) {
-    mm_reallocentries(mm, mm->allocd*2 + 1);
-    search= mm->entries + insertat;
+  new_used= mm.used - (replace_end - replace_start) + nreplacements;
+
+  if (new_used > mm.space)
+    mm_reallocentries(mm, new_used * 2);
+
+  for (scan=replacements, i=0;
+       i < nreplacements;
+       scan++, i++) {
+    scan->data= data;
+    Tcl_IncrRefCount(scan->data);
   }
-  if (findend > insertat)
-    memmove(search + 1, search, sizeof(*search) * (findend - insertat));
-  *search= mme;
 
- put_here:
-  Tcl_IncrRefCount(data);
-  search->data= data;
-  return TCL_OK;
+  for (i= replace_start, scan= mm.entries+i;
+       i < replace_end;
+       i++, scan++) {
+    mme_free(scan);
+  }
 
- x_rc:
-  mme_free(&mme);
-  return rc;
+  memmove(mm.entries + replace_start + nreplacements,
+	  mm.entries + replace_end,
+	  sizeof(*mm.entries) * (mm.used - replace_end));
+
+  memcpy(mm.entries + replace_start,
+	 replacements,
+	 sizeof(*mm.entries) * nreplacements);
+
+  mm.used= new_used;
+  if (replacements != &new)
+    /* we don't bother freeing the actual array elements because
+     * if replacements!=&new the array is only full if we're
+     * committed and have already copied the values into the actual
+     * MaskMap_Value. */
+    TFREE(replacements);
+
+  return TCL_OK;
 }
 
+/*---------- other substantial operations on mask maps ----------*/
+
 int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip,
 		      Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
 		      Tcl_Obj **result) {
   MaskMap_Value *mm= (void*)&mapo->internalRep;
-  MaskMap_Entry *search;
   const Byte *addr= hbytes_data(&addrhb);
   int addrbytes= hbytes_len(&addrhb);
-  int i, directbytes, leftoverbits;
+  int i, addrbits, place;
+  Search_Result sr;
+
+  addrbits= addrbytes * 8;
+  sr= mm_search(mm, addr, addrbits, &place);
+
+  switch (sr) {
 
-  search= mm->entries;
-  if (!search || search->prefixlen==-1) goto not_found;
+  case sr_notfound:
+    if (!def) return staticerr(ip, "address not found in mask-map",
+			       "HBYTES MASKMAP NOMATCH");
+    *result= def;
+    break;
 
-  /* longest masks are first, so we can test this once */
-  if (addrbytes < prefix_bytes(search->prefixlen))
-    return staticerr(ip, "address shorter than mask(s) in map",
+  case sr_aroundsmall:
+    return staticerr(ip, "address shorter than mask in map",
 		     "HBYTES MASKMAP UNDERRUN");
 
-  for (i=0;
-       i < mm->allocd && search->prefixlen != -1;
-       i++, search++) {
-    directbytes= search->prefixlen / 8;
-    if (memcmp(search->prefix, addr, directbytes)) continue;
-
-    leftoverbits= search->prefixlen % 8;
-    if (leftoverbits)
-      if ((addr[directbytes] & (0xffu << leftoverbits))
-	  != search->prefix[directbytes])
-	continue;
-
-    /*found*/
-    *result= search->data;
-    return TCL_OK;
+  case sr_exact:
+  case sr_inbig:
+    *result= mm.entres[place].data;
+    break;
+    
   }
 
- not_found:
-  if (!def)
-    return staticerr(ip, "address not found in mask-map",
-		     "HBYTES MASKMAP NOMATCH");
-  *result= def;
   return TCL_OK;
 }
 
@@ -226,7 +427,7 @@ static void maskmap_t_free(Tcl_Obj *o) {
   MaskMap_Entry *mme;
   int i;
   
-  for (i=0, mme=mm->entries; i<mm->allocd; i++, mme++) {
+  for (i=0, mme=mm->entries; i<mm->used; i++, mme++) {
     if (mme->prefixlen==-1) break;
     mme_free(mme);
   }
@@ -236,16 +437,16 @@ static void maskmap_t_dup(Tcl_Obj *sob, Tcl_Obj *dob) {
   MaskMap_Value *sm= (void*)&sob->internalRep;
   MaskMap_Value *dm= (void*)&dob->internalRep;
   MaskMap_Entry *sme, *dme;
-  int l, i, nbytes;
+  int i, nbytes;
 
   assert(sob->typePtr == &maskmap_type);
   objfreeir(dob);
-  l= mm_count(sm);
 
   mm_init(dm);
-  mm_reallocentries(dm,l);
+  mm_reallocentries(dm,sm->used);
+  dm->used= sm->used;
   for (i=0, sme=sm->entries, dme=dm->entries;
-       i<dm->allocd;
+       i < dm->used;
        i++, sme++, dme++) {
     *dme= *sme;
     nbytes= prefix_bytes(sme->prefixlen);
@@ -259,13 +460,12 @@ static void maskmap_t_dup(Tcl_Obj *sob, Tcl_Obj *dob) {
 static void maskmap_t_ustr(Tcl_Obj *so) {
   MaskMap_Value *sm= (void*)&so->internalRep;
   Tcl_Obj **mainlobjsl, *mainobj;
-  int i, l;
+  int i;
 
   assert(so->typePtr == &maskmap_type);
-  l= mm_count(sm);
-  mainlobjsl= TALLOC(sizeof(*mainlobjsl) * l);  assert(mainlobjsl);
+  mainlobjsl= TALLOC(sizeof(*mainlobjsl) * sm->used);  assert(mainlobjsl);
 
-  for (i=0; i<l; i++) {
+  for (i=0; i<sm->used; i++) {
     MaskMap_Entry *sme= &sm->entries[i];
     HBytes_Value hb;
     Tcl_Obj *subl[3], *sublo;
@@ -279,7 +479,7 @@ static void maskmap_t_ustr(Tcl_Obj *so) {
     mainlobjsl[i]= sublo;
   }
 
-  mainobj= Tcl_NewListObj(l,mainlobjsl);  assert(mainobj);
+  mainobj= Tcl_NewListObj(sm->used,mainlobjsl);  assert(mainobj);
   so->bytes= Tcl_GetStringFromObj(mainobj, &so->length);  assert(so->bytes);
   mainobj->bytes= 0; mainobj->length= 0; /* we stole it */
 }
@@ -287,6 +487,7 @@ static void maskmap_t_ustr(Tcl_Obj *so) {
 static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
   int rc, len, eol, i;
   MaskMap_Value mm;
+  MaskMap_Entry *mme;
   Tcl_Obj *eo, *prefixo, *prefixleno;
 
   mm_init(&mm);
@@ -294,7 +495,7 @@ static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
   rc= Tcl_ListObjLength(ip,o,&len);  if (rc) goto x_rc;
   mm_reallocentries(&mm, len);
   
-  for (i=0; i<len; i++) {
+  for (i=0, mme=mm.entries; i < len; i++, mme++) {
     rc= Tcl_ListObjIndex(ip,o,i,&eo);  if (rc) goto x_rc;
     rc= Tcl_ListObjLength(ip,eo,&eol);  if (rc) goto x_rc;
     if (eol != 3) {
@@ -307,11 +508,13 @@ static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
     rc= Tcl_ListObjIndex(ip,eo,2,&mm.entries[i].data);  if (rc) goto x_rc;
     Tcl_IncrRefCount(mm.entries[i].data);
 
-    rc= mme_parsekey(ip, &mm.entries[i], prefixo, prefixleno, 1);
+    rc= mme_parsekey(ip, mme, prefixo, prefixleno, 1);
     if (rc) goto x_rc;
 
+    mm->used++;
+
     if (i>0) {
-      if (mme_ordercompare(&mm.entries[i-1], &mm.entries[i]) <= 0) {
+      if (mme_ordercompare(mme-1, mme) <= 0) {
 	rc= staticerr(ip, "mask-map entries out of order",
 		      "HBYTES MASKMAP SYNTAX ORDER");
 	goto x_rc;
@@ -327,11 +530,9 @@ static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
   return TCL_OK;
 
 x_rc:
-  if (mm.entries) {
-    for (i=0; i<len; i++)
-      mme_free(&mm.entries[i]);
-    TFREE(mm.entries);
-  }
+  for (mme=mm.entries, i=0; i<mm.used; i++, mme++)
+    mme_free(mme);
+  TFREE(mm.entries);
   return rc;
 }