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