1 /* 2 ** Copyright 2003, Axel Dörfler, axeld@pinc-software.de. All rights reserved. 3 ** Distributed under the terms of the OpenBeOS License. 4 */ 5 #ifndef KERNEL_UTIL_DOUBLY_LINKED_LIST_H 6 #define KERNEL_UTIL_DOUBLY_LINKED_LIST_H 7 8 9 #include <SupportDefs.h> 10 #include <util/kernel_cpp.h> 11 12 13 #ifdef __cplusplus 14 15 /* This header defines a doubly-linked list. It differentiates between a link 16 * and an item. 17 * It's the C++ version of <util/list.h> it's very small and efficient, but 18 * has not been perfectly C++-ified yet. 19 * The link must be part of the item, it cannot be allocated on demand yet. 20 */ 21 22 namespace DoublyLinked { 23 24 class Link { 25 public: 26 Link *next; 27 Link *prev; 28 }; 29 30 template<class Item, Link Item::* LinkMember = &Item::fLink> class Iterator; 31 32 template<class Item, Link Item::* LinkMember = &Item::fLink> 33 class List { 34 public: 35 //typedef typename Item ValueType; 36 typedef Iterator<Item, LinkMember> IteratorType; 37 38 List() 39 { 40 fLink.next = fLink.prev = &fLink; 41 } 42 43 void Add(Item *item) 44 { 45 //Link *link = &item->*LinkMember; 46 (item->*LinkMember).next = &fLink; 47 (item->*LinkMember).prev = fLink.prev; 48 49 fLink.prev->next = &(item->*LinkMember); 50 fLink.prev = &(item->*LinkMember); 51 } 52 53 static void Remove(Item *item) 54 { 55 (item->*LinkMember).next->prev = (item->*LinkMember).prev; 56 (item->*LinkMember).prev->next = (item->*LinkMember).next; 57 } 58 59 Item *RemoveHead() 60 { 61 if (IsEmpty()) 62 return NULL; 63 64 Item *item = GetItem(fLink.next); 65 Remove(item); 66 67 return item; 68 } 69 70 IteratorType Iterator() 71 { 72 return IteratorType(*this); 73 } 74 75 bool IsEmpty() 76 { 77 return fLink.next == &fLink; 78 } 79 80 Link *Head() 81 { 82 return fLink.next; 83 } 84 85 static inline size_t Offset() 86 { 87 return (size_t)&(((Item *)1)->*LinkMember) - 1; 88 } 89 90 static inline Item *GetItem(Link *link) 91 { 92 return (Item *)((uint8 *)link - Offset()); 93 } 94 95 private: 96 friend class IteratorType; 97 Link fLink; 98 }; 99 100 template<class Item, Link Item::* LinkMember> 101 class Iterator { 102 public: 103 typedef List<Item, LinkMember> ListType; 104 105 Iterator() : fCurrent(NULL) {} 106 Iterator(ListType &list) : fList(&list), fCurrent(list.Head()) {} 107 108 Item *Next() 109 { 110 if (fCurrent == &fList->fLink) 111 return NULL; 112 113 Link *current = fCurrent; 114 fCurrent = fCurrent->next; 115 116 return ListType::GetItem(current); 117 } 118 119 private: 120 ListType *fList; 121 Link *fCurrent; 122 }; 123 124 } // namespace DoublyLinked 125 126 #endif /* __cplusplus */ 127 128 #endif /* KERNEL_UTIL_DOUBLY_LINKED_LIST_H */ 129