list.c

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

/*
 * 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]
 */ 

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

/*
 * List.c -- A doubly-linked list of item pointers.
 */

#pragma ident "@(#)List.c 1.4	99/05/28 SMI"

#if	!defined(LIST_HEADER)
#define	LIST_BODY
#define	LIST_INLINE	extern
#include "cobjs/List.h"
#endif	/* !defined(LIST_HEADER) */

#include <stdlib.h>
#include <synch.h>

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

#define	LIST_INIT_FREECNT		100

typedef struct ListItem ListItem;

struct ListItem {
    ListItem           *nextp;
    ListItem           *prevp;
    const void         *itemp;
};

struct _ListIter {
    List                list;
    ListItem           *curLip;
    ListItem            curLi;
    ListIter	        nextIterp;
};

/*
 * OBJECT List Instance Variables
 */
struct _List {
    ListItemSort        lis;
    ListItemIdentical   lii;
    size_t              size;		    /* INCLUDING ANCHOR! */
    ListItem		*freeItemp;
    ListItem		*itemArray;
#ifdef	ASSERTS
    Boolean		wasModified;
#endif /* ASSERTS */
    mutex_t		iterLock;
    struct _ListIter	iterHead;
};

static ListItem *listItemNew(List list);
static ListItem *listItem(List list, ListRef ref);
static ListRef listRef(List list, ListItem *lip);
static void listItemFree(List list, ListItem *lip);

INLINE_PRIVATE void listExpandFree(List list);

LIST_INLINE void   *
listHead(const List list)
{
    ListItem           *lip = list->itemArray[0].nextp;

    return lip != &list->itemArray[0] ? (void *) lip->itemp : NULL;
}

LIST_INLINE void   *
listTail(const List list)
{
    ListItem           *lip = list->itemArray[0].prevp;

    return lip != &list->itemArray[0] ? (void *) lip->itemp : NULL;
}

LIST_INLINE ListRef
listHeadInsert(List list, const void *itemp)
{
    ListItem           *nip = listItemNew(list);
    ListItem           *lip = list->itemArray[0].nextp;

    nip->itemp = itemp;

    lip->prevp->nextp = nip;
    nip->nextp = lip;
    nip->prevp = lip->prevp;
    lip->prevp = nip;
    list->size += 1;
#ifdef	ASSERTS
    list->wasModified = TRUE;
#endif /* ASSERTS */
    return listRef(list, nip);
}

LIST_INLINE ListRef
listTailInsert(List list, const void *itemp)
{
    ListItem           *nip = listItemNew(list);
    ListItem           *lip = &list->itemArray[0];

    nip->itemp = itemp;

    lip->prevp->nextp = nip;
    nip->nextp = lip;
    nip->prevp = lip->prevp;
    lip->prevp = nip;
    list->size += 1;
#ifdef	ASSERTS
    list->wasModified = TRUE;
#endif /* ASSERTS */
    return listRef(list, nip);
}

LIST_INLINE void               *
listHeadRemove(List list)
{
    ListItem           *lip = list->itemArray[0].nextp;
    void               *itemp = NULL;

    if (lip != &list->itemArray[0]) {
	lip->prevp->nextp = lip->nextp;
	lip->nextp->prevp = lip->prevp;
	itemp = (void *) lip->itemp;
	listItemFree(list, lip);
	list->size -= 1;
    }
#ifdef	ASSERTS
    list->wasModified = TRUE;
#endif /* ASSERTS */
    return itemp;
}

LIST_INLINE void               *
listTailRemove(List list)
{
    ListItem           *lip = list->itemArray[0].prevp;
    void               *itemp = NULL;

    if (lip != &list->itemArray[0]) {
	lip->prevp->nextp = lip->nextp;
	lip->nextp->prevp = lip->prevp;
	itemp = (void *) lip->itemp;
	listItemFree(list, lip);
	list->size -= 1;
    }
#ifdef	ASSERTS
    list->wasModified = TRUE;
#endif /* ASSERTS */
    return itemp;
}

LIST_INLINE void               *
listRefRemove(List list, ListRef ref)
{
    ListItem           *lip = listItem(list, ref);
    void               *itemp;

    lip->prevp->nextp = lip->nextp;
    lip->nextp->prevp = lip->prevp;
    itemp = (void *) lip->itemp;
    listItemFree(list, lip);
    list->size -= 1;
#ifdef	ASSERTS
    list->wasModified = TRUE;
#endif /* ASSERTS */
    return itemp;
}

LIST_INLINE void        *
listRefItem(List list, ListRef ref)
{
    return (void *) listItem(list, ref)->itemp;
}

LIST_INLINE void
listRefUpdate(List list, ListRef ref, const void *itemp)
{
    listItem(list, ref)->itemp = itemp;
#ifdef	ASSERTS
    list->wasModified = TRUE;
#endif /* ASSERTS */
}

LIST_INLINE Boolean
listIsEmpty(const List list)
{
    return Boolean(list->itemArray[0].nextp == &list->itemArray[0]);
}

LIST_INLINE size_t
listSize(const List list)
{
    /* decr by 1 because anchor is counted */
    return list->size - 1;
}

/************************************************************************
 * OBJECT ListIter Inlinable Instance Interface
 ************************************************************************/

