#include <mach/port.h>
#include <kern/assert.h>
#include <kern/macro_help.h>
#include <ipc/ipc_entry.h>
#include <ipc/ipc_splay.h>
#define MACH_PORT_SMALLEST ((mach_port_name_t) 0)
#define MACH_PORT_LARGEST ((mach_port_name_t) ~0)
static void
ipc_splay_prim_lookup(
mach_port_name_t name,
ipc_tree_entry_t tree,
ipc_tree_entry_t *treep,
ipc_tree_entry_t *ltreep,
ipc_tree_entry_t **ltreepp,
ipc_tree_entry_t *rtreep,
ipc_tree_entry_t **rtreepp)
{
mach_port_name_t tname;
ipc_tree_entry_t lchild, rchild;
assert(tree != ITE_NULL);
#define link_left \
MACRO_BEGIN \
*ltreep = tree; \
ltreep = &tree->ite_rchild; \
tree = *ltreep; \
MACRO_END
#define link_right \
MACRO_BEGIN \
*rtreep = tree; \
rtreep = &tree->ite_lchild; \
tree = *rtreep; \
MACRO_END
#define rotate_left \
MACRO_BEGIN \
ipc_tree_entry_t temp = tree; \
\
tree = temp->ite_rchild; \
temp->ite_rchild = tree->ite_lchild; \
tree->ite_lchild = temp; \
MACRO_END
#define rotate_right \
MACRO_BEGIN \
ipc_tree_entry_t temp = tree; \
\
tree = temp->ite_lchild; \
temp->ite_lchild = tree->ite_rchild; \
tree->ite_rchild = temp; \
MACRO_END
while (name != (tname = tree->ite_name)) {
if (name < tname) {
lchild = tree->ite_lchild;
if (lchild == ITE_NULL)
break;
tname = lchild->ite_name;
if ((name < tname) &&
(lchild->ite_lchild != ITE_NULL))
rotate_right;
link_right;
if ((name > tname) &&
(lchild->ite_rchild != ITE_NULL))
link_left;
} else {
rchild = tree->ite_rchild;
if (rchild == ITE_NULL)
break;
tname = rchild->ite_name;
if ((name > tname) &&
(rchild->ite_rchild != ITE_NULL))
rotate_left;
link_left;
if ((name < tname) &&
(rchild->ite_lchild != ITE_NULL))
link_right;
}
assert(tree != ITE_NULL);
}
*treep = tree;
*ltreepp = ltreep;
*rtreepp = rtreep;
#undef link_left
#undef link_right
#undef rotate_left
#undef rotate_right
}
static void
ipc_splay_prim_assemble(
ipc_tree_entry_t tree,
ipc_tree_entry_t *ltree,
ipc_tree_entry_t *ltreep,
ipc_tree_entry_t *rtree,
ipc_tree_entry_t *rtreep)
{
assert(tree != ITE_NULL);
*ltreep = tree->ite_lchild;
*rtreep = tree->ite_rchild;
tree->ite_lchild = *ltree;
tree->ite_rchild = *rtree;
}
void
ipc_splay_tree_init(
ipc_splay_tree_t splay)
{
splay->ist_root = ITE_NULL;
}
boolean_t
ipc_splay_tree_pick(
ipc_splay_tree_t splay,
mach_port_name_t *namep,
ipc_tree_entry_t *entryp)
{
ipc_tree_entry_t root;
ist_lock(splay);
root = splay->ist_root;
if (root != ITE_NULL) {
*namep = root->ite_name;
*entryp = root;
}
ist_unlock(splay);
return root != ITE_NULL;
}
ipc_tree_entry_t
ipc_splay_tree_lookup(
ipc_splay_tree_t splay,
mach_port_name_t name)
{
ipc_tree_entry_t root;
ist_lock(splay);
root = splay->ist_root;
if (root != ITE_NULL) {
if (splay->ist_name != name) {
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
ipc_splay_prim_lookup(name, root, &root,
&splay->ist_ltree, &splay->ist_ltreep,
&splay->ist_rtree, &splay->ist_rtreep);
splay->ist_name = name;
splay->ist_root = root;
}
if (name != root->ite_name)
root = ITE_NULL;
}
ist_unlock(splay);
return root;
}
void
ipc_splay_tree_insert(
ipc_splay_tree_t splay,
mach_port_name_t name,
ipc_tree_entry_t entry)
{
ipc_tree_entry_t root;
assert(entry != ITE_NULL);
ist_lock(splay);
root = splay->ist_root;
if (root == ITE_NULL) {
entry->ite_lchild = ITE_NULL;
entry->ite_rchild = ITE_NULL;
} else {
if (splay->ist_name != name) {
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
ipc_splay_prim_lookup(name, root, &root,
&splay->ist_ltree, &splay->ist_ltreep,
&splay->ist_rtree, &splay->ist_rtreep);
}
assert(root->ite_name != name);
if (name < root->ite_name) {
assert(root->ite_lchild == ITE_NULL);
*splay->ist_ltreep = ITE_NULL;
*splay->ist_rtreep = root;
} else {
assert(root->ite_rchild == ITE_NULL);
*splay->ist_ltreep = root;
*splay->ist_rtreep = ITE_NULL;
}
entry->ite_lchild = splay->ist_ltree;
entry->ite_rchild = splay->ist_rtree;
}
entry->ite_name = name;
splay->ist_root = entry;
splay->ist_name = name;
splay->ist_ltreep = &splay->ist_ltree;
splay->ist_rtreep = &splay->ist_rtree;
ist_unlock(splay);
}
void
ipc_splay_tree_delete(
ipc_splay_tree_t splay,
mach_port_name_t name,
__assert_only ipc_tree_entry_t entry)
{
ipc_tree_entry_t root, saved;
ist_lock(splay);
root = splay->ist_root;
assert(root != ITE_NULL);
if (splay->ist_name != name) {
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
ipc_splay_prim_lookup(name, root, &root,
&splay->ist_ltree, &splay->ist_ltreep,
&splay->ist_rtree, &splay->ist_rtreep);
}
assert(root->ite_name == name);
assert(root == entry);
*splay->ist_ltreep = root->ite_lchild;
*splay->ist_rtreep = root->ite_rchild;
ite_free(root);
root = splay->ist_ltree;
saved = splay->ist_rtree;
if (root == ITE_NULL)
root = saved;
else if (saved != ITE_NULL) {
ipc_splay_prim_lookup(MACH_PORT_LARGEST, root, &root,
&splay->ist_ltree, &splay->ist_ltreep,
&splay->ist_rtree, &splay->ist_rtreep);
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
assert(root->ite_rchild == ITE_NULL);
root->ite_rchild = saved;
}
splay->ist_root = root;
if (root != ITE_NULL) {
splay->ist_name = root->ite_name;
splay->ist_ltreep = &splay->ist_ltree;
splay->ist_rtreep = &splay->ist_rtree;
}
ist_unlock(splay);
}
void
ipc_splay_tree_split(
ipc_splay_tree_t splay,
mach_port_name_t name,
ipc_splay_tree_t small)
{
ipc_tree_entry_t root;
ipc_splay_tree_init(small);
ist_lock(splay);
root = splay->ist_root;
if (root != ITE_NULL) {
if (splay->ist_name != name) {
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
ipc_splay_prim_lookup(name, root, &root,
&splay->ist_ltree, &splay->ist_ltreep,
&splay->ist_rtree, &splay->ist_rtreep);
}
if (root->ite_name < name) {
*splay->ist_ltreep = root->ite_lchild;
*splay->ist_rtreep = ITE_NULL;
root->ite_lchild = splay->ist_ltree;
assert(root->ite_rchild == ITE_NULL);
small->ist_root = root;
small->ist_name = root->ite_name;
small->ist_ltreep = &small->ist_ltree;
small->ist_rtreep = &small->ist_rtree;
root = splay->ist_rtree;
splay->ist_root = root;
if (root != ITE_NULL) {
splay->ist_name = root->ite_name;
splay->ist_ltreep = &splay->ist_ltree;
splay->ist_rtreep = &splay->ist_rtree;
}
} else {
*splay->ist_ltreep = root->ite_lchild;
root->ite_lchild = ITE_NULL;
splay->ist_root = root;
splay->ist_name = name;
splay->ist_ltreep = &splay->ist_ltree;
root = splay->ist_ltree;
small->ist_root = root;
if (root != ITE_NULL) {
small->ist_name = root->ite_name;
small->ist_ltreep = &small->ist_ltree;
small->ist_rtreep = &small->ist_rtree;
}
}
}
ist_unlock(splay);
}
void
ipc_splay_tree_join(
ipc_splay_tree_t splay,
ipc_splay_tree_t small)
{
ipc_tree_entry_t sroot;
ist_lock(small);
sroot = small->ist_root;
if (sroot != ITE_NULL) {
ipc_splay_prim_assemble(sroot,
&small->ist_ltree, small->ist_ltreep,
&small->ist_rtree, small->ist_rtreep);
small->ist_root = ITE_NULL;
}
ist_unlock(small);
if (sroot != ITE_NULL) {
ipc_tree_entry_t root;
ist_lock(splay);
root = splay->ist_root;
if (root == ITE_NULL) {
root = sroot;
} else {
if (splay->ist_name != MACH_PORT_SMALLEST) {
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
ipc_splay_prim_lookup(MACH_PORT_SMALLEST,
root, &root,
&splay->ist_ltree, &splay->ist_ltreep,
&splay->ist_rtree, &splay->ist_rtreep);
}
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
assert(root->ite_lchild == ITE_NULL);
assert(sroot->ite_name < root->ite_name);
root->ite_lchild = sroot;
}
splay->ist_root = root;
splay->ist_name = root->ite_name;
splay->ist_ltreep = &splay->ist_ltree;
splay->ist_rtreep = &splay->ist_rtree;
ist_unlock(splay);
}
}
void
ipc_splay_tree_bounds(
ipc_splay_tree_t splay,
mach_port_name_t name,
mach_port_name_t *lowerp,
mach_port_name_t *upperp)
{
ipc_tree_entry_t root;
ist_lock(splay);
root = splay->ist_root;
if (root == ITE_NULL) {
*lowerp = MACH_PORT_LARGEST;
*upperp = MACH_PORT_SMALLEST;
} else {
mach_port_name_t rname;
if (splay->ist_name != name) {
ipc_splay_prim_assemble(root,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
ipc_splay_prim_lookup(name, root, &root,
&splay->ist_ltree, &splay->ist_ltreep,
&splay->ist_rtree, &splay->ist_rtreep);
splay->ist_name = name;
splay->ist_root = root;
}
rname = root->ite_name;
if (rname <= name)
*lowerp = rname;
else if (splay->ist_ltreep == &splay->ist_ltree)
*lowerp = MACH_PORT_LARGEST;
else {
ipc_tree_entry_t entry;
entry = (ipc_tree_entry_t)
((char *)splay->ist_ltreep -
((char *)&root->ite_rchild -
(char *)root));
*lowerp = entry->ite_name;
}
if (rname >= name)
*upperp = rname;
else if (splay->ist_rtreep == &splay->ist_rtree)
*upperp = MACH_PORT_SMALLEST;
else {
ipc_tree_entry_t entry;
entry = (ipc_tree_entry_t)
((char *)splay->ist_rtreep -
((char *)&root->ite_lchild -
(char *)root));
*upperp = entry->ite_name;
}
}
ist_unlock(splay);
}
ipc_tree_entry_t
ipc_splay_traverse_start(
ipc_splay_tree_t splay)
{
ipc_tree_entry_t current, parent;
ist_lock(splay);
current = splay->ist_root;
if (current != ITE_NULL) {
ipc_splay_prim_assemble(current,
&splay->ist_ltree, splay->ist_ltreep,
&splay->ist_rtree, splay->ist_rtreep);
parent = ITE_NULL;
while (current->ite_lchild != ITE_NULL) {
ipc_tree_entry_t next;
next = current->ite_lchild;
current->ite_lchild = parent;
parent = current;
current = next;
}
splay->ist_ltree = current;
splay->ist_rtree = parent;
}
return current;
}
ipc_tree_entry_t
ipc_splay_traverse_next(
ipc_splay_tree_t splay,
boolean_t delete)
{
ipc_tree_entry_t current, parent;
current = splay->ist_ltree;
parent = splay->ist_rtree;
assert(current != ITE_NULL);
if (!delete)
goto traverse_right;
if (current->ite_lchild == ITE_NULL) {
if (current->ite_rchild == ITE_NULL) {
if (parent == ITE_NULL) {
ite_free(current);
splay->ist_root = ITE_NULL;
return ITE_NULL;
}
if (current->ite_name < parent->ite_name) {
ite_free(current);
current = parent;
parent = current->ite_lchild;
current->ite_lchild = ITE_NULL;
goto traverse_entry;
} else {
ite_free(current);
current = parent;
parent = current->ite_rchild;
current->ite_rchild = ITE_NULL;
goto traverse_back;
}
} else {
ipc_tree_entry_t prev;
prev = current;
current = current->ite_rchild;
ite_free(prev);
goto traverse_left;
}
} else {
if (current->ite_rchild == ITE_NULL) {
ipc_tree_entry_t prev;
prev = current;
current = current->ite_lchild;
ite_free(prev);
goto traverse_back;
} else {
ipc_tree_entry_t prev;
ipc_tree_entry_t ltree, rtree;
ipc_tree_entry_t *ltreep, *rtreep;
prev = current;
ipc_splay_prim_lookup(MACH_PORT_LARGEST,
current->ite_lchild, ¤t,
<ree, <reep, &rtree, &rtreep);
ipc_splay_prim_assemble(current,
<ree, ltreep, &rtree, rtreep);
assert(current->ite_rchild == ITE_NULL);
current->ite_rchild = prev->ite_rchild;
ite_free(prev);
goto traverse_right;
}
}
traverse_left:
if (current->ite_lchild != ITE_NULL) {
ipc_tree_entry_t next;
next = current->ite_lchild;
current->ite_lchild = parent;
parent = current;
current = next;
goto traverse_left;
}
traverse_entry:
splay->ist_ltree = current;
splay->ist_rtree = parent;
return current;
traverse_right:
if (current->ite_rchild != ITE_NULL) {
ipc_tree_entry_t next;
next = current->ite_rchild;
current->ite_rchild = parent;
parent = current;
current = next;
goto traverse_left;
}
traverse_back:
if (parent == ITE_NULL) {
splay->ist_root = current;
return ITE_NULL;
}
if (current->ite_name < parent->ite_name) {
ipc_tree_entry_t prev;
prev = current;
current = parent;
parent = current->ite_lchild;
current->ite_lchild = prev;
goto traverse_entry;
} else {
ipc_tree_entry_t prev;
prev = current;
current = parent;
parent = current->ite_rchild;
current->ite_rchild = prev;
goto traverse_back;
}
}
void
ipc_splay_traverse_finish(
ipc_splay_tree_t splay)
{
ipc_tree_entry_t root;
root = splay->ist_root;
if (root != ITE_NULL) {
splay->ist_name = root->ite_name;
splay->ist_ltreep = &splay->ist_ltree;
splay->ist_rtreep = &splay->ist_rtree;
}
ist_unlock(splay);
}