diff options
Diffstat (limited to 'src/PtrList.c')
| -rw-r--r-- | src/PtrList.c | 851 |
1 files changed, 425 insertions, 426 deletions
diff --git a/src/PtrList.c b/src/PtrList.c index d15acc9..6c431d2 100644 --- a/src/PtrList.c +++ b/src/PtrList.c @@ -14,8 +14,8 @@ typedef struct ListPage_tag ListPage; typedef struct PtrList_tag { - ListPage *firstPage; - size_t itemsPerPage; + ListPage *firstPage; + size_t itemsPerPage; } PtrList_PLACEHOLDER; /* =========================================================================== @@ -26,26 +26,26 @@ typedef struct PtrList_tag typedef struct ListPage_tag { - size_t numberOfItems; - size_t maxItems; - ListPage * next; - void * *items; + size_t numberOfItems; + size_t maxItems; + ListPage * next; + void * *items; } ListPage_PLACEHOLDER; static ListPage * ListPage_New( size_t maxItems ) { - ListPage *new = (ListPage *)calloc( 1, sizeof( ListPage ) ); - if( new ) - { - new->items = malloc( maxItems * sizeof( void * ) ); - new->maxItems = maxItems; - } - return new; + ListPage *new = (ListPage *)calloc( 1, sizeof( ListPage ) ); + if( new ) + { + new->items = malloc( maxItems * sizeof( void * ) ); + new->maxItems = maxItems; + } + return new; } #define ListPage_IsFull( page ) \ - ( ((const ListPage *)page)->numberOfItems >= page->maxItems ) + ( ((const ListPage *)page)->numberOfItems >= page->maxItems ) static ListPage * @@ -60,82 +60,82 @@ ListPage_RemoveItem( ListPage * this, size_t index ); static void * ListPage_InsertItem( ListPage * this, size_t index, void * item ); - /* ListPage_Dup does not copy the next pointer */ + /* ListPage_Dup does not copy the next pointer */ ListPage * ListPage_Dup( const ListPage * other ) { - ListPage * this = ListPage_New( other->maxItems ); - if( other->numberOfItems > 0 ) - memcpy( this->items, other->items, - other->numberOfItems * sizeof( void * ) ); + ListPage * this = ListPage_New( other->maxItems ); + if( other->numberOfItems > 0 ) + memcpy( this->items, other->items, + other->numberOfItems * sizeof( void * ) ); - this->maxItems = other->maxItems; - this->numberOfItems = other->numberOfItems; + this->maxItems = other->maxItems; + this->numberOfItems = other->numberOfItems; - return this; + return this; } - /* Returns the input pointer if it doesn't fit on page - * (for similarity with InsertItem) */ + /* Returns the input pointer if it doesn't fit on page + * (for similarity with InsertItem) */ void * ListPage_Append( ListPage *this, void * item ) { - if( this->numberOfItems < this->maxItems ) /* If page not full */ - { - *( this->items + this->numberOfItems ) = item; /* item to end*/ - this->numberOfItems++; /* Update number of items on page */ - return NULL; - } - return item; + if( this->numberOfItems < this->maxItems ) /* If page not full */ + { + *( this->items + this->numberOfItems ) = item; /* item to end*/ + this->numberOfItems++; /* Update number of items on page */ + return NULL; + } + return item; } - /* Returns a pointer to the item removed, or NULL if no item found */ + /* Returns a pointer to the item removed, or NULL if no item found */ void * ListPage_RemoveItem( ListPage *this, size_t index ) { - if( index < this->numberOfItems ) - { - const size_t lastItemToShift = this->numberOfItems - 1; - size_t i; - void *item = *( this->items + index ); + if( index < this->numberOfItems ) + { + const size_t lastItemToShift = this->numberOfItems - 1; + size_t i; + void *item = *( this->items + index ); - this->numberOfItems--; + this->numberOfItems--; - for( i = index; i < lastItemToShift; i++ ) - *( this->items + i ) = *( this->items + i + 1 ); + for( i = index; i < lastItemToShift; i++ ) + *( this->items + i ) = *( this->items + i + 1 ); - return item; - } - return NULL; + return item; + } + return NULL; } - /* Returns a pointer to any item bumped off the page due to - * the page being full. (could be the input item) */ + /* Returns a pointer to any item bumped off the page due to + * the page being full. (could be the input item) */ void * ListPage_InsertItem( ListPage *this, size_t index, void * item ) { - void * remainder = NULL; + void * remainder = NULL; - if( index < this->numberOfItems ) - { - const size_t firstItemToShift = this->numberOfItems - 1; - size_t i; + if( index < this->numberOfItems ) + { + const size_t firstItemToShift = this->numberOfItems - 1; + size_t i; - if( this->numberOfItems >= this->maxItems ) - remainder = *( this->items + firstItemToShift ); + if( this->numberOfItems >= this->maxItems ) + remainder = *( this->items + firstItemToShift ); - this->numberOfItems = MIN( this->numberOfItems + 1, - this->maxItems ); + this->numberOfItems = MIN( this->numberOfItems + 1, + this->maxItems ); - for( i = firstItemToShift; i > index; i-- ) - *( this->items + i ) = *( this->items + i - 1 ); + for( i = firstItemToShift; i > index; i-- ) + *( this->items + i ) = *( this->items + i - 1 ); - *( this->items + index ) = item; - } - else - remainder = ListPage_Append( this, item ); + *( this->items + index ) = item; + } + else + remainder = ListPage_Append( this, item ); - return remainder; + return remainder; } /* =========================================================================== @@ -146,511 +146,510 @@ ListPage_InsertItem( ListPage *this, size_t index, void * item ) static void List_HandleAddressingError() { - /* To taste */ + /* To taste */ } static ListPage * List_Xerox( const PtrList *other); static void List_FindItemAddress( const PtrList *this, size_t itemNo, - ListPage ** thePage, size_t *thePageIndex ); + ListPage ** thePage, size_t *thePageIndex ); - /*_____________________________________________________________________ - **Constructor & Destructor**__________________________________________ - *_____________________________________________________________________ - */ + /*_____________________________________________________________________ + **Constructor & Destructor**__________________________________________ + *_____________________________________________________________________ + */ PtrList * List_New( void ) { - return List_NewWithPageSize( TAKEDEFAULTSIZE ); + return List_NewWithPageSize( TAKEDEFAULTSIZE ); } PtrList * List_NewWithPageSize( size_t itemsOnFullPage ) { - PtrList *new = (PtrList *)calloc( 1, sizeof( PtrList ) ); - if( new ) - { - if( itemsOnFullPage == TAKEDEFAULTSIZE ) - new->itemsPerPage = ITEMSONFULLPAGE; - else - new->itemsPerPage = itemsOnFullPage; - } - return new; + PtrList *new = (PtrList *)calloc( 1, sizeof( PtrList ) ); + if( new ) + { + if( itemsOnFullPage == TAKEDEFAULTSIZE ) + new->itemsPerPage = ITEMSONFULLPAGE; + else + new->itemsPerPage = itemsOnFullPage; + } + return new; } PtrList * List_MakeCopy( const PtrList *other ) { - PtrList *this = (PtrList *)calloc( 1, sizeof( PtrList ) ); - this->itemsPerPage = other->itemsPerPage; - this->firstPage = List_Xerox( other ); - return this; + PtrList *this = (PtrList *)calloc( 1, sizeof( PtrList ) ); + this->itemsPerPage = other->itemsPerPage; + this->firstPage = List_Xerox( other ); + return this; } void List_Delete( PtrList *list ) { - List_Empty( list ); - free( list ); + List_Empty( list ); + free( list ); } - /*_____________________________________________________________________ - **Empty**____________________________________________________________ - * Runs through the list of ListPages deleting the (previous) page. - *_____________________________________________________________________ - */ + /*_____________________________________________________________________ + **Empty**____________________________________________________________ + * Runs through the list of ListPages deleting the (previous) page. + *_____________________________________________________________________ + */ void List_Empty( PtrList * this ) { - if( this->firstPage != NULL ) - { - ListPage *prevPage = this->firstPage, - *startPage = this->firstPage->next; - ListPage *page; - - this->firstPage = NULL; /* Prefer to do this first, - so list is consistent */ - for( page = startPage; page != NULL; page = page->next ) - { - free( prevPage ); - prevPage = page; - } - free( prevPage ); - } + if( this->firstPage != NULL ) + { + ListPage *prevPage = this->firstPage, + *startPage = this->firstPage->next; + ListPage *page; + + this->firstPage = NULL; /* Prefer to do this first, + so list is consistent */ + for( page = startPage; page != NULL; page = page->next ) + { + free( prevPage ); + prevPage = page; + } + free( prevPage ); + } } - /*_____________________________________________________________________ - **NumberOfItems**______________________________________________________ - * Runs through the list of ListPages totalling the items on each page. - * -> This number could be cached. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **NumberOfItems**______________________________________________________ + * Runs through the list of ListPages totalling the items on each page. + * -> This number could be cached. + *______________________________________________________________________ + */ size_t List_NumberOfItems( const PtrList *this ) { - size_t number = 0; - ListPage *page; + size_t number = 0; + ListPage *page; - for( page = this->firstPage; page != NULL; page = page->next ) - number += page->numberOfItems; + for( page = this->firstPage; page != NULL; page = page->next ) + number += page->numberOfItems; - return number; + return number; } - /*_____________________________________________________________________ - **Append**_____________________________________________________________ - * This and Insert the only PtrList method that allocates ListPages. - * If there are no pages with space on them, it allocates an new - * page and links the page the the previous last page. - * If there is space on the page, it adds the item to the end of - * the page and updates the number of items on the page. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **Append**_____________________________________________________________ + * This and Insert the only PtrList method that allocates ListPages. + * If there are no pages with space on them, it allocates an new + * page and links the page the the previous last page. + * If there is space on the page, it adds the item to the end of + * the page and updates the number of items on the page. + *______________________________________________________________________ + */ void List_Append( PtrList *this, void * newItem ) { - ListPage *page; + ListPage *page; - if( this->firstPage == NULL ) /* Add first page if necessary*/ - this->firstPage = ListPage_New( this->itemsPerPage ); + if( this->firstPage == NULL ) /* Add first page if necessary*/ + this->firstPage = ListPage_New( this->itemsPerPage ); - page = this->firstPage; + page = this->firstPage; - while( page != NULL ) /* Cycle through pages */ - { /* Try to put on page*/ - if( ListPage_Append( page, newItem ) == NULL ) - return; /* Go home with a smile */ - else if( page->next == NULL ) /* If next page doesn't exist*/ - page->next = ListPage_New( this->itemsPerPage ); - /* make new page and */ - /* link to this*/ + while( page != NULL ) /* Cycle through pages */ + { /* Try to put on page*/ + if( ListPage_Append( page, newItem ) == NULL ) + return; /* Go home with a smile */ + else if( page->next == NULL ) /* If next page doesn't exist*/ + page->next = ListPage_New( this->itemsPerPage ); + /* make new page and */ + /* link to this*/ - page = page->next; /* Try the next page*/ - } - List_HandleAddressingError(); + page = page->next; /* Try the next page*/ + } + List_HandleAddressingError(); } - /*_____________________________________________________________________ - * Internal routine for List_Insert. - * Assumes check has already been done for item address and that - * it exists on the given page. - * - * It is inserted on the page. The question is, what to do if the - * page was almost empty, and an item had to be bumped off the page - * to accomodate it. - * - * Could shift all elemtents in the list up by one. Might be - * expensive - * - * Strategey here will be to add a new page after the present one - * if the next page is either full or non-existant. That way, only - * elements on the next page are affected, and if another item is - * added to the present page (as often happens) very little more work - * need be done. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + * Internal routine for List_Insert. + * Assumes check has already been done for item address and that + * it exists on the given page. + * + * It is inserted on the page. The question is, what to do if the + * page was almost empty, and an item had to be bumped off the page + * to accomodate it. + * + * Could shift all elemtents in the list up by one. Might be + * expensive + * + * Strategey here will be to add a new page after the present one + * if the next page is either full or non-existant. That way, only + * elements on the next page are affected, and if another item is + * added to the present page (as often happens) very little more work + * need be done. + *______________________________________________________________________ + */ static void List_InsertExistingItem( PtrList *list, ListPage *page, size_t pageIndex, - void *item ) -{ - void * remnant = ListPage_InsertItem( page, pageIndex, item ); - if( remnant ) /* An item got bumped off when inserting into page */ - { - ListPage *next = page->next; - if( next == NULL || ListPage_IsFull( next ) ) - { - ListPage *new = ListPage_New( list->itemsPerPage ); - ListPage_Append( new, item ); /* Item on new */ - new->next = next; /* link new page */ - page->next = new; - } - else - ListPage_InsertItem( next, 0, remnant ); - } + void *item ) +{ + void * remnant = ListPage_InsertItem( page, pageIndex, item ); + if( remnant ) /* An item got bumped off when inserting into page */ + { + ListPage *next = page->next; + if( next == NULL || ListPage_IsFull( next ) ) + { + ListPage *new = ListPage_New( list->itemsPerPage ); + ListPage_Append( new, item ); /* Item on new */ + new->next = next; /* link new page */ + page->next = new; + } + else + ListPage_InsertItem( next, 0, remnant ); + } } - /*_____________________________________________________________________ + /*_____________________________________________________________________ **List_Insert** - * Inserts the item at the specified index, shifting indices of - * existing list items as necessary. If index equals the number - * of items in the list less one, the item is appended to the list. - *______________________________________________________________________ - */ + * Inserts the item at the specified index, shifting indices of + * existing list items as necessary. If index equals the number + * of items in the list less one, the item is appended to the list. + *______________________________________________________________________ + */ void List_Insert( PtrList * list, size_t index, void * item ) { - if( index >= List_NumberOfItems( list ) ) - List_Append( list, item ); - else - { - ListPage *page = NULL; - size_t pageIndex; - - List_FindItemAddress( list, index, &page, &pageIndex ); - - if( page != NULL ) - List_InsertExistingItem( list, page, pageIndex, item ); - else - List_HandleAddressingError(); - /* probably should handle an addressing error */ - } + if( index >= List_NumberOfItems( list ) ) + List_Append( list, item ); + else + { + ListPage *page = NULL; + size_t pageIndex; + + List_FindItemAddress( list, index, &page, &pageIndex ); + + if( page != NULL ) + List_InsertExistingItem( list, page, pageIndex, item ); + else + List_HandleAddressingError(); + /* probably should handle an addressing error */ + } } - /*_____________________________________________________________________ - **Item**_______________________________________________________________ - * Returns the item of given index; returns NULL if no such index. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **Item**_______________________________________________________________ + * Returns the item of given index; returns NULL if no such index. + *______________________________________________________________________ + */ void * List_Item( const PtrList *this, size_t requestedIndex ) { - ListPage *itsPage = NULL; - size_t itsPageIndex; + ListPage *itsPage = NULL; + size_t itsPageIndex; - List_FindItemAddress( this, requestedIndex, &itsPage, &itsPageIndex ); + List_FindItemAddress( this, requestedIndex, &itsPage, &itsPageIndex ); - if( itsPage != NULL ) - return *( itsPage->items + itsPageIndex ); + if( itsPage != NULL ) + return *( itsPage->items + itsPageIndex ); - return NULL; + return NULL; } - /*_____________________________________________________________________ - **SetItem**____________________________________________________________ - * Sets the item of given index. Calls user-supplied addressing - * handler if no such item exists. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **SetItem**____________________________________________________________ + * Sets the item of given index. Calls user-supplied addressing + * handler if no such item exists. + *______________________________________________________________________ + */ void List_SetItem( PtrList *this, size_t requestedIndex, void *value ) { - ListPage *itsPage = NULL; - size_t itsPageIndex; + ListPage *itsPage = NULL; + size_t itsPageIndex; - List_FindItemAddress( this, requestedIndex, &itsPage, &itsPageIndex ); + List_FindItemAddress( this, requestedIndex, &itsPage, &itsPageIndex ); - if( itsPage != NULL ) - *( itsPage->items + itsPageIndex ) = value; - else - List_HandleAddressingError(); + if( itsPage != NULL ) + *( itsPage->items + itsPageIndex ) = value; + else + List_HandleAddressingError(); } - /*_____________________________________________________________________ - **CopyList**_________________________________________________________ - * Empties this list and puts items from other list in it. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **CopyList**_________________________________________________________ + * Empties this list and puts items from other list in it. + *______________________________________________________________________ + */ void List_CopyList( PtrList * this, const PtrList * other ) { - List_Empty( this ); - this->itemsPerPage = other->itemsPerPage; - this->firstPage = List_Xerox( other ); + List_Empty( this ); + this->itemsPerPage = other->itemsPerPage; + this->firstPage = List_Xerox( other ); } - /*_____________________________________________________________________ - **RemoveItem**_________________________________________________________ - * Removes the item of given index from the list by shifting all the - * following items back by one and reducing itsNumberOfItems by one. - * -> It would kind of be nice if this also deleted empty pages - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **RemoveItem**_________________________________________________________ + * Removes the item of given index from the list by shifting all the + * following items back by one and reducing itsNumberOfItems by one. + * -> It would kind of be nice if this also deleted empty pages + *______________________________________________________________________ + */ void * List_RemoveItem( PtrList *this, const size_t requestedIndex ) { - ListPage *page = NULL; - size_t pageIndex = 0; + ListPage *page = NULL; + size_t pageIndex = 0; - List_FindItemAddress( this, requestedIndex, &page, &pageIndex ); + List_FindItemAddress( this, requestedIndex, &page, &pageIndex ); - if( page != NULL ) - return ListPage_RemoveItem( page, pageIndex ); - else - List_HandleAddressingError(); + if( page != NULL ) + return ListPage_RemoveItem( page, pageIndex ); + else + List_HandleAddressingError(); - return NULL; + return NULL; } - /*_____________________________________________________________________ - **Remove**_____________________________________________________________ - * Removes the first item in the list with matching pointer. - * Note: No check is done for duplicate pointers in the list. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **Remove**_____________________________________________________________ + * Removes the first item in the list with matching pointer. + * Note: No check is done for duplicate pointers in the list. + *______________________________________________________________________ + */ void List_Remove( PtrList *this, void * item ) { - size_t index = 0; + size_t index = 0; - if( List_GetIndexOf( this, item, &index ) ) - List_RemoveItem( this, index ); + if( List_GetIndexOf( this, item, &index ) ) + List_RemoveItem( this, index ); } - /*_____________________________________________________________________ - **GetIndexOf**_________________________________________________________ - * Inverse of Item(), if pointers in list are unique. - * Note: No check is done for duplicate pointers in the list. - * Returns TRUE and sets the indexi argument to the first item in the - * list with matching pointer, if such an item exists; otherwise - * returns FALSE. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **GetIndexOf**_________________________________________________________ + * Inverse of Item(), if pointers in list are unique. + * Note: No check is done for duplicate pointers in the list. + * Returns TRUE and sets the indexi argument to the first item in the + * list with matching pointer, if such an item exists; otherwise + * returns FALSE. + *______________________________________________________________________ + */ PLBOOL List_GetIndexOf( const PtrList *this, const void * item, size_t * index ) { - size_t numItemsOnPreviousPages = 0; - ListPage *page = NULL; - - for( page = this->firstPage; page != NULL; page = page->next ) - { - const size_t numItemsOnPage = page->numberOfItems; - size_t i; - - for( i = 0; i < numItemsOnPage; i++ ) - if( *( page->items + i ) == item ) - { - *index = numItemsOnPreviousPages + i; - return PLTRUE; - } - numItemsOnPreviousPages += numItemsOnPage; - } - return PLFALSE; + size_t numItemsOnPreviousPages = 0; + ListPage *page = NULL; + + for( page = this->firstPage; page != NULL; page = page->next ) + { + const size_t numItemsOnPage = page->numberOfItems; + size_t i; + + for( i = 0; i < numItemsOnPage; i++ ) + if( *( page->items + i ) == item ) + { + *index = numItemsOnPreviousPages + i; + return PLTRUE; + } + numItemsOnPreviousPages += numItemsOnPage; + } + return PLFALSE; } #if 0 static void List_BubbleSort( PtrList * list, ListSortComparison comparison ) { - const size_t n = List_NumberOfItems( list ); - size_t i, j; + const size_t n = List_NumberOfItems( list ); + size_t i, j; - for( i = 0; i < n; i++ ) - { - void *item_i = List_Item( list, i ); + for( i = 0; i < n; i++ ) + { + void *item_i = List_Item( list, i ); - for( j = i + 1; j < n; j++ ) - { - void *item_j = List_Item( list, j ); + for( j = i + 1; j < n; j++ ) + { + void *item_j = List_Item( list, j ); - if( comparison( item_i, item_j ) > 0 ) - { - List_SwapItems( list, i, j ); - item_i = item_j; - } - } - } + if( comparison( item_i, item_j ) > 0 ) + { + List_SwapItems( list, i, j ); + item_i = item_j; + } + } + } } #endif void List_SwapItems( PtrList * v, size_t a, size_t b ) { - ListPage *aPage = NULL, *bPage = NULL; - size_t aPageInd, bPageInd; + ListPage *aPage = NULL, *bPage = NULL; + size_t aPageInd, bPageInd; - List_FindItemAddress( v, a, &aPage, &aPageInd ); - List_FindItemAddress( v, b, &bPage, &bPageInd ); + List_FindItemAddress( v, a, &aPage, &aPageInd ); + List_FindItemAddress( v, b, &bPage, &bPageInd ); - if( aPage != NULL && bPage != NULL ) - { - void *temp = *( aPage->items + aPageInd ); - *( aPage->items + aPageInd ) = *( bPage->items + bPageInd ); - *( bPage->items + bPageInd ) = temp; - } + if( aPage != NULL && bPage != NULL ) + { + void *temp = *( aPage->items + aPageInd ); + *( aPage->items + aPageInd ) = *( bPage->items + bPageInd ); + *( bPage->items + bPageInd ) = temp; + } } - /* Adapted from Kernighan & Ritchie */ + /* Adapted from Kernighan & Ritchie */ static void List_Qsort( PtrList * v, size_t left, size_t right, ListSortComparison comparison ) { - size_t i, last; - - if( left >= right ) /* do nothing if array contains */ - return; /* fewer than two elements */ - List_SwapItems( v, left, ( left + right ) / 2); /* move partition */ - last = left; /* elem to v[0] */ - for( i = left + 1; i <= right; i++ ) - {/* SW this could be improved a lot */ - void * item_i = List_Item( v, i ); - void * item_left = List_Item( v, left ); - if( comparison( item_i, item_left ) < 0 ) - List_SwapItems( v, ++last, i ); - } - List_SwapItems( v, left, last ); /* restore partition elem */ + size_t i, last; + + if( left >= right ) /* do nothing if array contains */ + return; /* fewer than two elements */ + List_SwapItems( v, left, ( left + right ) / 2); /* move partition */ + last = left; /* elem to v[0] */ + for( i = left + 1; i <= right; i++ ) + {/* SW this could be improved a lot */ + void * item_i = List_Item( v, i ); + void * item_left = List_Item( v, left ); + if( comparison( item_i, item_left ) < 0 ) + List_SwapItems( v, ++last, i ); + } + List_SwapItems( v, left, last ); /* restore partition elem */ /* SW NEED TO THINK ABOUT THIS */ - if( last > 0 ) /* K&R use int, so this isn't an issue for them */ - List_Qsort( v, left, last - 1, comparison ); - List_Qsort( v, last + 1, right, comparison ); + if( last > 0 ) /* K&R use int, so this isn't an issue for them */ + List_Qsort( v, left, last - 1, comparison ); + List_Qsort( v, last + 1, right, comparison ); } - /*_____________________________________________________________________ - **SortAccordingTo**__________________________________________________ - * Based on the comparison of any two items provided by the comparison - * function argument, sorts the list. - * Note here it uses a bubble sort, which is slow but easy to - * understand. Want something faster? Write your own! - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **SortAccordingTo**__________________________________________________ + * Based on the comparison of any two items provided by the comparison + * function argument, sorts the list. + * Note here it uses a bubble sort, which is slow but easy to + * understand. Want something faster? Write your own! + *______________________________________________________________________ + */ void List_SortAccordingTo( PtrList * list, ListSortComparison comparison ) { - size_t n = List_NumberOfItems( list ); - if( n > 1 ) - List_Qsort( list, 0, n - 1, comparison ); + size_t n = List_NumberOfItems( list ); + if( n > 1 ) + List_Qsort( list, 0, n - 1, comparison ); } - /*_____________________________________________________________________ - **FirstItemSuchThat**__________________________________________________ - * Takes a ListCondition function, returns the pointer value that - * satisfies the condition, otherwise returns NULL, - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **FirstItemSuchThat**__________________________________________________ + * Takes a ListCondition function, returns the pointer value that + * satisfies the condition, otherwise returns NULL, + *______________________________________________________________________ + */ void * List_FirstItemSuchThat( const PtrList *list, ListCondition condition ) { - const size_t n = List_NumberOfItems( list ); - size_t i; + const size_t n = List_NumberOfItems( list ); + size_t i; - for( i = 0; i < n; i++ ) - if( condition( List_Item( list, i ) ) ) - return List_Item( list, i ); + for( i = 0; i < n; i++ ) + if( condition( List_Item( list, i ) ) ) + return List_Item( list, i ); - return NULL; + return NULL; } - /*_____________________________________________________________________ - **FindFirstIndexSuchThat**_____________________________________________ - * Takes a ListCondition function, sets the index pointer to the index - * of the first pointer in the list that satisfies condition. - * Otherwise returns PLFALSE. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **FindFirstIndexSuchThat**_____________________________________________ + * Takes a ListCondition function, sets the index pointer to the index + * of the first pointer in the list that satisfies condition. + * Otherwise returns PLFALSE. + *______________________________________________________________________ + */ PLBOOL List_FindFirstIndexSuchThat( const PtrList *list, ListCondition condition, - size_t * index ) + size_t * index ) { - const size_t n = List_NumberOfItems( list ); - size_t i; + const size_t n = List_NumberOfItems( list ); + size_t i; - for( i = 0; i < n; i++ ) - if( condition( List_Item( list, i ) ) ) - { - *index = i; - return PLTRUE; - } + for( i = 0; i < n; i++ ) + if( condition( List_Item( list, i ) ) ) + { + *index = i; + return PLTRUE; + } - return PLFALSE; + return PLFALSE; } - /*_____________________________________________________________________ - **FreeItemsInListAndEmpty**____________________________________________ - * Lists don't usually delete the things they refer to. - * This function takes the list and uses it to free the listed items. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **FreeItemsInListAndEmpty**____________________________________________ + * Lists don't usually delete the things they refer to. + * This function takes the list and uses it to free the listed items. + *______________________________________________________________________ + */ void List_FreeItemsInListAndEmpty( PtrList * this ) { - size_t i = List_NumberOfItems( this ); - void *item = NULL; - - while( i > 0 ) /* Remove items in reverse order for efficeincy */ - { - i--; - item = List_Item( this, i ); - List_RemoveItem( this, i ); /* Remove item before deleting */ - /* (for consistency) */ - free( item ); - } + size_t i = List_NumberOfItems( this ); + void *item = NULL; + + while( i > 0 ) /* Remove items in reverse order for efficeincy */ + { + i--; + item = List_Item( this, i ); + List_RemoveItem( this, i ); /* Remove item before deleting */ + /* (for consistency) */ + free( item ); + } } - /*_____________________________________________________________________ - **FindItemAddress**____________________________________________________ - * Private utility that gets the page and index relative to the page - * given the item index. Sets *thePage to NULL if no such index. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **FindItemAddress**____________________________________________________ + * Private utility that gets the page and index relative to the page + * given the item index. Sets *thePage to NULL if no such index. + *______________________________________________________________________ + */ void List_FindItemAddress( const PtrList *this, size_t itemNo, - ListPage ** thePage, size_t *thePageIndex ) -{ - ListPage *page = NULL; - size_t numItemsIncludingThisPage = 0, - numItemsOnPreviousPages = 0; - - *thePage = NULL; - *thePageIndex = 0; - - for( page = this->firstPage; page != NULL; page = page->next ) - { - numItemsIncludingThisPage += page->numberOfItems; - - if( numItemsIncludingThisPage > itemNo ) - { - *thePage = page; - *thePageIndex = itemNo - numItemsOnPreviousPages; - return; - } - numItemsOnPreviousPages = numItemsIncludingThisPage; - } + ListPage ** thePage, size_t *thePageIndex ) +{ + ListPage *page = NULL; + size_t numItemsIncludingThisPage = 0, + numItemsOnPreviousPages = 0; + + *thePage = NULL; + *thePageIndex = 0; + + for( page = this->firstPage; page != NULL; page = page->next ) + { + numItemsIncludingThisPage += page->numberOfItems; + + if( numItemsIncludingThisPage > itemNo ) + { + *thePage = page; + *thePageIndex = itemNo - numItemsOnPreviousPages; + return; + } + numItemsOnPreviousPages = numItemsIncludingThisPage; + } } - /*_____________________________________________________________________ - **Xerox**______________________________________________________________ - * Private utility that makes a duplicate of the pages in the list. - *______________________________________________________________________ - */ + /*_____________________________________________________________________ + **Xerox**______________________________________________________________ + * Private utility that makes a duplicate of the pages in the list. + *______________________________________________________________________ + */ ListPage * List_Xerox( const PtrList *list) { - ListPage *copy = NULL, *newPage = NULL, *page = list->firstPage; - - if( list->firstPage != NULL ) - copy = newPage = ListPage_Dup( list->firstPage ); - - if( newPage != NULL ) - do - { - if( page->next != NULL ) - { - page = page->next; - newPage->next = ListPage_Dup( page ); - } - newPage = newPage->next; - } - while( newPage != NULL ); - return copy; + ListPage *copy = NULL, *newPage = NULL, *page = list->firstPage; + + if( list->firstPage != NULL ) + copy = newPage = ListPage_Dup( list->firstPage ); + + if( newPage != NULL ) + do + { + if( page->next != NULL ) + { + page = page->next; + newPage->next = ListPage_Dup( page ); + } + newPage = newPage->next; + } + while( newPage != NULL ); + return copy; } - |