From 86a68f7c8f058dcc55ee136da67c3e0c7030474d Mon Sep 17 00:00:00 2001 From: ian Date: Tue, 28 Dec 2004 00:08:11 +0000 Subject: [PATCH] working on new addrmap instead of maskmap - compiles, but have not yet implemented amend etc. --- base/chiark-tcl.h | 52 +++--- base/hook.c | 8 +- base/tables-examples.tct | 25 +-- base/troglodyte-Makefile | 2 +- hbytes/hbytes.h | 52 +++--- hbytes/hook.c | 8 +- maskmap/addrmap.c | 305 ++++++++++++++++++++++++++++++++++++ maskmap/maskmap.c | 330 ++++++++++----------------------------- 8 files changed, 464 insertions(+), 318 deletions(-) create mode 100644 maskmap/addrmap.c diff --git a/base/chiark-tcl.h b/base/chiark-tcl.h index b4fcfb8..206f97e 100644 --- a/base/chiark-tcl.h +++ b/base/chiark-tcl.h @@ -65,26 +65,31 @@ * 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 * @@ -99,13 +104,12 @@ * 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 */ diff --git a/base/hook.c b/base/hook.c index b65741f..5b163b3 100644 --- a/base/hook.c +++ b/base/hook.c @@ -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/base/tables-examples.tct b/base/tables-examples.tct index 8a28c4f..7ce5dc7 100644 --- a/base/tables-examples.tct +++ b/base/tables-examples.tct @@ -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 diff --git a/base/troglodyte-Makefile b/base/troglodyte-Makefile index ea2c10c..e458511 100644 --- a/base/troglodyte-Makefile +++ b/base/troglodyte-Makefile @@ -16,7 +16,7 @@ OBJS= tables.o \ algtables.o \ crypto.o \ parse.o \ - maskmap.o + addrmap.o HDRS= hbytes.h \ $(AUTO_HDRS) diff --git a/hbytes/hbytes.h b/hbytes/hbytes.h index b4fcfb8..206f97e 100644 --- a/hbytes/hbytes.h +++ b/hbytes/hbytes.h @@ -65,26 +65,31 @@ * 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 * @@ -99,13 +104,12 @@ * 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 */ diff --git a/hbytes/hook.c b/hbytes/hook.c index b65741f..5b163b3 100644 --- a/hbytes/hook.c +++ b/hbytes/hook.c @@ -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 index 0000000..2eb4898 --- /dev/null +++ b/maskmap/addrmap.c @@ -0,0 +1,305 @@ +/* + */ + +#include + +#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; iused; 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; entnumused; 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 +}; diff --git a/maskmap/maskmap.c b/maskmap/maskmap.c index 7e6bcf0..ee9ce4c 100644 --- a/maskmap/maskmap.c +++ b/maskmap/maskmap.c @@ -1,52 +1,24 @@ -/* - */ -#include -#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 (alprefix,bl)) return +1; } - else if (blprefix,al)) return -1; } + else if (alprefix,bl)) return +1; } + else if (blprefix,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; iused; 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; iused; 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