maciekm maciekm - 1 month ago 14
C++ Question

Using singly linked list when SLIST_ENTRY is not first member of item list

This is code from MSDN (using singly linked list):

typedef struct _PROGRAM_ITEM
{
SLIST_ENTRY ItemEntry;
ULONG Signature;

/* MY DATA */

} PROGRAM_ITEM, *PPROGRAM_ITEM;

int main( )
{
ULONG Count;
PSLIST_ENTRY pFirstEntry, pListEntry;
PSLIST_HEADER pListHead;
PPROGRAM_ITEM pProgramItem;
pListHead = (PSLIST_HEADER)_aligned_malloc(sizeof(SLIST_HEADER),
MEMORY_ALLOCATION_ALIGNMENT);

InitializeSListHead(pListHead);

// Insert 10 items into the list.
for( Count = 1; Count <= 10; Count += 1 )
{
pProgramItem = (PPROGRAM_ITEM)_aligned_malloc(sizeof(PROGRAM_ITEM),
MEMORY_ALLOCATION_ALIGNMENT);
pProgramItem->Signature = Count;
pFirstEntry = InterlockedPushEntrySList(pListHead,
&(pProgramItem->ItemEntry));
}

// Remove 10 items from the list and display the signature.
for( Count = 10; Count >= 1; Count -= 1 )
{
pListEntry = InterlockedPopEntrySList(pListHead);

pProgramItem = (PPROGRAM_ITEM)pListEntry;
printf("Signature is %d\n", pProgramItem->Signature);

_aligned_free(pListEntry);
}

pListEntry = InterlockedFlushSList(pListHead);
pFirstEntry = InterlockedPopEntrySList(pListHead);
if (pFirstEntry != NULL)
{
printf("Error: List is not empty.\n");
return -1;
}

_aligned_free(pListHead);

return 1;
}


It works well under one condition: SLIST_ENTRY must be first member in _PROGRAM_ITEM structure. But what if my _PROGRAM_ITEM should look like:

typedef struct _PROGRAM_ITEM
{
/* MY DATA */

SLIST_ENTRY ItemEntry;
ULONG Signature;

} PROGRAM_ITEM, *PPROGRAM_ITEM;


In this case InterlockedPushEntrySList,InterlockedPopEntrySList etc. dont't work properly.
HOW to deal with this situation?

Answer

It has to be that way because InterlockedPushEntrySList and family take a PSLIST_ENTRY. If ItemEntry is the first item in the list, you effectively have (void*)pProgramItem == (void*)&pProgramItem->ItemEntry. This also means that when you pop the entry off the list, you need only cast the PSLIST_ENTRY back to a PPROGRAM_ITEM.

Having it any other way is difficult, because an SLIST_ENTRY is required to be aligned as per MEMORY_ALLOCATION_ALIGNMENT. You would need any data in your _PROGRAM_ITEM struct that comes before the SLIST_ENTRY to be a multiple of this (or to pad out to this). Not to mention you need to do some pointer arithmetic to get your PPROGRAM_ITEM back from the PSLIST_ENTRY when you pop it off the list.

Is there any specific reason why you'd want your data to come first? It's much simpler to have the SLIST_ENTRY as the first data member.