sorttable.c

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

    }
    while (si->curNode != &sortTable->head
	   && (*sortTable->keyCmp)(key, si->curNode->item.key) <= 0) {
	(void) sortIterPrev(si);
    }
#ifdef	ASSERTS
    sortTable->wasModified = FALSE;
#endif	/* ASSERTS */
    return Boolean(si->curNode != &sortTable->head);
}

/*
 * Position iterator at next item in list. Return TRUE if there is a next
 * item; FALSE if wrapping around.
 */
Boolean
sortIterNext(SortIter si)
{
    SortNode *s = si->curNode;
    SortNode *c;

    if (s == &si->sortTable->head) {
	return sortIterHead(si);
    }

    ASSERT(! si->sortTable->wasModified);
    do {
	c = s;
	s = s->p;
    } while (s != &si->sortTable->head && s->link[SORT_NODE_DIR_RIGHT] == c);
    if (s != &si->sortTable->head) {
	s = s->link[SORT_NODE_DIR_RIGHT];
	while (s->link[SORT_NODE_DIR_LEFT] != &si->sortTable->head) {
	    s = s->link[SORT_NODE_DIR_LEFT];
	}
    }
    si->curNode = s;
    return Boolean(s != &si->sortTable->head);
}

/*
 * Position iterator at previous item in list. Return TRUE if there is a next
 * item; FALSE if wrapping around.
 */
Boolean
sortIterPrev(SortIter si)
{
    SortNode *s = si->curNode;
    SortNode *c;

    if (s == &si->sortTable->head) {
	return sortIterTail(si);
    }
    ASSERT(! si->sortTable->wasModified);
    do {
	c = s;
	s = s->p;
    } while (s != &si->sortTable->head && s->link[SORT_NODE_DIR_LEFT] == c);
    if (s != &si->sortTable->head) {
	s = s->link[SORT_NODE_DIR_LEFT];
	while (s->link[SORT_NODE_DIR_RIGHT] != &si->sortTable->head) {
	    s = s->link[SORT_NODE_DIR_RIGHT];
	}
    }
    si->curNode = s;
    return Boolean(s != &si->sortTable->head);
}

/*
 * Free an iterator
 */
extern void
sortIterFree(SortIter si)
{
    free(si);
}

/*************************************************************************
 * Private Methods
 *************************************************************************/

/*
 * Non-inlinable called from inline
 * INLINE_PRIVATE void
 * sortTableInlinePrivate(void)
 * {
 * }
 * 
 */

/*
 * Returns the value associated with key. Returns NULL if the key is not
 * found.
 */
static SortNode *
sortTableFind(const SortTable sortTable, const void *key)
{
    SortNode *s = sortTable->head.link[SORT_NODE_DIR_RIGHT];

    sortTable->head.item.key = key;	/* guarantee termination */
    for (;;) {
	int cmp = (*sortTable->keyCmp)(key, s->item.key);
	if (cmp == 0 && s->link[SORT_NODE_DIR_LEFT] == &sortTable->head) {
	    break;
	}
	s = s->link[cmp < 0];
    }
    return s;
}

static SortNode *
sortTableSplit(SortTable sortTable, const void *key, SortNode *s)
{
    SortNode *p = s->p;
    SortNodeDir cDir;
    SortNodeDir gcDir;

    s->isRed = TRUE;
    s->link[SORT_NODE_DIR_LEFT]->isRed = FALSE;
    s->link[SORT_NODE_DIR_RIGHT]->isRed = FALSE;
    if (p->isRed) {
	SortNode *g = p->p;
	SortNode *gg = g->p;
	g->isRed = TRUE;
	if (((*sortTable->keyCmp)(key, g->item.key) < 0)
		!= ((*sortTable->keyCmp)(key, p->item.key) < 0)) {
	    cDir = (p == g->link[SORT_NODE_DIR_LEFT])
		? SORT_NODE_DIR_LEFT : SORT_NODE_DIR_RIGHT;
	    gcDir = (s == p->link[SORT_NODE_DIR_LEFT])
		? SORT_NODE_DIR_LEFT : SORT_NODE_DIR_RIGHT;
	    p = sortTableRotate(g, cDir, gcDir);
	}
	cDir = (g == gg->link[SORT_NODE_DIR_LEFT])
		? SORT_NODE_DIR_LEFT : SORT_NODE_DIR_RIGHT;
	gcDir = (p == g->link[SORT_NODE_DIR_LEFT])
		? SORT_NODE_DIR_LEFT : SORT_NODE_DIR_RIGHT;
	s = sortTableRotate(g->p, cDir, gcDir);
	s->isRed = FALSE;
    }
    sortTable->head.link[SORT_NODE_DIR_RIGHT]->isRed = FALSE;
    return s;
}

