X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=maskmap%2Fmaskmap.c;h=1a176818642d672626a3a7920c9566263a61497b;hb=eef51b4e49bda639a2f4e871b4d8ac00a0988103;hp=bb1e258756626fcc53eb273ef1e538bb461cd52c;hpb=d55fe169a327a1a3352ed88587c8f52907e2301d;p=chiark-tcl.git
diff --git a/maskmap/maskmap.c b/maskmap/maskmap.c
index bb1e258..1a17681 100644
--- a/maskmap/maskmap.c
+++ b/maskmap/maskmap.c
@@ -1,176 +1,389 @@
/*
+ * maskmap - Tcl extension for address mask map data structures
+ * Copyright 2006-2012 Ian Jackson
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this library; if not, see .
*/
-#include "tables.h"
-#include "hbytes.h"
+#include "chiark_tcl_hbytes.h"
-typedef struct {
- int prefixlen; /* there may be some empty slots with prefixlen==-1 at end */
- Byte *prefix; /* ceil(prefixlen/8) bytes */
- Tcl_Obj *data;
-} MaskMap_Entry;
+/*---------- operations on AddrMap_Entry ----------*/
-struct MaskMap_Value {
- int allocd;
- MaskMap_Entry *entries;
-}; /* overlays internalRep */
-
-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 ame_init(AddrMap_Entry *ame) {
+ ame->prefixlen= -1;
+ ame->prefix= 0;
+ ame->data= 0;
}
-int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
- MaskMap_Var map, HBytes_Value prefix,
- int preflen, Tcl_Obj *data) {
- return TCL_OK;
+static unsigned ame_clear_unwanted(AddrMap_Entry *ame, int bytes) {
+ /* returns non-0 iff some bits were cleared */
+ int sparebits;
+ unsigned result, sparemask;
+ Byte *datap;
+
+ sparebits= bytes * 8 - ame->prefixlen;
+ if (!sparebits) return 0;
+
+ sparemask= (1u << sparebits) - 1;
+ datap= &ame->prefix[bytes-1];
+
+ result= *datap & sparemask;
+ *datap &= ~sparemask;
+
+ return result;
}
-int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip,
- MaskMap_Var map, HBytes_Value addr, Tcl_Obj *def,
- Tcl_Obj **result) {
+static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame,
+ Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
+ int inmap) {
+ /* *ame should be blank entry; after exit (even error exit) it will be valid
+ * - on errors, it will be blank. inmap is 1 if we're parsing an existing
+ * map or 0 if it's an entry to be added or modified. */
+ HBytes_Value prefix;
+ int suppliedprefixbytes, prefixbits, wantprefixbytes;
+ const Byte *data;
+ int rc;
+
+ hbytes_empty(&prefix);
+
+ rc= pat_hb(ip,prefixo,&prefix); if (rc) goto x_rc;
+ rc= pat_int(ip,prefixbitso,&prefixbits); if (rc) goto x_rc;
+
+ wantprefixbytes= prefix_bytes(prefixbits);
+ suppliedprefixbytes= hbytes_len(&prefix);
+
+ if (suppliedprefixbytes < wantprefixbytes) {
+ rc= staticerr(ip, "addr-map entry PREFIX too short for PREFIX-LEN",
+ "HBYTES ADDRMAP SYNTAX UNDERRUN");
+ goto x_rc;
+ }
+ if (inmap && suppliedprefixbytes > wantprefixbytes) {
+ rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN",
+ "HBYTES ADDRMAP SYNTAX OVERRUN");
+ goto x_rc;
+ }
+
+ ame->prefixlen= prefixbits;
+ ame->prefix= TALLOC(wantprefixbytes); assert(ame->prefix);
+ memcpy(ame->prefix, data, wantprefixbytes);
+
+ if (ame_clear_unwanted(ame, wantprefixbytes)) {
+ rc= staticerr(ip, "addr-map entry PREFIX contains bits excluded"
+ " by PREFIX-LEN", "HBYTES ADDRMAP SYNTAX EXCLBITS");
+ goto x_rc;
+ }
+
return TCL_OK;
-}
-static int prefix_bytes (int prefixlen) {
- return (prefixlen + 7)/8;
+ x_rc:
+ ame_free(ame);
+ return rc;
}
-static void mme_init(MaskMap_Entry *mme) {
- mme->prefix= 0;
- mme->data= 0;
-}
+static int ame_contains(const AddrMap_Entry *ref, const Byte *addr, int len) {
+ int directbytes, leftoverbits;
+
+ assert(len >= ref->prefixlen);
+
+ directbytes= ref->prefixlen / 8;
+ if (memcmp(ref->prefix, addr, directbytes)) return 0;
-static int mm_count(const MaskMap_Value *mm) {
- int i;
- for (i=0; iallocd && sm->entries[i].prefixlen != -1; i++);
- return i;
-}
+ leftoverbits= ref->prefixlen % 8;
+ if (leftoverbits)
+ if ((addr[directbytes] & (0xffu << leftoverbits))
+ != search->prefix[directbytes])
+ return 0;
+
+ return 1;
+}
-static void mm_allocentries(MaskMap_Value *mm, int len) {
- int i;
- mm->allocd= len;
- mm->entries= Tcl_Alloc(sizeof(*mm->entries) * len);
- assert(mm->entries);
- for (i=0; i < len; i++)
- mme_init(&mm->entries[i]);
+static int ame_compare(const AddrMap_Entry *a, const AddrMap_Entry *b) {
+ /* +2 = a covers later range of address space than b
+ * +1 = a wholly contains but is not equal to b
+ * 0 = a is identical to b
+ * -1 = b wholly contains but is not equal to a
+ * -2 = b covers later range of address space than a
+ */
+ int al= a->prefixlen;
+ int bl= b->prefixlen;
+ int ml, d;
+
+ if (al==bl) { ml=al; }
+ else if (alprefix,bl)) return +1; }
+ else if (blprefix,al)) return -1; }
+
+ d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
+ return (d > 0 ? +2 :
+ d < 0 ? -2 :
+ 0);
}
+
+/*---------- searching maps ----------*/
+
+typedef enum {
+ sr_notfound,
+ sr_exact,
+ sr_inbig,
+ sr_aroundsmall
+} Search_Result;
+
+static int
+am_binarychop(AddrMap_Value *am, int low_oreq, int high_strict, void *u,
+ int (*test)(AddrMap_Entry *am, void *u) /* -ve => look left */,
+ int *found_r) {
+ int mid, cmp;
-static void maskmap_t_free(Tcl_Obj *o) {
- MaskMap_Value *mm= (void*)&o->internalRep;
- for (i=0; ientries[mid], u);
+
+ if (!cmp) {
+ *found_r= 1;
+ return mid;
+ }
+
+ if (cmp < 0)
+ high_strict= mid;
+ else
+ low_oreq= mid+1;
}
}
-static void maskmap_t_dup(Tcl_Obj *so, Tcl_Obj *do) {
- MaskMap_Value *sm= (void*)&so->internalRep;
- MaskMap_Value *dm= (void*)&do->internalRep;
- int l, i, nbytes;
-
- assert(so->typePtr == &maskmap_type);
- objfreeir(do);
- l= mm_count(&sm);
-
- mm_allocentries(&dm,l);
- for (i=0, sme=sm->entries, dme=dm->entries;
- iallocd;
- i++, sme++, dme++) {
- *dme= *sme;
- nbytes= prefix_bytes(sme->prefixlen);
- dme->prefix= Tcl_Alloc(nbytes); assert(dme->prefix);
- memcpy(dme->prefix, sme->prefix, nbytes);
- Tcl_IncrRefCount(dme->data);
+struct am_search_u {
+ int forbid_aroundsmall;
+ AddrMap_Entry proposed;
+ Search_Result sr;
+};
+
+static int
+am_search_binchoptest(AddrMap_Entry *ame, void *u_v) {
+ struct am_search_u *u= u_v;
+ int cmp;
+
+ cmp= ame_compare(&u.proposed, ame);
+ switch (cmp) {
+ case -1: u->sr= sr_inbig; return 0;
+ case 0: u->sr= sr_exact; return 0;
+ case +1: u->sr= sr_aroundsmall; return 0;
+ default: return cmp;
}
}
-static void maskmap_t_ustr(Tcl_Obj *so) {
- MaskMap_Value *sm= (void*)&so->internalRep;
- Tcl_Obj **mainlobjsl, *mainobj;
- char *string;
- int stringl;
-
- assert(so->typePtr == &maskmap_type);
- l= mm_count(sm);
- mainlobjsl= Tcl_Alloc(sizeof(*mainobjsl) * l); assert(mainlobjsl);
-
- for (i=0; ientries[i];
- HBytes_Value hb;
- Tcl_Obj *subl[3], *sublo;
-
- hbytes_array(&hb, sme->prefix, prefix_bytes(sme->prefixlen));
- subl[0]= ret_hb(ip, &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;
- }
+static Search_Result
+am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) {
+ int place, found;
+ struct am_search_u u;
- mainobj= Tcl_NewListObj(l,mainlobjsl); assert(mainobj);
- so->bytes= Tcl_GetStringFromObj(mainobj, &so->length); assert(so->bytes);
- mainobj->bytes= 0; mainobj->length= 0; /* we stole it */
+ u.forbid_aroundsmall= forbid_aroundsmall;
+ u.proposed= proposed;
+ u.sr= sr_notfound;
+
+ *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found);
+
+ assert(!!found == (u.sr != sr_notfound));
+ return u.sr;
}
-static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
- int len, eol;
- MaskMap_Value mm;
+/*---------- useful operations on AddrMap_Value etc. ----------*/
- mm.allocd= 0;
- mm.entries= 0;
-
- rc= Tcl_ListObjLength(ip,o,&len); if (rc) goto x_rc;
- mm_allocentries(len);
+/*---------- amendment (complex algorithm) ----------*/
+
+struct am_amend_aroundsmall_u {
+ AddrMap_Entry *new;
+ int sign;
+};
+
+
+static int
+am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) {
+ struct am_amend_aroundsmall_u *u= u_v;
+
+ cmp= u->sign * ame_compare(search, u->new);
+
+ switch (cmp) {
+ case +2: return -u->sign;
+ case +1: return +u->sign;
+ default: abort();
+ }
+}
+
+int do_addrmap_amend(ClientData cd, Tcl_Interp *ip,
+ AddrMap_Var map, Tcl_Obj *prefix,
+ Tcl_Obj *preflen, Tcl_Obj *data) {
+ AddrMap_Value *am= map.am;
+ AddrMap_Entry new, *fragment;
+ AddrMap_Entry *breaking, *replacements;
+ int rc, insertat, findend, cmp, nreplacements, new_used;
+ struct am_amend_aroundsmall_u u;
+
+ ame_init(&new);
- for (i=0; i0) {
- if (mme_compare(&mm.entries[i-1], &mm.entries[i]) <= 0) {
- rc= staticerr(ip, "mask-map entries out of order");
- goto x_rc;
+ rc= ame_parsekey(ip,&new,prefix,preflen,0); if (rc) return rc;
+
+ sr= am_search(am, &new, &searched);
+
+ replacements= &new;
+ nreplacements= 1;
+ replace_start= searched;
+ replace_end= searched;
+
+ switch (sr) {
+
+ case sr_notfound:
+ break;
+
+ case sr_exact:
+ replace_end= searched+1;
+ break;
+
+ case sr_aroundsmall:
+ u.ame= new;
+ u.sign= -1;
+ replace_start= am_binarychop(am, 0, searched, &u,
+ am_amend_aroundsmall_binchoptest, &dummy);
+ u.sign= +1;
+ replace_end= am_binarychop(am, searched+1, am.used, &u,
+ am_amend_aroundsmall_binchoptest, &dummy);
+ break;
+
+ case sr_inbig:
+ /* Urgh, we need to break it up. This produces
+ * - innermost prefix (the new one) as specified
+ * - one for each bitlength
+ * <= innermost
+ * > outermost (the existing one)
+ * each one specifying the outermost prefix plus zero, one,
+ * two, etc. bits of the innermost followed by one bit
+ * opposite to the innermost, with the outermost's data
+ * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B
+ * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ...
+ * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
+ */
+
+ breaking= &am.entries[searched];
+ nreplacements= new.prefix - breaking->prefixlen + 1;
+ fixme check integer overflow ^
+ replacements= TALLOC(sizeof(*replacements) * nreplacements);
+
+ for (fragmentlen= breaking->prefixlen + 1,
+ left_insert= 0, right_insert= nreplacements;
+ fragmentlen <= new.prefix;
+ fragmentlen++) {
+ int fragmentbytes;
+
+ fragmentbytes= prefix_bytes(fragmentlen)
+ fragment->prefixlen= fragmentlen;
+ fragment->prefix= TALLOC(fragmentbytes);
+ memcpy(fragment->prefix, new.prefix, fragmentbytes);
+ ame_clear_unwanted(fragment, fragmentbytes);
+
+ fragment->prefix[fragmentbytes] ^=
+ 0x80u >> ((fragmentlen+7) & 7);
+
+ switch (ame_compare(&fragment, &new)) {
+ case -2: replacements[left_insert++]= fragment; break;
+ case +2: replacements[--right_insert]= fragment; break;
+ default: abort();
}
}
+ assert(left_insert == right_insert-1);
+ replacements[left_insert]= new;
+ ame_init(&new);
+
+ replace_end= searched+1;
+ break;
+
}
- /* we commit now */
- assert(sizeof(mm) <= sizeof(o.internalRep));
- objfreeir(o);
- memcpy(&o.internalRep, &mm, sizeof(mm));
- o.typePtr= &maskmap_type;
- return TCL_OK;
+ new_used= am.used - (replace_end - replace_start) + nreplacements;
-x_rc:
- if (mm.entries) {
- for (i=0; i am.space)
+ am_reallocentries(am, new_used * 2);
+
+ for (scan=replacements, i=0;
+ i < nreplacements;
+ scan++, i++) {
+ scan->data= data;
+ Tcl_IncrRefCount(scan->data);
}
- return rc;
+
+ for (i= replace_start, scan= am.entries+i;
+ i < replace_end;
+ i++, scan++) {
+ ame_free(scan);
+ }
+
+ memmove(am.entries + replace_start + nreplacements,
+ am.entries + replace_end,
+ sizeof(*am.entries) * (am.used - replace_end));
+
+ memcpy(am.entries + replace_start,
+ replacements,
+ sizeof(*am.entries) * nreplacements);
+
+ am.used= new_used;
+ if (replacements != &new)
+ /* we don't bother freeing the actual array elements because
+ * if replacements!=&new the array is only full if we're
+ * committed and have already copied the values into the actual
+ * AddrMap_Value. */
+ TFREE(replacements);
+
+ return TCL_OK;
}
- { free(mm.e
- return rc;
- rc= Tcl_ConvertToType(ip,o,
+/*---------- other substantial operations on mask maps ----------*/
+
+int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip,
+ Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
+ Tcl_Obj **result) {
+ AddrMap_Value *am= (void*)&mapo->internalRep;
+ const Byte *addr= hbytes_data(&addrhb);
+ int addrbytes= hbytes_len(&addrhb);
+ int i, addrbits, place;
+ Search_Result sr;
+
+ addrbits= addrbytes * 8;
+ sr= am_search(am, addr, addrbits, &place);
+
+ switch (sr) {
+
+ case sr_notfound:
+ if (!def) return staticerr(ip, "address not found in addr-map",
+ "HBYTES ADDRMAP NOMATCH");
+ *result= def;
+ break;
+
+ case sr_aroundsmall:
+ return staticerr(ip, "address shorter than mask in map",
+ "HBYTES ADDRMAP UNDERRUN");
+
+ case sr_exact:
+ case sr_inbig:
+ *result= am.entres[place].data;
+ break;
+
+ }
+
+ return TCL_OK;
}
-Tcl_ObjType maskmap_type = {
- "mask-map",
- maskmap_t_free, maskmap_t_dup, maskmap_t_ustr, maskmap_t_sfa
-};
+/*---------- Tcl type and arg parsing functions ----------*/
+