src/hb-pool.hh

   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
  43 template <typename T, unsigned ChunkLen = 32>
  44 struct 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 */