sorttable.c

来自「Sun公司Dream项目」· C语言 代码 · 共 1,136 行 · 第 1/3 页

    }
    if (n != NULL) {
	if (sortTable->keyFree != NULL) {
	    (*sortTable->keyFree)((void *)n->item.key);
	}
	sortTableNodeFree(sortTable, t);
    }
#ifdef	ASSERTS
    sortTable->wasModified = TRUE;
#endif	/* ASSERTS */
    return retVal;
}

void        *
_sortTableGet(const SortTable sortTable, const void *key)
{
    return (void *)sortTableFind(sortTable, key)->item.value;
}

/*
 * Returns true if the key is a member of the sorttable.
 */
Boolean
_sortTableIsMember(const SortTable sortTable, const void *key)
{
    return Boolean(sortTableFind(sortTable, key) != &sortTable->head);
}

/*
 * Remove the key-value pair from the sort table. It is not an error if key
 * does not exist. Returns the value associated with the removed key-value.
 * Returns NULL if the key is not found.
 */
void        *
_sortTableRemove(SortTable sortTable, const void *key)
{
    SortNode *s = sortTable->head.link[SORT_NODE_DIR_RIGHT];
    SortNodeDir dir = SORT_NODE_DIR_RIGHT;
    void *valuep = NULL;

    if (sortTable->mode == SORT_TABLE_MODE_MULTIPLE) {
	ABORT("attempt to remove from SORT_TABLE_MODE_MULTIPLE SortTable");
    }
    if (! s->link[SORT_NODE_DIR_LEFT]->isRed
	&& ! s->link[SORT_NODE_DIR_RIGHT]->isRed) {
	s->isRed = TRUE;
    }
    for (;;) {
	SortNodeDir nextDir;

	if (s->link[SORT_NODE_DIR_LEFT] == &sortTable->head) {
	    break;
	}
	nextDir = SortNodeDir((*sortTable->keyCmp)(key, s->item.key) < 0);
	if (! s->isRed && !s->link[nextDir]->isRed) {
	    if (s->link[!nextDir]->isRed) {
		(void) sortTableRotate(s->p, dir, SortNodeDir(!nextDir));
		s->isRed = TRUE;
		s->p->isRed = FALSE;
	    } else {
		SortNode *sib = s->p->link[!dir];

		ASSERT(s->p->isRed);
		ASSERT(! sib->isRed);
		ASSERT(sib->link[SORT_NODE_DIR_LEFT] != &sortTable->head);
		s->isRed = TRUE;
		s->p->isRed = FALSE;
		if (!sib->link[SORT_NODE_DIR_LEFT]->isRed
		    && !sib->link[SORT_NODE_DIR_RIGHT]->isRed) {
		    sib->isRed = TRUE;
		} else {
		    SortNodeDir redKidDir
			= (sib->link[SORT_NODE_DIR_LEFT]->isRed)
			      ? SORT_NODE_DIR_LEFT : SORT_NODE_DIR_RIGHT;
		    SortNode *p = s->p;
		    SortNode *g = p->p;
		    SortNodeDir cDir = (p == g->link[SORT_NODE_DIR_LEFT])
			? SORT_NODE_DIR_LEFT : SORT_NODE_DIR_RIGHT;

		    if (dir != redKidDir) {
			sib->isRed = TRUE;
			sib->link[redKidDir]->isRed = FALSE;
			(void) sortTableRotate(g, cDir, SortNodeDir(!dir));
		    } else {
			(void) sortTableRotate(s->p, SortNodeDir(!dir), redKidDir);
			(void) sortTableRotate(g, cDir, SortNodeDir(!dir));
		    }
		}
	    }
	}
	dir = nextDir;
	s = s->link[dir];
    }
    if (s != &sortTable->head && (*sortTable->keyCmp)(key, s->item.key) == 0) {
	SortNode *p = s->p;
	SortNode *g = p->p;
	SortNode *c = p->link[!dir];
	SortNodeDir gDir = (g == &sortTable->head) ? SORT_NODE_DIR_RIGHT
	     : SortNodeDir((*sortTable->keyCmp)(s->item.key, g->item.key) < 0);

	ASSERT (p->isRed || p == &sortTable->head);
	g->link[gDir] = c;
	c->p = g;
	if (p != &sortTable->head) {
	    if (sortTable->keyFree != NULL) {
		(*sortTable->keyFree)((void *)p->item.key);
	    }
	    sortTableNodeFree(sortTable, p);
	}

	valuep = (void *) s->item.value;
	if (sortTable->keyFree != NULL) {
	    (*sortTable->keyFree)((void *)s->item.key);
	}
	sortTableNodeFree(sortTable, s);
	sortTable->length -= 1;
    }
    sortTable->head.link[SORT_NODE_DIR_RIGHT]->isRed = FALSE;
#ifdef	ASSERTS
    sortTable->wasModified = TRUE;
#endif	/* ASSERTS */
    return valuep;
}

