dequeof.c

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

/***********************************************************************
 * Inlinable Instance Interface
 ***********************************************************************/

/*
 * Enqueues item on head of deque.
 */
DEQUEOF_INLINE void
_dequeOfEnqueueHead(DequeOf dequeOf, void *item)
{
    if (dequeOfIsFull(dequeOf)) {
	dequeOfGrow(dequeOf);
    }
    (void) memcpy(dequeOfItemPtr(dequeOf, dequeOf->head++), item,
		  dequeOf->itemSize);
    if (dequeOf->head >= dequeOf->size) {
	dequeOf->head = 0;
    }
#ifdef	ASSERTS
    dequeOf->wasModified = TRUE;
#endif	/* ASSERTS */
}

/*
 * Enqueues item on tail of deque.
 */
DEQUEOF_INLINE void
_dequeOfEnqueueTail(DequeOf dequeOf, void *item)
{
    if (dequeOfIsFull(dequeOf)) {
	dequeOfGrow(dequeOf);
    }
    if (dequeOf->tail <= 0) {
	dequeOf->tail = dequeOf->size;
    }
    (void) memcpy(dequeOfItemPtr(dequeOf, --dequeOf->tail), item,
		  dequeOf->itemSize);
#ifdef	ASSERTS
    dequeOf->wasModified = TRUE;
#endif	/* ASSERTS */
}

/*
 * Dequeues item from head of deque, returns NULL if deque is empty.
 */
DEQUEOF_INLINE void  *
_dequeOfDequeueHead(DequeOf dequeOf)
{
    if (dequeOfIsEmpty(dequeOf)) {
	return NULL;
    }
    if (dequeOf->head <= 0) {
	dequeOf->head = dequeOf->size;
    }
#ifdef	ASSERTS
    dequeOf->wasModified = TRUE;
#endif	/* ASSERTS */
    return dequeOfItemPtr(dequeOf, --dequeOf->head);
}

/*
 * Dequeues item from tail of deque, returns NULL if deque is empty.
 */
DEQUEOF_INLINE void *
_dequeOfDequeueTail(DequeOf dequeOf)
{
    void *item;

    if (dequeOfIsEmpty(dequeOf)) {
	return NULL;
    }
    item = dequeOfItemPtr(dequeOf, dequeOf->tail++);
    if (dequeOf->tail >= dequeOf->size) {
	dequeOf->tail = 0;
    }
#ifdef	ASSERTS
    dequeOf->wasModified = TRUE;
#endif	/* ASSERTS */
    return item;
}

/*
 * Returns item at index position in deque.  Index 0 refers to head,
 * index dequeOfLength() - 1 refers to tail.
 *
 * Returns NULL if index outside of deque.
 */
DEQUEOF_INLINE void        *
_dequeOfItemAt(DequeOf dequeOf, int index)
{
    void *item = NULL;

    if (index < dequeOfLength(dequeOf)) {
	int itemx = dequeOf->head - index - 1;
	if (itemx < 0) {
	    itemx += dequeOf->size;
	}
	item = dequeOfItemPtr(dequeOf, itemx);
    }
    return item;
}

DEQUEOF_INLINE void	*
_dequeOfHead(DequeOf dequeOf)
{
    return dequeOfIsEmpty(dequeOf) ? NULL
	: dequeOfItemPtr(dequeOf,
		dequeOf->head == 0 ? dequeOf->size - 1 : dequeOf->head - 1);
}

DEQUEOF_INLINE void	*
_dequeOfTail(DequeOf dequeOf)
{
    return dequeOfIsEmpty(dequeOf) ? NULL
	: dequeOfItemPtr(dequeOf, dequeOf->tail);
}

/*
 * Stores item into deque at index position.  Overwrites item previously at
 * index position.  Index 0 refers to head, index dequeLength() - 1 refers
 * to tail.
 *
 * Aborts if index outside of deque.
 */
DEQUEOF_INLINE void
_dequeOfSetItemAt(DequeOf dequeOf, int index, void *item)
{
    int itemx;

    if (index >= dequeOfLength(dequeOf)) ABORT("dequeOfSetItemAt: bad index");

    itemx = dequeOf->head + index;
    if (itemx >= dequeOf->size) {
	itemx -= dequeOf->size;
    }
    (void) memcpy(dequeOfItemPtr(dequeOf, itemx), item, dequeOf->itemSize);
#ifdef	ASSERTS
    dequeOf->wasModified = TRUE;
#endif	/* ASSERTS */
}

/*
 * Returns number of items in deque
 */
DEQUEOF_INLINE int
dequeOfLength(DequeOf dequeOf)
{
    int                 length;

    length = dequeOf->head - dequeOf->tail;
    return length < 0 ? length + dequeOf->size : length;
}

