1/*
2 * Copyright © 2019 Facebook, Inc.
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 *
24 * Facebook Author(s): Behdad Esfahbod
25 */
26
27#ifndef HB_POOL_HH
28#define HB_POOL_HH
29
30#include "hb.hh"
31
32/* Memory pool for persistent allocation of small objects.
33 *
34 * Some AI musings on this, not necessarily true:
35 *
36 * This is a very simple implementation, but it's good enough for our
37 * purposes. It's not thread-safe. It's not very fast. It's not
38 * very memory efficient. It's not very cache efficient. It's not
39 * very anything efficient. But it's simple and it works. And it's
40 * good enough for our purposes. If you need something more
41 * sophisticated, use a real allocator. Or use a real language. */
42
43template <typename T, unsigned ChunkLen = 32>
44struct hb_pool_t
45{
46 hb_pool_t () : next (nullptr) {}
47 ~hb_pool_t ()
48 {
49 next = nullptr;
50
51 + hb_iter (chunks)
52 | hb_apply (hb_free)
53 ;
54 }
55
56 T* alloc ()
57 {
58 if (unlikely (!next))
59 {
60 if (unlikely (!chunks.alloc (chunks.length + 1))) return nullptr;
61 chunk_t *chunk = (chunk_t *) hb_malloc (sizeof (chunk_t));
62 if (unlikely (!chunk)) return nullptr;
63 chunks.push (chunk);
64 next = chunk->thread ();
65 }
66
67 T* obj = next;
68 next = * ((T**) next);
69
70 hb_memset (obj, 0, sizeof (T));
71
72 return obj;
73 }
74
75 void release (T* obj)
76 {
77 * (T**) obj = next;
78 next = obj;
79 }
80
81 private:
82
83 static_assert (ChunkLen > 1, "");
84 static_assert (sizeof (T) >= sizeof (void *), "");
85 static_assert (alignof (T) % alignof (void *) == 0, "");
86
87 struct chunk_t
88 {
89 T* thread ()
90 {
91 for (unsigned i = 0; i < ARRAY_LENGTH (arrayZ) - 1; i++)
92 * (T**) &arrayZ[i] = &arrayZ[i + 1];
93
94 * (T**) &arrayZ[ARRAY_LENGTH (arrayZ) - 1] = nullptr;
95
96 return arrayZ;
97 }
98
99 T arrayZ[ChunkLen];
100 };
101
102 T* next;
103 hb_vector_t<chunk_t *> chunks;
104};
105
106
107#endif /* HB_POOL_HH */
108