/*----------------------------------------------------------- * Name: linked_list.c * Created: Fri Apr 22 02:31:08 1994 * Author: Jonathan DeKock * DESCR: generic linked list code */ #include #include #include #include #include #include /******************* Global Variables **********************/ static LL_ErrorProc LL_Handler = (LL_ErrorProc) LL_DefaultHandler; static LL_SortProc LL_SortFunction = NULL; const char *LL_errlist[] = { "unknown error", "memory error", "no such member", "list not empty", "list corrupted", "invalid operation", "invalid offset", "invalid set of attributes", "invalid argument", }; #if defined(LL_DEBUG) || defined(_LL_INTERNAL_DEBUG) static const char *tfs[] = { "False", "True", }; #endif /******************* Internal Macros ***********************/ #define tfm(a) ((a) ? tfs[1] : tfs[0]) /* Returns "True" or "False" */ /* Intrusive Macros for Next and Prev */ #define NextP(ll, d) *(DATA_PTR*)((char*)d + ll->next_offset) #define PrevP(ll, d) *(DATA_PTR*)((char*)d + ll->prev_offset) /*----------------------------------------------------------- * Name(s): LLM_PS() * LLM_PD() * LLM_PH() * LLM_PO() * Created: Wed Aug 31 00:25:50 1994 * Author: Jonathan DeKock * DESCR: prints the attribute and its value. */ #define LLM_PS(ll, attr, val) printf("LINKED LIST: 0x%.8x attribute %-18s = %s\n", (u_int)ll, attr, val) #define LLM_PD(ll, attr, val) printf("LINKED LIST: 0x%.8x attribute %-18s = %d\n", (u_int)ll, attr, (u_int)val) #define LLM_PH(ll, attr, val) printf("LINKED LIST: 0x%.8x attribute %-18s = 0x%.8x\n", (u_int)ll, attr, (u_int)val) /*----------------------------------------------------------- * Name: LLMacro_PrintAllAttr() * Created: Wed Aug 31 00:26:42 1994 * Author: Jonathan DeKock * DESCR: prints all the attributes */ #define LLMacro_PrintAllAttr(ll)\ {\ LLM_PS(ll, "LL_Intrusive", tfm(ll->attr & LL_Intrusive));\ LLM_PS(ll, "LL_AutoSort", tfm(ll->attr & LL_AutoSort));\ LLM_PS(ll, "LL_ReportChange", tfm(ll->attr & LL_ReportChange));\ LLM_PS(ll, "LL_ReportAccess", tfm(ll->attr & LL_ReportAccess));\ LLM_PD(ll, "ll->count", ll->count);\ if (ll->attr & LL_Intrusive) {\ LLM_PD(ll, "LL_NextOffset", ll->next_offset);\ LLM_PD(ll, "LL_PrevOffset", ll->prev_offset);\ }\ LLM_PH(ll, "LL_FindFunction", ll->find_fn);\ LLM_PH(ll, "LL_CompareFunction", ll->comp_fn);\ LLM_PH(ll, "LL_DestroyFunction", ll->destroy_fn);\ } /*----------------------------------------------------------- * Name: LLMacro_SetAttr() * Created: Wed Aug 31 00:44:58 1994 * Author: Jonathan DeKock * DESCR: sets the attribute attr with the next arg. */ #define LLMacro_SetAttr(ll, attr, ap, val, ptr) \ { \ switch (attr) {\ case LL_Intrusive:\ case LL_AutoSort:\ case LL_ReportChange:\ case LL_ReportAccess:\ val = va_arg(ap, int);\ if (val) ll->attr = (enum LL_ATTR)(ll->attr | attr);\ else ll->attr = (enum LL_ATTR)(ll->attr & ~attr);\ break;\ case LL_NonIntrusive:\ val = va_arg(ap, int);\ if (val) ll->attr = (enum LL_ATTR)(ll->attr & ~LL_Intrusive);\ else ll->attr = (enum LL_ATTR)(ll->attr | LL_Intrusive);\ break;\ case LL_NextOffset:\ val = va_arg(ap, int);\ ll->next_offset = (short) val;\ ll->attr = (enum LL_ATTR)(ll->attr | LL_Intrusive);\ break;\ case LL_PrevOffset:\ val = va_arg(ap, int);\ ll->prev_offset = (short) val;\ ll->attr = (enum LL_ATTR)(ll->attr | LL_Intrusive);\ break;\ case LL_PointersOffset:\ val = (enum LL_ATTR) va_arg(ap, int);\ ll->next_offset = (short) val;\ ll->prev_offset = (short) val + sizeof(DATA_PTR);\ ll->attr = (enum LL_ATTR)(ll->attr | LL_Intrusive);\ break;\ case LL_FindFunction:\ ptr = va_arg(ap, DATA_PTR);\ ll->find_fn = (LL_FindProc)ptr;\ break;\ case LL_CompareFunction:\ ptr = va_arg(ap, DATA_PTR);\ ll->comp_fn = (LL_CompareProc)ptr;\ break;\ case LL_DestroyFunction:\ ptr = va_arg(ap, DATA_PTR);\ ll->destroy_fn = (LL_DestroyProc)ptr;\ break;\ default:\ if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_SetAttributes()"); }\ attr = (enum LL_ATTR)0; /* inform caller of failure */\ break;\ }\ } #ifdef LL_DEBUG /*----------------------------------------------------------- * Name: LLMacro_VerifyList() * Created: Wed Aug 31 00:47:18 1994 * Author: Jonathan DeKock * DESCR: in debug mode this verifies a valid list */ #define LLMacro_VerifyList(ll, fn) \ {\ /* if Intrusive must have diff offsets */\ if ((ll->attr & LL_Intrusive) && (ll->next_offset == ll->prev_offset) && (LL_Handler)) { \ (LL_Handler)(ll, LL_BadAttributes, fn); \ }\ /* if Auto-sorted, must have comparison function */\ if ((ll->attr & LL_AutoSort) && (ll->comp_fn == NULL) && (LL_Handler)) {\ (LL_Handler)(ll, LL_BadAttributes, fn);\ }\ } #endif /* LL_DEBUG */ /*----------------------------------------------------------- * Name: LLMacro_GetContainer() * Created: Fri Sep 2 02:10:48 1994 * Author: Jonathan DeKock * DESCR: gets a container for an item dddddd */ #define LLMacro_GetContainer(ll, result, input)\ {\ if ((ll->last) && (ll->last->data == input)) {\ result = ll->last;\ }\ else if ((ll->last) && (ll->last->next != NULL) && (ll->last->next->data == input)) {\ result = ll->last->next;\ }\ else if ((ll->last) && (ll->last->prev) && (ll->last->prev->data == input)) {\ result = ll->last->prev;\ }\ else {\ for (result = ll->head.cont; result; result = result->next) {\ if (result->data == input) break;\ }\ }\ } /*void LLMacro_GetContainer(LINKED_LIST *ll, DATA_PTR result, DATA_PTR input) { if ((ll->last) && (ll->last->data == input)) { result = ll->last; } else if ((ll->last) && (ll->last->next != NULL) && (ll->last->next->data == input)) { result = ll->last->next; } else if ((ll->last) && (ll->last->prev) && (ll->last->prev->data == input)) { result = ll->last->prev;\ } else { for (result = ll->head.cont; result; result = result->next) { if (result->data == input) break; } } } */ /*----------------------------------------------------------- * Name: LLMacro_ContPlaceBetween() * Created: Fri Sep 2 17:29:37 1994 * Author: Jonathan DeKock * DESCR: places container "elt" between "before" and "after" */ #ifdef notdef /* * Here should be a bug so that LL_Prepend doesn't work properly. * This routine is a macro but the arguments before and after * can be ll->head.cont and ll->tail.cont respectively. * In case that after is ll->head.cont, which will be refered * later in the macro, the argument after gets modofied before * the refference occurs if before is null. * This is the case to prepend an item. If this routine were a * function, this hasn't happened. */ #define LLMacro_ContPlaceBetween(ll, elt, before, after)\ {\ elt->next = after;\ elt->prev = before;\ if (before) before->next = elt;\ else ll->head.cont = elt;\ if (after) after->prev = elt;\ else ll->tail.cont = elt;\ } #else /* * Masaki's fix */ #define LLMacro_ContPlaceBetween(ll, elt, before, after)\ {\ /* This is another fix not to allow a duplicate data */\ /*LL_CONTAINER *Xcp; */ \ /*for (Xcp = ll->head.cont; Xcp; Xcp = Xcp->next) {\ if (Xcp->data == elt->data) {\ if (LL_Handler) {\ (LL_Handler)(ll, LL_UnknownErr, "LLMacro_ContPlaceBetween()");\ }\ }\ }\ */ \ elt->next = after;\ elt->prev = before;\ if (before) {\ before->next = elt;\ if (after) after->prev = elt;\ else ll->tail.cont = elt;\ }\ else {\ if (after) after->prev = elt;\ else ll->tail.cont = elt;\ ll->head.cont = elt;\ }\ } #endif /*----------------------------------------------------------- * Name: LLMacro_IntrPlaceBetween() * Created: Fri Sep 2 17:40:56 1994 * Author: Jonathan DeKock * DESCR: places data "elt" between "before" and "after" */ #ifdef notdef /* See LLMacro_ContPlaceBetween -- Masaki */ #define LLMacro_IntrPlaceBetween(ll, elt, before, after)\ {\ NextP(ll, elt) = after;\ PrevP(ll, elt) = before;\ if (before) NextP(ll, before) = elt;\ else ll->head.data = elt;\ if (after) PrevP(ll, after) = elt;\ } #else #define LLMacro_IntrPlaceBetween(ll, elt, before, after)\ {\ NextP(ll, elt) = after;\ PrevP(ll, elt) = before;\ if (before) {\ NextP(ll, before) = elt;\ if (after) PrevP(ll, after) = elt;\ else ll->tail.data = elt;\ }\ else {\ if (after) PrevP(ll, after) = elt;\ else ll->tail.data = elt;\ ll->head.data = elt;\ }\ } #endif /******************* Function Definitions ******************/ /*----------------------------------------------------------- * Name: LL_Create() * Created: Tue Aug 30 19:12:42 1994 * Author: Jonathan DeKock * DESCR: Creates and initilizes a linked list with var. args */ LINKED_LIST *LL_Create(int first, ...) { va_list ap; enum LL_ATTR attr; int val; DATA_PTR ptr; LINKED_LIST *ll; /* Create it */ if (!(ll = New(LINKED_LIST))) { if (LL_Handler) { (LL_Handler)(ll, LL_MemoryErr, "LL_Create()"); } return(NULL); } /* Initialize it */ ll->head.data = NULL; ll->head.cont = NULL; ll->tail.data = NULL; ll->tail.cont = NULL; ll->last = NULL; ll->find_fn = NULL; ll->comp_fn = NULL; ll->destroy_fn = NULL; ll->count = 0; ll->next_offset = 0; ll->prev_offset = sizeof(DATA_PTR); ll->attr = (enum LL_ATTR) 0; /* Process the Arguments */ va_start(ap, first); for (attr = (enum LL_ATTR)first; attr; attr = va_arg(ap, enum LL_ATTR)) { LLMacro_SetAttr(ll, attr, ap, val, ptr); if (!attr) break; /* something went wrong inside --> hit default, bad attribute*/ } va_end(ap); #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x Create()\n", ll); LLMacro_PrintAllAttr(ll); } LLMacro_VerifyList(ll, "LL_Create()"); #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(ll); } /*----------------------------------------------------------- * Name: LL_ClearFn() * Created: Wed Aug 31 01:31:06 1994 * Author: Jonathan DeKock * DESCR: removes every item from the list, * but leaves attributes intact. */ void LL_ClearFn(LINKED_LIST *ll, LL_DestroyProc destroy) { DATA_PTR data; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Clear()"); } return; } #endif while ((data = LL_GetHead(ll))) { LL_RemoveFn(ll, data, destroy); } #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) printf("LINKED LIST: 0x%.8x Clear(0x%.8x)\n", ll, destroy); #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } /*----------------------------------------------------------- * Name: LL_DestroyFn() * Created: Wed Aug 31 01:57:27 1994 * Author: Jonathan DeKock * DESCR: destroys a linked list and frees all Memory */ void LL_DestroyFn(LINKED_LIST *ll, LL_DestroyProc destroy) { #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Destroy()"); } return; } #endif LL_ClearFn(ll, destroy); Delete(ll); #ifdef LL_DEBUG /* if (ll->attr & LL_ReportChange) printf("LINKED LIST: 0x%.8x Destroy(0x%.8x)\n", ll, destroy);*/ #endif } /*----------------------------------------------------------- * Name: LL_SetAttributes() * Created: Wed Aug 31 03:29:08 1994 * Author: Jonathan DeKock * DESCR: sets 1 or more attributes */ void LL_SetAttributes(LINKED_LIST *ll, enum LL_ATTR first, ...) { va_list ap; enum LL_ATTR attr; int val; DATA_PTR ptr; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_SetAttributes()"); } return; } #endif va_start(ap, first); for (attr = first; attr; attr = va_arg(ap, enum LL_ATTR)) { LLMacro_SetAttr(ll, attr, ap, val, ptr); if (!attr) break; /* Attribute set failure --> BAD ATTRIBUTE */ #ifdef LL_DEBUG if (ll->count != 0 && ((attr & LL_Intrusive) || (attr & LL_NonIntrusive) || (attr & LL_NextOffset) || (attr & LL_PrevOffset) || (attr & LL_PointersOffset))) { if (LL_Handler) { (LL_Handler)(ll, LL_ListNotEmpty, "LL_SetAttributes()"); } break; } #endif } va_end(ap); #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x SetAttributes()\n", ll); LLMacro_PrintAllAttr(ll); } LLMacro_VerifyList(ll, "LL_SetAttributes()"); #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } /*----------------------------------------------------------- * Name: LL_Append() * Created: Wed Aug 31 16:49:07 1994 * Author: Jonathan DeKock * DESCR: appends a item onto the linked list */ DATA_PTR LL_Append(LINKED_LIST *ll, DATA_PTR data) { #ifdef LL_DEBUG if (!ll || !data) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Append()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { LLMacro_IntrPlaceBetween(ll, data, ll->tail.data, NULL); } else { LL_CONTAINER *NULL_CONT = NULL; /* Required to make macro work */ LL_CONTAINER *cont = New(LL_CONTAINER); if (!cont) { if (LL_Handler) { (LL_Handler)(ll, LL_MemoryErr, "LL_Append()"); } return(NULL); } cont->data = data; LLMacro_ContPlaceBetween(ll, cont, ll->tail.cont, NULL_CONT); ll->last = cont; } ll->count++; #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x Append(0x%.8x) count = %d\n", ll, data, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(data); } /*----------------------------------------------------------- * Name: LL_Prepend() * Created: Thu Sep 1 14:40:33 1994 * Author: Jonathan DeKock * DESCR: places data on the head of the list */ DATA_PTR LL_Prepend(LINKED_LIST *ll, DATA_PTR data) { #ifdef LL_DEBUG if (!ll || !data) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Prepend()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { LLMacro_IntrPlaceBetween(ll, data, NULL, ll->head.data); } else { LL_CONTAINER *NULL_CONT = NULL; /* Required to make macro work */ LL_CONTAINER *cont = New(LL_CONTAINER); if (!cont) { if (LL_Handler) {(LL_Handler)(ll, LL_MemoryErr, "LL_Prepend()"); } return(NULL); } cont->data = data; LLMacro_ContPlaceBetween(ll, cont, NULL_CONT, ll->head.cont); ll->last = cont; } ll->count++; #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x Prepend(0x%.8x) count = %d\n", ll, data, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(data); } /*----------------------------------------------------------- * Name: LL_InsertSorted() * Created: Thu Sep 1 23:44:55 1994 * Author: Jonathan DeKock * DESCR: inserts an element into a sorted list */ DATA_PTR LL_InsertSorted(LINKED_LIST *ll, DATA_PTR data, ...) { LL_CompareProc compare = ll->comp_fn; #ifdef LL_DEBUG if (!ll || !data) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_InsertSorted()"); } return(NULL); } #endif if (!(compare)) { va_list ap; va_start(ap, data); compare = va_arg(ap, LL_CompareProc); va_end(ap); } #ifdef LL_DEBUG if (!compare) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_InsertSorted()"); } return(NULL); } #endif LL_InsertSortedFn(ll, data, compare); #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(data); } /*----------------------------------------------------------- * Name: LL_InsertSortedFn() * Created: Thu Sep 1 23:49:05 1994 * Author: Jonathan DeKock * DESCR: inserts an element into a sorted list by function compare */ DATA_PTR LL_InsertSortedFn(LINKED_LIST *ll, DATA_PTR data, LL_CompareProc compare) { DATA_PTR before, after; #ifdef LL_DEBUG if (!ll || !data || !compare) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_InsertSortedFn()"); } return(NULL); } #endif /* If the list is Intrusive */ if (ll->attr & LL_Intrusive) { /* Search backwards to find position */ for (after = NULL, before = ll->tail.data; before; after = before, before = PrevP(ll, before)) { if ((compare)(before, data) <= 0) break; /* Got it, insert between before and after */ } LLMacro_IntrPlaceBetween(ll, data, before, after); } else { /* Container */ LL_CONTAINER *before_cont, *after_cont, *cont; cont = New(LL_CONTAINER); if (!cont) { if (LL_Handler) { (LL_Handler)(ll, LL_MemoryErr, "LL_InsertSorted()"); } return(NULL); } /* Search backwards to find position */ for (after_cont = NULL, before_cont = ll->tail.cont; before_cont; after_cont = before_cont, before_cont = before_cont->prev) { if ((compare)(before_cont->data, data) <= 0) break; /* Got it, insert between before and after */ } cont->data = data; LLMacro_ContPlaceBetween(ll, cont, before_cont, after_cont); before = (before_cont) ? before_cont->data : NULL; after = (after_cont) ? after_cont->data : NULL; ll->last = cont; } ll->count++; #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x InsertSorted(0x%.8x, 0x%.8x) count = %d\n", ll, data, compare, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(data); } /*----------------------------------------------------------- * Name: LL_InsertAfter() * Created: Fri Sep 2 01:51:07 1994 * Author: Jonathan DeKock * DESCR: inserts a data element after another elt. * before is the item "before me" or * the item which i am to follow * i.e. i am the item after BEFORE */ DATA_PTR LL_InsertAfter(LINKED_LIST *ll, DATA_PTR data, DATA_PTR before) { #ifdef LL_DEBUG if (!ll || !data) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_InsertAfter()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { DATA_PTR after; if (before) { #ifdef LL_DEBUG /* Verify that this item is on the list */ for (after = ll->head.data; after; after = NextP(ll, after)) { if (after == before) break; } if (!after) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_InsertAfter()"); } return(NULL); } #endif after = NextP(ll, before); } else { /* if !before */ after = ll->head.data; } LLMacro_IntrPlaceBetween(ll, data, before, after); } else { /* Container */ LL_CONTAINER *after_cont, *before_cont, *cont; cont = New(LL_CONTAINER); if (!cont) { if (LL_Handler) { (LL_Handler)(ll, LL_MemoryErr, "LL_InsertAfter()"); } return(NULL); } if (before) { LLMacro_GetContainer(ll, before_cont, before); #ifdef LL_DEBUG if (!before_cont) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_InsertAfter()"); } Delete(cont); return(NULL); } #endif after_cont = before_cont->next; } else { after_cont = ll->head.cont; before_cont = NULL; } cont->data = data; LLMacro_ContPlaceBetween(ll, cont, before_cont, after_cont); ll->last = cont; } ll->count++; #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x InsertAfter(0x%.8x, 0x%.8x) count = %d\n", ll, data, before, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(data); } /*----------------------------------------------------------- * Name: LL_InsertBefore() * Created: Fri Sep 2 03:14:46 1994 * Author: Jonathan DeKock * DESCR: inserts an element before another element * after is the element which will be "after" me. */ DATA_PTR LL_InsertBefore(LINKED_LIST *ll, DATA_PTR data, DATA_PTR after) { #ifdef LL_DEBUG if (!ll || !data) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_InsertBefore()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { DATA_PTR before; if (after) { #ifdef LL_DEBUG /* Verify that this item is on the list */ for (before = ll->head.data; before; before = NextP(ll, before)) { if (before == after) break; if (before == ll->tail.data) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_InsertBefore()"); } return(NULL); } } #endif before = PrevP(ll, after); } else { before = ll->tail.data; } LLMacro_IntrPlaceBetween(ll, data, before, after); } else { LL_CONTAINER *before_cont, *after_cont, *cont; cont = New(LL_CONTAINER); if (!cont) { if (LL_Handler) { (LL_Handler)(ll, LL_MemoryErr, "LL_InsertAfter()"); } return(NULL); } if (after) { LLMacro_GetContainer(ll, after_cont, after); #ifdef LL_DEBUG if (!after_cont) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_InsertAfter()"); } Delete(cont); return(NULL); } #endif before_cont = after_cont->prev; } else { before_cont = ll->tail.cont; after_cont = NULL; } cont->data = data; LLMacro_ContPlaceBetween(ll, cont, before_cont, after_cont); ll->last = cont; } ll->count++; #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x InsertBefore(0x%.8x, 0x%.8x) count = %d\n", ll, data, after, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(data); } /*----------------------------------------------------------- * Name: LL_RemoveFn() * Created: Fri Sep 2 03:43:24 1994 * Author: Jonathan DeKock * DESCR: removes an item from the list, * destroying it with function fn */ void LL_RemoveFn(LINKED_LIST *ll, DATA_PTR data, LL_DestroyProc destroy) { #ifdef LL_DEBUG if (!ll || !data) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Remove()"); } return; } #endif if (ll->attr & LL_Intrusive) { #ifdef LL_DEBUG DATA_PTR tmp; /* Verify that this item is on the list */ for (tmp = ll->head.data; tmp; tmp = NextP(ll, tmp)) { if (tmp == data) break; if (tmp == ll->tail.data) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_Remove()"); } return; } } #endif if (NextP(ll, data)) PrevP(ll, NextP(ll, data)) = PrevP(ll, data); else ll->tail.data = PrevP(ll, data); if (PrevP(ll, data)) NextP(ll, PrevP(ll, data)) = NextP(ll, data); else ll->head.data = NextP(ll, data); #ifdef LL_DEBUG NextP(ll, data) = NULL; PrevP(ll, data) = NULL; #endif } else { /* Container */ LL_CONTAINER *cont; LLMacro_GetContainer(ll, cont, data); if (!cont) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_Remove()"); } return; } if (ll->last == cont) { /* last can no longer point to this item */ if (cont->prev) ll->last = cont->prev; else ll->last = cont->next; } if (cont->next) cont->next->prev = cont->prev; else ll->tail.cont = cont->prev; if (cont->prev) cont->prev->next = cont->next; else ll->head.cont = cont->next; #ifdef LL_DEBUG cont->next = NULL; cont->prev = NULL; cont->data = NULL; #endif Delete(cont); } ll->count--; if (destroy) { (destroy)(data); } #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x Remove(x%.8x, 0x%.8x) count = %d\n", ll, data, destroy, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } /*----------------------------------------------------------- * Name: LList_GetHead() * Created: Fri Sep 2 19:45:56 1994 * Author: Jonathan DeKock * DESCR: returns the head of a linked list */ DATA_PTR LList_GetHead(LINKED_LIST *ll) { DATA_PTR ret; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_GetHead()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { ret = ll->head.data; } else { ll->last = ll->head.cont; if (ll->head.cont) ret = ll->head.cont->data; else ret = NULL; } #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x GetHead() = 0x%.8x\n", ll, ret); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(ret); } /*----------------------------------------------------------- * Name: LListGetTail() * Created: Fri Sep 2 20:11:46 1994 * Author: Jonathan DeKock * DESCR: gets the tail of a linked list */ DATA_PTR LList_GetTail(LINKED_LIST *ll) { DATA_PTR ret; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_GetTail()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { ret = ll->tail.data; } else { ll->last = ll->tail.cont; if (ll->tail.cont) ret = ll->tail.cont->data; else ret = NULL; } #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x GetTail() = 0x%.8x\n", ll, ret); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(ret); } /*----------------------------------------------------------- * Name: LList_GetNext() * Created: Fri Sep 2 20:22:52 1994 * Author: Jonathan DeKock * DESCR: gets the next item on a list */ DATA_PTR LList_GetNext(LINKED_LIST *ll, DATA_PTR data) { DATA_PTR ret; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_GetNext()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { if (data) { #ifdef LL_DEBUG DATA_PTR tmp; /* Verify that this item is on the list */ for (tmp = ll->head.data; tmp; tmp = NextP(ll, tmp)) { if (tmp == data) break; if (tmp == ll->tail.data) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_GetNext()"); } return(NULL); } } #endif ret = NextP(ll, data); } else { ret = ll->head.data; } } else { LL_CONTAINER *cont = NULL; if (data) { LLMacro_GetContainer(ll, cont, data); #ifdef LL_DEBUG if (!cont) { /* DATA is not on the LIST */ if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_GetNext()"); } return(NULL); } #endif ll->last = cont->next; if (cont->next) ret = cont->next->data; else ret = NULL; } else { ll->last = ll->head.cont; if (ll->head.cont) ret = ll->head.cont->data; else ret = NULL; } } #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x GetNext(0x%.8x) = 0x%.8x\n", ll, data, ret); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(ret); } /*----------------------------------------------------------- * Name: LList_GetPrev() * Created: Fri Sep 2 23:35:25 1994 * Author: Jonathan DeKock * DESCR: returns the previous item */ DATA_PTR LList_GetPrev(LINKED_LIST *ll, DATA_PTR data) { DATA_PTR ret; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_GetPrev()"); } return(NULL); } #endif if (ll->attr & LL_Intrusive) { if (data) { #ifdef LL_DEBUG DATA_PTR tmp; /* Verify that this item is on the list */ for (tmp = ll->head.data; tmp; tmp = NextP(ll, tmp)) { if (tmp == data) break; if (tmp == ll->tail.data) { if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_GetPrev()"); } return(NULL); } } #endif ret = PrevP(ll, data); } else { ret = ll->tail.data; } } else { LL_CONTAINER *cont = NULL; if (data) { LLMacro_GetContainer(ll, cont, data); #ifdef LL_DEBUG if (!cont) { /* DATA is not on the LIST */ if (LL_Handler) { (LL_Handler)(ll, LL_NoMember, "LL_GetPrev()"); } return(NULL); } #endif ll->last = cont->prev; if (cont->prev) ret = cont->prev->data; else ret = NULL; } else { ll->last = ll->tail.cont; if (ll->tail.cont) ret = ll->tail.cont->data; else ret = NULL; } } #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x GetPrev(x%.8x) = 0x%.8x\n", ll, data, ret); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(ret); } /*----------------------------------------------------------- * Name: LL_Sort() * Created: Sun Sep 4 01:22:27 1994 * Author: Jonathan DeKock * DESCR: sorts a linked list */ void LL_Sort(LINKED_LIST *ll, ...) { LL_CompareProc compare; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Sort()"); } return; } #endif compare = ll->comp_fn; if (!compare) { va_list ap; va_start(ap, ll); compare = va_arg(ap, LL_CompareProc); va_end(ap); } #ifdef LL_DEBUG if (!compare) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Sort()"); } return; } #endif LL_SortFn(ll, compare); #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } /*----------------------------------------------------------- * Name: LL_SortFn() * Created: Sun Sep 4 01:38:01 1994 * Author: Jonathan DeKock * DESCR: sorts by comparison funciton given */ void LL_SortFn(LINKED_LIST *ll, LL_CompareProc compare) { LL_SortProc sort = LL_SortFunction; #ifdef LL_DEBUG if (!ll || !compare) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Sort()"); } return; } if ((LL_SortFunction == (LL_SortProc)LL_Sort) || (LL_SortFunction == (LL_SortProc)LL_SortFn)) { if (LL_Handler) { (LL_Handler)(ll, LL_BadOperation, "LL_Sort()"); } sort = (LL_SortProc)LL_BubbleSort; } #endif #ifdef notdef if (!sort) { if ((ll->attr & LL_AutoSort) || (ll->count < 30)) { sort = (LL_SortProc)LL_BubbleSort; } else if (ll->count < 100) { sort = (LL_SortProc)LL_QuickSort; } else { sort = (LL_SortProc)LL_MergeSort; } } #else /* I can't beleive the other codes -- masaki */ /* Indeed, they have some bugs. I won't fix them */ /* I just fixed some part of bubble sort */ sort = (LL_SortProc)LL_BubbleSort; #endif /* Perform the actual sort */ (sort)(ll, compare); #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x Sort(0x%.8x) complete\n", ll, compare); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } /*----------------------------------------------------------- * Name: LL_BubbleSort() * Created: Sun Sep 4 01:48:33 1994 * Author: Jonathan DeKock * DESCR: bubble sorts a linked list */ void LL_BubbleSort(LINKED_LIST *ll, LL_CompareProc compare) { #ifdef LL_DEBUG if (!ll || !compare) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_BubbleSort()"); } return; } #endif if (ll->attr & LL_Intrusive) { #ifdef notdef DATA_PTR data, bubble; for (data = NextP(ll, ll->head.data); data; data = NextP(ll, data)) { for (bubble = PrevP(ll, data); bubble; bubble = PrevP(ll, bubble)) { if (((compare)(bubble, data)) < 0) break; } if (bubble && bubble != PrevP(ll, data)) { /* it has moved */ /* unlink it */ if (NextP(ll, data)) PrevP(ll, NextP(ll, data)) = PrevP(ll, data); else ll->tail.data = PrevP(ll, data); if (PrevP(ll, data)) NextP(ll, PrevP(ll, data)) = NextP(ll, data); else ll->head.data = NextP(ll, data); /* re-link it */ if (bubble) { LLMacro_IntrPlaceBetween(ll, data, bubble, NextP(ll, bubble)); } else { LLMacro_IntrPlaceBetween(ll, data, bubble, ll->head.data); } } } #else /* The above code is incorrect. Should not be used. -- masaki */ abort(); #endif } else { /* container */ LL_CONTAINER *bubble, *cont; DATA_PTR data; #ifdef notdef for (cont = ll->head.cont->next; cont; cont = cont->next) { for (bubble = cont->prev; bubble; bubble = bubble->prev) { if (((compare)(bubble->data, cont->data)) < 0) break; } if (bubble && bubble != cont->prev) { /* it has moved */ /* switch the data pointers around */ data = bubble->data; bubble->data = cont->data; cont->data = data; } } #else /* I can't imagine what the above code intended to -- masaki */ for (cont = ll->head.cont; cont; cont = cont->next) { for (bubble = ll->tail.cont; bubble != cont; bubble = bubble->prev) { if (((compare)(bubble->prev->data, bubble->data)) > 0) { data = bubble->data; bubble->data = bubble->prev->data; bubble->prev->data = data; } } } #endif } #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x BubbleSort(0x%.8x) complete\n", ll, compare); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } #ifdef notdef /* Masaki says this is bad code, ifdef out -ljb */ /*----------------------------------------------------------- * Name: LL_QuickSort() * Created: Sun Sep 4 02:18:00 1994 * Author: Jonathan DeKock * DESCR: quick sorts an linked list */ void LL_QuickSort(LINKED_LIST *ll, LL_CompareProc compare) { DATA_PTR *array = NULL; #ifdef LL_DEBUG if (!ll || !compare) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_QuickSort()"); } return; } #endif if (ll->count <= 1) return; /* nothing to sort */ /* Create a big enough array */ if (!(LL_SortArraySize)) { array = NewArray(DATA_PTR, ll->count); if (array) { LL_SortArraySize = ll->count; LL_SortArray = array; } } else if (LL_SortArraySize < ll->count) { array = ReallocateArray(LL_SortArray, DATA_PTR, ll->count); if (array) { LL_SortArraySize = ll->count; LL_SortArray = array; } else { Delete(LL_SortArray); /* no memory, get rid of this */ LL_SortArray = NULL; LL_SortArraySize = 0; } } /* Make sure we didn't have a memory error */ if (!LL_SortArray) { LL_BubbleSort(ll, compare); return; } /* Actual array conversion, sort, and re-conversion */ LL_ToArray(ll, LL_SortArray, NULL); ARRAY_QuickSort(LL_SortArray, ll->count, (DATA_PTR)compare); LL_FromArray(ll, LL_SortArray, ll->count); #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x QuickSort(0x%.8x) complete\n", ll, compare); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } /*----------------------------------------------------------- * Name: LL_MergeSort() * Created: Sun Sep 4 02:19:12 1994 * Author: Jonathan DeKock * DESCR: merge sorts an array */ void LL_MergeSort(LINKED_LIST *ll, LL_CompareProc compare) { DATA_PTR *array = NULL; #ifdef LL_DEBUG if (!ll || !compare) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_MergeSort()"); } return; } #endif if (!ll->count) return; /* nothing to sort */ /* Create a big enough array */ if (!(LL_SortArraySize)) { array = NewArray(DATA_PTR, ll->count); if (array) { LL_SortArraySize = ll->count; LL_SortArray = array; } } else if (LL_SortArraySize < ll->count) { array = ReallocateArray(LL_SortArray, DATA_PTR, ll->count); if (array) { LL_SortArraySize = ll->count; LL_SortArray = array; } else { Delete(LL_SortArray); /* no memory, get rid of this */ LL_SortArray = NULL; LL_SortArraySize = 0; } } /* Make sure we didn't have a memory error */ if (!LL_SortArray) { LL_BubbleSort(ll, compare); return; } /* Actual conversion, sort, and re-conversion */ LL_ToArray(ll, LL_SortArray, NULL); ARRAY_MergeSort(LL_SortArray, ll->count, (DATA_PTR)compare); LL_FromArray(ll, LL_SortArray, ll->count); #ifdef LL_DEBUG if (ll->attr & LL_ReportChange) { printf("LINKED LIST: 0x%.8x MergeSort(0x%.8x) complete\n", ll, compare); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } #endif #ifdef _LL_INTERNAL_DEBUG /*----------------------------------------------------------- * Name: LL_Process() * Created: Sun Sep 4 03:50:17 1994 * Author: Jonathan DeKock * DESCR: runs function on each item of the list */ void LL_Process(LINKED_LIST *ll, LL_ProcessProc fn) { #ifdef LL_DEBUG if (!ll || !fn) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_Process()"); } return; } if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x Process(0x%.8x) started\n", ll, fn); } #endif if (ll->attr & LL_Intrusive) { DATA_PTR data; for (data = ll->head.data; data; data = NextP(ll, data)) { (fn)(data); } } else { LL_CONTAINER *cont; for (cont = ll->head.cont; cont; cont = cont->next) { (fn)(cont->data); } } #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x Process(0x%.8x) complete\n", ll, fn); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } /*----------------------------------------------------------- * Name: LL_ProcessPlus() * Created: Sun Sep 4 03:55:50 1994 * Author: Jonathan DeKock * DESCR: funs with across every item of list */ void LL_ProcessPlus(LINKED_LIST *ll, LL_ProcessPlusProc fn, DATA_PTR arg2) { #ifdef LL_DEBUG if (!ll || !fn) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_ProcessPlus()"); } return; } if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x ProcessPlus(0x%.8x, 0x%.8x) started\n", ll, fn, arg2); } #endif if (ll->attr & LL_Intrusive) { DATA_PTR data; for (data = ll->head.data; data; data = NextP(ll, data)) { (fn)(data, arg2); } } else { LL_CONTAINER *cont; for (cont = ll->head.cont; cont; cont = cont->next) { (fn)(cont->data, arg2); } } #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x ProcessPlus(0x%.8x, 0x%.8x) complete\n", ll, fn, arg2); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif } #endif /* _LL_INTERNAL_DEBUG */ #ifdef notdef /* used by quicksort code, currently not used -ljb */ /*----------------------------------------------------------- * Name: LL_ToArray() * Created: Sun Sep 4 03:58:52 1994 * Author: Jonathan DeKock * DESCR: converts a linked list to an array */ DATA_PTR *LL_ToArray(LINKED_LIST *ll, DATA_PTR *array, unsigned *size) { u_int i; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_ToArray()"); } return(NULL); } #endif if (!array) { array = NewArray(DATA_PTR, ll->count); if (!array) { if (LL_Handler) { (LL_Handler)(ll, LL_MemoryErr, "LL_ToArray()"); } return(NULL); } } if (ll->attr & LL_Intrusive) { DATA_PTR data; for (i = 0, data = ll->head.data; i < ll->count; data = NextP(ll, data), i++) { array[i] = data; } } else { LL_CONTAINER *cont; for (i = 0, cont = ll->head.cont; i < ll->count; cont = cont->next) { array[i] = cont->data; } } if (size) *size = ll->count; #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x ToArray(0x%.8x, %d) complete\n", ll, array, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(array); } /*----------------------------------------------------------- * Name: LL_FromArray() * Created: Sun Sep 4 04:10:39 1994 * Author: Jonathan DeKock * DESCR: converts an array to a linked list */ LINKED_LIST *LL_FromArray(LINKED_LIST *ll, DATA_PTR *array, unsigned size) { u_int i; #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_FromArray()"); } return(NULL); } #endif if (!ll) ll = LL_Create(0); if (ll->attr & LL_Intrusive) { if (size > 0) { ll->head.data = array[0]; ll->tail.data = array[size-1]; } if (ll->head.data) { PrevP(ll, ll->head.data) = NULL; NextP(ll, ll->head.data) = (size > 1) ? array[1] : NULL; } if (ll->tail.data) { NextP(ll, ll->tail.data) = NULL; PrevP(ll, ll->tail.data) = (size > 1) ? array[size-2] : NULL; } for (i = 1; i < size-1; i++) { NextP(ll, array[i]) = array[i+1]; PrevP(ll, array[i]) = array[i-1]; } } else if (size && (ll->count == size)) { LL_CONTAINER *cont; for (cont = ll->head.cont, i=0; i < size; cont = cont->next, i++) cont->data = array[i]; } else { LL_ClearFn(ll, NULL); ll->count = 0; ll->head.cont = NULL; ll->tail.cont = NULL; for (i = 0; i < size; i++) { LL_Append(ll, array[i]); } } ll->count = size; #ifdef LL_DEBUG if (ll->attr & LL_ReportAccess) { printf("LINKED LIST: 0x%.8x FromArray(0x%.8x, %d) complete\n", ll, array, ll->count); } #endif #ifdef _LL_INTERNAL_DEBUG LL_Verify(ll); #endif return(ll); } #endif /*----------------------------------------------------------- * Name: LL_SetHandler() * Created: Sun Sep 4 06:33:10 1994 * Author: Jonathan DeKock * DESCR: sets the error handler to */ LL_ErrorProc LL_SetHandler(LL_ErrorProc fn, char *name) { LL_ErrorProc tmp= LL_Handler; LL_Handler = fn; #ifdef LL_DEBUG if (name) printf("LINKED LIST: Handler changed to %s() = 0x%.8x\n", name, fn); else printf("LINKED LIST: Handler changed to 0x%.8x\n", fn); #endif return(tmp); } #ifdef notdef /* masaki says only bubblesort works */ /*----------------------------------------------------------- * Name: LL_SetSorter() * Created: Wed Sep 14 04:24:59 1994 * Author: Jonathan DeKock * DESCR: sets the global sorter function */ LL_SortProc LL_SetSorter(LL_SortProc fn, char *name) { LL_SortProc tmp = LL_SortFunction; LL_SortFunction = fn; #ifdef LL_DEBUG if (name) printf("LINKED LIST: Sorter changed to %s() = 0x%.8x\n", name, fn); else printf("LINKED LIST: Sorter changed to 0x%.8x\n", fn); #endif return(tmp); } #endif /*----------------------------------------------------------- * Name: LL_DefaultHandler() * Created: Tue Aug 30 19:37:58 1994 * Author: Jonathan DeKock * DESCR: default error handler */ void LL_DefaultHandler(LINKED_LIST *ll, enum LL_ERROR num, char *name) { #ifdef LL_DEBUG FILE *out = stdout; #else FILE *out = stderr; #endif fflush(stdout); fflush(stderr); fprintf(out, "LINKED LIST: 0x%.8x Error in function %s: \"%s\"\n", (u_int)ll, name, LL_errlist[num]); fflush(out); } /*----------------------------------------------------------- * Name: LL_CallHandler() * Created: Sat Sep 3 00:18:54 1994 * Author: Jonathan DeKock * DESCR: calls the error handler * used as interface to get to the * _static_ "global" variable */ DATA_PTR LL_CallHandler(LINKED_LIST *ll, enum LL_ERROR num, char *name) { if (LL_Handler) { (LL_Handler)(ll, num, name); } return(NULL); } #ifdef _LL_INTERNAL_DEBUG /*----------------------------------------------------------- * Name: LL_Verify() * Created: Sun Sep 4 06:53:54 1994 * Author: Jonathan DeKock * DESCR: verifies a list */ int LL_Verify(LINKED_LIST *ll) { int ret = 1; u_int count = 0; int last_found = 0; DATA_PTR data; LL_CONTAINER *cont; /* Are the attributes correct???? */ /* if Intrusive, must have diff offsets */ if ((ll->attr & LL_Intrusive) && (ll->next_offset == ll->prev_offset)) { if (LL_Handler) { (LL_Handler)(ll, LL_BadAttributes, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found (prev_offset == next_offset) = %d\n", ll, ll->prev_offset); #endif } /* if Auto-sorted, must have comparison function */ if ((ll->attr & LL_AutoSort) && (ll->comp_fn == NULL)) { if (LL_Handler) { (LL_Handler)(ll, LL_BadAttributes, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found auto-sort, but no comp_fn\n", ll); #endif } /* If the list is empty, are the pointers NULL ? */ if (!ll->count) { if ((ll->head.data) || (ll->tail.data) || (ll->last)) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found non-empty head or tail on empty list\n", ll); #endif } } else { /* list not empty */ if (!(ll->head.data) || !(ll->tail.data)) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found empty head or tail on non-empty list\n", ll); #endif } if (ll->attr & LL_Intrusive) { if (NextP(ll, ll->tail.data) != NULL) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found invalid next pointer on tail\n", ll); #endif } if (PrevP(ll, ll->head.data) != NULL) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found invalid prev pointer on head\n", ll); #endif } for (data = ll->head.data; data; data = NextP(ll, data)) { count++; /* Check that data->next->prev == data */ if ((!(NextP(ll, data))) && (data != ll->tail.data)) { /* list quit to soon */ if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found a NULL next pointer mid-list\n", ll); #endif } else if ((NextP(ll, data)) && (PrevP(ll, NextP(ll, data)) != data)) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found data->next->prev != data\n", ll); #endif } if (ll->attr & LL_AutoSort) { if ((ll->comp_fn)(data, NextP(ll, data)) > 0) { /* Not Sorted */ if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found an auto-sorted list un-sorted\n", ll); #endif } } } if (count != ll->count) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found the count incorrect\n", ll); #endif } } else { /* container */ if (ll->tail.cont->next != NULL) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found invalid next pointer on tail\n", ll); #endif } if (ll->head.cont->prev != NULL) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found invalid prev pointer on head\n", ll); #endif } if (!ll->last) last_found = 1; for (cont = ll->head.cont; cont; cont = cont->next) { count++; if (!cont->data) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found a container with NULL data pointer\n", ll); #endif } /* Check that cont->next->prev == cont */ if ((!cont->next) && (cont != ll->tail.cont)) { /* list quit to soon */ if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found a NULL next pointer mid-list\n", ll); #endif } else if (cont->next && (cont->next->prev != cont)) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found cont->next->prev != cont\n", ll); #endif } if (ll->attr & LL_AutoSort) { if (cont->next && (ll->comp_fn)(cont->data, cont->next->data) > 0) { /* Not Sorted */ if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found an auto-sorted list un-sorted\n", ll); #endif } } if (ll->last == cont) last_found = 1; } if (count != ll->count) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found the count incorrect\n", ll); #endif } if (!last_found) { if (LL_Handler) { (LL_Handler)(ll, LL_ListCorrupted, "LL_Verify()"); } ret = 0; #ifdef _LL_INTERNAL_DEBUG printf("LINKED LIST: 0x%.8x Verify() found an invalid last argument\n", ll); #endif } } } #ifdef _LL_INTERNAL_DEBUG if (!ret) printf("LINKED LIST: 0x%.8x is NOT valid\n", ll); #endif return(ret); } /*----------------------------------------------------------- * Name: LL_Print() * Created: Sun Sep 4 08:00:05 1994 * Author: Jonathan DeKock * DESCR: verifies and prints a list */ void LL_Print(LINKED_LIST *ll, LL_ProcessProc print) { #ifdef LL_DEBUG if (!ll) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_PrintListDataToFile()"); } return; } #endif LL_Verify(ll); if (!print) print = (LL_ProcessProc) LL_DefaultPrinter; printf("LINKED LIST: 0x%.8x Printing..\n", (u_int)ll); LLMacro_PrintAllAttr(ll); LL_Process(ll, print); } /*----------------------------------------------------------- * Name: LL_DefaultPrinter * Created: Wed Sep 14 04:31:58 1994 * Author: Jonathan DeKock * DESCR: default printing funciton */ void LL_DefaultPrinter(DATA_PTR data) { printf("0x%.8x\n", (u_int)data); } #endif /* _LL_INTERNAL_DEBUG */ /*----------------------------------------------------------- * Name: LL_GetContainer() * Created: Thu Sep 15 19:17:22 1994 * Author: Jonathan DeKock * DESCR: retrieves the container for data */ LL_CONTAINER *LL_GetContainer(LINKED_LIST *ll, DATA_PTR data) { LL_CONTAINER *cont; #ifdef LL_DEBUG if (!ll || !data) { if (LL_Handler) { (LL_Handler)(ll, LL_BadArgument, "LL_GetContainer()"); } return(NULL); } if (ll->attr & LL_Intrusive) { if (LL_Handler) { (LL_Handler)(ll, LL_BadOperation, "LL_GetContainer()"); } return(NULL); } #endif LLMacro_GetContainer(ll, cont, data); return(cont); }