* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
- *
+ *
* http://www.apache.org/licenses/LICENSE-2.0
- *
+ *
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
- File: GenLinkedList.c
+ File: GenLinkedList.c
- Contains: implementation of generic linked lists.
+ Contains: implementation of generic linked lists.
- Version: 1.0
- Tabs: 4 spaces
+ Version: 1.0
+ Tabs: 4 spaces
*/
#include "GenLinkedList.h"
// Return the link pointer contained within element e at offset o.
-#define GETLINK( e, o) ( *(void**)((char*) (e) + (o)) )
+#define GETLINK( e, o) ( *(void**)((char*) (e) + (o)) )
// Assign the link pointer l to element e at offset o.
-#define ASSIGNLINK( e, l, o) ( *((void**)((char*) (e) + (o))) = (l))
+#define ASSIGNLINK( e, l, o) ( *((void**)((char*) (e) + (o))) = (l))
// GenLinkedList /////////////////////////////////////////////////////////////
-void InitLinkedList( GenLinkedList *pList, size_t linkOffset)
+void InitLinkedList( GenLinkedList *pList, size_t linkOffset)
/* Initialize the block of memory pointed to by pList as a linked list. */
{
- pList->Head = NULL;
- pList->Tail = NULL;
- pList->LinkOffset = linkOffset;
+ pList->Head = NULL;
+ pList->Tail = NULL;
+ pList->LinkOffset = linkOffset;
}
-void AddToTail( GenLinkedList *pList, void *elem)
+void AddToTail( GenLinkedList *pList, void *elem)
/* Add a linked list element to the tail of the list. */
{
- if ( pList->Tail) {
- ASSIGNLINK( pList->Tail, elem, pList->LinkOffset);
- } else
- pList->Head = elem;
- ASSIGNLINK( elem, NULL, pList->LinkOffset);
+ if ( pList->Tail) {
+ ASSIGNLINK( pList->Tail, elem, pList->LinkOffset);
+ } else
+ pList->Head = elem;
+ ASSIGNLINK( elem, NULL, pList->LinkOffset);
- pList->Tail = elem;
+ pList->Tail = elem;
}
-void AddToHead( GenLinkedList *pList, void *elem)
+void AddToHead( GenLinkedList *pList, void *elem)
/* Add a linked list element to the head of the list. */
{
- ASSIGNLINK( elem, pList->Head, pList->LinkOffset);
- if ( pList->Tail == NULL)
- pList->Tail = elem;
+ ASSIGNLINK( elem, pList->Head, pList->LinkOffset);
+ if ( pList->Tail == NULL)
+ pList->Tail = elem;
- pList->Head = elem;
+ pList->Head = elem;
}
-int RemoveFromList( GenLinkedList *pList, void *elem)
+int RemoveFromList( GenLinkedList *pList, void *elem)
/* Remove a linked list element from the list. Return 0 if it was not found. */
/* If the element is removed, its link will be set to NULL. */
{
-void *iElem, *lastElem;
-
- for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) {
- if ( iElem == elem) {
- if ( lastElem) { // somewhere past the head
- ASSIGNLINK( lastElem, GETLINK( elem, pList->LinkOffset), pList->LinkOffset);
- } else { // at the head
- pList->Head = GETLINK( elem, pList->LinkOffset);
- }
- if ( pList->Tail == elem)
- pList->Tail = lastElem ? lastElem : NULL;
- ASSIGNLINK( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug.
- return 1;
- }
- lastElem = iElem;
- }
-
- return 0;
+ void *iElem, *lastElem;
+
+ for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) {
+ if ( iElem == elem) {
+ if ( lastElem) { // somewhere past the head
+ ASSIGNLINK( lastElem, GETLINK( elem, pList->LinkOffset), pList->LinkOffset);
+ } else { // at the head
+ pList->Head = GETLINK( elem, pList->LinkOffset);
+ }
+ if ( pList->Tail == elem)
+ pList->Tail = lastElem ? lastElem : NULL;
+ ASSIGNLINK( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug.
+ return 1;
+ }
+ lastElem = iElem;
+ }
+
+ return 0;
}
-int ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem)
+int ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem)
/* Replace an element in the list with a new element, in the same position. */
{
-void *iElem, *lastElem;
-
- if ( elemInList == NULL || newElem == NULL)
- return 0;
-
- for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset))
- {
- if ( iElem == elemInList)
- {
- ASSIGNLINK( newElem, GETLINK( elemInList, pList->LinkOffset), pList->LinkOffset);
- if ( lastElem) // somewhere past the head
- {
- ASSIGNLINK( lastElem, newElem, pList->LinkOffset);
- }
- else // at the head
- {
- pList->Head = newElem;
- }
- if ( pList->Tail == elemInList)
- pList->Tail = newElem;
- return 1;
- }
- lastElem = iElem;
- }
-
- return 0;
+ void *iElem, *lastElem;
+
+ if ( elemInList == NULL || newElem == NULL)
+ return 0;
+
+ for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset))
+ {
+ if ( iElem == elemInList)
+ {
+ ASSIGNLINK( newElem, GETLINK( elemInList, pList->LinkOffset), pList->LinkOffset);
+ if ( lastElem) // somewhere past the head
+ {
+ ASSIGNLINK( lastElem, newElem, pList->LinkOffset);
+ }
+ else // at the head
+ {
+ pList->Head = newElem;
+ }
+ if ( pList->Tail == elemInList)
+ pList->Tail = newElem;
+ return 1;
+ }
+ lastElem = iElem;
+ }
+
+ return 0;
}
// GenDoubleLinkedList /////////////////////////////////////////////////////////
-void InitDoubleLinkedList( GenDoubleLinkedList *pList, size_t fwdLinkOffset,
- size_t backLinkOffset)
+void InitDoubleLinkedList( GenDoubleLinkedList *pList, size_t fwdLinkOffset,
+ size_t backLinkOffset)
/* Initialize the block of memory pointed to by pList as a double linked list. */
{
- pList->Head = NULL;
- pList->Tail = NULL;
- pList->FwdLinkOffset = fwdLinkOffset;
- pList->BackLinkOffset = backLinkOffset;
+ pList->Head = NULL;
+ pList->Tail = NULL;
+ pList->FwdLinkOffset = fwdLinkOffset;
+ pList->BackLinkOffset = backLinkOffset;
}
-void DLLAddToHead( GenDoubleLinkedList *pList, void *elem)
+void DLLAddToHead( GenDoubleLinkedList *pList, void *elem)
/* Add a linked list element to the head of the list. */
{
-void *pNext;
+ void *pNext;
- pNext = pList->Head;
+ pNext = pList->Head;
- // fix up the forward links
- ASSIGNLINK( elem, pList->Head, pList->FwdLinkOffset);
- pList->Head = elem;
+ // fix up the forward links
+ ASSIGNLINK( elem, pList->Head, pList->FwdLinkOffset);
+ pList->Head = elem;
- // fix up the backward links
- if ( pNext) {
- ASSIGNLINK( pNext, elem, pList->BackLinkOffset);
- } else
- pList->Tail = elem;
- ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
+ // fix up the backward links
+ if ( pNext) {
+ ASSIGNLINK( pNext, elem, pList->BackLinkOffset);
+ } else
+ pList->Tail = elem;
+ ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
}
-void DLLRemoveFromList( GenDoubleLinkedList *pList, void *elem)
+void DLLRemoveFromList( GenDoubleLinkedList *pList, void *elem)
/* Remove a linked list element from the list. */
/* When the element is removed, its link will be set to NULL. */
{
-void *pNext, *pPrev;
-
- pNext = GETLINK( elem, pList->FwdLinkOffset);
- pPrev = GETLINK( elem, pList->BackLinkOffset);
-
- // fix up the forward links
- if ( pPrev)
- ASSIGNLINK( pPrev, pNext, pList->FwdLinkOffset);
- else
- pList->Head = pNext;
-
- // fix up the backward links
- if ( pNext)
- ASSIGNLINK( pNext, pPrev, pList->BackLinkOffset);
- else
- pList->Tail = pPrev;
-
- ASSIGNLINK( elem, NULL, pList->FwdLinkOffset);
- ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
+ void *pNext, *pPrev;
+
+ pNext = GETLINK( elem, pList->FwdLinkOffset);
+ pPrev = GETLINK( elem, pList->BackLinkOffset);
+
+ // fix up the forward links
+ if ( pPrev)
+ ASSIGNLINK( pPrev, pNext, pList->FwdLinkOffset);
+ else
+ pList->Head = pNext;
+
+ // fix up the backward links
+ if ( pNext)
+ ASSIGNLINK( pNext, pPrev, pList->BackLinkOffset);
+ else
+ pList->Tail = pPrev;
+
+ ASSIGNLINK( elem, NULL, pList->FwdLinkOffset);
+ ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
}
// GenLinkedOffsetList /////////////////////////////////////////////////////
// Extract the Next offset from element
-#define GETOFFSET( e, o) ( *(size_t*)((char*) (e) + (o)) )
+#define GETOFFSET( e, o) ( *(size_t*)((char*) (e) + (o)) )
-static void AssignOffsetLink( void *elem, void *link, size_t linkOffset);
+static void AssignOffsetLink( void *elem, void *link, size_t linkOffset);
-static void AssignOffsetLink( void *elem, void *link, size_t linkOffset)
+static void AssignOffsetLink( void *elem, void *link, size_t linkOffset)
// Assign link to elem as an offset from elem. Assign 0 to elem if link is NULL.
{
- GETOFFSET( elem, linkOffset) = link ? (size_t) link - (size_t) elem : 0;
+ GETOFFSET( elem, linkOffset) = link ? (size_t) link - (size_t) elem : 0;
}
-void *GetHeadPtr( GenLinkedOffsetList *pList)
+void *GetHeadPtr( GenLinkedOffsetList *pList)
/* Return a pointer to the head element of a list, or NULL if none. */
{
- return pList->Head ? ( (char*) (pList) + pList->Head) : NULL;
+ return pList->Head ? ( (char*) (pList) + pList->Head) : NULL;
}
-void *GetTailPtr( GenLinkedOffsetList *pList)
+void *GetTailPtr( GenLinkedOffsetList *pList)
/* Return a pointer to the tail element of a list, or NULL if none. */
{
- return pList->Tail ? ( (char*) (pList) + pList->Tail) : NULL;
+ return pList->Tail ? ( (char*) (pList) + pList->Tail) : NULL;
}
-void *GetOffsetLink( GenLinkedOffsetList *pList, void *elem)
+void *GetOffsetLink( GenLinkedOffsetList *pList, void *elem)
/* Return the link pointer contained within element e for pList, or NULL if it is 0. */
{
-size_t nextOffset;
+ size_t nextOffset;
- nextOffset = GETOFFSET( elem, pList->LinkOffset);
+ nextOffset = GETOFFSET( elem, pList->LinkOffset);
- return nextOffset ? (char*) elem + nextOffset : NULL;
+ return nextOffset ? (char*) elem + nextOffset : NULL;
}
-void InitLinkedOffsetList( GenLinkedOffsetList *pList, size_t linkOffset)
+void InitLinkedOffsetList( GenLinkedOffsetList *pList, size_t linkOffset)
/* Initialize the block of memory pointed to by pList as a linked list. */
{
- pList->Head = 0;
- pList->Tail = 0;
- pList->LinkOffset = linkOffset;
+ pList->Head = 0;
+ pList->Tail = 0;
+ pList->LinkOffset = linkOffset;
}
-void OffsetAddToTail( GenLinkedOffsetList *pList, void *elem)
+void OffsetAddToTail( GenLinkedOffsetList *pList, void *elem)
/* Add a linked list element to the tail of the list. */
{
- if ( pList->Tail) {
- AssignOffsetLink( GetTailPtr( pList), elem, pList->LinkOffset);
- } else
- pList->Head = (size_t) elem - (size_t) pList;
- AssignOffsetLink( elem, NULL, pList->LinkOffset);
+ if ( pList->Tail) {
+ AssignOffsetLink( GetTailPtr( pList), elem, pList->LinkOffset);
+ } else
+ pList->Head = (size_t) elem - (size_t) pList;
+ AssignOffsetLink( elem, NULL, pList->LinkOffset);
- pList->Tail = (size_t) elem - (size_t) pList;
+ pList->Tail = (size_t) elem - (size_t) pList;
}
-void OffsetAddToHead( GenLinkedOffsetList *pList, void *elem)
+void OffsetAddToHead( GenLinkedOffsetList *pList, void *elem)
/* Add a linked list element to the head of the list. */
{
- AssignOffsetLink( elem, GetHeadPtr( pList), pList->LinkOffset);
- if ( pList->Tail == 0)
- pList->Tail = (size_t) elem - (size_t) pList;
+ AssignOffsetLink( elem, GetHeadPtr( pList), pList->LinkOffset);
+ if ( pList->Tail == 0)
+ pList->Tail = (size_t) elem - (size_t) pList;
- pList->Head = (size_t) elem - (size_t) pList;
+ pList->Head = (size_t) elem - (size_t) pList;
}
-int OffsetRemoveFromList( GenLinkedOffsetList *pList, void *elem)
+int OffsetRemoveFromList( GenLinkedOffsetList *pList, void *elem)
/* Remove a linked list element from the list. Return 0 if it was not found. */
/* If the element is removed, its link will be set to NULL. */
{
-void *iElem, *lastElem;
-
- for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
- iElem = GetOffsetLink( pList, iElem))
- {
- if ( iElem == elem) {
- if ( lastElem) { // somewhere past the head
- AssignOffsetLink( lastElem, GetOffsetLink( pList, elem), pList->LinkOffset);
- } else { // at the head
- iElem = GetOffsetLink( pList, elem);
- pList->Head = iElem ? (size_t) iElem - (size_t) pList : 0;
- }
- if ( GetTailPtr( pList) == elem)
- pList->Tail = lastElem ? (size_t) lastElem - (size_t) pList : 0;
- AssignOffsetLink( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug.
- return 1;
- }
- lastElem = iElem;
- }
-
- return 0;
+ void *iElem, *lastElem;
+
+ for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
+ iElem = GetOffsetLink( pList, iElem))
+ {
+ if ( iElem == elem) {
+ if ( lastElem) { // somewhere past the head
+ AssignOffsetLink( lastElem, GetOffsetLink( pList, elem), pList->LinkOffset);
+ } else { // at the head
+ iElem = GetOffsetLink( pList, elem);
+ pList->Head = iElem ? (size_t) iElem - (size_t) pList : 0;
+ }
+ if ( GetTailPtr( pList) == elem)
+ pList->Tail = lastElem ? (size_t) lastElem - (size_t) pList : 0;
+ AssignOffsetLink( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug.
+ return 1;
+ }
+ lastElem = iElem;
+ }
+
+ return 0;
}
-int OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem)
+int OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem)
/* Replace an element in the list with a new element, in the same position. */
{
-void *iElem, *lastElem;
-
- if ( elemInList == NULL || newElem == NULL)
- return 0;
-
- for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
- iElem = GetOffsetLink( pList, iElem))
- {
- if ( iElem == elemInList)
- {
- AssignOffsetLink( newElem, GetOffsetLink( pList, elemInList), pList->LinkOffset);
- if ( lastElem) // somewhere past the head
- {
- AssignOffsetLink( lastElem, newElem, pList->LinkOffset);
- }
- else // at the head
- {
- pList->Head = (size_t) newElem - (size_t) pList;
- }
- if ( GetTailPtr( pList) == elemInList)
- pList->Tail = (size_t) newElem - (size_t) pList;
- return 1;
- }
- lastElem = iElem;
- }
-
- return 0;
+ void *iElem, *lastElem;
+
+ if ( elemInList == NULL || newElem == NULL)
+ return 0;
+
+ for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
+ iElem = GetOffsetLink( pList, iElem))
+ {
+ if ( iElem == elemInList)
+ {
+ AssignOffsetLink( newElem, GetOffsetLink( pList, elemInList), pList->LinkOffset);
+ if ( lastElem) // somewhere past the head
+ {
+ AssignOffsetLink( lastElem, newElem, pList->LinkOffset);
+ }
+ else // at the head
+ {
+ pList->Head = (size_t) newElem - (size_t) pList;
+ }
+ if ( GetTailPtr( pList) == elemInList)
+ pList->Tail = (size_t) newElem - (size_t) pList;
+ return 1;
+ }
+ lastElem = iElem;
+ }
+
+ return 0;
}
projects / apple / mdnsresponder.git / blobdiff