1 /* Copyright (c) 2009, 2021, Oracle and/or its affiliates. 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License, version 2.0, 5 as published by the Free Software Foundation. 6 7 This program is also distributed with certain software (including 8 but not limited to OpenSSL) that is licensed under separate terms, 9 as designated in a particular file or component or in included license 10 documentation. The authors of MySQL hereby grant you an additional 11 permission to link the program and your derivative works with the 12 separately licensed software that they have included with MySQL. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License, version 2.0, for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */ 22 23 24 #ifndef NDB_LINKEDSTACK_HPP 25 #define NDB_LINKEDSTACK_HPP 26 27 #include <ndb_global.h> 28 29 /** 30 * LinkedStack 31 * 32 * A templated class for a stack of elements E. 33 * Storage for the elements is allocated using the passed 34 * allocator. 35 * Push copies the supplied element into the stack 36 * Pop overwrites the supplied element with the contents 37 * of the top of the stack 38 * Internally, the class allocates 'blocks' of elements of 39 * the size passed, linking them together as necessary. 40 * As the stack shrinks, the blocks are not released. 41 * Blocks are returned to the allocator when release() is 42 * called. 43 * reset() empties the stack without releasing the allocated 44 * storage. 45 */ 46 template <typename E, typename A> 47 class LinkedStack 48 { 49 private: 50 struct BlockHeader 51 { 52 BlockHeader* next; 53 BlockHeader* prev; 54 E* elements; 55 }; 56 allocBlock()57 BlockHeader* allocBlock() 58 { 59 /* Alloc blockheader and element array */ 60 BlockHeader* h = (BlockHeader*) A::alloc(allocatorContext, 61 sizeof(BlockHeader)); 62 E* e = (E*) A::mem_calloc(allocatorContext, blockElements, sizeof(E)); 63 64 h->next = NULL; 65 h->prev = NULL; 66 h->elements = e; 67 68 return h; 69 } 70 valid()71 bool valid() 72 { 73 if (stackTop) 74 { 75 assert(firstBlock != NULL); 76 assert(currBlock != NULL); 77 /* Check that currBlock is positioned on correct 78 * block, except for block boundary case 79 */ 80 Uint32 blockNum = (stackTop - 1) / blockElements; 81 BlockHeader* bh = firstBlock; 82 while(blockNum--) 83 { 84 bh = bh->next; 85 } 86 assert(bh == currBlock); 87 } 88 else 89 { 90 assert(currBlock == NULL); 91 } 92 return true; 93 } 94 95 /* Note that stackTop is 'next insertion point' whereas 96 * currBlock points to block last inserted to. 97 * On block boundaries, they refer to different blocks 98 */ 99 void* allocatorContext; 100 BlockHeader* firstBlock; 101 BlockHeader* currBlock; 102 Uint32 stackTop; 103 Uint32 blockElements; 104 105 public: LinkedStack(Uint32 _blockElements,void * _allocatorContext=NULL)106 LinkedStack(Uint32 _blockElements, void* _allocatorContext=NULL) 107 : allocatorContext(_allocatorContext), 108 firstBlock(NULL), 109 currBlock(NULL), 110 stackTop(0), 111 blockElements(_blockElements) 112 { 113 assert(blockElements > 0); 114 assert(valid()); 115 } 116 ~LinkedStack()117 ~LinkedStack() 118 { 119 assert(valid()); 120 /* Release block storage if present */ 121 release(); 122 } 123 push(E & elem)124 bool push(E& elem) 125 { 126 assert(valid()); 127 Uint32 blockOffset = stackTop % blockElements; 128 129 if (blockOffset == 0) 130 { 131 /* On block boundary */ 132 if (stackTop) 133 { 134 /* Some elements exist already */ 135 if (!currBlock->next) 136 { 137 /* End of block list, alloc another */ 138 BlockHeader* newBlock = allocBlock(); 139 if (!newBlock) 140 return false; 141 142 currBlock->next = newBlock; 143 currBlock->next->prev = currBlock; 144 } 145 currBlock = currBlock->next; 146 } 147 else 148 { 149 /* First element */ 150 if (!firstBlock) 151 { 152 BlockHeader* newBlock = allocBlock(); 153 if (!newBlock) 154 return false; 155 156 firstBlock = currBlock = newBlock; 157 } 158 currBlock = firstBlock; 159 } 160 } 161 162 currBlock->elements[ blockOffset ] = elem; 163 stackTop++; 164 165 assert(valid()); 166 return true; 167 } 168 pop(E & elem)169 bool pop(E& elem) 170 { 171 assert(valid()); 172 if (stackTop) 173 { 174 stackTop--; 175 Uint32 blockOffset = stackTop % blockElements; 176 elem = currBlock->elements[ blockOffset ]; 177 178 if (blockOffset == 0) 179 { 180 /* Block boundary, shift back to prev block. */ 181 if (stackTop) 182 assert(currBlock->prev); 183 184 currBlock = currBlock->prev; 185 } 186 187 assert(valid()); 188 return true; 189 } 190 return false; 191 } 192 size() const193 Uint32 size() const 194 { 195 return stackTop; 196 } 197 reset()198 void reset() 199 { 200 assert(valid()); 201 stackTop = 0; 202 currBlock = NULL; 203 assert(valid()); 204 }; 205 release()206 void release() 207 { 208 assert(valid()); 209 BlockHeader* h = firstBlock; 210 while (h) 211 { 212 BlockHeader* n = h->next; 213 A::mem_free(allocatorContext, h->elements); 214 A::mem_free(allocatorContext, h); 215 h = n; 216 }; 217 stackTop = 0; 218 firstBlock = currBlock = NULL; 219 assert(valid()); 220 } 221 }; 222 223 #endif 224