sorttable.c

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

/*
 * The contents of this file are subject to the terms
 * of the Common Development and Distribution License
 * (the "License").  You may not use this file except
 * in compliance with the License.
 *
 * You can obtain a copy of the license at
 * http://www.opensource.org/licenses/cddl1.php
 * 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
 * http://www.opensource.org/licenses/cddl1.php.  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]
 */ 

/*
 * $(@)SortTable.c $Revision: 1.2 $ $Date: 2006/07/15 00:02:35 $
 * 
 * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
 */
/*
 * Copyright (c) 1998 by Sun Microsystems, Inc.
 */

/*
 * SortTable.c -- Iterable red-black binary tree.
 *
 * FIXME: This doesn't free key's properly -- how should duplicated
 * internal keys be handled??
 */

#pragma ident "@(#)SortTable.c 1.2	99/03/22 SMI"

#if	!defined(SORTTABLE_HEADER)
#define	SORTTABLE_BODY
#define	SORTTABLE_INLINE		extern
#include "cobjs/SortTable.h"
#endif					   /* !defined(SORTTABLE_HEADER) */

#include <stdlib.h>

#include "cobjs/Deque.h"
#include "cobjs/Log.h"
#include "cobjs/Macros.h"
#include "cobjs/Types.h"

/*************************************************************************
 * Defines
 *************************************************************************/

#define	SORT_TABLE_DEFAULT_SIZE		128

/*************************************************************************
 * Instance Variables
 *************************************************************************/

typedef struct SortNode SortNode;

struct SortNode {
    SortItem	item;
    SortNode	*link[2];
    SortNode	*p;
    Boolean	isRed:1;
    Boolean	isFree:1;
    Boolean	wasSeen:1;
    Boolean	hasData:1;
    int		printLow:10;
    int		printHigh:10;
    int		level:8;
};

struct _SortTable {
    SortTableMode	mode;
    int			length;		/* used entries in nodeArray */
    int			size;		/* total entries in nodeArray */
    int			blackDepth;
    SortNode		head;
    SortNode		*freeNodep;
    SortNode		*nodeArray;
    SortKeyCmp		keyCmp;
    SortKeyDup		keyDup;
    SortKeyFree		keyFree;
    SortTablePrintFunc	pFunc;
    SortTableItemToStringFunc iFunc;
    int			maxWidth;
#ifdef	ASSERTS
    Boolean		wasModified;
#endif	/* ASSERTS */
};

struct _SortIter {
    SortTable		sortTable;
    SortNode		*curNode;
};

/*************************************************************************
 * Private types and prototypes referenced from inlines
 *************************************************************************/

/*
 * Use INLINE_PRIVATE if non-inline-able, define in Non-inlinable section
 * Use static if inline-able, define in Private Inline-able section
 *
 * INLINE_PRIVATE void sortTableInlinePrivate(void);
 */

/*************************************************************************
 * Private class data referenced from inlines
 *************************************************************************/

/*************************************************************************
 * Inline Methods
 *************************************************************************/

/*
 * Returns the current length of the sort table.
 */
SORTTABLE_INLINE int
sortTableLength(const SortTable sortTable)
{
    return sortTable->length;
}

/*
 * Return the item referenced by the iterator Returns NULL if iterator not
 * positioned at item.
 */
SORTTABLE_INLINE SortItem   *
sortIterItem(const SortIter si)
{
    ASSERT(! si->sortTable->wasModified);
    return sortIterValid(si) ? &si->curNode->item : NULL;
}

/*
 * Return the key referenced by the iterator Returns NULL if iterator not
 * positioned at item.
 */
SORTTABLE_INLINE const void   *
sortIterKey(const SortIter si)
{
    ASSERT(! si->sortTable->wasModified);
    return si->curNode->item.key;
}

/*
 * Return the value referenced by the iterator Returns NULL if iterator not
 * positioned at item.
 */
