1 /* Copyright (C) 2011 Wildfire Games.
2 *
3 * Permission is hereby granted, free of charge, to any person obtaining
4 * a copy of this software and associated documentation files (the
5 * "Software"), to deal in the Software without restriction, including
6 * without limitation the rights to use, copy, modify, merge, publish,
7 * distribute, sublicense, and/or sell copies of the Software, and to
8 * permit persons to whom the Software is furnished to do so, subject to
9 * the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included
12 * in all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 */
22
23 #ifndef INCLUDED_ALLOCATORS_FREELIST
24 #define INCLUDED_ALLOCATORS_FREELIST
25
26 // "freelist" is a pointer to the first unused element or a sentinel.
27 // their memory holds a pointer to the previous element in the freelist
28 // (or its own address in the case of sentinels to avoid branches)
29 //
30 // rationale for the function-based interface: a class encapsulating the
31 // freelist pointer would force each header to include this header,
32 // whereas this approach only requires a void* pointer and calling
33 // mem_freelist_Sentinel from the implementation.
34 //
35 // these functions are inlined because allocation is sometimes time-critical.
36
37 // @return the address of a sentinel element, suitable for initializing
38 // a freelist pointer. subsequent mem_freelist_Detach on that freelist
39 // will return 0.
40 LIB_API void* mem_freelist_Sentinel();
41
mem_freelist_AddToFront(void * & freelist,void * el)42 static inline void mem_freelist_AddToFront(void*& freelist, void* el)
43 {
44 ASSERT(freelist != 0);
45 ASSERT(el != 0);
46
47 memcpy(el, &freelist, sizeof(void*));
48 freelist = el;
49 }
50
51 // @return 0 if the freelist is empty, else a pointer that had
52 // previously been passed to mem_freelist_AddToFront.
mem_freelist_Detach(void * & freelist)53 static inline void* mem_freelist_Detach(void*& freelist)
54 {
55 ASSERT(freelist != 0);
56
57 void* prev_el;
58 memcpy(&prev_el, freelist, sizeof(void*));
59 void* el = (freelist == prev_el)? 0 : freelist;
60 freelist = prev_el;
61 return el;
62 }
63
64 #endif // #ifndef INCLUDED_ALLOCATORS_FREELIST
65