Односвязный список средствами Windows API

WinMain · 19 янв 2016, 09:49

Всем привет! В последние дни на форуме активно обсуждается тема реализации односвязных списков. Я решил предложить свой вариант использования такого контейнера, частично реализованного функциями Windows API. Применение этих функций может быть полезно в много-поточных приложениях.
Сначала я сделал небольшой класс-обёртку для этих функций...

Код: Выделить всё

class CSList
{
public:
	CSList()
	{
		::InitializeSListHead(&m_head);
	}

	USHORT Depth()
	{
		return ::QueryDepthSList(&m_head);
	}

	PSLIST_ENTRY Flush()
	{
		return ::InterlockedFlushSList(&m_head);
	}

	PSLIST_ENTRY First()
	{
		return ::RtlFirstEntrySList(&m_head);
	}

	PSLIST_ENTRY Push(PSLIST_ENTRY ListEntry)
	{
		return ::InterlockedPushEntrySList(&m_head, ListEntry);
	}

	PSLIST_ENTRY Pop()
	{
		return ::InterlockedPopEntrySList(&m_head);
	}

private:
	SLIST_HEADER m_head;
};

// Documentation...
// https://msdn.microsoft.com/en-us/library/ms684121 - Interlocked Singly Linked Lists

Далее на основе этого класса я сделал простой шаблон стека.
Там же приведён пример его использования...

Код: Выделить всё

#include <iostream>

using namespace std;

template <typename T>
class TSimpleStack
{
public:
	typedef struct DATA_ENTRY : SINGLE_LIST_ENTRY
	{
		T Data;
		DATA_ENTRY(const T& val) : Data(val)	
		{	
		}
	} *LPDATA_ENTRY;

	~TSimpleStack()
	{
		// удаление элементов стека
		while (m_list.Depth() > 0)
		{
			delete static_cast<LPDATA_ENTRY>(m_list.Pop());
		}
	}

	USHORT Count()
	{
		return m_list.Depth();
	}

	LPDATA_ENTRY Push(const T& data)
	{
		LPDATA_ENTRY lpEntry = new DATA_ENTRY(data);
		// Возвращает указатель на предыдущий элемент списка
		return static_cast<LPDATA_ENTRY>(m_list.Push(lpEntry));
	}

	BOOL Pop(T& outVal)
	{
		BOOL bOut = FALSE;
		if (m_list.Depth() > 0)
		{
			LPDATA_ENTRY lpEntry = static_cast<LPDATA_ENTRY>(m_list.Pop());
			if (lpEntry != NULL)
			{
				outVal = lpEntry->Data;
				delete lpEntry;
				bOut = TRUE;
			}
		}
		return bOut;
	}

private:
	CSList m_list;
};

int _tmain(int argc, _TCHAR* argv[])
{
	TSimpleStack<long> sl;
	sl.Push(10);
	sl.Push(20);
	sl.Push(50);
	sl.Push(100);
	sl.Push(500);

	// вывод данных
	long data (0);
	while (sl.Pop(data))
	{
		cout << data << ' ';
	}

	_gettch();

	return 0;
}

Кому интересен будет этот вариант контейнера данных, пишите свои предложения по его доработке и улучшению.
С уважением, ваш WinMain

Absurd · 19 янв 2016, 10:28

Если поставлена глобальная цель использования только чистого как слеза Win32 API вместо С++ Runtime, то почему бы не использовать LocalAlloc или IMalloc вместо new? Там будет небольшой кариес на пару строчек с placement new, но это вполне терпимо.

WinMain · 19 янв 2016, 13:21

Основная идея моего замысла сводилась к тому, чтобы использовать готовое функциональное ядро Windows API, в котором уже реализован механизм взаимосвязей между элементами списка. Мне же оставалось навесить на него свою структуру данных. О "чистоте" Windows API речь изначально не шла. Но если это для кого-то будет актуально, то можно в качестве дополнительного параметра шаблона указать нужный тип аллокатора. А уже в этом аллокаторе будут вызываться соответствующие функции для выделения/удаления памяти.

Absurd · 19 янв 2016, 18:37

