dburgess | 82c46ff | 2011-10-07 02:40:51 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2008 Free Software Foundation, Inc. |
| 3 | * |
dburgess | 82c46ff | 2011-10-07 02:40:51 +0000 | [diff] [blame] | 4 | * This software is distributed under the terms of the GNU Affero Public License. |
| 5 | * See the COPYING file in the main directory for details. |
| 6 | * |
| 7 | * This use of this software may be subject to additional restrictions. |
| 8 | * See the LEGAL file in the main directory for details. |
| 9 | |
| 10 | This program is free software: you can redistribute it and/or modify |
| 11 | it under the terms of the GNU Affero General Public License as published by |
| 12 | the Free Software Foundation, either version 3 of the License, or |
| 13 | (at your option) any later version. |
| 14 | |
| 15 | This program is distributed in the hope that it will be useful, |
| 16 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 17 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 18 | GNU Affero General Public License for more details. |
| 19 | |
| 20 | You should have received a copy of the GNU Affero General Public License |
| 21 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
| 22 | |
| 23 | */ |
| 24 | |
| 25 | |
| 26 | |
| 27 | #ifndef LINKEDLISTS_H |
| 28 | #define LINKEDLISTS_H |
| 29 | |
| 30 | #include <stdlib.h> |
| 31 | |
| 32 | |
| 33 | |
| 34 | /** This node class is used to build singly-linked lists. */ |
| 35 | class ListNode { |
| 36 | |
| 37 | private: |
| 38 | |
| 39 | ListNode* mNext; |
| 40 | void* mData; |
| 41 | |
| 42 | public: |
| 43 | |
| 44 | ListNode* next() { return mNext; } |
| 45 | void next(ListNode* wNext) { mNext=wNext; } |
| 46 | |
| 47 | void* data() { return mData; } |
| 48 | void data(void* wData) { mData=wData; } |
| 49 | }; |
| 50 | |
| 51 | |
| 52 | |
| 53 | |
| 54 | /** A fast FIFO for pointer-based storage. */ |
| 55 | class PointerFIFO { |
| 56 | |
| 57 | private: |
| 58 | |
| 59 | ListNode* mHead; ///< points to next item out |
| 60 | ListNode* mTail; ///< points to last item in |
| 61 | ListNode* mFreeList; ///< pool of previously-allocated nodes |
| 62 | unsigned mSize; ///< number of items in the FIFO |
| 63 | |
| 64 | public: |
| 65 | |
| 66 | PointerFIFO() |
| 67 | :mHead(NULL),mTail(NULL),mFreeList(NULL), |
| 68 | mSize(0) |
| 69 | {} |
| 70 | |
| 71 | unsigned size() const { return mSize; } |
| 72 | |
| 73 | /** Put an item into the FIFO. */ |
| 74 | void put(void* val); |
| 75 | |
| 76 | /** |
| 77 | Take an item from the FIFO. |
| 78 | Returns NULL for empty list. |
| 79 | */ |
| 80 | void* get(); |
| 81 | |
| 82 | |
| 83 | private: |
| 84 | |
| 85 | /** Allocate a new node to extend the FIFO. */ |
| 86 | ListNode *allocate(); |
| 87 | |
| 88 | /** Release a node to the free pool after removal from the FIFO. */ |
| 89 | void release(ListNode* wNode); |
| 90 | |
| 91 | }; |
| 92 | |
| 93 | |
| 94 | |
| 95 | |
| 96 | |
| 97 | #endif |
| 98 | // vim: ts=4 sw=4 |