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

[Romeo]

На 2010 не выйдет, она старенькая слишком, там только крошечные ошмётки 11-го стандарта есть. А вот на 2015-й уже практически полная поддержка С++11. Rvalue ссылки там уже во всю можно применять.

[Absurd]

Кинул буржуинам чтобы поковырялись. Уже есть несколько нареканий.

http://codereview.stackexchange.com/que ... 490#117490

In TSimpleStack::Pop you don't need to check the depth as m_list.Pop() will return null if the stack is empty.

В методе TSimpleStack::Pop проверка глубины не имеет смысла, так как m_list.Pop() все равно вернет null если стек пустой.

The repeated allocations and frees kind of rub me the wrong way. Instead you can add a CSList m_freeList; member and allocate from that

Можно в стек добавить второй список с аллокированными блоками памяти чтобы не аллокировать по 100500 раз, а брать уже готовое.

A destructor to CSList with at least an assert that m_head is empty.

Деструктор в CSList должен делать как минимум assert что m_head - пустой.

CSList should probably disallow copying and moving.

Имеет смысл запретить move и copy присваивание в CSList.

But TSimpleStack should definatley have a copy constructor and assignment operator (plus the move variants) to follow the rule of 3 (5) or disallow them which is saner because it is hard to ensure thread safety when copying/movin

Имеет смысл либо реализовать move и copy присваивание в TSimpleStack либо явно запретить их если это будет мешать многопоточности.

[WinMain]

Кое-что изменил с учётом выше-изложенных рекомендаций.
Остальное уже по мере необходимости...
В любом случае, спасибо всем за полезные рекомендации.

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

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

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

	PSLIST_ENTRY Flush()
	{
		return ::InterlockedFlushSList(&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;
	CSList(const CSList&)
	{
		// запрет на копирование объекта
	}
};

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()
	{
		// удаление элементов стека
		LPDATA_ENTRY lpEntry = NULL;
		while (TRUE) 
		{
			lpEntry = (LPDATA_ENTRY) m_list.Pop();
			if (lpEntry != NULL)
			{
				lpEntry->~DATA_ENTRY();
				_aligned_free(lpEntry);
				continue;
			}
			break;
		}
	}

	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;
		LPDATA_ENTRY lpEntry = (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;
};

[Absurd]

Там же англоязычные люди пишут что в С++ про const лучше не забывать.

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

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

// logically const:
USHORT Depth() const
{
    return ::QueryDepthSList(const_cast<PSLIST_HEADER>(&m_head));
}

PSLIST_ENTRY Flush() const
{
    return ::InterlockedFlushSList(const_cast<PSLIST_HEADER>(&m_head));
}

И вообще писать попроще.

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

BOOL Pop(T& outVal)
{
    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);
            return true;
        }
    }
    return false;
}

[Romeo]

Ну прям вылизали код

Кстати, рекомендация сделать в деструкторе SList assert на то, что список пуст, весьма здравая. Таким образом мы проверим, что пользователь класса подчистил за собой память. Я понимаю, что пользователь класса SList сейчас всего один (класс TSimpleStack) и он в своём деструкторе эту чистку как раз делает. Но если пользователь класса появится ещё один, и там ты забудешь сделать чистку, то assert тебе об этом сразу напомнит при первом запуске.

[WinMain]

Как вариант, можно вообще отказаться от класса CSList, а весь его функционал перенести непосредственно в шаблон стека.
Тогда вопрос "неучтённых" элементов списка отпадает сам собой.
Вот как-то так...

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

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()
	{
		::InitializeSListHead(&m_head);
	}

	~TSimpleStack()
	{
		// удаление элементов стека
		LPDATA_ENTRY lpEntry = NULL;
		while (TRUE) 
		{
			lpEntry = (LPDATA_ENTRY) ::InterlockedPopEntrySList(&m_head);
			if (lpEntry != NULL)
			{
				lpEntry->~DATA_ENTRY();
				_aligned_free(lpEntry);
				continue;
			}
			break;
		}
	}

	USHORT Count() const
	{
		return ::QueryDepthSList(&m_head);
	}

	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)::InterlockedPushEntrySList(&m_head, lpEntry);
	}

	BOOL Pop(T& outVal)
	{
		LPDATA_ENTRY lpEntry = (LPDATA_ENTRY) ::InterlockedPopEntrySList(&m_head);
		if (lpEntry != NULL)
		{
			outVal = lpEntry->Data;
			lpEntry->~DATA_ENTRY();
			_aligned_free(lpEntry);
			return TRUE;
		}
		return FALSE;
	}

private:
	SLIST_HEADER m_head;
	TSimpleStack(const TSimpleStack&)
	{
		// запрет на копирование объекта
	}
};

[Romeo]

Да, как вариант.

Кстати, помимо конструктора копирования, для целостности нужно запретить и оператор присваивания.

Студия 2010, в которой уже есть самые начала поддержки C++11, вроде, уже должна поддерживать вот такой синтаксис:

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

TSimpleStack(const TSimpleStack&) = delete;
TSimpleStack& operator=(const TSimpleStack&) = delete;

[Absurd]

Но вот англоязычные люди проглядели одну значимую вещь:

Метод Count():

a) не позволяет достоверно определить, является ли стек пустым, поскольку если количество элементов кратно 2^16, то он вернет 0. А в наши времена мне иногда кажется что уже и 2^32 это совсем маленькое число.
b) Он имеет сложность O(N).
c) Он (ИМХО) не будет работать в многопоточном варианте, поскольку я не знаю как подобный метод заставить работать в многопоточном варианте не применяя мутексов и используя только атомики.

Так что лучше его убрать от греха подальше, и сделать метод IsEmpty() на базе RtlFirstEntrySList().

[WinMain]

На счёт сложности O(N) - это преувеличение. В структуре SLIST_HEADER есть поле Depth, в котором хранится число элементов списка. А вот число 65536, которое в двухбайтовой переменной обращается в ноль - это действительно нехорошо. Я так подозреваю, что вместимость самого этого списка не превышает 65536 элементов. Это конечно же совсем мало для современных приложений. Видимо такие ограничения как раз и нужны для реализации алгоритма безмьютексной синхронизации, но это всего лишь мои предположения.

[Absurd]

На счёт сложности O(N) - это преувеличение. В структуре SLIST_HEADER есть поле Depth, в котором хранится число элементов списка.

Это плохо. Значит эта переменная тоже обновлается после каждого обращения к списку, и эта операция находится в зависимости от добавления - удаления элементов из списка. Значит, действительно безлокового алгоритма там нет, а есть что-то типа spinlock-а. Тем более что знание размера стека абсолютно бесполезно. Для всех разумных алгоритмов работы со списками значение может иметь лишь то пуст список или же не пуст, для чего достаточно проверить на null голову списка при помощи единственной atomic операции.

А вот число 65536, которое в двухбайтовой переменной обращается в ноль - это действительно нехорошо. Я так подозреваю, что вместимость самого этого списка не превышает 65536 элементов.

Это мало. Стек используется для обхода вершин в графе, и 65536 вершин современный процессор может обойти за доли секунд даже в однопоточном режиме. Сейчас графы очень большие. Сложные фильтры в фотошопе рассматривают целую картинку как граф. Пиксель - вершина, ребра соединяют его со смежными вершинами, разница в цвете - вес ребра. Разумно сложную обработку распараллелить на несколько ядер. Но 65536 - это картинка 255X255, что очень мало.