contrib/jemalloc/src/rtree.c

   1 #define JEMALLOC_RTREE_C_
   2 #include "jemalloc/internal/jemalloc_internal.h"
   3
   4 static unsigned
   5 hmin(unsigned ha, unsigned hb)
   6 {
   7
   8         return (ha < hb ? ha : hb);
   9 }
  10
  11 /* Only the most significant bits of keys passed to rtree_[gs]et() are used. */
  12 bool
  13 rtree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc,
  14     rtree_node_dalloc_t *dalloc)
  15 {
  16         unsigned bits_in_leaf, height, i;
  17
  18         assert(RTREE_HEIGHT_MAX == ((ZU(1) << (LG_SIZEOF_PTR+3)) /
  19             RTREE_BITS_PER_LEVEL));
  20         assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3));
  21
  22         bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL
  23             : (bits % RTREE_BITS_PER_LEVEL);
  24         if (bits > bits_in_leaf) {
  25                 height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL;
  26                 if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits)
  27                         height++;
  28         } else
  29                 height = 1;
  30         assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits);
  31
  32         rtree->alloc = alloc;
  33         rtree->dalloc = dalloc;
  34         rtree->height = height;
  35
  36         /* Root level. */
  37         rtree->levels[0].subtree = NULL;
  38         rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL :
  39             bits_in_leaf;
  40         rtree->levels[0].cumbits = rtree->levels[0].bits;
  41         /* Interior levels. */
  42         for (i = 1; i < height-1; i++) {
  43                 rtree->levels[i].subtree = NULL;
  44                 rtree->levels[i].bits = RTREE_BITS_PER_LEVEL;
  45                 rtree->levels[i].cumbits = rtree->levels[i-1].cumbits +
  46                     RTREE_BITS_PER_LEVEL;
  47         }
  48         /* Leaf level. */
  49         if (height > 1) {
  50                 rtree->levels[height-1].subtree = NULL;
  51                 rtree->levels[height-1].bits = bits_in_leaf;
  52                 rtree->levels[height-1].cumbits = bits;
  53         }
  54
  55         /* Compute lookup table to be used by rtree_start_level(). */
  56         for (i = 0; i < RTREE_HEIGHT_MAX; i++) {
  57                 rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height -
  58                     1);
  59         }
  60
  61         return (false);
  62 }
  63
  64 static void
  65 rtree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level)
  66 {
  67
  68         if (level + 1 < rtree->height) {
  69                 size_t nchildren, i;
  70
  71                 nchildren = ZU(1) << rtree->levels[level].bits;
  72                 for (i = 0; i < nchildren; i++) {
  73                         rtree_node_elm_t *child = node[i].child;
  74                         if (child != NULL)
  75                                 rtree_delete_subtree(rtree, child, level + 1);
  76                 }
  77         }
  78         rtree->dalloc(node);
  79 }
  80
  81 void
  82 rtree_delete(rtree_t *rtree)
  83 {
  84         unsigned i;
  85
  86         for (i = 0; i < rtree->height; i++) {
  87                 rtree_node_elm_t *subtree = rtree->levels[i].subtree;
  88                 if (subtree != NULL)
  89                         rtree_delete_subtree(rtree, subtree, i);
  90         }
  91 }
  92
  93 static rtree_node_elm_t *
  94 rtree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp)
  95 {
  96         rtree_node_elm_t *node;
  97
  98         if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) {
  99                 /*
 100                  * Another thread is already in the process of initializing.
 101                  * Spin-wait until initialization is complete.
 102                  */
 103                 do {
 104                         CPU_SPINWAIT;
 105                         node = atomic_read_p((void **)elmp);
 106                 } while (node == RTREE_NODE_INITIALIZING);
 107         } else {
 108                 node = rtree->alloc(ZU(1) << rtree->levels[level].bits);
 109                 if (node == NULL)
 110                         return (NULL);
 111                 atomic_write_p((void **)elmp, node);
 112         }
 113
 114         return (node);
 115 }
 116
 117 rtree_node_elm_t *
 118 rtree_subtree_read_hard(rtree_t *rtree, unsigned level)
 119 {
 120
 121         return (rtree_node_init(rtree, level, &rtree->levels[level].subtree));
 122 }
 123
 124 rtree_node_elm_t *
 125 rtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level)
 126 {
 127
 128         return (rtree_node_init(rtree, level, &elm->child));
 129 }