SORTTABLE_INLINE const void   *
sortIterValue(const SortIter si)
{
    ASSERT(! si->sortTable->wasModified);
    return si->curNode->item.value;
}

/*
 * Return TRUE if iterator points to valid item
 */
SORTTABLE_INLINE Boolean
sortIterValid(const SortIter si)
{
    ASSERT(! si->sortTable->wasModified);
    return Boolean(si->curNode != &si->sortTable->head);
}

/*************************************************************************
 * Private Inlineable Methods and Functions Called From Inlines
 *************************************************************************/

#if	!defined(SORTTABLE_HEADER)

/*************************************************************************
 * Private types
 *************************************************************************/

typedef enum SortNodeDir {
    SORT_NODE_DIR_RIGHT = 0,
    SORT_NODE_DIR_LEFT = 1
}  SortNodeDir;

/*************************************************************************
 * Private method prototypes
 *************************************************************************/
static SortNode *sortTableFind(const SortTable sortTable, const void *key);
static SortNode *sortTableSplit(SortTable sortTable, const void *key,
				SortNode *s);
static SortNode *sortTableRotate(SortNode *r, SortNodeDir cDir,
				 SortNodeDir gcDir);
static SortNode *sortTableNodeAlloc(SortTable sortTable, SortNode **reallocpp);
static void sortTableNodeFree(SortTable sortTable, SortNode *nodep);
static void sortTableTraverse(SortTable sortTable, int blackDepth, SortNode *n,
	SortNode *min, SortNode *max);
static void sortTableTraversePrint(SortTable sortTable, Deque deque,
	SortTablePrintFunc pFunc, SortTableItemToStringFunc iFunc, int level,
	int maxWidth);

/*************************************************************************
 * Private function prototypes
 *************************************************************************/
static int strKeyCmp(const void *key1, const void *key2);
static const void *strKeyDup(const void *key, const void *value);
static int intKeyCmp(const void *key1, const void *key2);
static void strInsert(char *dst, char *src, int maxlen);

/*************************************************************************
 * Private class data
 *************************************************************************/

/*************************************************************************
 * Class Methods
 *************************************************************************/

/*
 * Create a string keyed sorttable.
 */
SortTable
sortTableStrNew(SortTableMode mode)
{
    return sortTableNewWithSize(mode, SORT_TABLE_DEFAULT_SIZE, strKeyCmp,
				strKeyDup, free);
}

/*
 * Create an integer keyed sorttable.
 */
SortTable
sortTableIntNew(SortTableMode mode)
{
    return sortTableNewWithSize(mode, SORT_TABLE_DEFAULT_SIZE, intKeyCmp,
				NULL, NULL);
}

/*
 * Creates and returns a new sort table with default size and fill factor.
 * 
 * keyCmp, keyDup, and keyFree are routines which implement the
 * named key functions.
 */
SortTable
sortTableNew(SortTableMode mode, SortKeyCmp keyCmp, SortKeyDup keyDup,
	SortKeyFree keyFree)
{
    return sortTableNewWithSize(mode, SORT_TABLE_DEFAULT_SIZE, keyCmp, keyDup,
				keyFree);
}

SortTable
sortTableIntNewWithSize(SortTableMode mode, int size)
{
    return sortTableNewWithSize(mode, size, intKeyCmp, NULL, NULL);
}

SortTable
sortTableStrNewWithSize(SortTableMode mode, int size)
{
    return sortTableNewWithSize(mode, size, strKeyCmp, strKeyDup, free);
}

/*
 * Create a sort table with a given initial size.
 */