static SortNode *
sortTableRotate(SortNode *r, SortNodeDir cDir, SortNodeDir gcDir)
{
    SortNode *c;
    SortNode *gc; 

    c = r->link[cDir];
    gc = c->link[gcDir];

    c->link[gcDir] = gc->link[!gcDir];
    gc->link[!gcDir]->p = c;

    gc->link[!gcDir] = c;
    c->p = gc;

    r->link[cDir] = gc;
    gc->p = r;

    return gc;
}

static void
sortTableNodeFree(SortTable sortTable, SortNode *nodep)
{
    nodep->link[SORT_NODE_DIR_RIGHT] = sortTable->freeNodep;
    sortTable->freeNodep = nodep;
    nodep->hasData = FALSE;
    nodep->isFree = TRUE;
    nodep->isRed = FALSE;
}

#define	RELOCATE(sortTable, type, p, delta)			\
    BEGIN_STMT							\
	if ((p) != &(sortTable)->head) {			\
	    (p) = (type)(((char *)(p)) + (delta));		\
	}							\
    END_STMT

static SortNode *
sortTableNodeAlloc(SortTable sortTable, SortNode **reallocpp)
{
    SortNode *n;

    if (sortTable->freeNodep == NULL) {
	int newSize = (sortTable->size + 1) * 1.5;
	SortNode *newArray = RENEW(SortNode, sortTable->nodeArray, newSize);
	int ptrDelta = (char *)newArray - (char *)sortTable->nodeArray;
	int i;
	for (i = 0; i < sortTable->size; i++) {
	    SortNode *p = &newArray[i];
	    /* LINTED */
	    RELOCATE(sortTable, SortNode *, p->link[SORT_NODE_DIR_LEFT],
			ptrDelta);
	    /* LINTED */
	    RELOCATE(sortTable, SortNode *, p->link[SORT_NODE_DIR_RIGHT],
			ptrDelta);
	    /* LINTED */
	    RELOCATE(sortTable, SortNode *, p->p, ptrDelta);
	}
	if (reallocpp != NULL) {
	    /* LINTED */
	    RELOCATE(sortTable, SortNode *, *reallocpp, ptrDelta);
	}
	/* LINTED */
	RELOCATE(sortTable, SortNode *,
		sortTable->head.link[SORT_NODE_DIR_LEFT], ptrDelta);
	/* LINTED */
	RELOCATE(sortTable, SortNode *,
		sortTable->head.link[SORT_NODE_DIR_RIGHT], ptrDelta);
	/* LINTED */
	RELOCATE(sortTable, SortNode *, sortTable->head.p, ptrDelta);
	for (i = sortTable->size; i < newSize; i++) {
	    sortTableNodeFree(sortTable, &newArray[i]);
	}
	sortTable->nodeArray = newArray;
	sortTable->size = newSize;
    }
    n = sortTable->freeNodep;
    sortTable->freeNodep = n->link[SORT_NODE_DIR_RIGHT];
    n->isFree = FALSE;
    return n;
}

