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