SortTable
sortTableNewWithSize(SortTableMode mode, int size, SortKeyCmp keyCmp,
	SortKeyDup keyDup, SortKeyFree keyFree)
{
    SortTable sortTable = NEW_ZEROED(struct _SortTable, 1);
    int i;

    switch (mode) {
    case SORT_TABLE_MODE_UNIQUE:
    case SORT_TABLE_MODE_OVERWRITE:
    case SORT_TABLE_MODE_MULTIPLE:
	break;
    default:
	ABORT("illegal sortTable mode value");
    }
    sortTable->mode = mode;
    sortTable->keyCmp = keyCmp;
    sortTable->keyDup = keyDup;
    sortTable->keyFree = keyFree;
    sortTable->pFunc = NULL;
    sortTable->iFunc = NULL;
    sortTable->maxWidth = 80;
    sortTable->length = 0;
    sortTable->nodeArray = NEW_ZEROED(SortNode, size);
    sortTable->size = size;
    sortTable->freeNodep = NULL;
    for (i = 0; i < size; i++) {
	sortTableNodeFree(sortTable, &sortTable->nodeArray[i]);
    }
    sortTable->head.item.key = NULL;
    sortTable->head.item.value = NULL;
    sortTable->head.link[SORT_NODE_DIR_LEFT] = &sortTable->head;
    sortTable->head.link[SORT_NODE_DIR_RIGHT] = &sortTable->head;
    sortTable->head.p = &sortTable->head;
    sortTable->head.isRed = FALSE;
    sortTable->head.hasData = FALSE;
    sortTable->head.isFree = FALSE;
#ifdef	ASSERTS
    sortTable->wasModified = FALSE;
#endif	/* ASSERTS */
    return sortTable;
}

/*************************************************************************
 * Instance Methods
 *************************************************************************/

/*
 * Enters key-value pair into sort table. If key already exists, it's value
 * is overwritten.
 */
Boolean
_sortTablePut(SortTable sortTable, const void *key, const void *value)
{
    SortNode *n = sortTableNodeAlloc(sortTable, NULL);
    SortNode *t = sortTableNodeAlloc(sortTable, &n);
    SortNode *s = sortTable->head.link[SORT_NODE_DIR_RIGHT];
    SortNode *p;
    SortNodeDir pDir = SORT_NODE_DIR_RIGHT;
    Boolean retVal = TRUE;

    n->link[SORT_NODE_DIR_LEFT] = &sortTable->head;
    n->link[SORT_NODE_DIR_RIGHT] = &sortTable->head;
    n->item.key = sortTable->keyDup != NULL
		? (*sortTable->keyDup)(key, NULL) : key;
    n->item.value = value;
    n->hasData = TRUE;

    while (s->link[SORT_NODE_DIR_RIGHT] != &sortTable->head) {
	if (s->link[SORT_NODE_DIR_LEFT]->isRed
	    && s->link[SORT_NODE_DIR_RIGHT]->isRed) {
	    s = sortTableSplit(sortTable, key, s);
	}
	pDir = SortNodeDir((*sortTable->keyCmp)(key, s->item.key) < 0);
	s = s->link[pDir];
    }
    p = s->p;
    if (p != s) {
	int cmp = (*sortTable->keyCmp)(key, s->item.key);
	const void *iKey;
	SortNodeDir dir = SortNodeDir(cmp < 0);
	if (cmp == 0) {
	    retVal = FALSE;
	    switch (sortTable->mode) {
	    case SORT_TABLE_MODE_UNIQUE:
		goto done;
	    case SORT_TABLE_MODE_OVERWRITE:
		s->item.value = value;
		goto done;
	    }
	}
	iKey = (dir == SORT_NODE_DIR_LEFT) ? s->item.key : n->item.key;
	t->item.key = sortTable->keyDup != NULL
		    ? (*sortTable->keyDup)(iKey, NULL) : iKey;
	t->item.value = NULL;
	t->link[dir] = n;
	t->link[! dir] = s;
	t->hasData = FALSE;
	n->p = t;
	s->p = t;
	n = t;
	t = NULL;
    }
    n->p = p;
    p->link[pDir] = n;
    (void) sortTableSplit(sortTable, n->item.key, n);
    n = NULL;
    sortTable->length += 1;
done:
    if (t != NULL) {
	sortTableNodeFree(sortTable, t);