1 /* 2 * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Distributed under the terms of the MIT License. 4 */ 5 #ifndef KERNEL_TEAM_THREAD_TABLES_H 6 #define KERNEL_TEAM_THREAD_TABLES_H 7 8 9 #include <thread_types.h> 10 11 12 namespace BKernel { 13 14 15 template<typename Element> 16 struct TeamThreadTable { 17 public: 18 typedef typename Element::id_type id_type; 19 typedef typename Element::iterator_type IteratorEntry; 20 21 struct Iterator { 22 Iterator() 23 : 24 fNext(NULL) 25 { 26 } 27 28 Iterator(IteratorEntry* nextEntry) 29 { 30 _SetNext(nextEntry); 31 } 32 33 bool HasNext() const 34 { 35 return fNext != NULL; 36 } 37 38 Element* Next() 39 { 40 Element* result = fNext; 41 if (result != NULL) 42 _SetNext(result->GetDoublyLinkedListLink()->next); 43 44 return result; 45 } 46 47 private: 48 void _SetNext(IteratorEntry* entry) 49 { 50 while (entry != NULL) { 51 if (entry->id >= 0) { 52 fNext = static_cast<Element*>(entry); 53 return; 54 } 55 56 entry = entry->GetDoublyLinkedListLink()->next; 57 } 58 59 fNext = NULL; 60 } 61 62 private: 63 Element* fNext; 64 }; 65 66 public: 67 TeamThreadTable() 68 : 69 fNextSerialNumber(1) 70 { 71 } 72 73 status_t Init(size_t initialSize) 74 { 75 return fTable.Init(initialSize); 76 } 77 78 void Insert(Element* element) 79 { 80 element->serial_number = fNextSerialNumber++; 81 fTable.InsertUnchecked(element); 82 fList.Add(element); 83 } 84 85 void Remove(Element* element) 86 { 87 fTable.RemoveUnchecked(element); 88 fList.Remove(element); 89 } 90 91 Element* Lookup(id_type id, bool visibleOnly = true) const 92 { 93 Element* element = fTable.Lookup(id); 94 return element != NULL && (!visibleOnly || element->visible) 95 ? element : NULL; 96 } 97 98 /*! Gets an iterator. 99 The iterator iterates through all, including invisible, entries! 100 */ 101 Iterator GetIterator() 102 { 103 return Iterator(fList.Head()); 104 } 105 106 void InsertIteratorEntry(IteratorEntry* entry) 107 { 108 // add to front 109 entry->id = -1; 110 entry->visible = false; 111 fList.Add(entry, false); 112 } 113 114 void RemoveIteratorEntry(IteratorEntry* entry) 115 { 116 fList.Remove(entry); 117 } 118 119 Element* NextElement(IteratorEntry* entry, bool visibleOnly = true) 120 { 121 if (entry == fList.Tail()) 122 return NULL; 123 124 IteratorEntry* nextEntry = entry; 125 126 while (true) { 127 nextEntry = nextEntry->GetDoublyLinkedListLink()->next; 128 if (nextEntry == NULL) { 129 // end of list -- requeue entry at the end and return NULL 130 fList.Remove(entry); 131 fList.Add(entry); 132 return NULL; 133 } 134 135 if (nextEntry->id >= 0 && (!visibleOnly || nextEntry->visible)) { 136 // found an element -- requeue entry after element 137 Element* element = static_cast<Element*>(nextEntry); 138 fList.Remove(entry); 139 fList.InsertAfter(nextEntry, entry); 140 return element; 141 } 142 } 143 } 144 145 private: 146 struct HashDefinition { 147 typedef id_type KeyType; 148 typedef Element ValueType; 149 150 size_t HashKey(id_type key) const 151 { 152 return key; 153 } 154 155 size_t Hash(Element* value) const 156 { 157 return HashKey(value->id); 158 } 159 160 bool Compare(id_type key, Element* value) const 161 { 162 return value->id == key; 163 } 164 165 Element*& GetLink(Element* value) const 166 { 167 return value->hash_next; 168 } 169 }; 170 171 typedef BOpenHashTable<HashDefinition> ElementTable; 172 typedef DoublyLinkedList<IteratorEntry> List; 173 174 private: 175 ElementTable fTable; 176 List fList; 177 int64 fNextSerialNumber; 178 }; 179 180 181 } // namespace BKernel 182 183 184 #endif // KERNEL_TEAM_THREAD_TABLES_H 185