![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to radix.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Net/2] / Net2 / net|
Return to radix.c CVS log | Up to [Net/2] / Net2 / net |
1.1 root 1: /*
2: * Copyright (c) 1988, 1989 Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms, with or without
6: * modification, are permitted provided that the following conditions
7: * are met:
8: * 1. Redistributions of source code must retain the above copyright
9: * notice, this list of conditions and the following disclaimer.
10: * 2. Redistributions in binary form must reproduce the above copyright
11: * notice, this list of conditions and the following disclaimer in the
12: * documentation and/or other materials provided with the distribution.
13: * 3. All advertising materials mentioning features or use of this software
14: * must display the following acknowledgement:
15: * This product includes software developed by the University of
16: * California, Berkeley and its contributors.
17: * 4. Neither the name of the University nor the names of its contributors
18: * may be used to endorse or promote products derived from this software
19: * without specific prior written permission.
20: *
21: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31: * SUCH DAMAGE.
32: *
33: * @(#)radix.c 7.9 (Berkeley) 2/4/91
34: */
35:
36: /*
37: * Routines to build and maintain radix trees for routing lookups.
38: */
39: #ifndef RNF_NORMAL
40: #include "param.h"
41: #include "radix.h"
42: #include "malloc.h"
43: #define M_DONTWAIT M_NOWAIT
44: #endif
45: struct radix_node_head *mask_rnhead;
46: #define rn_maskhead mask_rnhead->rnh_treetop
47: struct radix_mask *rn_mkfreelist;
48: struct radix_node_head *radix_node_head;
49: #undef Bcmp
50: #define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l))
51: /*
52: * The data structure for the keys is a radix tree with one way
53: * branching removed. The index rn_b at an internal node n represents a bit
54: * position to be tested. The tree is arranged so that all descendants
55: * of a node n have keys whose bits all agree up to position rn_b - 1.
56: * (We say the index of n is rn_b.)
57: *
58: * There is at least one descendant which has a one bit at position rn_b,
59: * and at least one with a zero there.
60: *
61: * A route is determined by a pair of key and mask. We require that the
62: * bit-wise logical and of the key and mask to be the key.
63: * We define the index of a route to associated with the mask to be
64: * the first bit number in the mask where 0 occurs (with bit number 0
65: * representing the highest order bit).
66: *
67: * We say a mask is normal if every bit is 0, past the index of the mask.
68: * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b,
69: * and m is a normal mask, then the route applies to every descendant of n.
70: * If the index(m) < rn_b, this implies the trailing last few bits of k
71: * before bit b are all 0, (and hence consequently true of every descendant
72: * of n), so the route applies to all descendants of the node as well.
73: *
74: * The present version of the code makes no use of normal routes,
75: * but similar logic shows that a non-normal mask m such that
76: * index(m) <= index(n) could potentially apply to many children of n.
77: * Thus, for each non-host route, we attach its mask to a list at an internal
78: * node as high in the tree as we can go.
79: */
80:
81: struct radix_node *
82: rn_search(v, head)
83: struct radix_node *head;
84: register caddr_t v;
85: {
86: register struct radix_node *x;
87:
88: for (x = head; x->rn_b >= 0;) {
89: if (x->rn_bmask & v[x->rn_off])
90: x = x->rn_r;
91: else
92: x = x->rn_l;
93: }
94: return x;
95: };
96:
97: struct radix_node *
98: rn_search_m(v, head, m)
99: struct radix_node *head;
100: register caddr_t v, m;
101: {
102: register struct radix_node *x;
103:
104: for (x = head; x->rn_b >= 0;) {
105: if ((x->rn_bmask & m[x->rn_off]) &&
106: (x->rn_bmask & v[x->rn_off]))
107: x = x->rn_r;
108: else
109: x = x->rn_l;
110: }
111: return x;
112: };
113:
114:
115: static int gotOddMasks;
116: static char maskedKey[MAXKEYLEN];
117:
118: struct radix_node *
119: rn_match(v, head)
120: struct radix_node *head;
121: caddr_t v;
122: {
123: register struct radix_node *t = head, *x;
124: register caddr_t cp = v, cp2, cp3;
125: caddr_t cplim, mstart;
126: struct radix_node *saved_t;
127: int off = t->rn_off, vlen = *(u_char *)cp, matched_off;
128:
129: /*
130: * Open code rn_search(v, head) to avoid overhead of extra
131: * subroutine call.
132: */
133: for (; t->rn_b >= 0; ) {
134: if (t->rn_bmask & cp[t->rn_off])
135: t = t->rn_r;
136: else
137: t = t->rn_l;
138: }
139: /*
140: * See if we match exactly as a host destination
141: */
142: cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
143: for (; cp < cplim; cp++, cp2++)
144: if (*cp != *cp2)
145: goto on1;
146: /*
147: * This extra grot is in case we are explicitly asked
148: * to look up the default. Ugh!
149: */
150: if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey)
151: t = t->rn_dupedkey;
152: return t;
153: on1:
154: matched_off = cp - v;
155: saved_t = t;
156: do {
157: if (t->rn_mask) {
158: /*
159: * Even if we don't match exactly as a hosts;
160: * we may match if the leaf we wound up at is
161: * a route to a net.
162: */
163: cp3 = matched_off + t->rn_mask;
164: cp2 = matched_off + t->rn_key;
165: for (; cp < cplim; cp++)
166: if ((*cp2++ ^ *cp) & *cp3++)
167: break;
168: if (cp == cplim)
169: return t;
170: cp = matched_off + v;
171: }
172: } while (t = t->rn_dupedkey);
173: t = saved_t;
174: /* start searching up the tree */
175: do {
176: register struct radix_mask *m;
177: t = t->rn_p;
178: if (m = t->rn_mklist) {
179: /*
180: * After doing measurements here, it may
181: * turn out to be faster to open code
182: * rn_search_m here instead of always
183: * copying and masking.
184: */
185: off = min(t->rn_off, matched_off);
186: mstart = maskedKey + off;
187: do {
188: cp2 = mstart;
189: cp3 = m->rm_mask + off;
190: for (cp = v + off; cp < cplim;)
191: *cp2++ = *cp++ & *cp3++;
192: x = rn_search(maskedKey, t);
193: while (x && x->rn_mask != m->rm_mask)
194: x = x->rn_dupedkey;
195: if (x &&
196: (Bcmp(mstart, x->rn_key + off,
197: vlen - off) == 0))
198: return x;
199: } while (m = m->rm_mklist);
200: }
201: } while (t != head);
202: return 0;
203: };
204:
205: #ifdef RN_DEBUG
206: int rn_nodenum;
207: struct radix_node *rn_clist;
208: int rn_saveinfo;
209: #endif
210:
211: struct radix_node *
212: rn_newpair(v, b, nodes)
213: caddr_t v;
214: struct radix_node nodes[2];
215: {
216: register struct radix_node *tt = nodes, *t = tt + 1;
217: t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7);
218: t->rn_l = tt; t->rn_off = b >> 3;
219: tt->rn_b = -1; tt->rn_key = v; tt->rn_p = t;
220: tt->rn_flags = t->rn_flags = RNF_ACTIVE;
221: #ifdef RN_DEBUG
222: tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
223: tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
224: #endif
225: return t;
226: }
227:
228: int rn_debug = 1;
229: struct radix_node *
230: rn_insert(v, head, dupentry, nodes)
231: caddr_t v;
232: struct radix_node *head;
233: int *dupentry;
234: struct radix_node nodes[2];
235: {
236: int head_off = head->rn_off, vlen = (int)*((u_char *)v);
237: register struct radix_node *t = rn_search(v, head);
238: register caddr_t cp = v + head_off;
239: register int b;
240: struct radix_node *tt;
241: /*
242: *find first bit at which v and t->rn_key differ
243: */
244: {
245: register caddr_t cp2 = t->rn_key + head_off;
246: register int cmp_res;
247: caddr_t cplim = v + vlen;
248:
249: while (cp < cplim)
250: if (*cp2++ != *cp++)
251: goto on1;
252: *dupentry = 1;
253: return t;
254: on1:
255: *dupentry = 0;
256: cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
257: for (b = (cp - v) << 3; cmp_res; b--)
258: cmp_res >>= 1;
259: }
260: {
261: register struct radix_node *p, *x = head;
262: cp = v;
263: do {
264: p = x;
265: if (cp[x->rn_off] & x->rn_bmask)
266: x = x->rn_r;
267: else x = x->rn_l;
268: } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */
269: #ifdef RN_DEBUG
270: if (rn_debug)
271: printf("Going In:\n"), traverse(p);
272: #endif
273: t = rn_newpair(v, b, nodes); tt = t->rn_l;
274: if ((cp[p->rn_off] & p->rn_bmask) == 0)
275: p->rn_l = t;
276: else
277: p->rn_r = t;
278: x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */
279: if ((cp[t->rn_off] & t->rn_bmask) == 0) {
280: t->rn_r = x;
281: } else {
282: t->rn_r = tt; t->rn_l = x;
283: }
284: #ifdef RN_DEBUG
285: if (rn_debug)
286: printf("Coming out:\n"), traverse(p);
287: #endif
288: }
289: return (tt);
290: }
291:
292: struct radix_node *
293: rn_addmask(netmask, search, skip)
294: caddr_t netmask;
295: {
296: register struct radix_node *x;
297: register caddr_t cp, cplim;
298: register int b, mlen, j;
299: int maskduplicated;
300:
301: mlen = *(u_char *)netmask;
302: if (search) {
303: x = rn_search(netmask, rn_maskhead);
304: mlen = *(u_char *)netmask;
305: if (Bcmp(netmask, x->rn_key, mlen) == 0)
306: return (x);
307: }
308: R_Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x));
309: if (x == 0)
310: return (0);
311: Bzero(x, MAXKEYLEN + 2 * sizeof (*x));
312: cp = (caddr_t)(x + 2);
313: Bcopy(netmask, cp, mlen);
314: netmask = cp;
315: x = rn_insert(netmask, rn_maskhead, &maskduplicated, x);
316: /*
317: * Calculate index of mask.
318: */
319: cplim = netmask + mlen;
320: for (cp = netmask + skip; cp < cplim; cp++)
321: if (*(u_char *)cp != 0xff)
322: break;
323: b = (cp - netmask) << 3;
324: if (cp != cplim) {
325: if (*cp != 0) {
326: gotOddMasks = 1;
327: for (j = 0x80; j; b++, j >>= 1)
328: if ((j & *cp) == 0)
329: break;
330: }
331: }
332: x->rn_b = -1 - b;
333: return (x);
334: }
335:
336: struct radix_node *
337: rn_addroute(v, netmask, head, treenodes)
338: struct radix_node *head;
339: caddr_t netmask, v;
340: struct radix_node treenodes[2];
341: {
342: register int j;
343: register caddr_t cp;
344: register struct radix_node *t, *x, *tt;
345: short b = 0, b_leaf;
346: int vlen = *(u_char *)v, mlen, keyduplicated;
347: caddr_t cplim; unsigned char *maskp;
348: struct radix_mask *m, **mp;
349: struct radix_node *saved_tt;
350:
351: /*
352: * In dealing with non-contiguous masks, there may be
353: * many different routes which have the same mask.
354: * We will find it useful to have a unique pointer to
355: * the mask to speed avoiding duplicate references at
356: * nodes and possibly save time in calculating indices.
357: */
358: if (netmask) {
359: x = rn_search(netmask, rn_maskhead);
360: mlen = *(u_char *)netmask;
361: if (Bcmp(netmask, x->rn_key, mlen) != 0) {
362: x = rn_addmask(netmask, 0, head->rn_off);
363: if (x == 0)
364: return (0);
365: }
366: netmask = x->rn_key;
367: b = -1 - x->rn_b;
368: }
369: /*
370: * Deal with duplicated keys: attach node to previous instance
371: */
372: saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
373: if (keyduplicated) {
374: do {
375: if (tt->rn_mask == netmask)
376: return (0);
377: t = tt;
378: } while (tt = tt->rn_dupedkey);
379: /*
380: * If the mask is not duplicated, we wouldn't
381: * find it among possible duplicate key entries
382: * anyway, so the above test doesn't hurt.
383: *
384: * XXX: we really ought to sort the masks
385: * for a duplicated key the same way as in a masklist.
386: * It is an unfortunate pain having to relocate
387: * the head of the list.
388: */
389: t->rn_dupedkey = tt = treenodes;
390: #ifdef RN_DEBUG
391: t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
392: tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
393: #endif
394: t = saved_tt;
395: tt->rn_key = (caddr_t) v;
396: tt->rn_b = -1;
397: tt->rn_flags = t->rn_flags & ~RNF_ROOT;
398: }
399: /*
400: * Put mask in tree.
401: */
402: if (netmask) {
403: tt->rn_mask = netmask;
404: tt->rn_b = x->rn_b;
405: }
406: t = saved_tt->rn_p;
407: b_leaf = -1 - t->rn_b;
408: if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r;
409: /* Promote general routes from below */
410: if (x->rn_b < 0) {
411: if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) {
412: MKGet(m);
413: if (m) {
414: Bzero(m, sizeof *m);
415: m->rm_b = x->rn_b;
416: m->rm_mask = x->rn_mask;
417: x->rn_mklist = t->rn_mklist = m;
418: }
419: }
420: } else if (x->rn_mklist) {
421: /*
422: * Skip over masks whose index is > that of new node
423: */
424: for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist)
425: if (m->rm_b >= b_leaf)
426: break;
427: t->rn_mklist = m; *mp = 0;
428: }
429: /* Add new route to highest possible ancestor's list */
430: if ((netmask == 0) || (b > t->rn_b ))
431: return tt; /* can't lift at all */
432: b_leaf = tt->rn_b;
433: do {
434: x = t;
435: t = t->rn_p;
436: } while (b <= t->rn_b && x != head);
437: /*
438: * Search through routes associated with node to
439: * insert new route according to index.
440: * For nodes of equal index, place more specific
441: * masks first.
442: */
443: cplim = netmask + mlen;
444: for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) {
445: if (m->rm_b < b_leaf)
446: continue;
447: if (m->rm_b > b_leaf)
448: break;
449: if (m->rm_mask == netmask) {
450: m->rm_refs++;
451: tt->rn_mklist = m;
452: return tt;
453: }
454: maskp = (u_char *)m->rm_mask;
455: for (cp = netmask; cp < cplim; cp++)
456: if (*(u_char *)cp > *maskp++)
457: goto on2;
458: }
459: on2:
460: MKGet(m);
461: if (m == 0) {
462: printf("Mask for route not entered\n");
463: return (tt);
464: }
465: Bzero(m, sizeof *m);
466: m->rm_b = b_leaf;
467: m->rm_mask = netmask;
468: m->rm_mklist = *mp;
469: *mp = m;
470: tt->rn_mklist = m;
471: return tt;
472: }
473:
474: struct radix_node *
475: rn_delete(v, netmask, head)
476: caddr_t v, netmask;
477: struct radix_node *head;
478: {
479: register struct radix_node *t, *p, *x = head;
480: register struct radix_node *tt = rn_search(v, x);
481: int b, head_off = x->rn_off, vlen = * (u_char *) v;
482: struct radix_mask *m, *saved_m, **mp;
483: struct radix_node *dupedkey, *saved_tt = tt;
484:
485: if (tt == 0 ||
486: Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
487: return (0);
488: /*
489: * Delete our route from mask lists.
490: */
491: if (dupedkey = tt->rn_dupedkey) {
492: if (netmask)
493: netmask = rn_search(netmask, rn_maskhead)->rn_key;
494: while (tt->rn_mask != netmask)
495: if ((tt = tt->rn_dupedkey) == 0)
496: return (0);
497: }
498: if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
499: goto on1;
500: if (m->rm_mask != tt->rn_mask) {
501: printf("rn_delete: inconsistent annotation\n");
502: goto on1;
503: }
504: if (--m->rm_refs >= 0)
505: goto on1;
506: b = -1 - tt->rn_b;
507: t = saved_tt->rn_p;
508: if (b > t->rn_b)
509: goto on1; /* Wasn't lifted at all */
510: do {
511: x = t;
512: t = t->rn_p;
513: } while (b <= t->rn_b && x != head);
514: for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist)
515: if (m == saved_m) {
516: *mp = m->rm_mklist;
517: MKFree(m);
518: break;
519: }
520: if (m == 0)
521: printf("rn_delete: couldn't find our annotation\n");
522: on1:
523: /*
524: * Eliminate us from tree
525: */
526: if (tt->rn_flags & RNF_ROOT)
527: return (0);
528: #ifdef RN_DEBUG
529: /* Get us out of the creation list */
530: for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
531: if (t) t->rn_ybro = tt->rn_ybro;
532: #endif RN_DEBUG
533: t = tt->rn_p;
534: if (dupedkey) {
535: if (tt == saved_tt) {
536: x = dupedkey; x->rn_p = t;
537: if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x;
538: #ifndef RN_DEBUG
539: x++; t = tt + 1; *x = *t; p = t->rn_p;
540: #else
541: x++; b = x->rn_info; t = tt + 1; *x = *t; p = t->rn_p;
542: x->rn_info = b;
543: #endif
544: if (p->rn_l == t) p->rn_l = x; else p->rn_r = x;
545: x->rn_l->rn_p = x; x->rn_r->rn_p = x;
546: } else {
547: for (p = saved_tt; p && p->rn_dupedkey != tt;)
548: p = p->rn_dupedkey;
549: if (p) p->rn_dupedkey = tt->rn_dupedkey;
550: else printf("rn_delete: couldn't find us\n");
551: }
552: goto out;
553: }
554: if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l;
555: p = t->rn_p;
556: if (p->rn_r == t) p->rn_r = x; else p->rn_l = x;
557: x->rn_p = p;
558: /*
559: * Demote routes attached to us.
560: */
561: if (t->rn_mklist) {
562: if (x->rn_b >= 0) {
563: for (mp = &x->rn_mklist; m = *mp;)
564: mp = &m->rm_mklist;
565: *mp = t->rn_mklist;
566: } else {
567: for (m = t->rn_mklist; m;) {
568: struct radix_mask *mm = m->rm_mklist;
569: if (m == x->rn_mklist && (--(m->rm_refs) < 0)) {
570: x->rn_mklist = 0;
571: MKFree(m);
572: } else
573: printf("%s %x at %x\n",
574: "rn_delete: Orphaned Mask", m, x);
575: m = mm;
576: }
577: }
578: }
579: /*
580: * We may be holding an active internal node in the tree.
581: */
582: x = tt + 1;
583: if (t != x) {
584: #ifndef RN_DEBUG
585: *t = *x;
586: #else
587: b = t->rn_info; *t = *x; t->rn_info = b;
588: #endif
589: t->rn_l->rn_p = t; t->rn_r->rn_p = t;
590: p = x->rn_p;
591: if (p->rn_l == x) p->rn_l = t; else p->rn_r = t;
592: }
593: out:
594: tt->rn_flags &= ~RNF_ACTIVE;
595: tt[1].rn_flags &= ~RNF_ACTIVE;
596: return (tt);
597: }
598: char rn_zeros[MAXKEYLEN], rn_ones[MAXKEYLEN];
599:
600: rn_inithead(head, off, af)
601: struct radix_node_head **head;
602: int off;
603: {
604: register struct radix_node_head *rnh;
605: register struct radix_node *t, *tt, *ttt;
606: if (*head)
607: return (1);
608: R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));
609: if (rnh == 0)
610: return (0);
611: Bzero(rnh, sizeof (*rnh));
612: *head = rnh;
613: t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
614: ttt = rnh->rnh_nodes + 2;
615: t->rn_r = ttt;
616: t->rn_p = t;
617: tt = t->rn_l;
618: tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
619: tt->rn_b = -1 - off;
620: *ttt = *tt;
621: ttt->rn_key = rn_ones;
622: rnh->rnh_af = af;
623: rnh->rnh_treetop = t;
624: if (radix_node_head == 0) {
625: caddr_t cp = rn_ones, cplim = rn_ones + MAXKEYLEN;
626: while (cp < cplim)
627: *cp++ = -1;
628: if (rn_inithead(&radix_node_head, 0, 0) == 0) {
629: Free(rnh);
630: *head = 0;
631: return (0);
632: }
633: mask_rnhead = radix_node_head;
634: }
635: rnh->rnh_next = radix_node_head->rnh_next;
636: if (radix_node_head != rnh)
637: radix_node_head->rnh_next = rnh;
638: return (1);
639: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.