/* * Copyright (c) 2003 Research Engineering Development, Inc. * Author: Alfred Perlstein * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $Id: mtrie.c,v 1.6 2003/07/01 08:01:17 bright Exp $ * */ #include #include #if !defined(__FreeBSD__) || __FreeBSD_version >= 500000 #include #endif #include "mtrie.h" #ifdef DEBUG #include #endif #ifdef __unused #define UNUSED(x) x __unused #else #define UNUSED(x) x #endif /* * Head object, just a reference to the first 'row'. */ struct mtrie { struct ment *m_trie; }; /* * These are allocated in chunks of 256. * The 'mask' portion is required because we need to only overwrite * entries that are less specific. Meaning data for a /6 overrides data * for a /4. */ struct ment { struct ment *me_next; /* next octect or NULL. */ void *me_data; /* data or NULL. */ int me_mask; /* mask data was entered with. */ }; #define MTRIE_SIZE 256 static void ment_free(struct ment *ment); static int poweroftwo(int x); /* * std allocator. */ int mtrie_alloc(mtrie_t *m, UNUSED(int flags)) { *m = calloc(1, sizeof(**m)); return (*m == NULL ? -1 : 0); } void mtrie_free(mtrie_t m) { if (m->m_trie) ment_free(m->m_trie); free(m); } static void ment_free(struct ment *ment) { int i; for (i = 0; i < MTRIE_SIZE; i++) if (ment->me_next != NULL) ment_free(ment->me_next); free(ment); } /* * return 2^x */ static int poweroftwo(int x) { return (1 << x); } /* * std debug macro. */ #ifdef DEBUG #define bug(fmt, args...) \ do { \ if (getenv("DEBUG")) \ fprintf(stderr, "%d: " fmt "\n", __LINE__, ##args); \ } while (0); #else #define bug(fmt, args...) #endif /* * insert into the mtrie */ int mtrie_insert(mtrie_t m, uint32_t ip, uint8_t mask, void *datum) { unsigned char *ov; struct ment **place, *prev; int idx, pow, accum, lowrange, rem, x; ov = (unsigned char *)&ip; place = &m->m_trie; prev = NULL; idx = 3; for ( ;; ) { /* * allocate a new slot if needed */ bug("looping idx = %d", idx); if (*place == NULL) { *place = calloc(MTRIE_SIZE, sizeof(**place)); if (*place == NULL) return (-1); } prev = &(*place)[ov[idx]]; bug("mask = %d", mask); /* * If we're still greater than 8, go down another row. */ if (mask > 8) { mask -= 8; place = &prev->me_next; idx--; continue; } /* * If we're exactly at 8, just fill the data. */ if (mask == 8) { prev->me_data = datum; return (0); } accum = 0; rem = 8 - mask; /* * Get the next highest multiple of 2^rem over * the current cell, example: * poweroftwo(rem) == 8, ov[idx] = 29 * then we want: * accum = 32, lowrange = 24. */ pow = poweroftwo(rem); x = ov[idx]; lowrange = x - (x % pow); accum = lowrange + pow; /* * Now fill in the entries in the row. */ while (accum-- > lowrange) { struct ment *mp; mp = (*place) + accum; /* * If there is no data or we're an equal or * more specific mask then overwrite the data. */ if (mp->me_data == NULL || mp->me_mask >= rem) { /* * If we wanted to be able to delete entries * we'd probably stack them here instead, * it would be a good idea to do the * necessary allocation up front. */ mp->me_data = datum; mp->me_mask = rem; bug("accum: %d, datum %p, mp = %p, rem = %d", accum, datum, mp, rem); } else { bug("SET!!! " "accum: %d, datum %p, mp = %p, rem = %d", accum, datum, mp, rem); } } return (0); } } /* * lookup in the mtrie. */ int mtrie_lookup(mtrie_t m, uint32_t ip, void **datap) { struct ment **place, *prev; unsigned char *ov; int idx; void *last; ov = (char *)&ip; place = &m->m_trie; prev = NULL; *datap = NULL; last = NULL; /* * Walk the octets. */ for (idx = 3 ; idx >= 0; idx--) { bug("looping: idx = %d, *place = %p, prev = %p", idx, *place, prev); bug("prev->me_data == %p", prev != NULL ? prev->me_data : NULL); if (*place == NULL) break; /* * if we're going deeper into the mtrie and * leaving a node that has data then we need * to remember that in case we fall out of the * tree at a lower level where no specific route * has been entered. */ if (prev != NULL && prev->me_data != NULL) last = prev->me_data; prev = &(*place)[ov[idx]]; place = &prev->me_next; } bug("lookup: idx = %d, *place = %p, prev = %p", idx, *place, prev); bug("prev->me_data == %p", prev != NULL ? prev->me_data : NULL); /* we lost, nothing matches. */ if (prev == NULL) return (-1); /* * Get the data at the node we were at before * we fell out. */ *datap = prev->me_data; /* * If it was null then take a shot at the 'last' * node that had data, that will be the data * entered by a route higher up in the tree. */ if (*datap == NULL) *datap = last; /* we could have still lost. */ return (*datap == NULL ? -1 : 0); }