| /* |
| * patricia.c |
| * |
| * Patricia trie implementation. |
| * |
| * Functions for inserting nodes, removing nodes, and searching in |
| * a Patricia trie designed for IP addresses and netmasks. A |
| * head node must be created with (key,mask) = (0,0). |
| * |
| * NOTE: The fact that we keep multiple masks per node makes this |
| * more complicated/computationally expensive then a standard |
| * trie. This is because we need to do longest prefix matching, |
| * which is useful for computer networks, but not as useful |
| * elsewhere. |
| * |
| * Matthew Smart <mcsmart@eecs.umich.edu> |
| * |
| * Copyright (c) 2000 |
| * The Regents of the University of Michigan |
| * All rights reserved |
| * |
| * $Id$ |
| */ |
| |
| #include <stdlib.h> /* free(), malloc() */ |
| #include <string.h> /* bcopy() */ |
| #include "patricia.h" |
| |
| |
| /* |
| * Private function used to return whether |
| * or not bit 'i' is set in 'key'. |
| */ |
| static __inline |
| unsigned long |
| bit(int i, unsigned long key) |
| { |
| return key & (1 << (31-i)); |
| } |
| |
| |
| /* |
| * Count the number of masks (and therefore entries) |
| * in the Patricia trie. |
| */ |
| static int |
| pat_count(struct ptree *t, int b) |
| { |
| int count; |
| |
| if (t->p_b <= b) return 0; |
| |
| count = t->p_mlen; |
| |
| count += pat_count(t->p_left, t->p_b); |
| count += pat_count(t->p_right, t->p_b); |
| |
| return count; |
| } |
| |
| |
| /* |
| * Private function used for inserting a node recursively. |
| */ |
| static struct ptree * |
| insertR(struct ptree *h, struct ptree *n, int d, struct ptree *p) |
| { |
| if ((h->p_b >= d) || (h->p_b <= p->p_b)) { |
| n->p_b = d; |
| n->p_left = bit(d, n->p_key) ? h : n; |
| n->p_right = bit(d, n->p_key) ? n : h; |
| return n; |
| } |
| |
| if (bit(h->p_b, n->p_key)) |
| h->p_right = insertR(h->p_right, n, d, h); |
| else |
| h->p_left = insertR(h->p_left, n, d, h); |
| return h; |
| } |
| |
| |
| /* |
| * Patricia trie insert. |
| * |
| * 1) Go down to leaf. |
| * 2) Determine longest prefix match with leaf node. |
| * 3) Insert new internal node at appropriate location and |
| * attach new external node. |
| */ |
| struct ptree * |
| pat_insert(struct ptree *n, struct ptree *head) |
| { |
| struct ptree *t; |
| struct ptree_mask *buf, *pm; |
| int i, copied; |
| |
| if (!head || !n || !n->p_m) |
| return 0; |
| |
| /* |
| * Make sure the key matches the mask. |
| */ |
| n->p_key &= n->p_m->pm_mask; |
| |
| /* |
| * Find closest matching leaf node. |
| */ |
| t = head; |
| do { |
| i = t->p_b; |
| t = bit(t->p_b, n->p_key) ? t->p_right : t->p_left; |
| } while (i < t->p_b); |
| |
| /* |
| * If the keys are the same we need to check the masks. |
| */ |
| if (n->p_key == t->p_key) { |
| /* |
| * If we have a duplicate mask, replace the entry |
| * with the new one. |
| */ |
| for (i=0; i < t->p_mlen; i++) { |
| if (n->p_m->pm_mask == t->p_m[i].pm_mask) { |
| t->p_m[i].pm_data = n->p_m->pm_data; |
| free(n->p_m); |
| free(n); |
| n = 0; |
| return t; |
| } |
| } |
| |
| /* |
| * Allocate space for a new set of masks. |
| */ |
| buf = (struct ptree_mask *)malloc( |
| sizeof(struct ptree_mask)*(t->p_mlen+1)); |
| |
| /* |
| * Insert the new mask in the proper order from least |
| * to greatest mask. |
| */ |
| copied = 0; |
| for (i=0, pm=buf; i < t->p_mlen; pm++) { |
| if (n->p_m->pm_mask > t->p_m[i].pm_mask) { |
| bcopy(t->p_m + i, pm, sizeof(struct ptree_mask)); |
| i++; |
| } |
| else { |
| bcopy(n->p_m, pm, sizeof(struct ptree_mask)); |
| n->p_m->pm_mask = 0xffffffff; |
| copied = 1; |
| } |
| } |
| if (!copied) { |
| bcopy(n->p_m, pm, sizeof(struct ptree_mask)); |
| } |
| free(n->p_m); |
| free(n); |
| n = 0; |
| t->p_mlen++; |
| |
| /* |
| * Free old masks and point to new ones. |
| */ |
| free(t->p_m); |
| t->p_m = buf; |
| |
| return t; |
| } |
| |
| /* |
| * Find the first bit that differs. |
| */ |
| for (i=1; i < 32 && bit(i, n->p_key) == bit(i, t->p_key); i++); |
| |
| /* |
| * Recursive step. |
| */ |
| if (bit(head->p_b, n->p_key)) |
| head->p_right = insertR(head->p_right, n, i, head); |
| else |
| head->p_left = insertR(head->p_left, n, i, head); |
| |
| return n; |
| } |
| |
| |
| /* |
| * Remove an entry given a key in a Patricia trie. |
| */ |
| int |
| pat_remove(struct ptree *n, struct ptree *head) |
| { |
| struct ptree *p, *g, *pt, *pp, *t; |
| struct ptree_mask *buf, *pm; |
| int i; |
| |
| if (!n || !n->p_m || !t) |
| return 0; |
| |
| /* |
| * Search for the target node, while keeping track of the |
| * parent and grandparent nodes. |
| */ |
| g = p = t = head; |
| do { |
| i = t->p_b; |
| g = p; |
| p = t; |
| t = bit(t->p_b, n->p_key) ? t->p_right : t->p_left; |
| } while (i < t->p_b); |
| |
| /* |
| * For removal, we need an exact match. |
| */ |
| if (t->p_key != n->p_key) |
| return 0; |
| |
| /* |
| * If there is only 1 mask, we can remove the entire node. |
| */ |
| if (t->p_mlen == 1) { |
| /* |
| * Don't allow removal of the default entry. |
| */ |
| if (t->p_b == 0) |
| return 0; |
| |
| /* |
| * Must match on the mask. |
| */ |
| if (t->p_m->pm_mask != n->p_m->pm_mask) |
| return 0; |
| |
| /* |
| * Search for the node that points to the parent, so |
| * we can make sure it doesn't get lost. |
| */ |
| pp = pt = p; |
| do { |
| i = pt->p_b; |
| pp = pt; |
| pt = bit(pt->p_b, p->p_key) ? pt->p_right : pt->p_left; |
| } while (i < pt->p_b); |
| |
| if (bit(pp->p_b, p->p_key)) |
| pp->p_right = t; |
| else |
| pp->p_left = t; |
| |
| /* |
| * Point the grandparent to the proper node. |
| */ |
| if (bit(g->p_b, n->p_key)) |
| g->p_right = bit(p->p_b, n->p_key) ? |
| p->p_left : p->p_right; |
| else |
| g->p_left = bit(p->p_b, n->p_key) ? |
| p->p_left : p->p_right; |
| |
| /* |
| * Delete the target's data and copy in its parent's |
| * data, but not the bit value. |
| */ |
| if (t->p_m->pm_data) |
| free(t->p_m->pm_data); |
| free(t->p_m); |
| if (t != p) { |
| t->p_key = p->p_key; |
| t->p_m = p->p_m; |
| t->p_mlen = p->p_mlen; |
| } |
| free(p); |
| |
| return 1; |
| } |
| |
| /* |
| * Multiple masks, so we need to find the one to remove. |
| * Return if we don't match on any of them. |
| */ |
| for (i=0; i < t->p_mlen; i++) |
| if (n->p_m->pm_mask == t->p_m[i].pm_mask) |
| break; |
| if (i >= t->p_mlen) |
| return 0; |
| |
| /* |
| * Allocate space for a new set of masks. |
| */ |
| buf = (struct ptree_mask *)malloc( |
| sizeof(struct ptree_mask)*(t->p_mlen-1)); |
| |
| for (i=0, pm=buf; i < t->p_mlen; i++) { |
| if (n->p_m->pm_mask != t->p_m[i].pm_mask) { |
| bcopy(t->p_m + i, pm++, sizeof(struct ptree_mask)); |
| } |
| } |
| |
| /* |
| * Free old masks and point to new ones. |
| */ |
| t->p_mlen--; |
| free(t->p_m); |
| t->p_m = buf; |
| return 1; |
| } |
| |
| |
| /* |
| * Find an entry given a key in a Patricia trie. |
| */ |
| struct ptree * |
| pat_search(unsigned long key, struct ptree *head) |
| { |
| struct ptree *p = 0, *t = head; |
| int i; |
| |
| if (!t) |
| return 0; |
| |
| /* |
| * Find closest matching leaf node. |
| */ |
| do { |
| /* |
| * Keep track of most complete match so far. |
| */ |
| if (t->p_key == (key & t->p_m->pm_mask)) { |
| p = t; |
| } |
| |
| i = t->p_b; |
| t = bit(t->p_b, key) ? t->p_right : t->p_left; |
| } while (i < t->p_b); |
| |
| /* |
| * Compare keys (and masks) to see if this |
| * is really the node we want. |
| */ |
| return (t->p_key == (key & t->p_m->pm_mask)) ? t : p; |
| } |