/*
 * Position iterator at list head Returns TRUE if list is non-empty; FALSE if
 * list is empty.
 */
LIST_INLINE Boolean
listIterHead(ListIter li)
{
    li->curLip = li->list->itemArray[0].nextp;
    li->curLi = *li->curLip;
#ifdef	ASSERTS
    li->list->wasModified = FALSE;
#endif /* ASSERTS */
    return Boolean(li->curLip != &li->list->itemArray[0]);
}

/*
 * Position iterator at list tail Returns TRUE if list is non-empty; FALSE if
 * list is empty.
 */
LIST_INLINE Boolean
listIterTail(ListIter li)
{
#ifdef	ASSERTS
    li->list->wasModified = FALSE;
#endif /* ASSERTS */
    li->curLip = li->list->itemArray[0].prevp;
    li->curLi = *li->curLip;
    return Boolean(li->curLip != &li->list->itemArray[0]);
}

/*
 * Position iterator at next item in list. Return TRUE if there is a next
 * item; FALSE if wrapping around.
 */
LIST_INLINE Boolean
listIterNext(ListIter li)
{
    if (li->curLip == NULL) {
	li->curLip = &li->list->itemArray[0];
	li->curLi = *li->curLip;
#ifdef	ASSERTS
	li->list->wasModified = FALSE;
#endif /* ASSERTS */
    }
    ASSERT(! li->list->wasModified);
    li->curLip = li->curLi.nextp;
    li->curLi = *li->curLip;
    return Boolean(li->curLip != &li->list->itemArray[0]);
}

/*
 * Position iterator at previous item in list. Return TRUE if there is a
 * previous item; FALSE if wrapping around.
 */
LIST_INLINE Boolean
listIterPrev(ListIter li)
{
    if (li->curLip == NULL) {
	li->curLip = &li->list->itemArray[0];
	li->curLi = *li->curLip;
#ifdef	ASSERTS
	li->list->wasModified = FALSE;
#endif /* ASSERTS */
    }
    ASSERT(! li->list->wasModified);
    li->curLip = li->curLi.prevp;
    li->curLi = *li->curLip;
    return Boolean(li->curLip != &li->list->itemArray[0]);
}

LIST_INLINE void
listIterRef(ListIter li, ListRef ref)
{
    li->curLip = listItem(li->list, ref);
    li->curLi = *li->curLip;
#ifdef	ASSERTS
    li->list->wasModified = FALSE;
#endif /* ASSERTS */
}

/*
 * Return the item referenced by the iterator Returns NULL if iterator not
 * positioned at item.
 */
LIST_INLINE void   *
listIterItem(const ListIter li)
{
    ASSERT(! li->list->wasModified);
    return (void *) li->curLi.itemp;
}

/*
 * Return TRUE if iterator points to valid item
 */
LIST_INLINE Boolean
listIterValid(const ListIter li)
{
    ASSERT(! li->list->wasModified);
    return Boolean(li->curLip != NULL && li->curLip != &li->list->itemArray[0]);
}

LIST_INLINE ListRef
listIterToRef(const ListIter li)
{
    ASSERT(! li->list->wasModified);
    return li->curLip == NULL ? 0 : li->curLip - &li->list->itemArray[0];
}

/*
 * Removes and returns the item referenced by the iterator. Returns NULL if
 * iterator not positioned at item.
 */
LIST_INLINE void               *
listIterRemove(ListIter li)
{
    ListItem           *lip = li->curLip;

    ASSERT(! li->list->wasModified);
    if (lip != NULL && lip != &li->list->itemArray[0]) {
	lip->prevp->nextp = lip->nextp;
	lip->nextp->prevp = lip->prevp;
	listItemFree(li->list, lip);
	li->list->size -= 1;
    }
    li->curLip = &li->list->itemArray[0];
    return (void *) li->curLi.itemp;
}

/*
 * Insert an item before the item reference by the iterator. Iterator
 * position is unchanged.  If iterator is not positioned at item, insert at
 * list head.
 */
LIST_INLINE ListRef
listIterInsert(ListIter li, const void *itemp)
{
    ListItem           *nip = listItemNew(li->list);
    ListItem           *lip = li->curLip;

    ASSERT(! li->list->wasModified);
    if (lip == NULL || lip == &li->list->itemArray[0]) {
	lip = li->list->itemArray[0].nextp;
    }
    nip->itemp = itemp;

    lip->prevp->nextp = nip;
    nip->nextp = lip;
    nip->prevp = lip->prevp;
    lip->prevp = nip;

    li->curLi = *li->curLip;
    li->list->size += 1;
    return listRef(li->list, nip);
}

/*
 * Append an item after the item reference by the iterator. Iterator position
 * is unchanged.  If iterator is not positioned at item, insert at list tail.
 */
LIST_INLINE ListRef
listIterAppend(ListIter li, const void *itemp)
{
    ListItem           *nip = listItemNew(li->list);
    ListItem           *lip = li->curLip;

    ASSERT(! li->list->wasModified);
    if (lip == NULL || lip == &li->list->itemArray[0]) {
	lip = li->list->itemArray[0].prevp;
    }
    nip->itemp = itemp;

    lip->nextp->prevp = nip;
    nip->prevp = lip;
    nip->nextp = lip->nextp;
    lip->nextp = nip;

    li->curLi = *li->curLip;