websocket/biglist.h

#ifndef __BIGLIST_H
#define __BIGLIST_H
// A biglist is a linked list of fifty item arrays.
// If you add more than fifty items, another fifty item node is added.
// If you delete an item, the used property is set to false.
// When you iterate through the list using biglist_iterator, it 
// skips the unused items.
// Concurrency problems are unlikely with this design.
#include "idisposable.h"
template <class T>
class biglist_item
{
	public:
	T item;
	bool used;
};
template <class T>
class biglist
{
	public:
	static const int BIGLIST_SIZE = 50;
	biglist_item<T> items[BIGLIST_SIZE];
	biglist *next;
	biglist_item<T> *operator[](int index)
	{
		biglist *loop;		
		if (index < 0) {
			return nullptr;
		}
		loop = this;
		while (index >= BIGLIST_SIZE) {
			loop = loop->next;
			index -= BIGLIST_SIZE;
			if (loop == nullptr) {
				return nullptr;
			}
		}
		return &loop->items[index];
	}
	biglist()
	{
		int loop;
		next = nullptr;
		for(loop=0;loop<BIGLIST_SIZE;loop++) {
			items[loop].used = false;
		}
	}
	void deleteallitems() { // This should only be called if T inherits from idisposable.
		biglist *loop1;
		int loop2;
		T temp;
		bool should_delete = true;		
		/* This safety check requires C++17. But my compiler is too old for it.
		if ((!std::is_base_of<idisposable, T>) && (!std::is_same<idisposable, T>)) {
			should_delete = false;
		} */		
		for(loop1=this;loop1!=nullptr;loop1=loop1->next) {		
			for(loop2=0;loop2<BIGLIST_SIZE;loop2++) {
				if (loop1->items[loop2].used) {
					temp = loop1->items[loop2].item;
					loop1->items[loop2].used = false;
					if (should_delete) {
						loop1->items[loop2].item = nullptr;
						delete (idisposable *)temp;
					}
				}
			}
		}
		clear(true);
	}
	~biglist()
	{
		biglist *loop1 = next;
		biglist *loop2;
		
		while (loop1 != nullptr) {
			loop2 = loop1;
			loop1 = loop1->next;
			loop2->next = nullptr;
			delete loop2;
		}
		next = nullptr;	
	}
	void clear(bool shorten) // If shorten is true, remove extra list items > BIGLIST_SIZE.
	{
		biglist *loop1;
		int loop2;		
		if (shorten) {
			for(loop2=0;loop2<BIGLIST_SIZE;loop2++) {
				items[loop2].used = false;
			}
			while (next != nullptr) {
				loop1 = next;
				next = next->next;
				loop1->next = nullptr;
				delete loop1;
			}
		} else {
			for(loop1 = this;loop1 != nullptr; loop1 = loop1->next) {
				for(loop2=0;loop2<BIGLIST_SIZE;loop2++) {
					loop1->items[loop2].used = false;
				}
			}
		}
	}	
	bool find(T item)
	{
		biglist *loop1 = this;
		int loop2;
		
		while (loop1 != nullptr) {
			for(loop2=0;loop2 < BIGLIST_SIZE;loop2++) {
				if ((items[loop2].used) && (items[loop2].item == item)) {
					return true;
				}
			}
			loop1 = loop1->next;
		}
		return false;
	}
	biglist_item<T> *add_to_end(T item)
	{
		// Adds an item to the end of the list.
		// Empty items that are not at the end of the list are ignored.
		biglist *loop1 = this;
		biglist *loop1_previous = nullptr; // loop1->previous.
		biglist *empty_block_parent = nullptr; // the parent of a block of empty items.		
		int loop2;
		biglist *empty1 = nullptr;
		int empty2;
		bool has_items; // Does this block have items?
		
		while (true) {
			has_items = false;
			for(loop2=0;loop2 < BIGLIST_SIZE;loop2++) {
				if (loop1->items[loop2].used) {
					has_items = true;
					empty1 = nullptr;
				} else {
					if (empty1 == nullptr) {
						empty1 = loop1;
						empty2 = loop2;
					}
				}
			}
			if ((!has_items) && (loop1_previous != nullptr)) {
				// This entire list should be moved to the end. 
				// This fixes the problem of a list that keeps getting stuff added to and deleted from.
				empty_block_parent = loop1_previous;
			}
			loop1_previous = loop1;
			loop1 = loop1->next;
			if (loop1 == nullptr) { // Terminating condition of the loop.
				if ((loop1_previous != nullptr) && (has_items) && (empty_block_parent != nullptr) && (empty1 == nullptr)) {
					// Move that block of empty items to the end of this list.
					empty1 = empty_block_parent->next;
					empty2 = 0;
					empty_block_parent->next = empty1->next;
					loop1_previous->next = empty1;
					empty1->next = nullptr;	
				}
				break;
			}
		}
		while (empty1 != nullptr) {
			if (empty1->items[empty2].used) {
				if (++empty2 >= BIGLIST_SIZE) {
					empty2 = 0;
					empty1 = empty1->next;
				}
			} else {
				empty1->items[empty2].used = true;
				empty1->items[empty2].item = item;
				return empty1->items+empty2;
			}
		}
		empty1 = new biglist<T>();
		if (empty1 == nullptr) {
			return nullptr; // Memory error.
		}
		empty1->items[0].used = true;
		empty1->items[0].item = item;
		empty1->next = nullptr;
		loop1 = this;
		while (loop1->next != nullptr) {
			loop1 = loop1->next;
		}
		loop1->next = empty1;
		return empty1->items;
	}
	biglist_item<T> *add(T item)
	{
		// Adds the item. Returns the added item or nullptr if out of memory.
		biglist *loop1 = this;
		int loop2;
		biglist *empty1 = nullptr;
		int empty2;
		
		while (loop1 != nullptr) {
			for(loop2=0;loop2 < BIGLIST_SIZE;loop2++) {
				if (loop1->items[loop2].used) {
					if (loop1->items[loop2].item == item) {
						return loop1->items+loop2;
					}
				} else {
					if (empty1 == nullptr) {
						empty1 = loop1;
						empty2 = loop2;
					}
				}		
			}
			loop1 = loop1->next;
		}
		
		while (empty1 != nullptr) {
			if (empty1->items[empty2].used) {
				if (++empty2 >= BIGLIST_SIZE) {
					empty2 = 0;
					empty1 = empty1->next;
				}
			} else {
				empty1->items[empty2].used = true;
				empty1->items[empty2].item = item;
				return empty1->items+empty2;
			}
		}
		empty1 = new biglist<T>();
		if (empty1 == nullptr) {
			return nullptr; // Memory error.
		}
		empty1->items[0].used = true;
		empty1->items[0].item = item;
		empty1->next = next;
		next = empty1;
		return empty1->items;
	}
	void remove(T item)
	{
		biglist *loop1 = this;
		int loop2;		
		while (loop1 != nullptr) {
			for(loop2=0;loop2 < BIGLIST_SIZE;loop2++) {
				if ((items[loop2].used) && (items[loop2].item == item)) {					
					items[loop2].used = false;
					break;
				}
			}
			loop1 = loop1->next;
		}
		return;
	}
	int length()
	{
		biglist *loop1 = this;
		int loop2;
		int total = 0;
		while (loop1 != nullptr) {
			for(loop2=0;loop2 < BIGLIST_SIZE;loop2++) {
				if (items[loop2].used) {
					total++;
				}
			}
			loop1 = loop1->next;
		}
		return total;
	}	
};

template <class T>
class biglist_iterator
{
	private:
	biglist<T> *_list;
	biglist<T> *_current;	
	int _currentpos;
	public:
	biglist_item<T> *row;	
	T item;
	void movenext()
	{
		do
		{
			if (_current == nullptr) {
				row = nullptr;
				return;
			}
			if (++_currentpos >= biglist<T>::BIGLIST_SIZE) {
				_currentpos = 0;
				_current = _current->next;
				if (_current == nullptr) {
					row = nullptr;
					return;
				}
			}
		} while (!_current->items[_currentpos].used);
		row = _current->items+_currentpos;
		item = row->item;
		return;
	}
	void movefirst()
	{
		row = nullptr;
		_current = _list;
		_currentpos = -1;
		movenext();
	}	
	biglist_iterator(biglist<T> *list)
	{
		_list = list;
		item = nullptr;
		movefirst();
	}	
	bool eof()
	{
		return _current == nullptr;
	}
};
#endif