chiark / gitweb /
mask-map nonoverlapping representation - wip (needs compile errors fixing and debuggi...
[chiark-tcl.git] / maskmap / maskmap.c
1 /*
2  */
3
4 #include <string.h>
5
6 #include "tables.h"
7 #include "hbytes.h"
8
9 typedef struct {
10   int prefixlen; /* there may be some empty slots with prefixlen==-1 at end */
11   Byte *prefix; /* ceil(prefixlen/8) bytes */
12   Tcl_Obj *data;
13 } MaskMap_Entry;
14
15 struct MaskMap_Value {
16   int used, space;
17   MaskMap_Entry *entries;
18 }; /* overlays internalRep */
19
20 /*---------- useful stuff ----------*/
21
22 static int prefix_bytes (int prefixlen) {
23   return (prefixlen + 7)/8;
24 }
25
26 /*---------- operations on MaskMap_Entry ----------*/
27
28 static void mme_init(MaskMap_Entry *mme) {
29   mme->prefixlen= -1;
30   mme->prefix= 0;
31   mme->data= 0;
32 }
33
34 static void mme_free(MaskMap_Entry *mme) {
35   TFREE(mme->prefix);  mme->prefix=0;
36   if (mme->data) { Tcl_DecrRefCount(mme->data); mme->data=0; }
37 }
38
39 static unsigned mme_clear_unwanted(MaskMap_Entry *mme, int bytes) {
40   /* returns non-0 iff some bits were cleared */
41   int sparebits;
42   unsigned result, sparemask;
43   Byte *datap;
44
45   sparebits= bytes * 8 - mme->prefixlen;
46   if (!sparebits) return 0;
47
48   sparemask= (1u << sparebits) - 1;
49   datap= &mme->prefix[bytes-1];
50
51   result= *datap & sparemask;
52   *datap &= ~sparemask;
53
54   return result;
55 }
56
57 static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme,
58                         Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
59                         int inmap) {
60  /* *mme should be blank entry; after exit (even error exit) it will be valid
61   * - on errors, it will be blank.  inmap is 1 if we're parsing an existing
62   * map or 0 if it's an entry to be added or modified. */
63   HBytes_Value prefix;
64   int suppliedprefixbytes, prefixbits, wantprefixbytes;
65   const Byte *data;
66   int rc;
67
68   hbytes_empty(&prefix);
69   
70   rc= pat_hb(ip,prefixo,&prefix);  if (rc) goto x_rc;
71   rc= pat_int(ip,prefixbitso,&prefixbits);  if (rc) goto x_rc;
72
73   wantprefixbytes= prefix_bytes(prefixbits);
74   suppliedprefixbytes= hbytes_len(&prefix);
75
76   if (suppliedprefixbytes < wantprefixbytes) {
77     rc= staticerr(ip, "mask-map entry PREFIX too short for PREFIX-LEN",
78                   "HBYTES MASKMAP SYNTAX UNDERRUN");
79     goto x_rc;
80   }
81   if (inmap && suppliedprefixbytes > wantprefixbytes) {
82     rc= staticerr(ip, "mask-map existing entry PREFIX too long for PREFIX-LEN",
83                   "HBYTES MASKMAP SYNTAX OVERRUN");
84     goto x_rc;
85   }
86
87   mme->prefixlen= prefixbits;
88   mme->prefix= TALLOC(wantprefixbytes);  assert(mme->prefix);
89   memcpy(mme->prefix, data, wantprefixbytes);
90
91   if (mme_clear_unwanted(mme, wantprefixbytes)) {
92     rc= staticerr(ip, "mask-map entry PREFIX contains bits excluded"
93                   " by PREFIX-LEN", "HBYTES MASKMAP SYNTAX EXCLBITS");
94     goto x_rc;
95   }
96
97   return TCL_OK;
98
99  x_rc:
100   mme_free(mme);
101   return rc;
102 }
103
104 static int mme_contains(const MaskMap_Entry *ref, const Byte *addr, int len) {
105   int directbytes, leftoverbits;
106   
107   assert(len >= ref->prefixlen);
108   
109   directbytes= ref->prefixlen / 8;
110   if (memcmp(ref->prefix, addr, directbytes)) return 0;
111
112   leftoverbits= ref->prefixlen % 8;
113   if (leftoverbits)
114     if ((addr[directbytes] & (0xffu << leftoverbits))
115         != search->prefix[directbytes])
116       return 0;
117
118   return 1;
119 }  
120
121 static int mme_compare(const MaskMap_Entry *a, const MaskMap_Entry *b) {
122   /*    +2 =    a   covers later range of address space than  b
123    *    +1 =    a   wholly contains but is not equal to       b
124    *     0 =    a   is identical to                           b
125    *    -1 =    b   wholly contains but is not equal to       a
126    *    -2 =    b   covers later range of address space than  a
127    */
128   int al= a->prefixlen;
129   int bl= b->prefixlen;
130   int ml, d;
131
132   if (al==bl) { ml=al; }
133   else if (al<bl) { ml=al; if (mme_contains(a,b->prefix,bl)) return +1; }
134   else if (bl<al) { ml=bl; if (mme_contains(b,a->prefix,al)) return -1; }
135
136   d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
137   return (d > 0 ? +2 :
138           d < 0 ? -2 :
139           0);
140 }
141
142 /*---------- searching maps ----------*/
143
144 typedef enum {
145   sr_notfound,
146   sr_exact,
147   sr_inbig,
148   sr_aroundsmall
149 } Search_Result;
150
151 static int
152 mm_binarychop(MaskMap_Value *mm, int low_oreq, int high_strict, void *u,
153               int (*test)(MaskMap_Entry *mm, void *u) /* -ve => look left */,
154               int *found_r) {
155   int mid, cmp;
156   
157   for (;;) {
158     if (high_strict <= low_oreq) {
159       assert(high_strict == low_oreq);
160       *found_r= 0;
161       return high_strict;
162     }
163
164     mid= (high_strict + low_oreq) / 2;
165     cmp= test(&mm->entries[mid], u);
166
167     if (!cmp) {
168       *found_r= 1;
169       return mid;
170     }
171
172     if (cmp < 0)
173       high_strict= mid;
174     else
175       low_oreq= mid+1;
176   }
177 }
178
179 struct mm_search_u {
180   int forbid_aroundsmall;
181   MaskMap_Entry proposed;
182   Search_Result sr;
183 };
184
185 static int
186 mm_search_binchoptest(MaskMap_Entry *mme, void *u_v) {
187   struct mm_search_u *u= u_v;
188   int cmp;
189
190   cmp= mme_compare(&u.proposed, mme);
191   switch (cmp) {
192   case -1:  u->sr= sr_inbig;        return  0;
193   case  0:  u->sr= sr_exact;        return  0;
194   case +1:  u->sr= sr_aroundsmall;  return  0;
195   default:                          return cmp;
196   }
197 }
198
199 static Search_Result
200 mm_search(MaskMap_Value *mm, const MaskMap_Entry *proposed, int *place_r) {
201   int place, found;
202   struct mm_search_u u;
203
204   u.forbid_aroundsmall= forbid_aroundsmall;
205   u.proposed= proposed;
206   u.sr= sr_notfound;
207
208   *place_r= mm_binarychop(mm, 0, mm.used, &u, mm_search_binchoptest, &found);
209
210   assert(!!found == (u.sr != sr_notfound));
211   return u.sr;
212 }
213
214 /*---------- useful operations on MaskMap_Value etc. ----------*/
215
216 static void mm_init(MaskMap_Value *mm) {
217   mm->used= 0;
218   mm->space= 0;
219   mm->entries= 0;
220 }
221
222 static void mm_reallocentries(MaskMap_Value *mm, int len) {
223   MaskMap_Entry *newentries;
224
225   assert(len >= mm->space);
226   if (!len) return;
227
228   newentries= TREALLOC(mm->entries, sizeof(*newentries)*len);
229   assert(newentries);
230   
231   mm->space= len;
232   mm->entries= newentries;
233 }
234
235 /*---------- amendment (complex algorithm) ----------*/
236
237 struct mm_amend_aroundsmall_u {
238   MaskMap_Entry *new;
239   int sign;
240 };
241
242
243 static int
244 mm_amend_aroundsmall_binchoptest(MaskMap_Entry *search, void *u_v) {
245   struct mm_amend_aroundsmall_u *u= u_v;
246
247   cmp= u->sign * mme_compare(search, u->new);
248
249   switch (cmp) {
250   case +2:  return -u->sign;
251   case +1:  return +u->sign;
252   default:  abort();
253   }
254 }
255
256 int do_maskmap_amend(ClientData cd, Tcl_Interp *ip,
257                      MaskMap_Var map, Tcl_Obj *prefix,
258                      Tcl_Obj *preflen, Tcl_Obj *data) {
259   MaskMap_Value *mm= map.mm;
260   MaskMap_Entry new, *fragment;
261   MaskMap_Entry *breaking, *replacements;
262   int rc, insertat, findend, cmp, nreplacements, new_used;
263   struct mm_amend_aroundsmall_u u;
264
265   mme_init(&new);
266   
267   rc= mme_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
268
269   sr= mm_search(mm, &new, &searched);
270
271   replacements= &new;
272   nreplacements= 1;
273   replace_start= searched;
274   replace_end= searched;
275
276   switch (sr) {
277
278   case sr_notfound:
279     break;
280
281   case sr_exact:
282     replace_end= searched+1;
283     break;
284
285   case sr_aroundsmall:
286     u.mme= new;
287     u.sign= -1;
288     replace_start= mm_binarychop(mm, 0, searched, &u,
289                                  mm_amend_aroundsmall_binchoptest, &dummy);
290     u.sign= +1;
291     replace_end= mm_binarychop(mm, searched+1, mm.used, &u,
292                                  mm_amend_aroundsmall_binchoptest, &dummy);
293     break;
294
295   case sr_inbig:
296     /* Urgh, we need to break it up.  This produces
297      *   - innermost prefix (the new one) as specified
298      *   - one for each bitlength
299      *       <= innermost
300      *        > outermost (the existing one)
301      *     each one specifying the outermost prefix plus zero, one,
302      *     two, etc. bits of the innermost followed by one bit
303      *     opposite to the innermost, with the outermost's data
304      * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B
305      * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ...
306      * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
307      */
308
309     breaking= &mm.entries[searched];
310     nreplacements= new.prefix - breaking->prefixlen + 1;
311     replacements= TALLOC(sizeof(*replacements) * nreplacements);
312
313     for (fragmentlen= breaking->prefixlen + 1,
314            left_insert= 0, right_insert= nreplacements;
315          fragmentlen <= new.prefix;
316          fragmentlen++) {
317       int fragmentbytes;
318
319       fragmentbytes= prefix_bytes(fragmentlen)
320       fragment->prefixlen= fragmentlen;
321       fragment->prefix= TALLOC(fragmentbytes);
322       memcpy(fragment->prefix, new.prefix, fragmentbytes);
323       mme_clear_unwanted(fragment, fragmentbytes);
324
325       fragment->prefix[fragmentbytes] ^=
326         0x80u >> ((fragmentlen+7) & 7);
327
328       switch (mme_compare(&fragment, &new)) {
329       case -2:  replacements[left_insert++]=  fragment;  break;
330       case +2:  replacements[--right_insert]= fragment;  break;
331       default: abort();
332       }
333     }
334     assert(left_insert == right_insert-1);
335     replacements[left_insert]= new;
336     mme_init(&new);
337
338     replace_end= searched+1;
339     break;
340
341   }
342
343   new_used= mm.used - (replace_end - replace_start) + nreplacements;
344
345   if (new_used > mm.space)
346     mm_reallocentries(mm, new_used * 2);
347
348   for (scan=replacements, i=0;
349        i < nreplacements;
350        scan++, i++) {
351     scan->data= data;
352     Tcl_IncrRefCount(scan->data);
353   }
354
355   for (i= replace_start, scan= mm.entries+i;
356        i < replace_end;
357        i++, scan++) {
358     mme_free(scan);
359   }
360
361   memmove(mm.entries + replace_start + nreplacements,
362           mm.entries + replace_end,
363           sizeof(*mm.entries) * (mm.used - replace_end));
364
365   memcpy(mm.entries + replace_start,
366          replacements,
367          sizeof(*mm.entries) * nreplacements);
368
369   mm.used= new_used;
370   if (replacements != &new)
371     /* we don't bother freeing the actual array elements because
372      * if replacements!=&new the array is only full if we're
373      * committed and have already copied the values into the actual
374      * MaskMap_Value. */
375     TFREE(replacements);
376
377   return TCL_OK;
378 }
379
380 /*---------- other substantial operations on mask maps ----------*/
381
382 int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip,
383                       Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
384                       Tcl_Obj **result) {
385   MaskMap_Value *mm= (void*)&mapo->internalRep;
386   const Byte *addr= hbytes_data(&addrhb);
387   int addrbytes= hbytes_len(&addrhb);
388   int i, addrbits, place;
389   Search_Result sr;
390
391   addrbits= addrbytes * 8;
392   sr= mm_search(mm, addr, addrbits, &place);
393
394   switch (sr) {
395
396   case sr_notfound:
397     if (!def) return staticerr(ip, "address not found in mask-map",
398                                "HBYTES MASKMAP NOMATCH");
399     *result= def;
400     break;
401
402   case sr_aroundsmall:
403     return staticerr(ip, "address shorter than mask in map",
404                      "HBYTES MASKMAP UNDERRUN");
405
406   case sr_exact:
407   case sr_inbig:
408     *result= mm.entres[place].data;
409     break;
410     
411   }
412
413   return TCL_OK;
414 }
415
416 /*---------- Tcl type and arg parsing functions ----------*/
417
418 int pat_maskmapv(Tcl_Interp *ip, Tcl_Obj *var, MaskMap_Var *agg) {
419   int rc;
420   rc= pat_somethingv(ip,var,&agg->sth,&maskmap_type);  if (rc) return rc;
421   agg->mm= (void*)&agg->sth.obj->internalRep;
422   return TCL_OK;
423 }
424
425 static void maskmap_t_free(Tcl_Obj *o) {
426   MaskMap_Value *mm= (void*)&o->internalRep;
427   MaskMap_Entry *mme;
428   int i;
429   
430   for (i=0, mme=mm->entries; i<mm->used; i++, mme++) {
431     if (mme->prefixlen==-1) break;
432     mme_free(mme);
433   }
434 }
435
436 static void maskmap_t_dup(Tcl_Obj *sob, Tcl_Obj *dob) {
437   MaskMap_Value *sm= (void*)&sob->internalRep;
438   MaskMap_Value *dm= (void*)&dob->internalRep;
439   MaskMap_Entry *sme, *dme;
440   int i, nbytes;
441
442   assert(sob->typePtr == &maskmap_type);
443   objfreeir(dob);
444
445   mm_init(dm);
446   mm_reallocentries(dm,sm->used);
447   dm->used= sm->used;
448   for (i=0, sme=sm->entries, dme=dm->entries;
449        i < dm->used;
450        i++, sme++, dme++) {
451     *dme= *sme;
452     nbytes= prefix_bytes(sme->prefixlen);
453     dme->prefix= TALLOC(nbytes);  assert(dme->prefix);
454     memcpy(dme->prefix, sme->prefix, nbytes);
455     Tcl_IncrRefCount(dme->data);
456   }
457   dob->typePtr= &maskmap_type;
458 }
459
460 static void maskmap_t_ustr(Tcl_Obj *so) {
461   MaskMap_Value *sm= (void*)&so->internalRep;
462   Tcl_Obj **mainlobjsl, *mainobj;
463   int i;
464
465   assert(so->typePtr == &maskmap_type);
466   mainlobjsl= TALLOC(sizeof(*mainlobjsl) * sm->used);  assert(mainlobjsl);
467
468   for (i=0; i<sm->used; i++) {
469     MaskMap_Entry *sme= &sm->entries[i];
470     HBytes_Value hb;
471     Tcl_Obj *subl[3], *sublo;
472
473     hbytes_array(&hb, sme->prefix, prefix_bytes(sme->prefixlen));
474     subl[0]= ret_hb(0, hb);  assert(subl[0]);
475     subl[1]= Tcl_NewIntObj(sme->prefixlen);  assert(subl[1]);
476     subl[2]= sme->data;
477     
478     sublo= Tcl_NewListObj(3,subl);  assert(sublo);
479     mainlobjsl[i]= sublo;
480   }
481
482   mainobj= Tcl_NewListObj(sm->used,mainlobjsl);  assert(mainobj);
483   so->bytes= Tcl_GetStringFromObj(mainobj, &so->length);  assert(so->bytes);
484   mainobj->bytes= 0; mainobj->length= 0; /* we stole it */
485 }
486
487 static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
488   int rc, len, eol, i;
489   MaskMap_Value mm;
490   MaskMap_Entry *mme;
491   Tcl_Obj *eo, *prefixo, *prefixleno;
492
493   mm_init(&mm);
494   
495   rc= Tcl_ListObjLength(ip,o,&len);  if (rc) goto x_rc;
496   mm_reallocentries(&mm, len);
497   
498   for (i=0, mme=mm.entries; i < len; i++, mme++) {
499     rc= Tcl_ListObjIndex(ip,o,i,&eo);  if (rc) goto x_rc;
500     rc= Tcl_ListObjLength(ip,eo,&eol);  if (rc) goto x_rc;
501     if (eol != 3) {
502       rc= staticerr(ip, "mask-map entry length != 3",
503                     "HBYTES MASKMAP SYNTAX LLENGTH");
504       goto x_rc;
505     }
506     rc= Tcl_ListObjIndex(ip,eo,0,&prefixo);  if (rc) goto x_rc;
507     rc= Tcl_ListObjIndex(ip,eo,1,&prefixleno);  if (rc) goto x_rc;
508     rc= Tcl_ListObjIndex(ip,eo,2,&mm.entries[i].data);  if (rc) goto x_rc;
509     Tcl_IncrRefCount(mm.entries[i].data);
510
511     rc= mme_parsekey(ip, mme, prefixo, prefixleno, 1);
512     if (rc) goto x_rc;
513
514     mm->used++;
515
516     if (i>0) {
517       if (mme_ordercompare(mme-1, mme) <= 0) {
518         rc= staticerr(ip, "mask-map entries out of order",
519                       "HBYTES MASKMAP SYNTAX ORDER");
520         goto x_rc;
521       }
522     }
523   }
524
525   /* we commit now */
526   assert(sizeof(mm) <= sizeof(o->internalRep));
527   objfreeir(o);
528   memcpy(&o->internalRep, &mm, sizeof(mm));
529   o->typePtr= &maskmap_type;
530   return TCL_OK;
531
532 x_rc:
533   for (mme=mm.entries, i=0; i<mm.used; i++, mme++)
534     mme_free(mme);
535   TFREE(mm.entries);
536   return rc;
537 }
538
539 Tcl_ObjType maskmap_type = {
540   "mask-map",
541   maskmap_t_free, maskmap_t_dup, maskmap_t_ustr, maskmap_t_sfa
542 };