/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2002-2003 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#define ZERO 0
/* Statics */
/*
* create_node(flag)
*
* generates a pointer to a new trie node
* flag is passed to kmem_alloc
* returns NULL to signify memory error
*/
node_t *
{
return (NULL);
}
return (buf);
}
/*
* t_split(c_node, pos, key_len)
*
* performs a split on c_node for the following three cases:
* 1 a mismatch occured between the insert key and the value at the node
* 2 the insert key specifies a shorter key than the one at the node
* 3 the insert key specifies a longer key than the one at the node
* cases 1 and 2 are handled in the same way
* when t_split returns, c_node->one and c_node->zero must != NULL
*
* (note: we assume a key_len = n (where in the real world n = 16 | 32),
* and a "key" in this example is actaully some value of key_len n that
* has its high order bits masked.
* For example: key = 1011 with key_len = 8, would actaully be the key:mask
* combo 1011xxxx:11110000. I am using short keys for ease of example)
* Case 1 and 2:
*
* assume 8 bit keys for all examples
*
* trie A contains keys 111011, 0, 10
* *
* / \
* *
* / \
* * * bits = 4 pos = 5 val = 1011 mask = 00111100
* inserting 111100 would result in the following split
* *
* / \
* *
* / \
* * bits = 1 pos = 5 val = 1 mask = 00100000
* / \
* bits = 2 pos = 3 val=11* * (to be inserted: (bits = 2 pos = 3 val = 00
* mask = 00001100 mask = 00001100))
*
* Case 3:
*
* trie A same as above, before insert
* inserting key 11101111 would results in the following split
* *
* / \
* *
* / \
* * * bits = 4 pos = 5 val = 1011 mask = 00111100
* / \
* * * (to be inserted: bits = 1 pos = 0 val = 1 mask = 00000001)
*/
/* ARGSUSED */
static void
{
uint8_t i;
int bit;
/* check if case is that the mask is longer */
/* pos is past the last bit covered at this node */
} else { /* pos > (nodep->pos - nodep->bits) */
/* nodep->pos will remain the same */
/* find the mismatch bit */
} else {
}
/* pos is before the last bit covered at this node */
/* bits gets remaining bits minus the link */
/* set bits that are covered by this node */
key_len);
}
} else { /* bit == ONE */
} else {
}
/* pos is before the last bit covered at this node */
/* bits gets remaining bits minus the link */
/* set bits that are covered by this node */
key_len);
}
}
/* clear bits no longer covered by this node, from pos=>0 */
for (i = 0; i <= pos; ++i) {
}
}
}
/*
* t_insert(tid, id, key, mask)
*
* inserts a new value, id, into the trie, tid->trie with the input key
* - if node exists, id is appended to element list at the node, if id does
* not already exist.
* - if node does not exist, a new node is created and id is the head of a new
* element list
* return DONTCARE_VALUE if mask == 0, otherwise NORMAL_VALUE
*/
int
{
int bit;
/* don't insert if don't care */
if (mask == 0) {
return (DONTCARE_VALUE);
}
/* traverse trie to the correct position */
/* check if bit is significant */
/* bit in key is significant if it is covered by the mask */
/* check if this is a path compressed internal node */
/* check if split is needed */
}
}
break;
}
/* extra bit at current position */
/* check if this is a path compressed internal node */
/* check if split is needed */
/* testing for mismatch */
key_len)) {
} else {
continue; /* bits match, so go on */
}
/* check if at a leaf node with elements */
/*
* this case occurs when mask for key
* is longer than mask for key at
* current node
*/
}
} /* else continue onto child */
}
}
/* bit at pos for node value should be 0 */
} else {
/* assert that trie is path compressed */
}
} else { /* ONE bit */
}
/* bit at pos for node value should be 1 */
} else {
/* assert that trie is path compressed */
}
}
}
/* insert at node */
/* update stats */
/*
* check if this is the first key to be inserted that is not a
* don't care (*)
*/
}
return (NORMAL_VALUE);
}
/*
* t_insert6(tid, id, key, mask)
*
* specific to inserting keys of 128 bits in length
*/
int
{
int bit, i;
/* don't insert if don't care */
return (DONTCARE_VALUE);
}
/*
* A IPv6 address is structured as an array of four uint32_t
* values. The highest order of the bits are located in array[0]
*/
for (i = 0; i < 4; ++i) {
/* traverse trie to the correct position */
/* check if bit is significant */
!= ONE) {
break;
}
}
} else { /* ONE bit */
}
}
}
}
/* insert at node */
/* update stats */
/*
* check if this is the first key to be inserted that is not a
* don't care (*)
*/
}
return (NORMAL_VALUE);
}
/*
* t_traverse_delete(in_node, pos, id, key, mask, tid)
*
* used to traverse to the node containing id, as found under key
* once id is found, it is removed from the trie.
* Upon removing the id from a given node in the trie, path compression
* will be applied to nodes that are no longer compressed.
* If the id is successfully removed, tid->stats are updated
*/
static boolean_t
{
int bit;
return (B_FALSE); /* base failure case */
}
/* we've found the node the id is probably at */
if ((pos == 0) ||
ipgpc0dbg(("t_traverse_delete: id %d does not " \
"exist in trie\n", id));
return (B_FALSE); /* key does not exist at node */
} else {
/* update stats */
/* check if 0 values are inserted in this trie */
/* update dontcareonly boolean */
}
}
/* check if node has zero elements, is a LEAF node */
/* make sure we don't delete the root */
return (B_TRUE);
} else {
/* this is the root, just zero out the info */
}
}
return (B_FALSE);
}
/* check to see if node describes bits to skip */
ipgpc0dbg(("t_traverse_delete: id %d does not " \
"exist in trie\n", id));
return (B_FALSE); /* key does not exist at node */
}
/* search should continue if mask and pos are valid */
if ((pos == 0) ||
!= 1)) {
/* this node probably contains the id */
ipgpc0dbg(("t_traverse_delete: id %d does" \
"not exist in trie\n", id));
return (B_FALSE);
} else {
/* update stats */
/* check if 0 values are inserted */
/* update dontcare boolean */
}
}
/* check if node has zero elements & is a LEAF node */
/* make sure we don't delete the root */
c_node);
return (B_TRUE);
} else {
/* this is the root, zero out info */
}
}
return (B_FALSE);
}
}
/* extract next bit and test */
}
} else { /* ONE bit */
}
}
/*
* non path-compressed nodes will contain one child and no elements
* what occurs here:
* *
* / \
* * * <-- p_node->elements == NULL
* /
* * <-- c_node->elements = foo
* / \
* * * <-- children of c_node
* after:
* *
* / \
* * * <-- p_node->elements = foo
* / \
* * * <-- p_node adopts children of c_node
*/
/* move child elements to parent */
/* be sure to include the link in the bits */
/* c_node->pos will remain the same */
/* don't forget to mark the link */
/* don't forget to mark the link */
/* adopt children */
} else {
}
/* move child elements to parent */
/* be sure to include the link in the bits */
/* c_node->pos will remain the same */
/* don't forget to mark the link */
/* don't forget to mark the link */
/* adopt children */
} else {
}
}
/* check if node has zero elements, is a LEAF node */
/* make sure we don't delete the root */
return (B_TRUE);
} else {
/* this is the root, just zero out the info */
}
}
return (B_FALSE);
}
/*
* t_remove(tid, id, key, mask)
*
* removes a value associated with an id from the trie
* - if the item does not exist, nothing is removed
* - if more than one id share the same key, only the id specified is removed
*/
void
{
/* don't cares are not inserted */
if (mask == 0) {
return;
}
/* traverse to node containing id and remove the id from the trie */
&tid);
}
/*
* t_remove6(tid, id, key, mask)
*
* specific to removing key of 128 bits in length
*/
void
{
int bit, i;
/* don't cares are not inserted */
return;
}
/*
* A IPv6 address is structured as an array of four uint32_t
* values. The higest order of the bits are located in array[0]
*/
for (i = 0; i < 4; ++i) {
/* traverse trie to the correct position */
/* check if bit is significant */
!= ONE) {
break;
}
break;
}
} else { /* ONE bit */
break;
}
}
}
}
/* update stats */
/*
* check to see if only dontcare's are inserted
*/
}
}
}
}
/*
* t_retrieve(tid, key, fid_table)
*
* returns the number of found filters that match the input key
* - each value that matches either a partial or exact match on the key
* is inserted into the fid_table
* - some nodes may contain multiple id's, all items will be inserted
* into the fid_table
* - the find stops when an edge node is reached, the left and right nodes
* for the current node are null
* - 0 is returned if no matches are found, otherwise the number of matches
* is returned
* - (-1) is returned if a memory error occurred
*/
int
{
int bit;
int num_found = 0;
int ret;
/* ensure trie structure is allocated */
return (num_found);
}
/*
* foreach node encountered in the search, collect elements and append
* to a list to be returned
*/
/* check node for bits to check */
return (num_found); /* search is done */
}
/* pos is set to next bit not covered by node */
/* if node covers rest of bits in key */
break;
}
}
/* check node for elements */
/* signifies a memory error */
return (-1);
}
}
} else { /* bit == ONE */
}
/* search is finished, edge node reached */
return (num_found);
}
}
/* see if current node contains elements */
fid_table)) == -1) {
return (-1); /* signifies a memory error */
}
}
return (num_found);
}
/*
* t_retrieve6(tid, key, fid_table)
*
* specific to retrieving keys of 128 bits in length
*/
int
{
int bit, i;
int num_found = 0;
int ret;
/* ensure trie structure is allocated */
return (num_found);
}
/*
* A IPv6 address is structured as an array of four uint32_t
* values. The higest order of the bits are located in array[0]
*/
for (i = 0; i < 4; ++i) {
/*
* foreach node encountered in the search, collect elements
* and append to a list to be returned
*/
/* extract bit at pos */
bit =
} else {
}
/* search is finished, edge node reached */
return (num_found);
}
/* see if current node contains elements */
/* signifies a memory error */
return (-1);
}
}
}
}
return (num_found);
}