uu_avl.c revision 8918dff3e162b85faa068f02fc6f2ca350150e71
/*
* 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 2005 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include "libuutil_common.h"
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
/*
* The index mark change on every insert and delete, to catch stale
* references.
*
* We leave the low bit alone, since the avl code uses it.
*/
#define INDEX_DECODE(i) ((i) & ~INDEX_MAX)
#define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0)
/*
* When an element is inactive (not in a tree), we keep a marked pointer to
* its containing pool in its first word, and a NULL pointer in its second.
*
* On insert, we use these to verify that it comes from the correct pool.
*/
(pp)->uap_nodeoffset))
#define DEAD_MARKER 0xc4
{
compare_func == NULL) {
return (NULL);
}
if (flags & ~UU_AVL_POOL_DEBUG) {
return (NULL);
}
return (NULL);
}
if (flags & UU_AVL_POOL_DEBUG)
pp->uap_last_index = 0;
(void) pthread_mutex_lock(&uu_apool_list_lock);
(void) pthread_mutex_unlock(&uu_apool_list_lock);
return (pp);
}
void
{
uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has "
"outstanding avls, or is corrupt.\n",
}
}
(void) pthread_mutex_lock(&uu_apool_list_lock);
(void) pthread_mutex_unlock(&uu_apool_list_lock);
}
void
{
uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
"offset %ld doesn't fit in object (size %ld)\n",
pp->uap_objsize);
}
uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
"offset %ld doesn't match pool's offset (%ld)\n",
pp->uap_objsize);
}
}
}
void
{
uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
"node already finied\n",
}
uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
"node corrupt, in tree, or in different pool\n",
}
}
na[0] = DEAD_MARKER;
}
struct uu_avl_node_compare_info {
void *ac_private;
void *ac_right;
void *ac_found;
};
static int
uu_avl_node_compare(const void *l, const void *r)
{
struct uu_avl_node_compare_info *info =
(struct uu_avl_node_compare_info *)l;
if (res == 0) {
return (-1);
}
if (res < 0)
return (1);
return (-1);
}
uu_avl_t *
{
if (flags & ~UU_AVL_DEBUG) {
return (NULL);
}
return (NULL);
}
pp->uap_nodeoffset);
return (ap);
}
void
{
}
uu_panic("uu_avl_destroy(%p): outstanding walkers\n",
ap);
}
}
}
{
}
void *
{
}
void *
{
}
void *
{
}
void *
{
}
static void
{
if (direction > 0)
else
}
}
static void *
{
return (NULL);
return (np);
}
static void
{
}
}
{
return (NULL);
}
return (NULL);
}
return (wp);
}
void *
{
}
void
{
}
int
{
void *e;
int status = UU_WALK_NEXT;
return (-1);
}
while (status == UU_WALK_NEXT &&
if (status >= 0)
return (0);
return (-1);
}
void
{
/*
* invalidate outstanding uu_avl_index_ts.
*/
}
/*
* Robust walkers most be advanced, if we are removing the node
* they are currently using. In debug mode, non-robust walkers
* are also on the walker list.
*/
if (wp->uaw_robust) {
uu_panic("uu_avl_remove(%p, %p): active non-robust "
}
}
}
void *
{
}
return (elem);
}
void *
{
struct uu_avl_node_compare_info info;
void *result;
uu_panic("uu_avl_find: internal error: avl_find succeeded\n");
}
void
{
uu_panic("uu_avl_insert(%p, %p, %p): node already "
"in tree, or corrupt\n",
uu_panic("uu_avl_insert(%p, %p, %p): node not "
"initialized\n",
uu_panic("uu_avl_insert(%p, %p, %p): node from "
"other pool, or corrupt\n",
uu_panic("uu_avl_insert(%p, %p, %p): %s\n",
"invalid index");
/*
* invalidate outstanding uu_avl_index_ts.
*/
}
}
void *
{
uu_panic("uu_avl_nearest_next(%p, %p): %s\n",
"invalid index");
}
void *
{
uu_panic("uu_avl_nearest_prev(%p, %p): %s\n",
"invalid index");
}
/*
* called from uu_lockup() and uu_release(), as part of our fork1()-safety.
*/
void
uu_avl_lockup(void)
{
(void) pthread_mutex_lock(&uu_apool_list_lock);
}
void
uu_avl_release(void)
{
(void) pthread_mutex_unlock(&uu_apool_list_lock);
}