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