Ну вообще интересно. Написание потоково-безопасного стека без применения мьютексов это нетривиальная задача*. Но вот оказывается начиная с WinXP все необходимые функции есть. Это может быть полезно. Хотя возможно что эти функции все равно реализованы через мьютекс.

*: http://www.drdobbs.com/cpp/lock-free-co ... /210600279

Romeo · 19 янв 2016, 19:17

Absurd писал(а):*: http://www.drdobbs.com/cpp/lock-free...rity/210600279

Да, Lock-Free - это подход, действительно дающий хорошее увеличение перфоменса в многопоточных приложениях, в которых потоки очень активно работают с общими ресурсами.

Далее по теме. Почитал я краткое овервью по SLists и был приятно удивлён тому, что в Windows такое есть. В особенности порадовала вот эта часть:

SLists are implemented using a nonblocking algorithm to provide atomic synchronization, increase system performance, and avoid problems such as priority inversion and lock convoys.

Как говорится, век живи - век учись.

Кстати, по поводу кода есть одно нарекание. Меня насторожили вот эти строки, которые фигурируют в ремарках к каждой функции:

All list items must be aligned on a MEMORY_ALLOCATION_ALIGNMENT boundary. Unaligned items can cause unpredictable results. See _aligned_malloc.

Указанный код перестанет работать как только он будет скомпилирован с выравниваем, отличным от MEMORY_ALLOCATION_ALIGNMENT. Я бы всё-таки рекомендовал перейти с new на _aligned_malloc, дабы застраховать себя от этой потенциальной проблемы. В частности, пример использования SLists из MSDN имплементирован именно так. Следует отметить, что в этом примере у нас разобрано создание списка из целых чисел, так что реализация достаточно проста, ведь то, что malloc/free не вызывают конструтор/деструктор, не играет никакой роли, так как конструктор/деструктор для целого числа пустые. Если же мы будем реализовывать список для произвольных типов, то этот факт уже станет критичным. Поэтому на всякий случай напомню, что для того, чтобы отработал конструктор нужно будет вызвать placement new, а чтобы отработал деструктор - придётся его вызвать вручную.

WinMain · 20 янв 2016, 18:06

Переписал шаблон стека с применением нужных функций выделения памяти...

Код: Выделить всё

template <typename T>
class TSimpleStack
{
public:
	typedef struct DATA_ENTRY : SINGLE_LIST_ENTRY
	{
		T Data;
	} *LPDATA_ENTRY;

	~TSimpleStack()
	{
		// удаление элементов стека
		while (m_list.Depth() > 0)
		{
			_aligned_free(m_list.Pop());
		}
	}

	USHORT Count()
	{
		return m_list.Depth();
	}

	LPDATA_ENTRY Push(const T& data)
	{
		LPDATA_ENTRY lpEntry = 
			(LPDATA_ENTRY)_aligned_malloc(sizeof(DATA_ENTRY), MEMORY_ALLOCATION_ALIGNMENT);
		if (lpEntry != NULL)
		{
			lpEntry->Data = data;
		}
		// Возвращает указатель на предыдущий элемент списка 
		return (lpEntry != NULL)? (LPDATA_ENTRY)m_list.Push(lpEntry) : NULL;
	}

	BOOL Pop(T& outVal)
	{
		BOOL bOut = FALSE;
		if (m_list.Depth() > 0)
		{
			LPDATA_ENTRY lpEntry = static_cast<LPDATA_ENTRY>(m_list.Pop());
			if (lpEntry != NULL)
			{
				outVal = lpEntry->Data;
				_aligned_free(lpEntry);
				bOut = TRUE;
			}
		}
		return bOut;
	}

private:
	CSList m_list;
};

Romeo · 20 янв 2016, 22:58

Смотрю, удалил из DATA_ENTRY конструктор. Видимо потому, что не разобрался, как его вызвать, если использовать malloc вместо new?

Я же писал про placement new и ручной вызов деструктора...

