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