/************************************************************************
 * OBJECT DequeOfIter Instance Interface
 ************************************************************************/

/*
 * Position iterator at deque head Returns TRUE if deque is non-empty; FALSE if
 * deque is empty.
 */
DEQUEOF_INLINE Boolean
dequeOfIterHead(DequeOfIter di)
{
    DequeOf dequeOf = di->dequeOf;

    if (dequeOfIsEmpty(dequeOf)) {
	return FALSE;
    }
#ifdef	ASSERTS
    dequeOf->wasModified = FALSE;
#endif	/* ASSERTS */
    di->pos = ((dequeOf->head == 0) ? dequeOf->size : dequeOf->head) - 1;
    return TRUE;
}

/*
 * Position iterator at deque tail Returns TRUE if deque is non-empty; FALSE if
 * deque is empty.
 */
DEQUEOF_INLINE Boolean
dequeOfIterTail(DequeOfIter di)
{
    DequeOf dequeOf = di->dequeOf;

    if (dequeOfIsEmpty(dequeOf)) {
	return FALSE;
    }
#ifdef	ASSERTS
    dequeOf->wasModified = FALSE;
#endif	/* ASSERTS */
    di->pos = dequeOf->tail;
    return TRUE;
}

/*
 * Position iterator at next item in deque. Return TRUE if there is a next
 * item; FALSE if wrapping around.
 *
 * NOTE: dequeIterNext moves from head towards tail.
 */
DEQUEOF_INLINE Boolean
dequeOfIterNext(DequeOfIter di)
{
    DequeOf dequeOf = di->dequeOf;

    if (di->pos == -1) {
	di->pos = dequeOf->head;
#ifdef	ASSERTS
	dequeOf->wasModified = FALSE;
#endif	/* ASSERTS */
    }
    ASSERT(! dequeOf->wasModified);
    ASSERT(dequeOfIterIsValid(di) || di->pos == dequeOf->head);
    if (di->pos == dequeOf->tail) {
	return FALSE;
    }
    di->pos = ((di->pos == 0) ? dequeOf->size : di->pos) - 1;
    return TRUE;
}

/*
 * Position iterator at previous item in deque. Return TRUE if there is a next
 * item; FALSE if wrapping around.
 *
 * NOTE: dequeOfIterPrev moves from tail towards head.
 */
DEQUEOF_INLINE Boolean
dequeOfIterPrev(DequeOfIter di)
{
    DequeOf dequeOf = di->dequeOf;
    int newPos = di->pos + 1;

    if (di->pos == -1) {
	di->pos = dequeOf->tail - 1;
#ifdef	ASSERTS
	dequeOf->wasModified = FALSE;
#endif	/* ASSERTS */
    }

    ASSERT(! dequeOf->wasModified);
    ASSERT(dequeOfIterIsValid(di));
    if (newPos >= dequeOf->size) newPos = 0;
    if (newPos == dequeOf->head) {
	return FALSE;
    }
    di->pos = newPos;
    return TRUE;
}

/*
 * Return the item referenced by the iterator Returns NULL if iterator not
 * positioned at item.
 */
DEQUEOF_INLINE void   *
_dequeOfIterItem(const DequeOfIter di)
{
    ASSERT(! di->dequeOf->wasModified);
    return dequeOfIterIsValid(di) ? dequeOfItemPtr(di->dequeOf, di->pos) : NULL;
}

/*
 * Return TRUE if iterator points to valid item
 */
DEQUEOF_INLINE Boolean
dequeOfIterIsValid(const DequeOfIter di)
{
    DequeOf dequeOf = di->dequeOf;

    ASSERT(! dequeOf->wasModified);
    ASSERT(di->pos >= 0 && di->pos < dequeOf->size);
    return Boolean((dequeOf->head >= dequeOf->tail)
        ? (dequeOf->tail <= di->pos && di->pos < dequeOf->head)
	: (di->pos < dequeOf->head || di->pos >= dequeOf->tail));
}

/************************************************************************
 * OBJECT Inlinable Private Routines
 ************************************************************************/

static              Boolean
dequeOfIsEmpty(DequeOf dequeOf)
{
    /*
     * Returns TRUE if the deque is empty, FALSE otherwise.
     */
    return Boolean(dequeOf->head == dequeOf->tail);
}

static              Boolean
dequeOfIsFull(DequeOf dequeOf)
{
    /*
     * Returns TRUE if deque is full, FALSE otherwise.
     */
    return Boolean( ((dequeOf->head + 1) % dequeOf->size) == dequeOf->tail );
}

static		    void *
dequeOfItemPtr(DequeOf dequeOf, int index)
{
    return (char *)(dequeOf->items) + (index * dequeOf->itemSize);
}