list.c

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

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

static ListItem *
listItemNew(List list)
{
    ListItem *nip;

    if (list->freeItemp == NULL) {
	listExpandFree(list);
    }
    ASSERT(list->freeItemp != NULL);
    nip = list->freeItemp;
    list->freeItemp = nip->nextp;
    return nip;
}

static ListRef
listRef(List list, ListItem *lip)
{
    return lip - list->itemArray;
}

static ListItem *
listItem(List list, ListRef ref)
{
    ASSERT(ref != 0);
    return &list->itemArray[ref];
}

static void
listItemFree(List list, ListItem *lip)
{
    lip->prevp = NULL;
    lip->itemp = NULL;
    lip->nextp = list->freeItemp;
    list->freeItemp = lip;
}

#if	!defined(LIST_HEADER)
/*
 * Private function prototypes
 */

#ifdef __cplusplus
extern "C" {
#endif

static Boolean
listDefaultSort(const void *listItemp,
		const void *newItemp);
static Boolean
listDefaultIdentical(const void *listItemp,
		     const void *testItemp);

#ifdef __cplusplus
}
#endif

/*
 * OBJECT List Class Methods
 */
List
listNew(ListItemSort lis, ListItemIdentical lii)
{
    return listNewWithSize(lis, lii, LIST_INIT_FREECNT);
}

List
listNewWithSize(ListItemSort lis, ListItemIdentical lii, size_t size)
{
    List                list;

    if ((list = NEW_ZEROED(struct _List, 1)) != NULL) {
	int i;
	list->lis = lis != NULL ? lis : listDefaultSort;
	list->lii = lii != NULL ? lii : listDefaultIdentical;
	list->itemArray = NEW_ZEROED(ListItem, size);
	list->itemArray[0].nextp = &list->itemArray[0];
	list->itemArray[0].prevp = &list->itemArray[0];
	list->size = 1;
	for (i = 1; i < size - 1; i++) {
	    list->itemArray[i].nextp = &list->itemArray[i + 1];
	}
	list->freeItemp = &list->itemArray[1];
#ifdef	ASSERTS
	list->wasModified = FALSE;
#endif	/* ASSERTS */
	(void) mutex_init(&list->iterLock, USYNC_THREAD, 0);
	/*
	 * Add sentinel at end of list.  A NULL won't work because
	 * of list relocation.
	 */
	list->iterHead.nextIterp = NEW_ZEROED(struct _ListIter, 1);
	list->iterHead.nextIterp->nextIterp = list->iterHead.nextIterp;
    }
    return list;
}

void
listFree(List list)
{
    ASSERT(list->iterHead.nextIterp->nextIterp == list->iterHead.nextIterp);
    (void) mutex_destroy(&list->iterLock);
    free(list->iterHead.nextIterp);
    free(list->itemArray);
    free(list);
}

ListRef
listSortedInsert(List list, const void *itemp)
{
    ListItem           *nip = listItemNew(list);
    ListItem           *lip;

    /*
     * ListItemSort routine should return TRUE if the itemp pointed to by
     * newItemp should be inserted closer to the list head than the item
     * pointed to by listItemp.
     */
    for (lip = list->itemArray[0].nextp;
	    lip != &list->itemArray[0];
	    lip = lip->nextp) {
	if ((*list->lis) (lip->itemp, itemp)) {
	    break;
	}
    }
    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);
}

