PtrList A C module for a list of pointers. Embodies the idea of a list as a grocery list: the list doesn't contain the groceries, it only refers to them; if you throw the list away, you don't necessarily lose the produce. Typical use =========== The items in a PtrList are referenced as pointers to void. PtrList can be used directly this way, but isn't type-safe. It is usually better to write a wrapper around PtrList for each type of data which needs to be listed, whose Item() function returns a pointer to an item of that type, etc. This can be done for simple cases with preprocessor macros, or for more involved cases with a separate header and source file. ------------------------------- EXAMPLE ---------------------------------- ------------------- MyList.h ------------------ typedef struct PtrList_tag MyListType; size_t MyListType_NumberOfThings( const MyListType * ); MyListType * MyListType_New( void ); ... ------------------- .c file ------------------- #include "MyList.h" size_t MyListType_NumberOfThings( const MyListType * list ) { return List_NumberOfItems( list ); } MyListType * MyListType_New() { return (MyListType *)List_New(); } ------------------------------------------------------------------- Life-cycle ========== 1) Create with PtrList_New PtrList_MakeCopy 2) Manipulate, pass to functions, etc 3) Reclaim memory with PtrList_Delete Efficiency ========== One efficiency concern governed the internal structure of the module, namely how to deal with memory needed to deal with the pointers being added. The simplest thing would be to allocate a block of memory the size of a pointer for each item added. For very simple applications making heavy use of a list with many items, this is prohibitive. PtrList does not require a memory allocation per item to append an item. Internally, the PtrList maintains a list of pages of pointers, each of which contains many pointers. When the first item is appended to an empty PtrList, one of these pages is allocated and initialized, and the pointer is written in the page. When a second item is appended, it is written directly into this existing page. Only when that page is full is another allocated. If an item is inserted into a PtrList, it is inserted into the appropriate page, and possibly the last item on that page needs to be moved to the next page, but if that page is again full, the PtrList just inserts a new empty page and puts the remaining item onto the new page. The only concession made in the API to this paging structure is the creator function ListPage_NewWithPageSize( size_t size ), which allows the user to set the number of elements on each page. For example, if the maximum number of items in the list is known for the application, the page size can be set to that maximum, thus avoiding much of the internal paging mechanism. Limitations =========== The PtrList does not (at present) put much effort into compressing pages from which items are removed. So if all but one item is removed from each page, it will stay that way, rather than compressing the items onto fewer pages. One improvment would be to make the list compress itself during a Remove call, whenever, say, a page is found to be less than half full. Various other improvements could be made: the number of items in the list could be cached for NumberOfItems. Name convention =============== In some applications, especially when the list items are guaranteed to be unique, it makes sense to refer to the pointer items by their values. In other applications, it only makes sense to refer to them by their indices. To distinguish between functions meant for the two cases, those which refer to the item by index will have Item in their name, whereas the corresponding funcition that refers to the item by value does not: Remove vs RemoveItem. Namespace ========= The header file PtrList_Namespace.h contains macros that locally transforms shortened PtrList function names to the full ones. Only names following the inclusion of the file are affected. So long as no other function names in your source file collide with these shortened names in your file, you may use them to make your code easier to read. The main creation and deletion functions are not shortened by this file. Special functions ================= Note: Lost_GetIndexOf List_Remove These just find the first item pointer whose value is the same as the input value. Note that PtrList makes no check as to the uniqueness of pointers put into the list. List_FreeItemsInListAndEmpty Is a useful utility, but it isn't really a method of a PtrList in the sense that in the common usage of the term 'list', a list doesn't throw away its items. Also, be aware that this assumes the items are simple blocks of memory allocated with one of the standard C library routines ('malloc', etc). It just calls free on each one and removes it in the most efficient way (from the end of the list). Function Reference ================== PtrList * List_New( void ) Creates a new empty list. PtrList * List_NewWithPageSize( size_t size ) Creates a new empty list, and sets the internal page size. PtrList * List_MakeCopy( const PtrList *other ) Creates a new list containing the same items as does the argument. void List_Delete( PtrList *list ) Frees the list and memory it allocates internally. DOES NOT do anything to the items pointed to by list items. static void List_HandleAddressingError() To be supplied by user of list code. Called when item accesssor is called with an index out of range. void List_Empty( PtrList * this ) Removes all the items on the list (does nothing to items pointed to by the list items). size_t List_NumberOfItems( const PtrList *this ) Returns the number of items in the list. void List_Append( PtrList *this, void * newItem ) Puts a new item on the end of the list. void List_InsertItem( PtrList *this, size_t index, void * newItem ) Inserts the item at the specified index, shifting indices of existing list items as necessary. If index is greater than or equal to the number of items initially in the list, the item is just appended. void * List_Item( const PtrList *this, size_t requestedIndex ) Returns the item of given index; returns NULL if no such index. The items are indexed beginning with 0; void List_SetItem( PtrList *this, size_t requestedIndex, void *value ) Sets the item of given index. Calls user-supplied addressing handler if no such item exists. void List_CopyList( PtrList *list, const PtrList * other ) Empties this list and puts items from other list in it. void * List_RemoveItem( PtrList *list, size_t index ) Removes the item of given index from the list. Returns a pointer to the item removed, or NULL if item not found. void List_Remove( PtrList *list, void * item ) Removes the first item in the list with pointer identical to 'item'. PLBOOL List_GetIndexOf( const PtrList *this, const void * item, size_t * index ) Returns TRUE and sets the index argument to the first item in the list with pointer identical to 'item', if such an item exists; otherwise returns FALSE. Note: is inverse of Item(), if pointers in list are unique. void List_SortAccordingTo( PtrList * list, ListSortComparison comparison ) Based on the comparison of any two items provided by the comparison function argument, sorts the list. void * List_FirstItemSuchThat( const PtrList *list, ListCondition condition ) Takes a ListCondition function, returns the pointer value that satisfies the condition, otherwise returns NULL, PLBOOL List_FindFirstIndexSuchThat( const PtrList *list, ListCondition condition, size_t * index ) Takes a ListCondition function, sets the index pointer to the index of the first pointer in the list that satisfies condition. Otherwise returns FALSE. void List_FreeItemsInListAndEmpty( PtrList * this ) Lists don't usually delete the things they refer to. This function takes the list and uses it to free the listed items.