hb-alloc-pool.hh (3637B)
1 /* 2 * This is part of HarfBuzz, a text shaping library. 3 * 4 * Permission is hereby granted, without written agreement and without 5 * license or royalty fees, to use, copy, modify, and distribute this 6 * software and its documentation for any purpose, provided that the 7 * above copyright notice and the following two paragraphs appear in 8 * all copies of this software. 9 * 10 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 11 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 12 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 13 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 14 * DAMAGE. 15 * 16 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 17 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 18 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 19 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 20 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 21 * 22 * Author(s): Behdad Esfahbod 23 */ 24 25 #ifndef HB_ALLOC_POOL_HH 26 #define HB_ALLOC_POOL_HH 27 28 #include "hb-vector.hh" 29 30 /* Memory pool for persistent small- to medium-sized allocations. 31 * 32 * Some AI musings on this, not necessarily true: 33 * 34 * This is a very simple implementation, but it's good enough for our 35 * purposes. It's not thread-safe. It's not very fast. It's not 36 * very memory efficient. It's not very cache efficient. It's not 37 * very anything efficient. But it's simple and it works. And it's 38 * good enough for our purposes. If you need something more 39 * sophisticated, use a real allocator. Or use a real language. */ 40 41 struct hb_alloc_pool_t 42 { 43 unsigned ChunkSize = 65536 - 2 * sizeof (void *); 44 45 void *alloc (size_t size, unsigned alignment = 2 * sizeof (void *)) 46 { 47 if (unlikely (chunks.in_error ())) return nullptr; 48 49 assert (alignment > 0); 50 assert (alignment <= 2 * sizeof (void *)); 51 assert ((alignment & (alignment - 1)) == 0); /* power of two */ 52 53 if (size > (ChunkSize) / 4) 54 { 55 /* Big chunk, allocate separately. */ 56 hb_vector_t<char> chunk; 57 if (unlikely (!chunk.resize (size))) return nullptr; 58 void *ret = chunk.arrayZ; 59 chunks.push (std::move (chunk)); 60 if (chunks.in_error ()) return nullptr; 61 if (chunks.length > 1) 62 { 63 // Bring back the previous last chunk to the end, so that 64 // we can continue to allocate from it. 65 hb_swap (chunks.arrayZ[chunks.length - 1], chunks.arrayZ[chunks.length - 2]); 66 } 67 return ret; 68 } 69 70 unsigned pad = (unsigned) ((alignment - ((uintptr_t) current_chunk.arrayZ & (alignment - 1))) & (alignment - 1)); 71 72 // Small chunk, allocate from the last chunk. 73 if (current_chunk.length < pad + size) 74 { 75 chunks.push (); 76 if (unlikely (chunks.in_error ())) return nullptr; 77 hb_vector_t<char> &chunk = chunks.arrayZ[chunks.length - 1]; 78 if (unlikely (!chunk.resize (ChunkSize))) return nullptr; 79 current_chunk = chunk; 80 pad = (unsigned) ((alignment - ((uintptr_t) current_chunk.arrayZ & (alignment - 1))) & (alignment - 1)); 81 } 82 83 current_chunk += pad; 84 85 assert (current_chunk.length >= size); 86 void *ret = current_chunk.arrayZ; 87 current_chunk += size; 88 return ret; 89 } 90 91 void discard (void *p_, size_t size) 92 { 93 // Reclaim memory if we can. 94 char *p = (char *) p_; 95 if (current_chunk.arrayZ == p + size && current_chunk.backwards_length >= size) 96 current_chunk -= size; 97 } 98 99 private: 100 hb_vector_t<hb_vector_t<char>> chunks; 101 hb_array_t<char> current_chunk; 102 }; 103 104 105 #endif /* HB_ALLOC_POOL_HH */