X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=maskmap%2Fmaskmap.c;h=ea2a690b6f4f4a1e78ef92497040493d9de76518;hb=f16e3e0cf0a2b965643df01e24ef59e1393da78d;hp=99688015252641a884983c387dd33f8af8b7ba0c;hpb=20f8f9dd8dcdc4b5c68331c8015c18eaf1813360;p=chiark-tcl.git

diff --git a/maskmap/maskmap.c b/maskmap/maskmap.c
index 9968801..ea2a690 100644
--- a/maskmap/maskmap.c
+++ b/maskmap/maskmap.c
@@ -1,45 +1,373 @@
 /*
  */
 
-#include "tables.h"
-#include "hbytes.h"
+#include "chiark_tcl_hbytes.h"
 
-typedef struct {
-  int prefixlen; /* there may be some empty slots with prefixlen==-1 at end */
-  Byte *prefix; /* ceil(prefixlen/8) bytes */
-  Tcl_Obj *data;
-} MaskMap_Entry;
+/*---------- operations on AddrMap_Entry ----------*/
 
-struct MaskMap_Value {
-  int allocd;
-  MaskMap_Entry *entries;
-}; /* overlays internalRep */
+static void ame_init(AddrMap_Entry *ame) {
+  ame->prefixlen= -1;
+  ame->prefix= 0;
+  ame->data= 0;
+}
+
+static unsigned ame_clear_unwanted(AddrMap_Entry *ame, int bytes) {
+  /* returns non-0 iff some bits were cleared */
+  int sparebits;
+  unsigned result, sparemask;
+  Byte *datap;
+
+  sparebits= bytes * 8 - ame->prefixlen;
+  if (!sparebits) return 0;
+
+  sparemask= (1u << sparebits) - 1;
+  datap= &ame->prefix[bytes-1];
+
+  result= *datap & sparemask;
+  *datap &= ~sparemask;
 
-int pat_maskmapv(Tcl_Interp *ip, Tcl_Obj *var, MaskMap_Var *agg) {
+  return result;
+}
+
+static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame,
+			Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
+			int inmap) {
+ /* *ame should be blank entry; after exit (even error exit) it will be valid
+  * - 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;
+  const Byte *data;
   int rc;
-  rc= pat_somethingv(ip,var,&agg->sth,&maskmap_type);  if (rc) return rc;
-  agg->mm= (void*)&agg->sth.obj->internalRep;
+
+  hbytes_empty(&prefix);
+  
+  rc= pat_hb(ip,prefixo,&prefix);  if (rc) goto x_rc;
+  rc= pat_int(ip,prefixbitso,&prefixbits);  if (rc) goto x_rc;
+
+  wantprefixbytes= prefix_bytes(prefixbits);
+  suppliedprefixbytes= hbytes_len(&prefix);
+
+  if (suppliedprefixbytes < wantprefixbytes) {
+    rc= staticerr(ip, "addr-map entry PREFIX too short for PREFIX-LEN",
+		  "HBYTES ADDRMAP SYNTAX UNDERRUN");
+    goto x_rc;
+  }
+  if (inmap && suppliedprefixbytes > wantprefixbytes) {
+    rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN",
+		  "HBYTES ADDRMAP SYNTAX OVERRUN");
+    goto x_rc;
+  }
+
+  ame->prefixlen= prefixbits;
+  ame->prefix= TALLOC(wantprefixbytes);  assert(ame->prefix);
+  memcpy(ame->prefix, data, wantprefixbytes);
+
+  if (ame_clear_unwanted(ame, wantprefixbytes)) {
+    rc= staticerr(ip, "addr-map entry PREFIX contains bits excluded"
+		  " by PREFIX-LEN", "HBYTES ADDRMAP SYNTAX EXCLBITS");
+    goto x_rc;
+  }
+
   return TCL_OK;
+
+ x_rc:
+  ame_free(ame);
+  return rc;
+}
+
+static int ame_contains(const AddrMap_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 ame_compare(const AddrMap_Entry *a, const AddrMap_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 (ame_contains(a,b->prefix,bl)) return +1; }
+  else if (bl<al) { ml=bl; if (ame_contains(b,a->prefix,al)) return -1; }
+
+  d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
+  return (d > 0 ? +2 :
+	  d < 0 ? -2 :
+	  0);
+}
+
+/*---------- searching maps ----------*/
+
+typedef enum {
+  sr_notfound,
+  sr_exact,
+  sr_inbig,
+  sr_aroundsmall
+} Search_Result;
+
+static int
+am_binarychop(AddrMap_Value *am, int low_oreq, int high_strict, void *u,
+	      int (*test)(AddrMap_Entry *am, 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(&am->entries[mid], u);
+
+    if (!cmp) {
+      *found_r= 1;
+      return mid;
+    }
+
+    if (cmp < 0)
+      high_strict= mid;
+    else
+      low_oreq= mid+1;
+  }
+}
+
+struct am_search_u {
+  int forbid_aroundsmall;
+  AddrMap_Entry proposed;
+  Search_Result sr;
+};
+
+static int
+am_search_binchoptest(AddrMap_Entry *ame, void *u_v) {
+  struct am_search_u *u= u_v;
+  int cmp;
+
+  cmp= ame_compare(&u.proposed, ame);
+  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
+am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) {
+  int place, found;
+  struct am_search_u u;
+
+  u.forbid_aroundsmall= forbid_aroundsmall;
+  u.proposed= proposed;
+  u.sr= sr_notfound;
+
+  *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found);
+
+  assert(!!found == (u.sr != sr_notfound));
+  return u.sr;
+}
+
+/*---------- useful operations on AddrMap_Value etc. ----------*/
+
+/*---------- amendment (complex algorithm) ----------*/
+
+struct am_amend_aroundsmall_u {
+  AddrMap_Entry *new;
+  int sign;
+};
+
+
+static int
+am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) {
+  struct am_amend_aroundsmall_u *u= u_v;
+
+  cmp= u->sign * ame_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, HBytes_Value prefix,
-		     int preflen, Tcl_Obj *data) {
+int do_addrmap_amend(ClientData cd, Tcl_Interp *ip,
+		     AddrMap_Var map, Tcl_Obj *prefix,
+		     Tcl_Obj *preflen, Tcl_Obj *data) {
+  AddrMap_Value *am= map.am;
+  AddrMap_Entry new, *fragment;
+  AddrMap_Entry *breaking, *replacements;
+  int rc, insertat, findend, cmp, nreplacements, new_used;
+  struct am_amend_aroundsmall_u u;
+
+  ame_init(&new);
+  
+  rc= ame_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
+
+  sr= am_search(am, &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.ame= new;
+    u.sign= -1;
+    replace_start= am_binarychop(am, 0, searched, &u,
+				 am_amend_aroundsmall_binchoptest, &dummy);
+    u.sign= +1;
+    replace_end= am_binarychop(am, searched+1, am.used, &u,
+				 am_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= &am.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);
+      ame_clear_unwanted(fragment, fragmentbytes);
+
+      fragment->prefix[fragmentbytes] ^=
+	0x80u >> ((fragmentlen+7) & 7);
+
+      switch (ame_compare(&fragment, &new)) {
+      case -2:  replacements[left_insert++]=  fragment;  break;
+      case +2:  replacements[--right_insert]= fragment;  break;
+      default: abort();
+      }
+    }
+    assert(left_insert == right_insert-1);
+    replacements[left_insert]= new;
+    ame_init(&new);
+
+    replace_end= searched+1;
+    break;
+
+  }
+
+  new_used= am.used - (replace_end - replace_start) + nreplacements;
+
+  if (new_used > am.space)
+    am_reallocentries(am, new_used * 2);
+
+  for (scan=replacements, i=0;
+       i < nreplacements;
+       scan++, i++) {
+    scan->data= data;
+    Tcl_IncrRefCount(scan->data);
+  }
+
+  for (i= replace_start, scan= am.entries+i;
+       i < replace_end;
+       i++, scan++) {
+    ame_free(scan);
+  }
+
+  memmove(am.entries + replace_start + nreplacements,
+	  am.entries + replace_end,
+	  sizeof(*am.entries) * (am.used - replace_end));
+
+  memcpy(am.entries + replace_start,
+	 replacements,
+	 sizeof(*am.entries) * nreplacements);
+
+  am.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
+     * AddrMap_Value. */
+    TFREE(replacements);
+
   return TCL_OK;
 }
 