void               *
listRemove(List list, const void *itemp)
{
    ListItem           *lip;

    for (lip = list->itemArray[0].nextp;
	    lip != &list->itemArray[0];
	    lip = lip->nextp) {
	if ((*list->lii) (lip->itemp, itemp)) {
	    void               *retItemp;

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

Boolean
listIsMember(const List list, const void *itemp)
{
    ListItem           *lip;

    for (lip = list->itemArray[0].nextp;
	    lip != &list->itemArray[0];
	    lip = lip->nextp) {
	if ((*list->lii) (lip->itemp, itemp)) {
	    return TRUE;
	}
    }
    return FALSE;
}

/************************************************************************
 * OBJECT ListIter Class Interface
 ************************************************************************/

/*
 * Create a list Iterator
 * 
 * List iterator is initialized to reference head item of list.
 * 
 * A list iterator is invalidated by any non-iterator-based list operation.
 */
ListIter
listIterNew(const List list)
{
    ListIter            li;

    if ((li = NEW_ZEROED(struct _ListIter, 1)) != NULL) {
	li->list = list;
	li->curLip = NULL;
	li->curLi.itemp = NULL;
	(void) mutex_lock(&list->iterLock);
	li->nextIterp = list->iterHead.nextIterp;
	list->iterHead.nextIterp = li;
	(void) mutex_unlock(&list->iterLock);
    }
    return li;
}

/*
 * Position iterator at item.  Search for item proceeds from head to tail.
 * Return TRUE if item found.  Return FALSE if item not found. Position of
 * iterator is unchanged if item not found.
 */
Boolean
listIterFind(ListIter li, const void *itemp)
{
    List		list = li->list;
    ListItem           *lip;

    for (lip = list->itemArray[0].nextp;
	    lip != &list->itemArray[0];
	    lip = lip->nextp) {
	if ((*list->lii) (lip->itemp, itemp)) {
	    li->curLip = lip;
	    li->curLi = *li->curLip;
#ifdef	ASSERTS
	    list->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.
 */
Boolean
listIterAfter(ListIter li, const void *itemp)
{
    List		list = li->list;
    ListItem           *lip;

    for (lip = list->itemArray[0].nextp;
	    lip != &list->itemArray[0];
	    lip = lip->nextp) {
	if ((*list->lis) (lip->itemp, itemp)) {
	    /*
	     * Sort routine returns TRUE when looking at item we should
	     * insert before, so if item doesn't exist, lip is now pointing
	     * at item after where item would be.
	     * 
	     * If item does exist, sort routine can place us at first of run of
	     * identical items or after item (depending on whether sort
	     * intends identical items to  insert before or after existing
	     * identical items).  If pointing at the first of a run of
	     * identical items, skip them here.
	     */
	    while (lip != &list->itemArray[0]
		    && (*list->lii) (lip->itemp, itemp)) {
		lip = lip->nextp;
	    }
	    break;
	}
    }
    li->curLip = lip;
    li->curLi = *li->curLip;
#ifdef	ASSERTS
    list->wasModified = FALSE;
#endif /* ASSERTS */
    return Boolean(lip != &list->itemArray[0]);
}

/*
 * 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.
 */
Boolean
listIterBefore(ListIter li, const void *itemp)
{
    List		list = li->list;
    ListItem           *lip;

    for (lip = list->itemArray[0].nextp;
	    lip != &list->itemArray[0];
	    lip = lip->nextp) {
	if ((*list->lis) (lip->itemp, itemp)) {
	    /*
	     * Sort routine returns TRUE when looking at item we should
	     * insert before, so if item doesn't exist, lip is now pointing
	     * at item after where item would be.  Since this routine should
	     * return item BEFORE, back lip up one item.
	     * 
	     * If item does exist, sort routine can place us at first of run of
	     * identical items or after item (depending on whether sort
	     * intends identical items to  insert before or after existing
	     * identical items).  Since we've backed-up one item, we are now
	     * either before a run of identical items or pointing at the last
	     * of a run of identical items. If pointing at the last of a run
	     * of identical items, skip them here.
	     */
	    lip = lip->prevp;
	    while (lip != &list->itemArray[0]
		    && (*list->lii) (lip->itemp, itemp)) {
		lip = lip->prevp;
	    }
	    break;
	}
    }
    li->curLip = lip;
    li->curLi = *li->curLip;
#ifdef	ASSERTS
    list->wasModified = FALSE;
#endif /* ASSERTS */
    return Boolean(lip != &list->itemArray[0]);
}

/*
 * Free an iterator
 */
void
listIterFree(ListIter li)
{
    List list = li->list;
    ListIter prevLi;

    (void) mutex_lock(&list->iterLock);
    prevLi = &list->iterHead;
    while (prevLi->nextIterp != li) {
	prevLi = prevLi->nextIterp;
	ASSERT(prevLi->nextIterp != prevLi);
    }
    prevLi->nextIterp = li->nextIterp;
    (void) mutex_unlock(&list->iterLock);
    free(li);
}


#define	LIST_RELOCATE(list, type, p, delta)	    \
	(p) = (type)(((char *)(p)) + (delta));

INLINE_PRIVATE void
listExpandFree(List list)
{
    ListItem *oldArray = list->itemArray;
    int incr = list->size / 10;
    ListIter li;
    long reloc;
    int i;

    if (incr < LIST_INIT_FREECNT) incr = LIST_INIT_FREECNT;

    list->itemArray = RENEW(ListItem, list->itemArray, list->size + incr);
    reloc = (char *)list->itemArray - (char *)oldArray;
    if (reloc != 0) {
	/*
	 * Relocate all listItem pointers
	 */
	for (i = 0; i < list->size; i++) {
	    /* LINTED */
	    LIST_RELOCATE(list, ListItem *, list->itemArray[i].nextp, reloc);
	    /* LINTED */
	    LIST_RELOCATE(list, ListItem *, list->itemArray[i].prevp, reloc);
	}
	/*
	 * Relocate all listIter pointers
	 */
	(void) mutex_lock(&list->iterLock);
	for (li = list->iterHead.nextIterp;
	     li->nextIterp != li;
	     li = li->nextIterp) {
	    if (li->curLip != NULL) {
		/* LINTED */
		LIST_RELOCATE(list, ListItem *, li->curLip, reloc);
		/* LINTED */
		LIST_RELOCATE(list, ListItem *, li->curLi.nextp, reloc);
		/* LINTED */
		LIST_RELOCATE(list, ListItem *, li->curLi.prevp, reloc);
	    }
	}
	(void) mutex_unlock(&list->iterLock);
    }
    /*
     * Link up new free entries
     */
    (void) memset(&list->itemArray[list->size], 0, incr * sizeof(ListItem));
    for (i = list->size; i < list->size + incr - 1; i++) {
	list->itemArray[i].nextp = &list->itemArray[i + 1];
    }
    list->freeItemp = &list->itemArray[list->size];
}

static Boolean
listDefaultIdentical(const void *listItemp, const void *testItemp)
{
    return Boolean(listItemp == testItemp);
}

static Boolean
listDefaultSort(const void *listItemp, const void *newItemp)
{
    return Boolean(newItemp < listItemp);
}

#endif					   /* !defined(LIST_HEADER) */