void
sortTableVerify(SortTable sortTable)
{
    /*
     * Verify:
     *	All nodes are either in tree or in free list.
     *  No node appears more than once.
     *  Children have correct parent pointers.
     *  Tree is correctly partitioned.
     *  No consecutive red nodes.
     *  All leaves are black.
     *  All data is in leaves.
     *  Black height is uniform.
     */
    int i;
    SortNode *n;

    sortTable->blackDepth = -1;
    sortTable->head.wasSeen = FALSE;
    for (i = 0; i < sortTable->size; i++) {
	sortTable->nodeArray[i].wasSeen = FALSE;
    }
    for (n = sortTable->freeNodep; n != NULL;
	    n = n->link[SORT_NODE_DIR_RIGHT]) {
	if (! n->isFree || n->wasSeen || n->hasData || n->isRed) {
	    ABORT("free corrupted");
	}
	n->wasSeen = TRUE;
    }
    if (sortTable->head.link[SORT_NODE_DIR_LEFT] != &sortTable->head
	|| sortTable->head.isRed || sortTable->head.isFree
	|| sortTable->head.wasSeen || sortTable->head.hasData
	|| sortTable->head.p != &sortTable->head) {
	ABORT("head corrupted");
    }
    sortTable->head.wasSeen = TRUE;
    if (sortTable->head.link[SORT_NODE_DIR_RIGHT] != &sortTable->head) {
	n = sortTable->head.link[SORT_NODE_DIR_RIGHT];
	if (n->p != &sortTable->head) {
	    ABORT("root parent");
	}
	if (n->link[SORT_NODE_DIR_LEFT] == &sortTable->head
		&& n->link[SORT_NODE_DIR_RIGHT] == &sortTable->head) {
	    /* Single node tree */
	    if (! n->hasData || n->isRed || n->isFree || n->wasSeen) {
		ABORT("single node corrupt");
	    }
	    n->wasSeen = TRUE;
	} else {
	    sortTableTraverse(sortTable, 0, n, NULL, NULL);
	}
    }
    for (i = 0; i < sortTable->size; i++) {
	if (! sortTable->nodeArray[i].wasSeen) {
	    ABORT("lost node");
	}
    }

}

void
sortTablePrint(SortTable sortTable, SortTablePrintFunc pFunc,
	       SortTableItemToStringFunc iFunc, int maxWidth)
{
    SortNode *n = sortTable->head.link[SORT_NODE_DIR_RIGHT];

    if (pFunc != NULL) {
	sortTable->pFunc = pFunc;
    } else {
	pFunc = sortTable->pFunc;
    }
    if (pFunc == NULL) {
	ABORT("no pFunc");
    }
    if (iFunc != NULL) {
	sortTable->iFunc = iFunc;
    } else {
	iFunc = sortTable->iFunc;
    }
    if (iFunc == NULL) {
	ABORT("no iFunc");
    }
    if (maxWidth != 0) {
	sortTable->maxWidth = maxWidth;
    } else {
	maxWidth = sortTable->maxWidth;
    }
    (*pFunc)("SortTable Contents:\n\n");
    if (n == &sortTable->head) {
	(*pFunc)("empty tree\n");
    } else {
	Deque deque = dequeNew(10, 10);
	n->printLow = 0;
	n->printHigh = maxWidth;
	n->level = 0;
	dequeEnqueueTail(deque, n);
	sortTableTraversePrint(sortTable, deque, pFunc, iFunc, 0, maxWidth);
	dequeFree(deque);
    }
    (*pFunc)("\n\n\n\n");
}


/*
 * Frees the sorttable. Does not free the values.
 */
void
sortTableFree(SortTable sortTable)
{
    if (sortTable->keyFree != NULL) {
	SortIter si = sortIterNew(sortTable);
	while (sortIterNext(si)) {
	    (*sortTable->keyFree)((void *)sortIterItem(si)->key);
	}
	sortIterFree(si);
    }
    free(sortTable->nodeArray);
    free(sortTable);
}

