1 /* 2 3 4 W3C Sample Code Library libwww List Class 5 6 7 ! 8 The List Class 9 ! 10 */ 11 12 /* 13 ** (c) COPYRIGHT MIT 1995. 14 ** Please first read the full copyright statement in the file COPYRIGH. 15 */ 16 17 /* 18 19 The list class defines a generic container for storing collections of things 20 in order. In principle it could be implemented in many ways, but in practice 21 knowing that it is a linked list is important for speed. 22 23 This module is implemented by HTList.c, and it is 24 a part of the W3C Sample Code 25 Library. 26 */ 27 28 #ifndef HTLIST_H 29 #define HTLIST_H 30 31 #include "HTArray.h" 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 typedef struct _HTList HTList; 38 39 struct _HTList { 40 void * object; 41 HTList * next; 42 }; 43 44 /* 45 . 46 Creation and Deletion Methods 47 . 48 49 These two functions create and deletes a list 50 */ 51 52 extern HTList * HTList_new (void); 53 extern BOOL HTList_delete (HTList *me); 54 55 /* 56 . 57 Add an Element to List 58 . 59 60 A new list element is added to the beginning of the list so that it is first 61 element just after the head element. 62 */ 63 extern BOOL HTList_addObject (HTList *me, void *newObject); 64 65 /* 66 67 You can also append an element to the end of 68 the list (the end is the first entered object) by using the following function: 69 */ 70 71 extern BOOL HTList_appendObject (HTList * me, void * newObject); 72 73 /* 74 The following two functions, contributed by Vic 75 Bancroft (bancroft@america.net) that do the same operation as above, but return 76 a pointer to the new HTList element that was added or appended. This allows 77 one to keep a reference to the end of the list outside of the list itself, 78 which can be used to speed up certain list operations. 79 */ 80 81 extern HTList * HTList_addList (HTList * me, void * newObject); 82 extern HTList * HTList_appendList (HTList * me, void * newObject); 83 84 /* 85 . 86 Remove List Elements 87 . 88 89 You can delete elements in a list using the following methods. The 90 first method only removes the first entry that it finds matching the 91 oldObject whereas the second method removes all 92 occurances of oldObject. 93 94 */ 95 96 extern BOOL HTList_removeObject (HTList * me, void * oldObject); 97 extern BOOL HTList_quickRemoveElement (HTList * me, HTList * last); 98 extern BOOL HTList_removeObjectAll (HTList * me, void * oldObject); 99 100 extern void * HTList_removeLastObject (HTList * me); 101 extern void * HTList_removeFirstObject (HTList * me); 102 103 /* 104 . 105 Size of a List 106 . 107 108 Two small function to ask for the size 109 */ 110 111 #define HTList_isEmpty(me) (me ? me->next == NULL : YES) 112 extern int HTList_count (HTList *me); 113 114 /* 115 . 116 Reference List Elements By Index 117 . 118 119 In some situations is is required to use an index in order to refer to a 120 list element. This is for example the case if an element can be registered 121 multiple times. 122 */ 123 124 extern int HTList_indexOf (HTList * me, void * object); 125 extern int HTList_indexOfElement (HTList * me, HTList * element); 126 extern void * HTList_objectAt (HTList * me, int position); 127 extern HTList * HTList_elementOf (HTList * me, void * object, HTList ** pLast); 128 #define HTList_objectOf(me) (me ? me->object: NULL) 129 130 /* 131 . 132 Find List Elements 133 . 134 135 This method returns the last element to the list or NULL if list is 136 empty 137 */ 138 139 #define HTList_lastObject(me) \ 140 ((me) && (me)->next ? (me)->next->object : NULL) 141 142 /* 143 144 This method returns the first element to the list or NULL if list 145 is empty 146 */ 147 extern void * HTList_firstObject (HTList * me); 148 149 /* 150 . 151 Traverse list 152 . 153 154 Fast macro to traverse the list. Call it first with copy of list header: 155 it returns the first object and increments the passed list pointer. Call 156 it with the same variable until it returns NULL. 157 */ 158 159 #define HTList_nextObject(me) \ 160 ((me) && ((me) = (me)->next) ? (me)->object : NULL) 161 162 /* 163 . 164 Insertion Sort a List 165 . 166 167 This function sorts a list using the insertion sort mechanism. The comparison 168 function is passed as a parameter and you can find the definition of 169 HTComparer in the HTArray module. 170 Insertion sort is good method whenever a list is nearly in the correct order 171 and few items are many positions away from their sorted location. If the 172 list gets very long then you may wanna use a quicksort instead. 173 */ 174 extern BOOL HTList_insertionSort(HTList * list, HTComparer * comp); 175 176 /* 177 . 178 Free list 179 . 180 */ 181 182 #define HTList_free(x) HT_FREE(x) 183 184 #ifdef __cplusplus 185 } 186 #endif 187 188 #endif /* HTLIST_H */ 189 190 /* 191 192 193 194 @(#) $Id$ 195 196 */ 197