chiark / gitweb /
fix up compilation errors
[chiark-tcl.git] / maskmap / maskmap.c
1 /*
2  * maskmap - Tcl extension for address mask map data structures
3  * Copyright 2006 Ian Jackson
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License as
7  * published by the Free Software Foundation; either version 2 of the
8  * License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful, but
11  * WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this library; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
18  * 02110-1301, USA.
19  */
20
21 #include "chiark_tcl_hbytes.h"
22
23 /*---------- operations on AddrMap_Entry ----------*/
24
25 static void ame_init(AddrMap_Entry *ame) {
26   ame->prefixlen= -1;
27   ame->prefix= 0;
28   ame->data= 0;
29 }
30
31 static unsigned ame_clear_unwanted(AddrMap_Entry *ame, int bytes) {
32   /* returns non-0 iff some bits were cleared */
33   int sparebits;
34   unsigned result, sparemask;
35   Byte *datap;
36
37   sparebits= bytes * 8 - ame->prefixlen;
38   if (!sparebits) return 0;
39
40   sparemask= (1u << sparebits) - 1;
41   datap= &ame->prefix[bytes-1];
42
43   result= *datap & sparemask;
44   *datap &= ~sparemask;
45
46   return result;
47 }
48
49 static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame,
50                         Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
51                         int inmap) {
52  /* *ame should be blank entry; after exit (even error exit) it will be valid
53   * - on errors, it will be blank.  inmap is 1 if we're parsing an existing
54   * map or 0 if it's an entry to be added or modified. */
55   HBytes_Value prefix;
56   int suppliedprefixbytes, prefixbits, wantprefixbytes;
57   const Byte *data;
58   int rc;
59
60   hbytes_empty(&prefix);
61   
62   rc= pat_hb(ip,prefixo,&prefix);  if (rc) goto x_rc;
63   rc= pat_int(ip,prefixbitso,&prefixbits);  if (rc) goto x_rc;
64
65   wantprefixbytes= prefix_bytes(prefixbits);
66   suppliedprefixbytes= hbytes_len(&prefix);
67
68   if (suppliedprefixbytes < wantprefixbytes) {
69     rc= staticerr(ip, "addr-map entry PREFIX too short for PREFIX-LEN",
70                   "HBYTES ADDRMAP SYNTAX UNDERRUN");
71     goto x_rc;
72   }
73   if (inmap && suppliedprefixbytes > wantprefixbytes) {
74     rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN",
75                   "HBYTES ADDRMAP SYNTAX OVERRUN");
76     goto x_rc;
77   }
78
79   ame->prefixlen= prefixbits;
80   ame->prefix= TALLOC(wantprefixbytes);  assert(ame->prefix);
81   memcpy(ame->prefix, data, wantprefixbytes);
82
83   if (ame_clear_unwanted(ame, wantprefixbytes)) {
84     rc= staticerr(ip, "addr-map entry PREFIX contains bits excluded"
85                   " by PREFIX-LEN", "HBYTES ADDRMAP SYNTAX EXCLBITS");
86     goto x_rc;
87   }
88
89   return TCL_OK;
90
91  x_rc:
92   ame_free(ame);
93   return rc;
94 }
95
96 static int ame_contains(const AddrMap_Entry *ref, const Byte *addr, int len) {
97   int directbytes, leftoverbits;
98   
99   assert(len >= ref->prefixlen);
100   
101   directbytes= ref->prefixlen / 8;
102   if (memcmp(ref->prefix, addr, directbytes)) return 0;
103
104   leftoverbits= ref->prefixlen % 8;
105   if (leftoverbits)
106     if ((addr[directbytes] & (0xffu << leftoverbits))
107         != search->prefix[directbytes])
108       return 0;
109
110   return 1;
111 }  
112
113 static int ame_compare(const AddrMap_Entry *a, const AddrMap_Entry *b) {
114   /*    +2 =    a   covers later range of address space than  b
115    *    +1 =    a   wholly contains but is not equal to       b
116    *     0 =    a   is identical to                           b
117    *    -1 =    b   wholly contains but is not equal to       a
118    *    -2 =    b   covers later range of address space than  a
119    */
120   int al= a->prefixlen;
121   int bl= b->prefixlen;
122   int ml, d;
123
124   if (al==bl) { ml=al; }
125   else if (al<bl) { ml=al; if (ame_contains(a,b->prefix,bl)) return +1; }
126   else if (bl<al) { ml=bl; if (ame_contains(b,a->prefix,al)) return -1; }
127
128   d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
129   return (d > 0 ? +2 :
130           d < 0 ? -2 :
131           0);
132 }
133
134 /*---------- searching maps ----------*/
135
136 typedef enum {
137   sr_notfound,
138   sr_exact,
139   sr_inbig,
140   sr_aroundsmall
141 } Search_Result;
142
143 static int
144 am_binarychop(AddrMap_Value *am, int low_oreq, int high_strict, void *u,
145               int (*test)(AddrMap_Entry *am, void *u) /* -ve => look left */,
146               int *found_r) {
147   int mid, cmp;
148   
149   for (;;) {
150     if (high_strict <= low_oreq) {
151       assert(high_strict == low_oreq);
152       *found_r= 0;
153       return high_strict;
154     }
155
156     mid= (high_strict + low_oreq) / 2;
157     cmp= test(&am->entries[mid], u);
158
159     if (!cmp) {
160       *found_r= 1;
161       return mid;
162     }
163
164     if (cmp < 0)
165       high_strict= mid;
166     else
167       low_oreq= mid+1;
168   }
169 }
170
171 struct am_search_u {
172   int forbid_aroundsmall;
173   AddrMap_Entry proposed;
174   Search_Result sr;
175 };
176
177 static int
178 am_search_binchoptest(AddrMap_Entry *ame, void *u_v) {
179   struct am_search_u *u= u_v;
180   int cmp;
181
182   cmp= ame_compare(&u.proposed, ame);
183   switch (cmp) {
184   case -1:  u->sr= sr_inbig;        return  0;
185   case  0:  u->sr= sr_exact;        return  0;
186   case +1:  u->sr= sr_aroundsmall;  return  0;
187   default:                          return cmp;
188   }
189 }
190
191 static Search_Result
192 am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) {
193   int place, found;
194   struct am_search_u u;
195
196   u.forbid_aroundsmall= forbid_aroundsmall;
197   u.proposed= proposed;
198   u.sr= sr_notfound;
199
200   *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found);
201
202   assert(!!found == (u.sr != sr_notfound));
203   return u.sr;
204 }
205
206 /*---------- useful operations on AddrMap_Value etc. ----------*/
207
208 /*---------- amendment (complex algorithm) ----------*/
209
210 struct am_amend_aroundsmall_u {
211   AddrMap_Entry *new;
212   int sign;
213 };
214
215
216 static int
217 am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) {
218   struct am_amend_aroundsmall_u *u= u_v;
219
220   cmp= u->sign * ame_compare(search, u->new);
221
222   switch (cmp) {
223   case +2:  return -u->sign;
224   case +1:  return +u->sign;
225   default:  abort();
226   }
227 }
228
229 int do_addrmap_amend(ClientData cd, Tcl_Interp *ip,
230                      AddrMap_Var map, Tcl_Obj *prefix,
231                      Tcl_Obj *preflen, Tcl_Obj *data) {
232   AddrMap_Value *am= map.am;
233   AddrMap_Entry new, *fragment;
234   AddrMap_Entry *breaking, *replacements;
235   int rc, insertat, findend, cmp, nreplacements, new_used;
236   struct am_amend_aroundsmall_u u;
237
238   ame_init(&new);
239   
240   rc= ame_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
241
242   sr= am_search(am, &new, &searched);
243
244   replacements= &new;
245   nreplacements= 1;
246   replace_start= searched;
247   replace_end= searched;
248
249   switch (sr) {
250
251   case sr_notfound:
252     break;
253
254   case sr_exact:
255     replace_end= searched+1;
256     break;
257
258   case sr_aroundsmall:
259     u.ame= new;
260     u.sign= -1;
261     replace_start= am_binarychop(am, 0, searched, &u,
262                                  am_amend_aroundsmall_binchoptest, &dummy);
263     u.sign= +1;
264     replace_end= am_binarychop(am, searched+1, am.used, &u,
265                                  am_amend_aroundsmall_binchoptest, &dummy);
266     break;
267
268   case sr_inbig:
269     /* Urgh, we need to break it up.  This produces
270      *   - innermost prefix (the new one) as specified
271      *   - one for each bitlength
272      *       <= innermost
273      *        > outermost (the existing one)
274      *     each one specifying the outermost prefix plus zero, one,
275      *     two, etc. bits of the innermost followed by one bit
276      *     opposite to the innermost, with the outermost's data
277      * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B
278      * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ...
279      * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
280      */
281
282     breaking= &am.entries[searched];
283     nreplacements= new.prefix - breaking->prefixlen + 1;
284     replacements= TALLOC(sizeof(*replacements) * nreplacements);
285
286     for (fragmentlen= breaking->prefixlen + 1,
287            left_insert= 0, right_insert= nreplacements;
288          fragmentlen <= new.prefix;
289          fragmentlen++) {
290       int fragmentbytes;
291
292       fragmentbytes= prefix_bytes(fragmentlen)
293       fragment->prefixlen= fragmentlen;
294       fragment->prefix= TALLOC(fragmentbytes);
295       memcpy(fragment->prefix, new.prefix, fragmentbytes);
296       ame_clear_unwanted(fragment, fragmentbytes);
297
298       fragment->prefix[fragmentbytes] ^=
299         0x80u >> ((fragmentlen+7) & 7);
300
301       switch (ame_compare(&fragment, &new)) {
302       case -2:  replacements[left_insert++]=  fragment;  break;
303       case +2:  replacements[--right_insert]= fragment;  break;
304       default: abort();
305       }
306     }
307     assert(left_insert == right_insert-1);
308     replacements[left_insert]= new;
309     ame_init(&new);
310
311     replace_end= searched+1;
312     break;
313
314   }
315
316   new_used= am.used - (replace_end - replace_start) + nreplacements;
317
318   if (new_used > am.space)
319     am_reallocentries(am, new_used * 2);
320
321   for (scan=replacements, i=0;
322        i < nreplacements;
323        scan++, i++) {
324     scan->data= data;
325     Tcl_IncrRefCount(scan->data);
326   }
327
328   for (i= replace_start, scan= am.entries+i;
329        i < replace_end;
330        i++, scan++) {
331     ame_free(scan);
332   }
333
334   memmove(am.entries + replace_start + nreplacements,
335           am.entries + replace_end,
336           sizeof(*am.entries) * (am.used - replace_end));
337
338   memcpy(am.entries + replace_start,
339          replacements,
340          sizeof(*am.entries) * nreplacements);
341
342   am.used= new_used;
343   if (replacements != &new)
344     /* we don't bother freeing the actual array elements because
345      * if replacements!=&new the array is only full if we're
346      * committed and have already copied the values into the actual
347      * AddrMap_Value. */
348     TFREE(replacements);
349
350   return TCL_OK;
351 }
352
353 /*---------- other substantial operations on mask maps ----------*/
354
355 int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip,
356                       Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
357                       Tcl_Obj **result) {
358   AddrMap_Value *am= (void*)&mapo->internalRep;
359   const Byte *addr= hbytes_data(&addrhb);
360   int addrbytes= hbytes_len(&addrhb);
361   int i, addrbits, place;
362   Search_Result sr;
363
364   addrbits= addrbytes * 8;
365   sr= am_search(am, addr, addrbits, &place);
366
367   switch (sr) {
368
369   case sr_notfound:
370     if (!def) return staticerr(ip, "address not found in addr-map",
371                                "HBYTES ADDRMAP NOMATCH");
372     *result= def;
373     break;
374
375   case sr_aroundsmall:
376     return staticerr(ip, "address shorter than mask in map",
377                      "HBYTES ADDRMAP UNDERRUN");
378
379   case sr_exact:
380   case sr_inbig:
381     *result= am.entres[place].data;
382     break;
383     
384   }
385
386   return TCL_OK;
387 }
388
389 /*---------- Tcl type and arg parsing functions ----------*/
390