15a1d355fSStephan Aßmus// SLList.h
25a1d355fSStephan Aßmus
35a1d355fSStephan Aßmus#ifndef SL_LIST_H
45a1d355fSStephan Aßmus#define SL_LIST_H
55a1d355fSStephan Aßmus
65a1d355fSStephan Aßmus#include <SupportDefs.h>
75a1d355fSStephan Aßmus
85a1d355fSStephan Aßmusnamespace UserlandFSUtil {
95a1d355fSStephan Aßmus
105a1d355fSStephan Aßmus// SLListLink
115a1d355fSStephan Aßmustemplate<typename Element>
125a1d355fSStephan Aßmusclass SLListLink {
135a1d355fSStephan Aßmuspublic:
145a1d355fSStephan Aßmus	SLListLink() : next(NULL) {}
155a1d355fSStephan Aßmus	~SLListLink() {}
165a1d355fSStephan Aßmus
175a1d355fSStephan Aßmus	Element	*next;
185a1d355fSStephan Aßmus};
195a1d355fSStephan Aßmus
205a1d355fSStephan Aßmus// SLListLinkImpl
215a1d355fSStephan Aßmustemplate<typename Element>
225a1d355fSStephan Aßmusclass SLListLinkImpl {
235a1d355fSStephan Aßmusprivate:
245a1d355fSStephan Aßmus	typedef SLListLink<Element> Link;
255a1d355fSStephan Aßmus
265a1d355fSStephan Aßmuspublic:
275a1d355fSStephan Aßmus	SLListLinkImpl() : fSLListLink()	{}
285a1d355fSStephan Aßmus	~SLListLinkImpl()					{}
295a1d355fSStephan Aßmus
305a1d355fSStephan Aßmus	Link *GetSLListLink()				{ return &fSLListLink; }
315a1d355fSStephan Aßmus	const Link *GetSLListLink() const	{ return &fSLListLink; }
325a1d355fSStephan Aßmus
335a1d355fSStephan Aßmusprivate:
345a1d355fSStephan Aßmus	Link	fSLListLink;
355a1d355fSStephan Aßmus};
365a1d355fSStephan Aßmus
375a1d355fSStephan Aßmus// SLListStandardGetLink
385a1d355fSStephan Aßmustemplate<typename Element>
395a1d355fSStephan Aßmusclass SLListStandardGetLink {
405a1d355fSStephan Aßmusprivate:
415a1d355fSStephan Aßmus	typedef SLListLink<Element> Link;
425a1d355fSStephan Aßmus
435a1d355fSStephan Aßmuspublic:
445a1d355fSStephan Aßmus	inline Link *operator()(Element *element) const
455a1d355fSStephan Aßmus	{
465a1d355fSStephan Aßmus		return element->GetSLListLink();
475a1d355fSStephan Aßmus	}
485a1d355fSStephan Aßmus
495a1d355fSStephan Aßmus	inline const Link *operator()(const Element *element) const
505a1d355fSStephan Aßmus	{
515a1d355fSStephan Aßmus		return element->GetSLListLink();
525a1d355fSStephan Aßmus	}
535a1d355fSStephan Aßmus};
545a1d355fSStephan Aßmus
555a1d355fSStephan Aßmus// for convenience
565a1d355fSStephan Aßmus#define SL_LIST_TEMPLATE_LIST template<typename Element, typename GetLink>
575a1d355fSStephan Aßmus#define SL_LIST_CLASS_NAME SLList<Element, GetLink>
585a1d355fSStephan Aßmus
595a1d355fSStephan Aßmus// SLList
605a1d355fSStephan Aßmustemplate<typename Element, typename GetLink = SLListStandardGetLink<Element> >
615a1d355fSStephan Aßmusclass SLList {
625a1d355fSStephan Aßmusprivate:
635a1d355fSStephan Aßmus	typedef SLList<Element, GetLink>	List;
645a1d355fSStephan Aßmus	typedef SLListLink<Element>			Link;
655a1d355fSStephan Aßmus
665a1d355fSStephan Aßmuspublic:
675a1d355fSStephan Aßmus	class Iterator {
685a1d355fSStephan Aßmus	public:
695a1d355fSStephan Aßmus		Iterator(List *list)
705a1d355fSStephan Aßmus			: fList(list),
715a1d355fSStephan Aßmus			  fPrevious(NULL),
725a1d355fSStephan Aßmus			  fCurrent(NULL),
735a1d355fSStephan Aßmus			  fNext(fList->GetFirst())
745a1d355fSStephan Aßmus		{
755a1d355fSStephan Aßmus		}
765a1d355fSStephan Aßmus
775a1d355fSStephan Aßmus		Iterator(const Iterator &other)
785a1d355fSStephan Aßmus		{
795a1d355fSStephan Aßmus			*this = other;
805a1d355fSStephan Aßmus		}
815a1d355fSStephan Aßmus
825a1d355fSStephan Aßmus		bool HasNext() const
835a1d355fSStephan Aßmus		{
845a1d355fSStephan Aßmus			return fNext;
855a1d355fSStephan Aßmus		}
865a1d355fSStephan Aßmus
875a1d355fSStephan Aßmus		Element *Next()
885a1d355fSStephan Aßmus		{
895a1d355fSStephan Aßmus			if (fCurrent)
905a1d355fSStephan Aßmus				fPrevious = fCurrent;
915a1d355fSStephan Aßmus
925a1d355fSStephan Aßmus			fCurrent = fNext;
935a1d355fSStephan Aßmus
945a1d355fSStephan Aßmus			if (fNext)
955a1d355fSStephan Aßmus				fNext = fList->GetNext(fNext);
965a1d355fSStephan Aßmus
975a1d355fSStephan Aßmus			return fCurrent;
985a1d355fSStephan Aßmus		}
995a1d355fSStephan Aßmus
1005a1d355fSStephan Aßmus		Element *Remove()
1015a1d355fSStephan Aßmus		{
1025a1d355fSStephan Aßmus			Element *element = fCurrent;
1035a1d355fSStephan Aßmus			if (fCurrent) {
1045a1d355fSStephan Aßmus				fList->_Remove(fPrevious, fCurrent);
1055a1d355fSStephan Aßmus				fCurrent = NULL;
1065a1d355fSStephan Aßmus			}
1075a1d355fSStephan Aßmus			return element;
1085a1d355fSStephan Aßmus		}
1095a1d355fSStephan Aßmus
1105a1d355fSStephan Aßmus		Iterator &operator=(const Iterator &other)
1115a1d355fSStephan Aßmus		{
1125a1d355fSStephan Aßmus			fList = other.fList;
1135a1d355fSStephan Aßmus			fPrevious = other.fPrevious;
1145a1d355fSStephan Aßmus			fCurrent = other.fCurrent;
1155a1d355fSStephan Aßmus			fNext = other.fNext;
1165a1d355fSStephan Aßmus			return *this;
1175a1d355fSStephan Aßmus		}
1185a1d355fSStephan Aßmus
1195a1d355fSStephan Aßmus	private:
1205a1d355fSStephan Aßmus		List	*fList;
1215a1d355fSStephan Aßmus		Element *fPrevious;
1225a1d355fSStephan Aßmus		Element	*fCurrent;
1235a1d355fSStephan Aßmus		Element	*fNext;
1245a1d355fSStephan Aßmus	};
1255a1d355fSStephan Aßmus
1265a1d355fSStephan Aßmus	class ConstIterator {
1275a1d355fSStephan Aßmus	public:
1285a1d355fSStephan Aßmus		ConstIterator(const List *list)
1295a1d355fSStephan Aßmus			: fList(list),
1305a1d355fSStephan Aßmus			  fNext(list->GetFirst())
1315a1d355fSStephan Aßmus		{
1325a1d355fSStephan Aßmus		}
1335a1d355fSStephan Aßmus
1345a1d355fSStephan Aßmus		ConstIterator(const ConstIterator &other)
1355a1d355fSStephan Aßmus		{
1365a1d355fSStephan Aßmus			*this = other;
1375a1d355fSStephan Aßmus		}
1385a1d355fSStephan Aßmus
1395a1d355fSStephan Aßmus		bool HasNext() const
1405a1d355fSStephan Aßmus		{
1415a1d355fSStephan Aßmus			return fNext;
1425a1d355fSStephan Aßmus		}
1435a1d355fSStephan Aßmus
1445a1d355fSStephan Aßmus		Element *Next()
1455a1d355fSStephan Aßmus		{
1465a1d355fSStephan Aßmus			Element *element = fNext;
1475a1d355fSStephan Aßmus			if (fNext)
1485a1d355fSStephan Aßmus				fNext = fList->GetNext(fNext);
1495a1d355fSStephan Aßmus			return element;
1505a1d355fSStephan Aßmus		}
1515a1d355fSStephan Aßmus
1525a1d355fSStephan Aßmus		ConstIterator &operator=(const ConstIterator &other)
1535a1d355fSStephan Aßmus		{
1545a1d355fSStephan Aßmus			fList = other.fList;
1555a1d355fSStephan Aßmus			fNext = other.fNext;
1565a1d355fSStephan Aßmus			return *this;
1575a1d355fSStephan Aßmus		}
1585a1d355fSStephan Aßmus
1595a1d355fSStephan Aßmus	private:
1605a1d355fSStephan Aßmus		const List	*fList;
1615a1d355fSStephan Aßmus		Element		*fNext;
1625a1d355fSStephan Aßmus	};
1635a1d355fSStephan Aßmus
1645a1d355fSStephan Aßmuspublic:
1655a1d355fSStephan Aßmus	SLList() : fFirst(NULL), fLast(NULL) {}
1665a1d355fSStephan Aßmus	SLList(const GetLink &getLink)
1675a1d355fSStephan Aßmus		: fFirst(NULL), fLast(NULL), fGetLink(getLink) {}
1685a1d355fSStephan Aßmus	~SLList() {}
1695a1d355fSStephan Aßmus
1705a1d355fSStephan Aßmus	inline bool IsEmpty() const			{ return (fFirst == NULL); }
1715a1d355fSStephan Aßmus
1725a1d355fSStephan Aßmus	inline void Insert(Element *element, bool back = true);
1735a1d355fSStephan Aßmus	inline void InsertAfter(Element *previous, Element *element);
1745a1d355fSStephan Aßmus	inline void Remove(Element *element);
1755a1d355fSStephan Aßmus		// O(n)!
1765a1d355fSStephan Aßmus
1775a1d355fSStephan Aßmus	inline void MoveFrom(SL_LIST_CLASS_NAME *fromList);
1785a1d355fSStephan Aßmus
1795a1d355fSStephan Aßmus	inline void RemoveAll();
1805a1d355fSStephan Aßmus
1815a1d355fSStephan Aßmus	inline Element *GetFirst() const	{ return fFirst; }
1825a1d355fSStephan Aßmus	inline Element *GetLast() const		{ return fLast; }
1835a1d355fSStephan Aßmus
1845a1d355fSStephan Aßmus	inline Element *GetHead() const		{ return fFirst; }
1855a1d355fSStephan Aßmus	inline Element *GetTail() const		{ return fLast; }
1865a1d355fSStephan Aßmus
1875a1d355fSStephan Aßmus	inline Element *GetNext(Element *element) const;
1885a1d355fSStephan Aßmus
1895a1d355fSStephan Aßmus	inline int32 Size() const;
1905a1d355fSStephan Aßmus		// O(n)!
1915a1d355fSStephan Aßmus
1925a1d355fSStephan Aßmus	inline Iterator GetIterator()				{ return Iterator(this); }
1935a1d355fSStephan Aßmus	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
1945a1d355fSStephan Aßmus
1955a1d355fSStephan Aßmusprivate:
1965a1d355fSStephan Aßmus	friend class Iterator;
1975a1d355fSStephan Aßmus
1985a1d355fSStephan Aßmus	inline void _Remove(Element *previous, Element *element);
1995a1d355fSStephan Aßmus
2005a1d355fSStephan Aßmusprivate:
2015a1d355fSStephan Aßmus	Element	*fFirst;
2025a1d355fSStephan Aßmus	Element	*fLast;
2035a1d355fSStephan Aßmus	GetLink	fGetLink;
2045a1d355fSStephan Aßmus};
2055a1d355fSStephan Aßmus
2065a1d355fSStephan Aßmus}	// namespace UserlandFSUtil
2075a1d355fSStephan Aßmus
2085a1d355fSStephan Aßmususing UserlandFSUtil::SLList;
2095a1d355fSStephan Aßmususing UserlandFSUtil::SLListLink;
2105a1d355fSStephan Aßmususing UserlandFSUtil::SLListLinkImpl;
2115a1d355fSStephan Aßmus
2125a1d355fSStephan Aßmus
2135a1d355fSStephan Aßmus// inline methods
2145a1d355fSStephan Aßmus
2155a1d355fSStephan Aßmus// Insert
2165a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
2175a1d355fSStephan Aßmusvoid
2185a1d355fSStephan AßmusSL_LIST_CLASS_NAME::Insert(Element *element, bool back)
2195a1d355fSStephan Aßmus{
2205a1d355fSStephan Aßmus	InsertAfter((back ? fLast : NULL), element);
2215a1d355fSStephan Aßmus}
2225a1d355fSStephan Aßmus
2235a1d355fSStephan Aßmus// InsertAfter
2245a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
2255a1d355fSStephan Aßmusvoid
2265a1d355fSStephan AßmusSL_LIST_CLASS_NAME::InsertAfter(Element *previous, Element *element)
2275a1d355fSStephan Aßmus{
2285a1d355fSStephan Aßmus	if (element) {
2295a1d355fSStephan Aßmus		Link *elLink = fGetLink(element);
2305a1d355fSStephan Aßmus		if (previous) {
2315a1d355fSStephan Aßmus			// insert after previous element
2325a1d355fSStephan Aßmus			Link *prevLink = fGetLink(previous);
2335a1d355fSStephan Aßmus			elLink->next = prevLink->next;
2345a1d355fSStephan Aßmus			prevLink->next = element;
2355a1d355fSStephan Aßmus		} else {
2365a1d355fSStephan Aßmus			// no previous element given: prepend
2375a1d355fSStephan Aßmus			elLink->next = fFirst;
2385a1d355fSStephan Aßmus			fFirst = element;
2395a1d355fSStephan Aßmus		}
2405a1d355fSStephan Aßmus
2415a1d355fSStephan Aßmus		// element may be new last element
2425a1d355fSStephan Aßmus		if (fLast == previous)
2435a1d355fSStephan Aßmus			fLast = element;
2445a1d355fSStephan Aßmus	}
2455a1d355fSStephan Aßmus}
2465a1d355fSStephan Aßmus
2475a1d355fSStephan Aßmus// Remove
2485a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
2495a1d355fSStephan Aßmusvoid
2505a1d355fSStephan AßmusSL_LIST_CLASS_NAME::Remove(Element *element)
2515a1d355fSStephan Aßmus{
2525a1d355fSStephan Aßmus	if (!element)
2535a1d355fSStephan Aßmus		return;
2545a1d355fSStephan Aßmus
2555a1d355fSStephan Aßmus	for (Iterator it = GetIterator(); it.HasNext();) {
2565a1d355fSStephan Aßmus		if (element == it.Next()) {
2575a1d355fSStephan Aßmus			it.Remove();
2585a1d355fSStephan Aßmus			return;
2595a1d355fSStephan Aßmus		}
2605a1d355fSStephan Aßmus	}
2615a1d355fSStephan Aßmus}
2625a1d355fSStephan Aßmus
2635a1d355fSStephan Aßmus// MoveFrom
2645a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
2655a1d355fSStephan Aßmusvoid
2665a1d355fSStephan AßmusSL_LIST_CLASS_NAME::MoveFrom(SL_LIST_CLASS_NAME *fromList)
2675a1d355fSStephan Aßmus{
2685a1d355fSStephan Aßmus	if (fromList && fromList->fFirst) {
2695a1d355fSStephan Aßmus		if (fFirst) {
2705a1d355fSStephan Aßmus			fGetLink(fLast)->next = fromList->fFirst;
2715a1d355fSStephan Aßmus			fLast = fromList->fLast;
2725a1d355fSStephan Aßmus		} else {
2735a1d355fSStephan Aßmus			fFirst = fromList->fFirst;
2745a1d355fSStephan Aßmus			fLast = fromList->fLast;
2755a1d355fSStephan Aßmus		}
2765a1d355fSStephan Aßmus		fromList->fFirst = NULL;
2775a1d355fSStephan Aßmus		fromList->fLast = NULL;
2785a1d355fSStephan Aßmus	}
2795a1d355fSStephan Aßmus}
2805a1d355fSStephan Aßmus
2815a1d355fSStephan Aßmus// RemoveAll
2825a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
2835a1d355fSStephan Aßmusvoid
2845a1d355fSStephan AßmusSL_LIST_CLASS_NAME::RemoveAll()
2855a1d355fSStephan Aßmus{
2865a1d355fSStephan Aßmus	Element *element = fFirst;
2875a1d355fSStephan Aßmus	while (element) {
2885a1d355fSStephan Aßmus		Link *elLink = fGetLink(element);
2895a1d355fSStephan Aßmus		element = elLink->next;
2905a1d355fSStephan Aßmus		elLink->next = NULL;
2915a1d355fSStephan Aßmus	}
2925a1d355fSStephan Aßmus	fFirst = NULL;
2935a1d355fSStephan Aßmus	fLast = NULL;
2945a1d355fSStephan Aßmus}
2955a1d355fSStephan Aßmus
2965a1d355fSStephan Aßmus// GetNext
2975a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
2985a1d355fSStephan AßmusElement *
2995a1d355fSStephan AßmusSL_LIST_CLASS_NAME::GetNext(Element *element) const
3005a1d355fSStephan Aßmus{
3015a1d355fSStephan Aßmus	return (element ? fGetLink(element)->next : NULL);
3025a1d355fSStephan Aßmus}
3035a1d355fSStephan Aßmus
3045a1d355fSStephan Aßmus// _Remove
3055a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
3065a1d355fSStephan Aßmusvoid
3075a1d355fSStephan AßmusSL_LIST_CLASS_NAME::_Remove(Element *previous, Element *element)
3085a1d355fSStephan Aßmus{
3095a1d355fSStephan Aßmus	Link *elLink = fGetLink(element);
3105a1d355fSStephan Aßmus	if (previous)
3115a1d355fSStephan Aßmus		fGetLink(previous)->next = elLink->next;
3125a1d355fSStephan Aßmus	else
3135a1d355fSStephan Aßmus		fFirst = elLink->next;
3145a1d355fSStephan Aßmus
3155a1d355fSStephan Aßmus	if (element == fLast)
3165a1d355fSStephan Aßmus		fLast = previous;
3175a1d355fSStephan Aßmus
3185a1d355fSStephan Aßmus	elLink->next = NULL;
3195a1d355fSStephan Aßmus}
3205a1d355fSStephan Aßmus
3215a1d355fSStephan Aßmus// Size
3225a1d355fSStephan AßmusSL_LIST_TEMPLATE_LIST
3235a1d355fSStephan Aßmusint32
3245a1d355fSStephan AßmusSL_LIST_CLASS_NAME::Size() const
3255a1d355fSStephan Aßmus{
3265a1d355fSStephan Aßmus	int32 count = 0;
3275a1d355fSStephan Aßmus	for (Element* element = GetFirst(); element; element = GetNext(element))
3285a1d355fSStephan Aßmus		count++;
3295a1d355fSStephan Aßmus	return count;
3305a1d355fSStephan Aßmus}
3315a1d355fSStephan Aßmus
3325a1d355fSStephan Aßmus#endif	// SL_LIST_H
333