X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=maskmap%2Fmaskmap.c;h=ea2a690b6f4f4a1e78ef92497040493d9de76518;hb=f16e3e0cf0a2b965643df01e24ef59e1393da78d;hp=7e6bcf04f4c961518c39c8412aec14fd90d9d51f;hpb=bf917064c5edc75fdd84371f53e7cef51ff05510;p=chiark-tcl.git diff --git a/maskmap/maskmap.c b/maskmap/maskmap.c index 7e6bcf0..ea2a690 100644 --- a/maskmap/maskmap.c +++ b/maskmap/maskmap.c @@ -1,52 +1,27 @@ /* */ -#include +#include "chiark_tcl_hbytes.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 +29,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 +49,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 +93,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 +105,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 +124,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 +137,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 +151,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 +172,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 +209,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 +239,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 +262,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 +276,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 +289,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 +308,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 +335,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 +371,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