-int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip,
-		      MaskMap_Var map, HBytes_Value addr, Tcl_Obj *def,
+/*---------- other substantial operations on mask maps ----------*/
+
+int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip,
+		      Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
 		      Tcl_Obj **result) {
+  AddrMap_Value *am= (void*)&mapo->internalRep;
+  const Byte *addr= hbytes_data(&addrhb);
+  int addrbytes= hbytes_len(&addrhb);
+  int i, addrbits, place;
+  Search_Result sr;
+
+  addrbits= addrbytes * 8;
+  sr= am_search(am, addr, addrbits, &place);
+
+  switch (sr) {
+
+  case sr_notfound:
+    if (!def) return staticerr(ip, "address not found in addr-map",
+			       "HBYTES ADDRMAP NOMATCH");
+    *result= def;
+    break;
+
+  case sr_aroundsmall:
+    return staticerr(ip, "address shorter than mask in map",
+		     "HBYTES ADDRMAP UNDERRUN");
+
+  case sr_exact:
+  case sr_inbig:
+    *result= am.entres[place].data;
+    break;
+    
+  }
+
   return TCL_OK;
 }
 
-static void maskmap_t_free(Tcl_Obj *o) { }
-static void maskmap_t_dup(Tcl_Obj *src, Tcl_Obj *dup) { }
-static void maskmap_t_ustr(Tcl_Obj *o) { }
-static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) { return TCL_ERROR; }
+/*---------- Tcl type and arg parsing functions ----------*/
 
-Tcl_ObjType maskmap_type = {
-  "mask-map",
-  maskmap_t_free, maskmap_t_dup, maskmap_t_ustr, maskmap_t_sfa
-};