Decoded: OpenTTD (2003) v1.8 (2018)
Source file: smallstack_type.hpp
Line-by-line code walkthrough by MaiZure

smallstack_type.hpp defines SmallStack and SimplePool container 

Original code:
https://github.com/MaiZure/OpenTTD-1.8/blob/master/src/core/smallstack_type.hpp





1     COMMENT (*)
2     BLANK (-)
3     *
4     *
5     *
6     *
7     *
8     *
9     -
10    *
11    -
12    Header guard
13    Header guard
14    -
15    Includes the OpenTTD SmallVector container
16    Includes the OpenTTD thread package header
17    -
18    *
19    *
20    *
21    *
22    *
23    Sets up a class template with 4 parameters:
24    BLOCK START - SimplePool, a slim pool-like container
25    Begins the public section of SimplePool
26    Defines a default constructor for SimplePool with empty initialization
27    Defines a destructor for SimplePool
28    -
29    *
30    *
31    *
32    *
33    *
34    Defines SimplePool::GetMutex to return a pointer to the mutex
35    -
36    *
37    *
38    *
39    *
40  Defines SimplePool::Get with one argument to return the pool item with that
      index
41    -
42    *
43    *
44    *
45    *
46    Defines SimplePool::Create
47    BLOCK START - SimplePool::Create
48    Gets the index of the first free item
49    If the index is valid...
50    Set the item as valid
51    Advance the first_free index tracker
52    Recheck the first_unused item
53    End check for valid item
54    Return the item index
55    BLOCK END - SimplePool::Create
56    -
57    *
58    *
59    *
60    *
61    Defines SimplePool::Destroy with one argument: an index
62    BLOCK START - SimplePool::Destroy
63    Invalidate the item
64    Update the first_free tracking variable
65    BLOCK END - SimplePool::Destroy
66    -
67    Begins the private section of SimplePool
68    -
69    Defines SimplePool::FindFirstFree with no arguments
70    BLOCK START - SimplePool::FindFirstFree
71    Start at the first_free mark
72    Loop between the first free and first unused...
73    Return the first invalid index
74    Repeat loop
75    -
76    If none found and the pool has room to grow
77    Resize the pool for one more item.
78    End check for pool growth space
79    Return the guaranteed free index at the original end (efge case bug?)
80    BLOCK END - SimplePool::FindFirstFree
81    -
82    BLOCK START - SimplePool::SimplePoolPoolItem as an extension of an item
83    Declare a valid flag
84    BLOCK END - SimplePool::SimplePoolPoolItem
85    -
86    Declare an index for the first unused pool item
87    Declare an index for the first free pool item
88    -
89    Declare a pool mutex for synchronization
90    Typedef the pool data as a SmallVector for ease of use
91    BLOCK END - SimplePool
92    -
93    *
94    *
95    *
96    *
97    Sets up a class template with two type paramters: Item type and index
      type
98    BLOCK START - SmallStackItem, object to manage a single item in a SmallStack
99    Declares an index to the next item
100   Declares the item value
101   *
102   *
103   *
104   *
105   *
106   *
107   Defines a parameterized constructor with two inputs: index and value
108   The default initialization list for SmallStackItem
109   BLOCK END - SmallStackItem
110   -
111   *
112   *
113   *
114   *
115   *
116   *
117   *
118   *
119   *
120   *
121   *
122   *
123   *
124   *
125   *
126   *
127   *
128   *
129   *
130   *
131   *
132   *
133   *
134   *
135   *
136   *
137   Sets up a class template with 5 arguments: two types, an item, index,
      increment size, and max size
138   BLOCK START - SmallStack, A stack implemented without pointers
139   Begins the public section of SmallStack
140   -
141   Typedef the SmallStack item as Item for ease of use
142   -
143   *
144   *
145   *
146   BLOCK START - PooledSmallStack, extends an Item 
147   Defines a counter for stack branches
148   BLOCK END - PooledSmallStack
149   *
150   *
151   *
152   *
153   *
154   *
155   *
156   Defines a parameterized constructor for SmallStack
157   -
158   *
159   *
160   *
161   Defines a destructor for SmallStack
162   BLOCK START - SmallStack destructor
163   *
164   Pop all items off the stack
165   BLOCK END - SmallStack destructor
166   -
167   *
168   *
169   *
170   *
171   Defines a copy constructor for SmallStack
172   -
173   *
174   *
175   *
176   *
177   *
178   Defines an overloaded assignment operator for SmallStack
179   BLOCK START - SmallStack = operator overload
180   If the assignment is from the same SmallStack, nothing to do
181   Pop all items off the current stack
182   Match the next variables
183   Match the value variables
184   *
185   *
186   Branch in to the other stack
187   Return pointer to self
188   BLOCK END - SmallStack = operator overload
189   -
190   *
191   *
192   *
193   *
194   *
195   Defines SmallStack::Push with one argument: an item
196   BLOCK START - SmallStack::Push
197   If the item is valid...
198   Lock the pool
199   Create a new item
200   If there is space in the pool...
201   Get the item from the pool
202   Match the values
203   Match the next pointer
204   No branching
205   Plug the new item in to the SmallStack
206   End check for space
207   End check for validity
208   Return the value
209   BLOCK END - SmallStack::Push
210   -
211   *
212   *
213   *
214   *
215   Defines SmallStack::Pop with no arguments
216   BLOCK START - SmallStack::Pop
217   Set the return value as the current value (top of the stack)
218   If the stack is full...
219   The value is invalid
220   Otherwise the stack has space...
221   Lock the pool
222   Get the next item
223   Set the value to the next item
224   If we're at the top of the stack...
225   Destroy the item
226   Otherwise there is branching so...
227   Decrement the branch counter
228   *
229   If the stack still has space...
230   Advance the branch counter around the popped branch
231   End check for stack space
232   End check for branching
233   *
234   *
235   *
236   *
237   Update next around the popped item
238   End check for space in the stack
239   Return the top of the stack
240   BLOCK END - SmallStack::Pop
241   -
242   *
243   *
244   *
245   *
246   Defines SmallStack::IsEmpty with no arguments
247   BLOCK START - SmallStack::IsEmpty
248   If the top is invalid and the next is the max size, stack it empty
249   BLOCK END - SmallStack::IsEmpty
250   -
251   *
252   *
253   *
254   *
255   *
256   Defines SmallStack::Contains with one argument: an item
257   BLOCK START - SmallStack::Contains
258   If the stack is empty or the item matches, return true
259   If there is space in the stack...
260   Acquire the mutex
261   Set the  current item pointer
262   Start a loop through all the stack items...
263   Get the next item from the stack...
264   after cast-fu...
265   If the item in the stack matches the input item, return true
266   Repeat loop while there are items in the stack
267   End check for space in the stack
268   Item is not in the stack
269   BLOCK END - SmallStack::Contains
270   -
271   Begins the protected section of SmallStack
272   Define a SmallStackPool private variable
273   -
274   *
275   *
276   *
277   Defines SmallStack::Branch with no arguments
278   BLOCK START - SmallStack::Branch
279   If there is space in the stack...
280   Acquire the mutex
281   Increment the branch counter
282   End check for space in the stack
283   BLOCK END - SmallStack::Branch
284   BLOCK END - SmallStack
285   -
286   Header guard end