How to use Interlocked Singly Linked Lists?

21 12 2008


Well, STL can provide you almost all kind of containers you want. But only one problem exists – they are not thread safe. If multiple threads are accessing the container at once, you have to add synchronization to them, by using mutex or similar ones. Well, the good news is if you need a singly linked list – windows have a built in one which is already synchonized.

singlylinkedlist


First of all you have to declare a structure to hold your data. Keep in mind that the first member should be of type – SLIST_ENTRY. Then only the api’s can work with it. Then you have to initialize the list by calling InitializeSListHead(). You can push and pop elements by calling InterlockedPushEntrySList() and InterlockedPopEntrySList(). And can flush it by calling InterlockedFlushSList(). Check the code snippet below. Its taken from MSDN and modified accordingly.

typedef struct _LIST_DATA
{
    SLIST_ENTRY ItemEntry; // SLIST_ENTRY should be first.
    int Data;               // Your data.
} LIST_DATA, *PLIST_DATA;

int _tmain(int argc, _TCHAR* argv[])
{
    PSLIST_ENTRY FirstEntry, ListEntry;
    SLIST_HEADER ListHead;
    PLIST_DATA pListData = 0;

    // Initialize the list header.
    InitializeSListHead(&ListHead);

    // Insert 10 items into the list.
    ULONG Count;
    for( Count = 0; Count < 10; ++Count )
    {
        // pListData = (PLIST_DATA)malloc(sizeof(*pListData));
        pListData = new LIST_DATA;
        pListData->Data = Count;
        FirstEntry = InterlockedPushEntrySList(&ListHead,
                       &pListData->ItemEntry);
    }

    // Remove 10 items from the list.
    for( Count = 0; Count < 10; ++Count )
    {
        ListEntry = InterlockedPopEntrySList(&ListHead);
        pListData = (PLIST_DATA)( ListEntry );
        cout << "Item : " << pListData->Data << endl;
        // free( pListData );
        delete pListData;
    }

    // Flush the list and verify that the items are gone.
    ListEntry = InterlockedFlushSList(&ListHead);
    FirstEntry = InterlockedPopEntrySList(&ListHead);

    if (FirstEntry != NULL)
    {
        printf("Error: List is not empty.");
    }
}


I think the best name will be Interlocked stack, since its using push and pop and behaves like stack. I can’t find why its named as a singly linked list. What do you think?


Targeted Audience – Beginners.