/************************************************************************
 * SortIter Class Interface
 ************************************************************************/

/*
 * Create a list Iterator
 * 
 * BEWARE: A list iterator is invalidated by any non-local-iterator list removal
 * of an item currently referenced by an iterator.  Doing so will cause
 * "undefined" results.
 */
SortIter
sortIterNew(const SortTable sortTable)
{
    SortIter si = NEW_ZEROED(struct _SortIter, 1);
    si->sortTable = sortTable;
    si->curNode = &sortTable->head;
    return si;
}

/************************************************************************
 * SortIter Instance Interface
 ************************************************************************/

/*
 * Position iterator at list head Returns TRUE if list is non-empty; FALSE if
 * list is empty.
 */
Boolean
sortIterHead(SortIter si)
{
    SortTable sortTable = si->sortTable;
    SortNode *n = sortTable->head.link[SORT_NODE_DIR_RIGHT];

    if (n == &sortTable->head) {
	return FALSE;
    }
    while (n->link[SORT_NODE_DIR_LEFT] != &sortTable->head) {
	n = n->link[SORT_NODE_DIR_LEFT];
    }
    si->curNode = n;
#ifdef	ASSERTS
    sortTable->wasModified = FALSE;
#endif	/* ASSERTS */
    return TRUE;
}

/*
 * Position iterator at list tail Returns TRUE if list is non-empty; FALSE if
 * list is empty.
 */
Boolean
sortIterTail(SortIter si)
{
    SortTable sortTable = si->sortTable;
    SortNode *n = sortTable->head.link[SORT_NODE_DIR_RIGHT];

    if (n == &sortTable->head) {
	return FALSE;
    }
    while (n->link[SORT_NODE_DIR_RIGHT] != &sortTable->head) {
	n = n->link[SORT_NODE_DIR_RIGHT];
    }
    si->curNode = n;
#ifdef	ASSERTS
    sortTable->wasModified = FALSE;
#endif	/* ASSERTS */
    return TRUE;
}

/*
 * Position iterator at item.  If duplicates are present, it is unpredictable
 * which of them will be found.
 * Return TRUE if item found.  Return FALSE if item not found. Position of
 * iterator is unchanged if item not found.
 */
extern Boolean
_sortIterFind(SortIter si, const void *key)
{
    SortTable sortTable = si->sortTable;
    SortNode *n = sortTableFind(sortTable, key);
    if (n != &sortTable->head) {
	si->curNode = n;
#ifdef	ASSERTS
	sortTable->wasModified = FALSE;
#endif	/* ASSERTS */
	return TRUE;
    }
    return FALSE;
}

/*
 * Position iterator after item. If item is not found, iterator is positioned
 * at first item that would be after the item if it were present.
 * Returns TRUE if there is an item after key, FALSE otherwise.
 */
extern Boolean
_sortIterAfter(SortIter si, const void *key)
{
    SortTable sortTable = si->sortTable;

    si->curNode = sortTable->head.link[SORT_NODE_DIR_RIGHT];
    for (;;) {
	if (si->curNode->link[SORT_NODE_DIR_RIGHT] == &sortTable->head) {
	    break;
	}
	si->curNode = si->curNode->link[
		(*sortTable->keyCmp)(key, si->curNode->item.key) < 0];
    }
    while (si->curNode != &sortTable->head
	   && (*sortTable->keyCmp)(key, si->curNode->item.key) >= 0) {
	(void) sortIterNext(si);
    }
#ifdef	ASSERTS
    sortTable->wasModified = FALSE;
#endif	/* ASSERTS */
    return Boolean(si->curNode != &sortTable->head);
}

/*
 * Position iterator before item. If item is not found, iterator is
 * positioned at first item that would be before the item if it were present.
 */
extern Boolean
_sortIterBefore(SortIter si, const void *key)
{
    SortTable sortTable = si->sortTable;

    si->curNode = sortTable->head.link[SORT_NODE_DIR_RIGHT];
    for (;;) {
	if (si->curNode->link[SORT_NODE_DIR_RIGHT] == &sortTable->head) {
	    break;
	}
	si->curNode = si->curNode->link[
		(*sortTable->keyCmp)(key, si->curNode->item.key) < 0];