1 static void bset_build_tree_noalloc(struct btree *b, unsigned set)
   2 {
   3         struct bset *i          = b->sets[set];
   4         struct bset_tree *t     = &b->tree[set];
   5 
   6         unsigned mantissa(struct bkey *k, struct bkey_float *f)
   7         {
   8                 if (f->exponent < 64)
   9                         return (k->key >> f->exponent) |
  10                                 (k->header << (64 - f->exponent));
  11                 else if (f->exponent < 127)
  12                         return k->header >> (f->exponent - 64);
  13                 return 0;
  14         }
  15 
  16         int dif(struct bkey *k, unsigned mid)
  17         {
  18                 return (((uint64_t *) k) - i->d) - mid;
  19         }
  20 
  21         bool check(struct bkey *k, struct bkey_float *f, unsigned mid)
  22         {
  23                 if (mantissa(k, f) == mantissa(prev(k), f))
  24                         return false;
  25                 f->m = dif(k, mid);
  26                 return true;
  27         }
  28 
  29         void make_key(struct bkey_float *f, unsigned l, unsigned r)
  30         {
  31                 struct bkey *kl = node(i, l), *kr = node(i, r);
  32                 unsigned m, mid = (l + r) >> 1;
  33 
  34                 m = mid == r ? mid : bset_middle(i, l, r);
  35 
  36                 if (kr == end(i))
  37                         kr = prev(kr);
  38 
  39                 if (kl != i->start)
  40                         kl = prev(kl);
  41 
  42                 if (KEY_DEV(kl) != KEY_DEV(kr))
  43                         f->exponent = fls64(KEY_DEV(kr) ^ KEY_DEV(kl)) + 64;
  44                 else if (kl->key != kr->key)
  45                         f->exponent = fls64(kr->key ^ kl->key);
  46 
  47                 f->exponent = max_t(int, f->exponent - BKEY_MANTISSA_BITS, 0);
  48 
  49                 kl = node(i, m);
  50                 kr = next(kl);
  51 
  52                 while (1) {
  53                         if (-dif(kl, mid) < dif(kr, mid)) {
  54                                 if (dif(kl, mid) * 2 < dif(node(i, l), mid) ||
  55                                     dif(kl, mid) < BKEY_MID_MIN)
  56                                         goto no_pivot;
  57 
  58                                 if (check(kl, f, mid))
  59                                         goto pivot;
  60 
  61                                 kl = prev(kl);
  62                         } else {
  63                                 if (dif(kr, mid) * 2 > dif(node(i, r), mid) ||
  64                                     dif(kr, mid) > BKEY_MID_MAX)
  65                                         goto no_pivot;
  66 
  67                                 if (check(kr, f, mid))
  68                                         goto pivot;
  69 
  70                                 kr = next(kr);
  71                         }
  72                 }
  73 
  74                 if (0) {
  75 no_pivot:               f->m = m - mid;
  76                         f->exponent = 127;
  77                 } else {
  78 pivot:                  m = mid + f->m;
  79                         f->mantissa = mantissa(node(i, m), f);
  80                 }
  81 
  82                 BUG_ON(m < l || m > r);
  83                 BUG_ON(!KEY_IS_HEADER(node(i, m)));
  84         }
  85 
  86         struct {
  87                 unsigned pc:2;
  88                 unsigned j:20;
  89                 unsigned l:21;
  90                 unsigned r:21;
  91         } stack[20], *sp = stack;
  92 
  93         sp->pc = 0;
  94         sp->j = 1;
  95         sp->l = 0;
  96         sp->r = i->keys;
  97 
  98         bkey_copy_key(&t->end, prev(end(i)));
  99 
 100         while (sp >= stack) {
 101                 struct bkey_float *f = &t->key[sp->j];
 102                 unsigned m;
 103 
 104                 if (sp->j < t->size) {
 105                         make_key(f, sp->l, sp->r);
 106                         m = ((sp->l + sp->r) >> 1) + f->m;
 107                 } else
 108                         sp->pc = 2;
 109 
 110                 switch (sp->pc++) {
 111                 case 0:
 112                         sp[1].pc = 0;
 113                         sp[1].j = sp->j * 2;
 114                         sp[1].l = sp->l;
 115                         sp[1].r = m;
 116                         sp++;
 117                         break;
 118                 case 1:
 119                         sp[1].pc = 0;
 120                         sp[1].j = sp->j * 2 + 1;
 121                         sp[1].l = m;
 122                         sp[1].r = sp->r;
 123                         sp++;
 124                         break;
 125                 case 2:
 126                         --sp;
 127                 }
 128         }
 129 }