Romeo писал(а): Следует отметить, что в этом примере у нас разобрано создание списка из целых чисел, так что реализация достаточно проста, ведь то, что malloc/free не вызывают конструтор/деструктор, не играет никакой роли, так как конструктор/деструктор для целого числа пустые. Если же мы будем реализовывать список для произвольных типов, то этот факт уже станет критичным. Поэтому на всякий случай напомню, что для того, чтобы отработал конструктор нужно будет вызвать placement new, а чтобы отработал деструктор - придётся его вызвать вручную.

У тебя сейчас не вызываются конструктор/деструктор DATA_ENTRY и, как следствие, конструктор/деструктор T. Если T - это не встроенный тип, то это выльется в реальную проблему.

Вот так должно выглядеть создание объекта DATA_ENTRY (при условии, что конструктор ты вернёшь назад):

Код: Выделить всё

        void* lpMemoryBuffer = _aligned_malloc(sizeof(DATA_ENTRY), MEMORY_ALLOCATION_ALIGNMENT)]

А вот так удаление объекта DATA_ENTRY:
[code=cpp]
        LPDATA_ENTRY lpEntry  = (LPDATA_ENTRY)m_list.Pop();
        lpEntry->~DATA_ENTRY();
        _aligned_free(lpEntry);

WinMain · 21 янв 2016, 09:21

Спасибо за поддержку! Вот обновлённый вариант контейнера с использованием конструктора и деструктора ...

Код: Выделить всё

class CSList
{
public:
	CSList()
	{
		::InitializeSListHead(&m_head);
	}

	USHORT Depth()
	{
		return ::QueryDepthSList(&m_head);
	}

	PSLIST_ENTRY Flush()
	{
		return ::InterlockedFlushSList(&m_head);
	}

	PSLIST_ENTRY First()
	{
		return ::RtlFirstEntrySList(&m_head);
	}

	PSLIST_ENTRY Push(PSLIST_ENTRY ListEntry)
	{
		return ::InterlockedPushEntrySList(&m_head, ListEntry);
	}

	PSLIST_ENTRY Pop()
	{
		return ::InterlockedPopEntrySList(&m_head);
	}

private:
	SLIST_HEADER m_head;
};

template <typename T>
class TSimpleStack
{
public:
	typedef struct DATA_ENTRY : SINGLE_LIST_ENTRY
	{
		T Data;
		DATA_ENTRY(const T& val) : Data(val)
		{
			SINGLE_LIST_ENTRY::Next = NULL;
		}
	} *LPDATA_ENTRY;

	~TSimpleStack()
	{
		// удаление элементов стека
		while (m_list.Depth() > 0)
		{
			LPDATA_ENTRY lpEntry = (LPDATA_ENTRY) m_list.Pop();
			if (lpEntry != NULL)
			{
				lpEntry->~DATA_ENTRY();
			}
			_aligned_free(lpEntry);
		}
	}

	USHORT Count()
	{
		return m_list.Depth();
	}

	LPDATA_ENTRY Push(const T& data)
	{
		LPVOID lpMemBuff = _aligned_malloc(sizeof(DATA_ENTRY), MEMORY_ALLOCATION_ALIGNMENT);
		LPDATA_ENTRY lpEntry = new (lpMemBuff) DATA_ENTRY(data);
		// Возвращает указатель на предыдущий элемент списка 
		return (LPDATA_ENTRY)m_list.Push(lpEntry);
	}

	BOOL Pop(T& outVal)
	{
		BOOL bOut = FALSE;
		if (m_list.Depth() > 0)
		{
			LPDATA_ENTRY lpEntry = static_cast<LPDATA_ENTRY>(m_list.Pop());
			if (lpEntry != NULL)
			{
				outVal = lpEntry->Data;
				lpEntry->~DATA_ENTRY();
				_aligned_free(lpEntry);
				bOut = TRUE;
			}
		}
		return bOut;
	}

private:
	CSList m_list;
};

Romeo · 21 янв 2016, 11:10

Всегда рад помочь. Вот теперь всё в порядке.

Кстати, какую студию используешь? Если уже доступна move sematic, то можно заоптимизировать копирование T внутри Push и Pop переведя всё на rvalue reference.

WinMain · 21 янв 2016, 11:45

Именно этот стек я делал на VS 2010. А так ещё использую VS 2012 Professional и VS2015 Community.