static void
sortTableTraverse(SortTable sortTable, int blackDepth, SortNode *n,
	SortNode *min, SortNode *max)
{
    SortNode *l = n->link[SORT_NODE_DIR_LEFT];
    SortNode *r = n->link[SORT_NODE_DIR_RIGHT];

    if (n->wasSeen) {
	ABORT("node multiple");
    }
    if (n->isFree) {
	ABORT("used free");
    }
    if (! n->isRed) {
	blackDepth += 1;
    }
    n->wasSeen = TRUE;
    if (min != NULL && (*sortTable->keyCmp)(n->item.key, min->item.key) < 0) {
	ABORT("low partition");
    }
    if (max != NULL && (*sortTable->keyCmp)(n->item.key, max->item.key) > 0) {
	ABORT("high partition");
    }
    if (l == &sortTable->head && r == &sortTable->head) {
	/* a leaf */
	if (! n->hasData || n->isRed) {
	    ABORT("corrupt leaf");
	}
	if (sortTable->blackDepth != -1
	    && sortTable->blackDepth != blackDepth) {
	    ABORT("black level");
	}
	sortTable->blackDepth = blackDepth;
    } else {
	/* an internal node */
	if (l == &sortTable->head || r == &sortTable->head) {
	    ABORT("missing child");
	}
	if (n->hasData) {
	    ABORT("internal data");
	}
	if (l->p != n || r->p != n) {
	    ABORT("bad parent");
	}
	if (n->isRed && (l->isRed || r->isRed)) {
	    ABORT("red length");
	}
	sortTableTraverse(sortTable, blackDepth, l, min, n);
	sortTableTraverse(sortTable, blackDepth, r, n, max);
    }
}

static void
sortTableTraversePrint(SortTable sortTable, Deque deque,
	SortTablePrintFunc pFunc, SortTableItemToStringFunc iFunc, int level,
	int maxWidth)
{
    char *buf = NEW(char, maxWidth + 2);
    char buf2[100];
    SortNode *n;
    int i;

    for (i = 0; i < maxWidth; i++) {
	buf[i] = ' ';
    }
    buf[maxWidth] = '\n';
    buf[maxWidth + 1] = '\0';
    while ((n = (SortNode*)dequeItemAt(deque, 0)) != NULL && n->level == level) {
	int startPoint;
	int midPoint;
	SortNode *l;
	SortNode *r;

	n = (SortNode*)dequeDequeueHead(deque);
	midPoint = (n->printHigh - n->printLow) / 2 + n->printLow;
	l = n->link[SORT_NODE_DIR_LEFT];
	r = n->link[SORT_NODE_DIR_RIGHT];

	(*iFunc)(&n->item, n->isRed, buf2, sizeof(buf2));
	startPoint = midPoint - strlen(buf2) / 2;
	if (startPoint > maxWidth) {
	    startPoint = maxWidth;
	}
	strInsert(&buf[startPoint], buf2, maxWidth - startPoint);
	if (l != &sortTable->head) {
	    l->printLow = n->printLow; 
	    l->printHigh = midPoint;
	    l->level = level + 1;
	    dequeEnqueueTail(deque, l);
	}
	if (r != &sortTable->head) {
	    r->printLow = midPoint; 
	    r->printHigh = n->printHigh;
	    r->level = level + 1;
	    dequeEnqueueTail(deque, r);
	}
    }
    (*pFunc)(buf);
    if (dequeLength(deque) != 0) {
	sortTableTraversePrint(sortTable, deque, pFunc, iFunc, level + 1,
	    maxWidth);
    }
    free(buf);
}

	
/*************************************************************************
 * Private Functions
 *************************************************************************/


static void
strInsert(char *dst, char *src, int maxlen)
{
    while (*src != '\0' && maxlen-- > 0) {
	*dst++ = *src++;
    }
}

static int
strKeyCmp(const void *key1, const void *key2)
{
    const char *s1 = (const char *)key1;
    const char *s2 = (const char *)key2;

    if(s1 == s2) {
	return(0);
    }
    while(*s1 == *s2++) {
	if(*s1++ == '\0') {
	    return(0);
	}
    }
    return(*s1 - s2[-1]);
}

/* ARGSUSED1 */
static const void *
strKeyDup(const void *key, const void *value)
{
    int keyLen = strlen((const char*)key) + 1;
    return memcpy(NEW(char, keyLen), key, keyLen);
}

static int
intKeyCmp(const void *key1, const void *key2)
{
    return (int)key1 - (int)key2;
}

#endif					   /* !defined(SORTTABLE_HEADER) */