chiark / gitweb /
working on new addrmap instead of maskmap - compiles, but have not yet implemented...
authorian <ian>
Tue, 28 Dec 2004 00:08:11 +0000 (00:08 +0000)
committerian <ian>
Tue, 28 Dec 2004 00:08:11 +0000 (00:08 +0000)
base/chiark-tcl.h
base/hook.c
base/tables-examples.tct
base/troglodyte-Makefile
hbytes/hbytes.h
hbytes/hook.c
maskmap/addrmap.c [new file with mode: 0644]
maskmap/maskmap.c

index b4fcfb8..206f97e 100644 (file)
  *               uint VARNAME/VALUE         (VARNAME if ul2bitfields;
  *               ulong VARNAME/VALUE         VALUE if bitfields2ul)
  *
- * Mask maps:
+ * Address ranges (addrmap.c):
  *
- *  A maskmap is a slightly efficient mapping from addresses to
- *  arbitrary data values.  An address is a number of octets expressed
- *  as an hbytes.  All the addresses covered by the same maskmap
- *  should have the same length (even though constructing the maskmap
- *  does not involve specifying that length).
+ *  An address range is a slightly efficient partial mapping from
+ *  addresses to arbitrary data values.  An address is a number of
+ *  octets expressed as an hbytes.  All the addresses covered by the
+ *  same addrmap should have the same length.
  *
- *  hbytes mask-map lookup MAP-VAR ADDRESS [DEFAULT]   => DATA
+ *  hbytes addr-map lookup MAP-VAR ADDRESS [DEFAULT]   => DATA
  *     Error on missing default or if any prefix longer than ADDRESS.
  *
- *  hbytes mask-map amend MAP-VAR PREFIX PREFIX-LENGTH DATA
+ *  hbytes addr-map amend-range MAP-VAR START END DATA
+ *  hbytes addr-map amend-mask MAP-VAR PREFIX PREFIX-LENGTH DATA
  *     Sets all of the addresses in PREFIX/PREFIX-LENGTH to the
  *     relevant value.
  *
  *  Representation:
- *     A maskmap MAP is [list [list PREFIX PREFIX-LENGTH DATA]].
- *     The list is sorted by ascending PREFIX and entries do not overlap.
- *     Each PREFIX in the map is truncated to the shortest number of
- *     pairs of hex digits which can represent it.
+ *     An address map MAP is
+ *           [list BIT-LENGTH                           \
+ *                 [list START END DATA-VALUE]          \
+ *                 [list START' END' DATA-VALUE']       \
+ *                 ...
+ *            ]
+ *     The list is sorted by ascending START and entries do not overlap.
+ *     START and END are both inclusive.  BIT-LENGTH is in usual Tcl
+ *     integer notation and must be a multiple of 8.
  *
  * Error codes
  *
  * HBYTES LENGTH MISMATCH              when blocks must be exactly same length
  * HBYTES SYNTAX                       supposed hex block had wrong syntax
  * HBYTES VALUE OVERFLOW               value to be conv'd to hex too big/long
- * HBYTES MASKMAP NOMATCH              no addr/mask matches address for lookup
- * HBYTES MASKMAP UNDERRUN             addr value for lookup is too short
- * HBYTES MASKMAP SYNTAX LLENGTH       value for mask-map entry not llength==3
- * HBYTES MASKMAP SYNTAX UNDERRUN      value for mask-map entry hex too short
- * HBYTES MASKMAP SYNTAX OVERRUN       actual mask-map entry hex too short
- * HBYTES MASKMAP SYNTAX ORDER         actual mask-map is disordered
- * HBYTES MASKMAP SYNTAX EXCLBITS      mask-map has 1-bits outside prefix len
+ * HBYTES ADDRMAP NOMATCH              no addr/mask matches address for lookup
+ * HBYTES ADDRMAP UNDERRUN             addr for lookup or amend is too short
+ * HBYTES ADDRMAP OVERRUN              addr for lookup or amend is too long
+ * HBYTES ADDRMAP EXCLBITS             amend-mask 1-bits outside prefix len
+ * HBYTES ADDRMAP BADRANGE             amend-range start > end
+ * HBYTES ADDRMAP VALUE                addr-map string value is erroneous
  * SOCKADDR AFUNIX LENGTH              path for AF_UNIX socket too long
  * SOCKADDR SYNTAX IPV4                bad IPv4 socket address &/or port
  * SOCKADDR SYNTAX OTHER               bad socket addr, couldn't tell what kind
@@ -295,16 +299,16 @@ typedef struct {
   Something_Var sth;
 } HBytes_Var;
 
-/* from maskmap.c */
+/* from addrmap.c */
 
-typedef struct MaskMap_Value MaskMap_Value;
+typedef struct AddrMap_Value AddrMap_Value;
 
 typedef struct {
-  MaskMap_Value *mm;
+  AddrMap_Value *am;
   Something_Var sth;
-} MaskMap_Var;
+} AddrMap_Var;
 
-extern Tcl_ObjType maskmap_type;
+extern Tcl_ObjType addrmap_type;
 
 /* from chop.c */
   /* only do_... functions declared in tables.h */
index b65741f..5b163b3 100644 (file)
@@ -324,9 +324,9 @@ int do_hbytes_range(ClientData cd, Tcl_Interp *ip,
   return TCL_OK;
 }
 
-int do_hbytes_mask_map(ClientData cd, Tcl_Interp *ip,
-                     const MaskMap_SubCommand *subcmd,
-                     int objc, Tcl_Obj *const *objv) {
+int do_hbytes_addr_map(ClientData cd, Tcl_Interp *ip,
+                      const AddrMap_SubCommand *subcmd,
+                      int objc, Tcl_Obj *const *objv) {
   return subcmd->func(0,ip,objc,objv);
 }
 
@@ -427,7 +427,7 @@ int Hbytes_Init(Tcl_Interp *ip) {
   Tcl_RegisterObjType(&sockaddr_type);
   Tcl_RegisterObjType(&tabledataid_nearlytype);
   Tcl_RegisterObjType(&ulong_type);
-  Tcl_RegisterObjType(&maskmap_type);
+  Tcl_RegisterObjType(&addrmap_type);
 
   for (cmd=toplevel_commands;
        cmd->name;
index 8a28c4f..7ce5dc7 100644 (file)
@@ -7,9 +7,9 @@ Fini hbv                        fini_somethingv(ip, rc, &@.sth);
 
 Type constv(Tcl_ObjType*):     Tcl_Obj *@
 
-Type maskmapv:                 MaskMap_Var @
-Init maskmapv                  @.mm=0; init_somethingv(&@.sth);
-Fini maskmapv                  fini_somethingv(ip, rc, &@.sth);
+Type addrmapv:                 AddrMap_Var @
+Init addrmapv                  @.am=0; init_somethingv(&@.sth);
+Fini addrmapv                  fini_somethingv(ip, rc, &@.sth);
 
 Type sockaddr:                 SockAddr_Value @
 Init sockaddr                  sockaddr_clear(&@);
@@ -74,15 +74,20 @@ Table adns Adns_SubCommand
        destroy-resolver
                res     iddata(&adnstcl_resolvers)
 
-Table maskmap MaskMap_SubCommand
+Table addrmap AddrMap_SubCommand
        lookup
-               map     constv(&maskmap_type)
+               map     constv(&addrmap_type)
                addr    hb
                ?def    obj
                =>      obj
-       amend
-               map     maskmapv
-               prefix  obj
+       amend-range
+               map     addrmapv
+               start   hb
+               end     hb
+               data    obj
+       amend-mask
+               map     addrmapv
+               prefix  hb
                preflen obj
                data    obj
 
@@ -218,8 +223,8 @@ Table hbytes HBytes_SubCommand
                prop    enum(HashAlgPropInfo, "prop")
                alg     enum(HashAlgInfo, "alg")
                =>      int
-       mask-map
-               subcmd  enum(MaskMap_SubCommand, "hbytes mask-map subcommand")
+       addr-map
+               subcmd  enum(AddrMap_SubCommand, "hbytes addr-map subcommand")
                ...     obj
 
 Table padmethodinfo PadMethodInfo
index ea2c10c..e458511 100644 (file)
@@ -16,7 +16,7 @@ OBJS=         tables.o \
                algtables.o \
                crypto.o \
                parse.o \
-               maskmap.o
+               addrmap.o
 
 HDRS=          hbytes.h \
                $(AUTO_HDRS)
index b4fcfb8..206f97e 100644 (file)
  *               uint VARNAME/VALUE         (VARNAME if ul2bitfields;
  *               ulong VARNAME/VALUE         VALUE if bitfields2ul)
  *
- * Mask maps:
+ * Address ranges (addrmap.c):
  *
- *  A maskmap is a slightly efficient mapping from addresses to
- *  arbitrary data values.  An address is a number of octets expressed
- *  as an hbytes.  All the addresses covered by the same maskmap
- *  should have the same length (even though constructing the maskmap
- *  does not involve specifying that length).
+ *  An address range is a slightly efficient partial mapping from
+ *  addresses to arbitrary data values.  An address is a number of
+ *  octets expressed as an hbytes.  All the addresses covered by the
+ *  same addrmap should have the same length.
  *
- *  hbytes mask-map lookup MAP-VAR ADDRESS [DEFAULT]   => DATA
+ *  hbytes addr-map lookup MAP-VAR ADDRESS [DEFAULT]   => DATA
  *     Error on missing default or if any prefix longer than ADDRESS.
  *
- *  hbytes mask-map amend MAP-VAR PREFIX PREFIX-LENGTH DATA
+ *  hbytes addr-map amend-range MAP-VAR START END DATA
+ *  hbytes addr-map amend-mask MAP-VAR PREFIX PREFIX-LENGTH DATA
  *     Sets all of the addresses in PREFIX/PREFIX-LENGTH to the
  *     relevant value.
  *
  *  Representation:
- *     A maskmap MAP is [list [list PREFIX PREFIX-LENGTH DATA]].
- *     The list is sorted by ascending PREFIX and entries do not overlap.
- *     Each PREFIX in the map is truncated to the shortest number of
- *     pairs of hex digits which can represent it.
+ *     An address map MAP is
+ *           [list BIT-LENGTH                           \
+ *                 [list START END DATA-VALUE]          \
+ *                 [list START' END' DATA-VALUE']       \
+ *                 ...
+ *            ]
+ *     The list is sorted by ascending START and entries do not overlap.
+ *     START and END are both inclusive.  BIT-LENGTH is in usual Tcl
+ *     integer notation and must be a multiple of 8.
  *
  * Error codes
  *
  * HBYTES LENGTH MISMATCH              when blocks must be exactly same length
  * HBYTES SYNTAX                       supposed hex block had wrong syntax
  * HBYTES VALUE OVERFLOW               value to be conv'd to hex too big/long
- * HBYTES MASKMAP NOMATCH              no addr/mask matches address for lookup
- * HBYTES MASKMAP UNDERRUN             addr value for lookup is too short
- * HBYTES MASKMAP SYNTAX LLENGTH       value for mask-map entry not llength==3
- * HBYTES MASKMAP SYNTAX UNDERRUN      value for mask-map entry hex too short
- * HBYTES MASKMAP SYNTAX OVERRUN       actual mask-map entry hex too short
- * HBYTES MASKMAP SYNTAX ORDER         actual mask-map is disordered
- * HBYTES MASKMAP SYNTAX EXCLBITS      mask-map has 1-bits outside prefix len
+ * HBYTES ADDRMAP NOMATCH              no addr/mask matches address for lookup
+ * HBYTES ADDRMAP UNDERRUN             addr for lookup or amend is too short
+ * HBYTES ADDRMAP OVERRUN              addr for lookup or amend is too long
+ * HBYTES ADDRMAP EXCLBITS             amend-mask 1-bits outside prefix len
+ * HBYTES ADDRMAP BADRANGE             amend-range start > end
+ * HBYTES ADDRMAP VALUE                addr-map string value is erroneous
  * SOCKADDR AFUNIX LENGTH              path for AF_UNIX socket too long
  * SOCKADDR SYNTAX IPV4                bad IPv4 socket address &/or port
  * SOCKADDR SYNTAX OTHER               bad socket addr, couldn't tell what kind
@@ -295,16 +299,16 @@ typedef struct {
   Something_Var sth;
 } HBytes_Var;
 
-/* from maskmap.c */
+/* from addrmap.c */
 
-typedef struct MaskMap_Value MaskMap_Value;
+typedef struct AddrMap_Value AddrMap_Value;
 
 typedef struct {
-  MaskMap_Value *mm;
+  AddrMap_Value *am;
   Something_Var sth;
-} MaskMap_Var;
+} AddrMap_Var;
 
-extern Tcl_ObjType maskmap_type;
+extern Tcl_ObjType addrmap_type;
 
 /* from chop.c */
   /* only do_... functions declared in tables.h */
index b65741f..5b163b3 100644 (file)
@@ -324,9 +324,9 @@ int do_hbytes_range(ClientData cd, Tcl_Interp *ip,
   return TCL_OK;
 }
 
-int do_hbytes_mask_map(ClientData cd, Tcl_Interp *ip,
-                     const MaskMap_SubCommand *subcmd,
-                     int objc, Tcl_Obj *const *objv) {
+int do_hbytes_addr_map(ClientData cd, Tcl_Interp *ip,
+                      const AddrMap_SubCommand *subcmd,
+                      int objc, Tcl_Obj *const *objv) {
   return subcmd->func(0,ip,objc,objv);
 }
 
@@ -427,7 +427,7 @@ int Hbytes_Init(Tcl_Interp *ip) {
   Tcl_RegisterObjType(&sockaddr_type);
   Tcl_RegisterObjType(&tabledataid_nearlytype);
   Tcl_RegisterObjType(&ulong_type);
-  Tcl_RegisterObjType(&maskmap_type);
+  Tcl_RegisterObjType(&addrmap_type);
 
   for (cmd=toplevel_commands;
        cmd->name;
diff --git a/maskmap/addrmap.c b/maskmap/addrmap.c
new file mode 100644 (file)
index 0000000..2eb4898
--- /dev/null
@@ -0,0 +1,305 @@
+/*
+ */
+
+#include <string.h>
+
+#include "tables.h"
+#include "hbytes.h"
+
+typedef struct {
+  Byte *start; /* byl bytes */
+  Tcl_Obj *data; /* may be 0 to mean empty */
+} AddrMap_Entry;
+
+struct AddrMap_Value {
+  int byl, used, space;
+  AddrMap_Entry *entries;
+  /* Entries are sorted by start.  Each entry gives value (or lack of
+   * it) for all A st START <= A < NEXT-START.  Last entry has value
+   * (or lack of it) for all A >= START.  First entry is always
+   * present and always has start all-bits-0. */
+}; /* internalRep.otherValuePtr */
+
+/*---------- operations on AddrMap_Entry ----------*/
+
+static void ame_free(AddrMap_Entry *ame) {
+  TFREE(ame->start);  ame->start=0;
+  if (ame->data) { Tcl_DecrRefCount(ame->data); ame->data=0; }
+}
+
+static const Byte *ame_parsecheck_addr(Tcl_Interp *ip, const AddrMap_Value *am,
+                                      const HBytes_Value *hb) {
+  int hbl= hbytes_len(hb);
+  if (hbl < am->byl) {
+    staticerr(ip,"addr-map address too short","HBYTES ADDRMAP UNDERRUN");
+    return 0;
+  }
+  if (hbl > am->byl) {
+    staticerr(ip,"addr-map address too long","HBYTES ADDRMAP OVERRUN");
+    return 0;
+  }
+  return hbytes_data(hb);
+}
+  
+static int ame_parsecheck_range(Tcl_Interp *ip, const AddrMap_Value *am,
+                               const HBytes_Value *starthb,
+                               const HBytes_Value *endhb,
+                               const Byte *p_r[2]) {
+  p_r[0]= ame_parsecheck_addr(ip,am,starthb);  if (!p_r[0]) return TCL_ERROR;
+  p_r[1]= ame_parsecheck_addr(ip,am,endhb);    if (!p_r[0]) return TCL_ERROR;
+  if (memcmp(p_r[0],p_r[1],am->byl) > 0)
+    return staticerr(ip, "addr-map range start is after end",
+                    "HBYTES ADDRMAP BADRANGE");
+  return TCL_OK;
+}
+  
+static int ame_ba_addsubtractone(Byte *out, const Byte *in, int byl,
+                                unsigned signum, unsigned onoverflow) {
+  /* On entry:
+   *   *in is an array of byl bytes
+   *   signum is 0xff or 0x01
+   *   onoverflow is what counts as overflowed value,
+   *     ie (for unsigned arith) 0x00 for add and 0xff for subtract
+   * On exit:
+   *   *out is the resulting value (subject to overflow truncation)
+   *   return value is TCL_OK, or TCL_ERROR if overflow happened
+   *   (but interpreter result is not set on overflow)
+   */
+  int j;
+      
+  for (j= byl, in += byl, out += byl;
+       in--, out--, j>0;
+       j--) {
+    *out = (*out) + signum;
+    if (*out != onoverflow)
+      return TCL_OK;
+  }
+  return TCL_ERROR;
+}
+
+/*---------- useful operations on AddrMap_Value etc. ----------*/
+
+static void am_init0(AddrMap_Value *am, int byl) {
+  am->byl= byl;
+  am->used= 0;
+  am->space= 0;
+  am->entries= 0;
+}
+
+static void am_reallocentries(AddrMap_Value *am, int len) {
+  AddrMap_Entry *newentries;
+
+  assert(len >= am->space);
+  if (!len) return;
+
+  newentries= TREALLOC(am->entries, sizeof(*newentries)*len);
+  assert(newentries);
+  
+  am->space= len;
+  am->entries= newentries;
+}
+
+static void am_free(AddrMap_Value *am) {
+  AddrMap_Entry *ame;
+  int i;
+
+  if (!am) return;
+  
+  for (i=0, ame=am->entries; i<am->used; i++, ame++)
+    ame_free(ame);
+
+  TFREE(am->entries);
+  TFREE(am);
+}
+
+/*---------- Tcl type and arg parsing functions ----------*/
+
+int pat_addrmapv(Tcl_Interp *ip, Tcl_Obj *var, AddrMap_Var *agg) {
+  int rc;
+  rc= pat_somethingv(ip,var,&agg->sth,&addrmap_type);  if (rc) return rc;
+  agg->am= agg->sth.obj->internalRep.otherValuePtr;
+  return TCL_OK;
+}
+
+static void addrmap_t_free(Tcl_Obj *o) {
+  AddrMap_Value *am= o->internalRep.otherValuePtr;
+  am_free(am);
+}
+
+static void addrmap_t_dup(Tcl_Obj *sob, Tcl_Obj *dob) {
+  AddrMap_Value *sm= sob->internalRep.otherValuePtr;
+  AddrMap_Value *dm;
+  AddrMap_Entry *sme, *dme;
+  int i;
+
+  assert(sob->typePtr == &addrmap_type);
+  objfreeir(dob);
+  dm= TALLOC(sizeof(*dm));
+
+  am_init0(dm,sm->byl);
+  am_reallocentries(dm,sm->used);
+  dm->used= sm->used;
+  for (i=0, sme=sm->entries, dme=dm->entries;
+       i < dm->used;
+       i++, sme++, dme++) {
+    *dme= *sme;
+    dme->start= TALLOC(sm->byl);  assert(dme->start);
+    memcpy(dme->start, sme->start, sm->byl);
+    Tcl_IncrRefCount(dme->data);
+  }
+  dob->internalRep.otherValuePtr= dm;
+  dob->typePtr= &addrmap_type;
+}
+
+static void addrmap_t_ustr(Tcl_Obj *so) {
+  AddrMap_Value *sm= so->internalRep.otherValuePtr;
+  Tcl_Obj **mainlobjsl, *surrogate;
+  AddrMap_Entry *sme;
+  int entnum, listlength;
+
+  assert(so->typePtr == &addrmap_type);
+  mainlobjsl= TALLOC(sizeof(*mainlobjsl) * (sm->used+1));  assert(mainlobjsl);
+  mainlobjsl[0]= Tcl_NewIntObj(sm->byl * 8);
+  listlength= 1;
+
+  for (entnum=0, sme=sm->entries; entnum<sm->used; entnum++, sme++) {
+    HBytes_Value hb;
+    Tcl_Obj *subl[3], *sublo;
+
+    if (!sme->data) continue;
+
+    hbytes_array(&hb, sme->start, sm->byl);
+    subl[0]= ret_hb(0, hb);  assert(subl[0]);
+
+    if (entnum+1 < sm->used) {
+      ame_ba_addsubtractone(hbytes_arrayspace(&hb, sm->byl),
+                           (sme+1)->start, sm->byl,
+                           /*subtract:*/ 0x0ffu, 0x0ffu);
+    } else {
+      memset(hbytes_arrayspace(&hb, sm->byl),
+            0x0ffu, sm->byl);
+    }
+
+    subl[1]= ret_hb(0, hb);  assert(subl[1]);
+    subl[2]= sme->data;
+    
+    sublo= Tcl_NewListObj(3,subl);  assert(sublo);
+    mainlobjsl[listlength++]= sublo;
+  }
+  assert(listlength <= sm->used+1);
+  surrogate= Tcl_NewListObj(listlength,mainlobjsl);  assert(surrogate);
+  assert(surrogate);
+  
+  so->bytes= Tcl_GetStringFromObj(surrogate, &so->length);  assert(so->bytes);
+  surrogate->bytes= 0; surrogate->length= 0; /* we stole it */
+}
+
+static AddrMap_Entry *ame_sfa_alloc(AddrMap_Value *am) {
+  AddrMap_Entry *ame;
+  
+  ame= am->entries + am->used;
+
+  am->used++;
+  assert(am->used <= am->space);
+
+  ame->start= TALLOC(am->byl);  assert(ame->start);
+  ame->data= 0;
+  return ame;
+}
+
+static int addrmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
+  int rc, inlen, eol, innum, bitlen, cmp;
+  Tcl_Obj *eo, *starto, *endo;
+  HBytes_Value starthb, endhb;
+  const Byte *rangeptrs[2];
+  AddrMap_Value *am;
+  AddrMap_Entry *ame;
+
+  am= TALLOC(sizeof(*am));  assert(am);
+  am_init0(am,0);
+
+  rc= Tcl_ListObjLength(ip,o,&inlen);  if (rc) goto x_badvalue_rc;
+
+  if (inlen<0) {
+    rc= staticerr(ip, "addr-map overall length < 1", 0);
+    goto x_badvalue_rc;
+  }
+
+  rc= Tcl_ListObjIndex(ip,o,0,&eo);  if (rc) goto x_badvalue_rc;
+  rc= Tcl_GetIntFromObj(ip,eo,&bitlen);  if (rc) goto x_badvalue_rc;
+
+  if (bitlen<0 || bitlen % 8) {
+    rc= staticerr(ip, "addr-map overall length < 1", 0);
+    goto x_badvalue_rc;
+  }
+
+  am->byl= bitlen/8;
+  am_reallocentries(am, (inlen-1)*2+1);
+
+  ame= ame_sfa_alloc(am);
+  memset(ame->start,0,am->byl);
+
+  for (innum=1; innum < inlen; innum++) {
+    rc= Tcl_ListObjIndex(ip,o,innum,&eo);  if (rc) goto x_badvalue_rc;
+    rc= Tcl_ListObjLength(ip,eo,&eol);  if (rc) goto x_badvalue_rc;
+
+    if (eol != 3) {
+      rc= staticerr(ip, "addr-map entry length != 3", 0);
+      goto x_badvalue_rc;
+    }
+    rc= Tcl_ListObjIndex(ip,eo,0,&starto);  if (rc) goto x_badvalue_rc;
+    rc= Tcl_ListObjIndex(ip,eo,1,&endo);    if (rc) goto x_badvalue_rc;
+
+    rc= pat_hb(ip,starto,&starthb);  if (rc) goto x_badvalue_rc;
+    rc= pat_hb(ip,endo,&endhb);  if (rc) goto x_badvalue_rc;
+
+    rc= ame_parsecheck_range(ip,am,&starthb,&endhb,rangeptrs);
+    if (rc) goto x_badvalue_rc;
+
+    cmp= memcmp(ame->start, rangeptrs[0], am->byl);
+    if (cmp < 0) {
+      rc= staticerr(ip, "addr-map entries out of order", 0);
+      goto x_badvalue_rc;
+    }
+    if (cmp > 0) {
+      ame= ame_sfa_alloc(am);
+      memcpy(ame->start, rangeptrs[0], am->byl);
+    }
+    
+    assert(!ame->data);
+    rc= Tcl_ListObjIndex(ip,eo,2,&ame->data);  if (rc) goto x_badvalue_rc;
+    Tcl_IncrRefCount(ame->data);
+
+    ame= ame_sfa_alloc(am);
+    rc= ame_ba_addsubtractone(ame->start, rangeptrs[1], am->byl,
+                             /*add:*/ 0x01u, 0x00u);
+    if (rc) {
+      /* we've overflowed.  it must have been ffffffff.... */
+      if (innum != inlen-1) {
+       rc= staticerr(ip, "addr-map non-last entry end is all-bits-1", 0);
+       goto x_badvalue_rc;
+      }
+      TFREE(ame->start);
+      am->used--;
+      break;
+    }
+  }
+    
+  /* we commit now */
+  objfreeir(o);
+  o->internalRep.otherValuePtr= am;
+  o->typePtr= &addrmap_type;
+  return TCL_OK;
+
+ x_badvalue_rc:
+  if (rc == TCL_ERROR)
+    Tcl_SetObjErrorCode(ip, Tcl_NewStringObj("HBYTES ADDRMAP VALUE", -1));
+
+  am_free(am);
+  return rc;
+}
+
+Tcl_ObjType addrmap_type = {
+  "addr-map",
+  addrmap_t_free, addrmap_t_dup, addrmap_t_ustr, addrmap_t_sfa
+};
index 7e6bcf0..ee9ce4c 100644 (file)
@@ -1,52 +1,24 @@
-/*
- */
 
-#include <string.h>
 
-#include "tables.h"
-#include "hbytes.h"
+/*---------- operations on AddrMap_Entry ----------*/
 
-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;
-
-struct MaskMap_Value {
-  int used, space;
-  MaskMap_Entry *entries;
-}; /* overlays internalRep */
-
-/*---------- useful stuff ----------*/
-
-static int prefix_bytes (int prefixlen) {
-  return (prefixlen + 7)/8;
+static void ame_init(AddrMap_Entry *ame) {
+  ame->prefixlen= -1;
+  ame->prefix= 0;
+  ame->data= 0;
 }
 
-/*---------- operations on MaskMap_Entry ----------*/
-
-static void mme_init(MaskMap_Entry *mme) {
-  mme->prefixlen= -1;
-  mme->prefix= 0;
-  mme->data= 0;
-}
-
-static void mme_free(MaskMap_Entry *mme) {
-  TFREE(mme->prefix);  mme->prefix=0;
-  if (mme->data) { Tcl_DecrRefCount(mme->data); mme->data=0; }
-}
-
-static unsigned mme_clear_unwanted(MaskMap_Entry *mme, int bytes) {
+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 - mme->prefixlen;
+  sparebits= bytes * 8 - ame->prefixlen;
   if (!sparebits) return 0;
 
   sparemask= (1u << sparebits) - 1;
-  datap= &mme->prefix[bytes-1];
+  datap= &ame->prefix[bytes-1];
 
   result= *datap & sparemask;
   *datap &= ~sparemask;
@@ -54,10 +26,10 @@ static unsigned mme_clear_unwanted(MaskMap_Entry *mme, int bytes) {
   return result;
 }
 
-static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
+static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame,
                        Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
                        int inmap) {
- /* *mme should be blank entry; after exit (even error exit) it will be valid
+ /* *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;
@@ -74,34 +46,34 @@ static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
   suppliedprefixbytes= hbytes_len(&prefix);
 
   if (suppliedprefixbytes < wantprefixbytes) {
-    rc= staticerr(ip, "mask-map entry PREFIX too short for PREFIX-LEN",
-                 "HBYTES MASKMAP SYNTAX UNDERRUN");
+    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, "mask-map existing entry PREFIX too long for PREFIX-LEN",
-                 "HBYTES MASKMAP SYNTAX OVERRUN");
+    rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN",
+                 "HBYTES ADDRMAP SYNTAX OVERRUN");
     goto x_rc;
   }
 
-  mme->prefixlen= prefixbits;
-  mme->prefix= TALLOC(wantprefixbytes);  assert(mme->prefix);
-  memcpy(mme->prefix, data, wantprefixbytes);
+  ame->prefixlen= prefixbits;
+  ame->prefix= TALLOC(wantprefixbytes);  assert(ame->prefix);
+  memcpy(ame->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");
+  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:
-  mme_free(mme);
+  ame_free(ame);
   return rc;
 }
 
-static int mme_contains(const MaskMap_Entry *ref, const Byte *addr, int len) {
+static int ame_contains(const AddrMap_Entry *ref, const Byte *addr, int len) {
   int directbytes, leftoverbits;
   
   assert(len >= ref->prefixlen);
@@ -118,7 +90,7 @@ static int mme_contains(const MaskMap_Entry *ref, const Byte *addr, int len) {
   return 1;
 }  
 
-static int mme_compare(const MaskMap_Entry *a, const MaskMap_Entry *b) {
+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
@@ -130,8 +102,8 @@ static int mme_compare(const MaskMap_Entry *a, const MaskMap_Entry *b) {
   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; }
+  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 :
@@ -149,8 +121,8 @@ typedef enum {
 } 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 */,
+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;
   
@@ -162,7 +134,7 @@ mm_binarychop(MaskMap_Value *mm, int low_oreq, int high_strict, void *u,
     }
 
     mid= (high_strict + low_oreq) / 2;
-    cmp= test(&mm->entries[mid], u);
+    cmp= test(&am->entries[mid], u);
 
     if (!cmp) {
       *found_r= 1;
@@ -176,18 +148,18 @@ mm_binarychop(MaskMap_Value *mm, int low_oreq, int high_strict, void *u,
   }
 }
 
-struct mm_search_u {
+struct am_search_u {
   int forbid_aroundsmall;
-  MaskMap_Entry proposed;
+  AddrMap_Entry proposed;
   Search_Result sr;
 };
 
 static int
-mm_search_binchoptest(MaskMap_Entry *mme, void *u_v) {
-  struct mm_search_u *u= u_v;
+am_search_binchoptest(AddrMap_Entry *ame, void *u_v) {
+  struct am_search_u *u= u_v;
   int cmp;
 
-  cmp= mme_compare(&u.proposed, mme);
+  cmp= ame_compare(&u.proposed, ame);
   switch (cmp) {
   case -1:  u->sr= sr_inbig;        return  0;
   case  0:  u->sr= sr_exact;        return  0;
@@ -197,54 +169,35 @@ mm_search_binchoptest(MaskMap_Entry *mme, void *u_v) {
 }
 
 static Search_Result
-mm_search(MaskMap_Value *mm, const MaskMap_Entry *proposed, int *place_r) {
+am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) {
   int place, found;
-  struct mm_search_u u;
+  struct am_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);
+  *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 MaskMap_Value etc. ----------*/
-
-static void mm_init(MaskMap_Value *mm) {
-  mm->used= 0;
-  mm->space= 0;
-  mm->entries= 0;
-}
-
-static void mm_reallocentries(MaskMap_Value *mm, int len) {
-  MaskMap_Entry *newentries;
-
-  assert(len >= mm->space);
-  if (!len) return;
-
-  newentries= TREALLOC(mm->entries, sizeof(*newentries)*len);
-  assert(newentries);
-  
-  mm->space= len;
-  mm->entries= newentries;
-}
+/*---------- useful operations on AddrMap_Value etc. ----------*/
 
 /*---------- amendment (complex algorithm) ----------*/
 
-struct mm_amend_aroundsmall_u {
-  MaskMap_Entry *new;
+struct am_amend_aroundsmall_u {
+  AddrMap_Entry *new;
   int sign;
 };
 
 
 static int
-mm_amend_aroundsmall_binchoptest(MaskMap_Entry *search, void *u_v) {
-  struct mm_amend_aroundsmall_u *u= u_v;
+am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) {
+  struct am_amend_aroundsmall_u *u= u_v;
 
-  cmp= u->sign * mme_compare(search, u->new);
+  cmp= u->sign * ame_compare(search, u->new);
 
   switch (cmp) {
   case +2:  return -u->sign;
@@ -253,20 +206,20 @@ mm_amend_aroundsmall_binchoptest(MaskMap_Entry *search, void *u_v) {
   }
 }
 
-int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
-                    MaskMap_Var map, Tcl_Obj *prefix,
+int do_addrmap_amend(ClientData cd, Tcl_Interp *ip,
+                    AddrMap_Var map, Tcl_Obj *prefix,
                     Tcl_Obj *preflen, Tcl_Obj *data) {
-  MaskMap_Value *mm= map.mm;
-  MaskMap_Entry new, *fragment;
-  MaskMap_Entry *breaking, *replacements;
+  AddrMap_Value *am= map.am;
+  AddrMap_Entry new, *fragment;
+  AddrMap_Entry *breaking, *replacements;
   int rc, insertat, findend, cmp, nreplacements, new_used;
-  struct mm_amend_aroundsmall_u u;
+  struct am_amend_aroundsmall_u u;
 
-  mme_init(&new);
+  ame_init(&new);
   
-  rc= mme_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
+  rc= ame_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
 
-  sr= mm_search(mm, &new, &searched);
+  sr= am_search(am, &new, &searched);
 
   replacements= &new;
   nreplacements= 1;
@@ -283,13 +236,13 @@ int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
     break;
 
   case sr_aroundsmall:
-    u.mme= new;
+    u.ame= new;
     u.sign= -1;
-    replace_start= mm_binarychop(mm, 0, searched, &u,
-                                mm_amend_aroundsmall_binchoptest, &dummy);
+    replace_start= am_binarychop(am, 0, searched, &u,
+                                am_amend_aroundsmall_binchoptest, &dummy);
     u.sign= +1;
-    replace_end= mm_binarychop(mm, searched+1, mm.used, &u,
-                                mm_amend_aroundsmall_binchoptest, &dummy);
+    replace_end= am_binarychop(am, searched+1, am.used, &u,
+                                am_amend_aroundsmall_binchoptest, &dummy);
     break;
 
   case sr_inbig:
@@ -306,7 +259,7 @@ int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
      * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
      */
 
-    breaking= &mm.entries[searched];
+    breaking= &am.entries[searched];
     nreplacements= new.prefix - breaking->prefixlen + 1;
     replacements= TALLOC(sizeof(*replacements) * nreplacements);
 
@@ -320,12 +273,12 @@ int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
       fragment->prefixlen= fragmentlen;
       fragment->prefix= TALLOC(fragmentbytes);
       memcpy(fragment->prefix, new.prefix, fragmentbytes);
-      mme_clear_unwanted(fragment, fragmentbytes);
+      ame_clear_unwanted(fragment, fragmentbytes);
 
       fragment->prefix[fragmentbytes] ^=
        0x80u >> ((fragmentlen+7) & 7);
 
-      switch (mme_compare(&fragment, &new)) {
+      switch (ame_compare(&fragment, &new)) {
       case -2:  replacements[left_insert++]=  fragment;  break;
       case +2:  replacements[--right_insert]= fragment;  break;
       default: abort();
@@ -333,17 +286,17 @@ int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
     }
     assert(left_insert == right_insert-1);
     replacements[left_insert]= new;
-    mme_init(&new);
+    ame_init(&new);
 
     replace_end= searched+1;
     break;
 
   }
 
-  new_used= mm.used - (replace_end - replace_start) + nreplacements;
+  new_used= am.used - (replace_end - replace_start) + nreplacements;
 
-  if (new_used > mm.space)
-    mm_reallocentries(mm, new_used * 2);
+  if (new_used > am.space)
+    am_reallocentries(am, new_used * 2);
 
   for (scan=replacements, i=0;
        i < nreplacements;
@@ -352,26 +305,26 @@ int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
     Tcl_IncrRefCount(scan->data);
   }
 
-  for (i= replace_start, scan= mm.entries+i;
+  for (i= replace_start, scan= am.entries+i;
        i < replace_end;
        i++, scan++) {
-    mme_free(scan);
+    ame_free(scan);
   }
 
-  memmove(mm.entries + replace_start + nreplacements,
-         mm.entries + replace_end,
-         sizeof(*mm.entries) * (mm.used - replace_end));
+  memmove(am.entries + replace_start + nreplacements,
+         am.entries + replace_end,
+         sizeof(*am.entries) * (am.used - replace_end));
 
-  memcpy(mm.entries + replace_start,
+  memcpy(am.entries + replace_start,
         replacements,
-        sizeof(*mm.entries) * nreplacements);
+        sizeof(*am.entries) * nreplacements);
 
-  mm.used= new_used;
+  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
-     * MaskMap_Value. */
+     * AddrMap_Value. */
     TFREE(replacements);
 
   return TCL_OK;
@@ -379,33 +332,33 @@ int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
 
 /*---------- other substantial operations on mask maps ----------*/
 
-int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip,
+int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip,
                      Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
                      Tcl_Obj **result) {
-  MaskMap_Value *mm= (void*)&mapo->internalRep;
+  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= mm_search(mm, addr, addrbits, &place);
+  sr= am_search(am, addr, addrbits, &place);
 
   switch (sr) {
 
   case sr_notfound:
-    if (!def) return staticerr(ip, "address not found in mask-map",
-                              "HBYTES MASKMAP NOMATCH");
+    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 MASKMAP UNDERRUN");
+                    "HBYTES ADDRMAP UNDERRUN");
 
   case sr_exact:
   case sr_inbig:
-    *result= mm.entres[place].data;
+    *result= am.entres[place].data;
     break;
     
   }
@@ -415,128 +368,3 @@ int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip,
 
 /*---------- Tcl type and arg parsing functions ----------*/
 
-int pat_maskmapv(Tcl_Interp *ip, Tcl_Obj *var, MaskMap_Var *agg) {
-  int rc;
-  rc= pat_somethingv(ip,var,&agg->sth,&maskmap_type);  if (rc) return rc;
-  agg->mm= (void*)&agg->sth.obj->internalRep;
-  return TCL_OK;
-}
-
-static void maskmap_t_free(Tcl_Obj *o) {
-  MaskMap_Value *mm= (void*)&o->internalRep;
-  MaskMap_Entry *mme;
-  int i;
-  
-  for (i=0, mme=mm->entries; i<mm->used; i++, mme++) {
-    if (mme->prefixlen==-1) break;
-    mme_free(mme);
-  }
-}
-
-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 i, nbytes;
-
-  assert(sob->typePtr == &maskmap_type);
-  objfreeir(dob);
-
-  mm_init(dm);
-  mm_reallocentries(dm,sm->used);
-  dm->used= sm->used;
-  for (i=0, sme=sm->entries, dme=dm->entries;
-       i < dm->used;
-       i++, sme++, dme++) {
-    *dme= *sme;
-    nbytes= prefix_bytes(sme->prefixlen);
-    dme->prefix= TALLOC(nbytes);  assert(dme->prefix);
-    memcpy(dme->prefix, sme->prefix, nbytes);
-    Tcl_IncrRefCount(dme->data);
-  }
-  dob->typePtr= &maskmap_type;
-}
-
-static void maskmap_t_ustr(Tcl_Obj *so) {
-  MaskMap_Value *sm= (void*)&so->internalRep;
-  Tcl_Obj **mainlobjsl, *mainobj;
-  int i;
-
-  assert(so->typePtr == &maskmap_type);
-  mainlobjsl= TALLOC(sizeof(*mainlobjsl) * sm->used);  assert(mainlobjsl);
-
-  for (i=0; i<sm->used; i++) {
-    MaskMap_Entry *sme= &sm->entries[i];
-    HBytes_Value hb;
-    Tcl_Obj *subl[3], *sublo;
-
-    hbytes_array(&hb, sme->prefix, prefix_bytes(sme->prefixlen));
-    subl[0]= ret_hb(0, hb);  assert(subl[0]);
-    subl[1]= Tcl_NewIntObj(sme->prefixlen);  assert(subl[1]);
-    subl[2]= sme->data;
-    
-    sublo= Tcl_NewListObj(3,subl);  assert(sublo);
-    mainlobjsl[i]= sublo;
-  }
-
-  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 */
-}
-
-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);
-  
-  rc= Tcl_ListObjLength(ip,o,&len);  if (rc) goto x_rc;
-  mm_reallocentries(&mm, len);
-  
-  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) {
-      rc= staticerr(ip, "mask-map entry length != 3",
-                   "HBYTES MASKMAP SYNTAX LLENGTH");
-      goto x_rc;
-    }
-    rc= Tcl_ListObjIndex(ip,eo,0,&prefixo);  if (rc) goto x_rc;
-    rc= Tcl_ListObjIndex(ip,eo,1,&prefixleno);  if (rc) goto x_rc;
-    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, mme, prefixo, prefixleno, 1);
-    if (rc) goto x_rc;
-
-    mm->used++;
-
-    if (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;
-      }
-    }
-  }
-
-  /* we commit now */
-  assert(sizeof(mm) <= sizeof(o->internalRep));
-  objfreeir(o);
-  memcpy(&o->internalRep, &mm, sizeof(mm));
-  o->typePtr= &maskmap_type;
-  return TCL_OK;
-
-x_rc:
-  for (mme=mm.entries, i=0; i<mm.used; i++, mme++)
-    mme_free(mme);
-  TFREE(mm.entries);
-  return rc;
-}
-
-Tcl_ObjType maskmap_type = {
-  "mask-map",
-  maskmap_t_free, maskmap_t_dup, maskmap_t_ustr, maskmap_t_sfa
-};