bitmapped_patricia_tree.c

   1 // -*- mode: c; coding: utf-8 -*- */
   2 //
   3 // Copyright 2010, 2011, Matthias Andreas Benkard.
   4 //
   5 //-----------------------------------------------------------------------------
   6 // This program is free software: you can redistribute it and/or modify
   7 // it under the terms of the GNU Affero General Public License as published by
   8 // the Free Software Foundation, either version 3 of the License, or
   9 // (at your option) any later version.
  10 //
  11 // This program is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU Affero General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Affero General Public License
  17 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 //-----------------------------------------------------------------------------
  19 //
  20
  21 // An implementation of a bitmapped Patricia tree.
  22
  23 //// Purpose ////
  24 //
  25 // The idea is to use a locally mutable, bitmapped Patricia tree as a
  26 // variable binding store (i.e. environment) in compiled code.  In this
  27 // way, there is no need for excessive copying when an independent
  28 // environment must be set up (such as when initiating the processing of
  29 // a new node in the search space).  Instead, significant amounts of
  30 // structure can be shared between child and parent environments.
  31
  32 //// Motivation ////
  33 //
  34 // 1. Patricia trees are very amenable to structure sharing.
  35 //
  36 // 2. Furthermore, big-endian Patricia trees are especially efficient
  37 //    when indices are allocated sequentially, as is the case for
  38 //    variables in code emitted by our compiler.
  39 //
  40 // 3. Finally, bitmapping improves the performance of copying because
  41 //    copying an array is much cheaper than copying an equivalent branch
  42 //    in a tree.  As we need to shallow-copy the tree at potentially
  43 //    each choice point, copying needs to be fast.
  44
  45
  46 #include <stdlib.h>
  47 #include <string.h>
  48 #include <assert.h>
  49
  50 #include "bitmapped_patricia_tree.h"
  51
  52 typedef struct bpt_nonempty *bpt_nonempty_t;
  53 typedef struct bpt_node *bpt_node_t;
  54 typedef struct bpt_leaf *bpt_leaf_t;
  55
  56 struct bpt {
  57   enum bpt_tag tag;
  58   int refcount;
  59   bool mutable;
  60   bpt_key_t prefix;
  61 };
  62
  63 struct bpt_leaf {
  64   struct bpt bpt;  // poor man's inheritance
  65   void *value;
  66 #ifdef BPT_ENABLE_DEALLOC_HOOKS
  67   void (*dealloc_hook)(bpt_key_t, void *);   // not actually used anywhere in client code
  68 #endif
  69 };
  70
  71 struct bpt_node {
  72   struct bpt bpt;  // poor man's inheritance
  73   unsigned int branching_chunk;
  74   bpt_key_bitmask_t bitmask;
  75   bpt_t *children;
  76 };
  77
  78
  79 void init_bpt_leaf(bpt_t a_leaf, bpt_key_t key, void *value) {
  80   bpt_leaf_t leaf = (bpt_leaf_t)a_leaf;
  81   leaf->bpt.tag = BPT_LEAF;
  82   leaf->bpt.mutable = true;
  83   leaf->bpt.prefix = key;
  84   leaf->value = value;
  85 #ifdef BPT_ENABLE_DEALLOC_HOOKS
  86   leaf->dealloc_hook = NULL;
  87 #endif
  88   leaf->bpt.refcount = 1;
  89 }
  90
  91 void init_bpt_node(bpt_node_t node, bpt_key_t prefix, unsigned int branching_chunk) {
  92   node->bpt.tag = BPT_INNER_NODE;
  93   node->bpt.mutable = true;
  94   node->bpt.prefix = prefix;
  95   node->branching_chunk = branching_chunk;
  96   node->bitmask = 0;
  97   node->children = NULL;
  98   node->bpt.refcount = 1;
  99 }
 100
 101
 102 bpt_t bpt_make_leaf(bpt_key_t key, void *value) {
 103   bpt_leaf_t leaf = malloc(sizeof *leaf);
 104   init_bpt_leaf((bpt_t)leaf, key, value);
 105   return (bpt_t)leaf;
 106 }
 107
 108 bpt_node_t bpt_make_node(bpt_key_t prefix, unsigned int branching_chunk) {
 109   bpt_node_t node = malloc(sizeof *node);
 110   init_bpt_node(node, prefix, branching_chunk);
 111   return node;
 112 }
 113
 114
 115 static inline unsigned int bpt_number_of_leading_zeros(bpt_key_t x);
 116 static inline unsigned int bpt_number_of_trailing_zeros(bpt_key_t x);
 117 static inline unsigned int bpt_popcount(bpt_key_bitmask_t key);
 118 static unsigned int bpt_compute_child_index(bpt_key_bitmask_t bitmask, unsigned int child_number);
 119 static inline uint_fast8_t bpt_offset_of_key(bpt_key_t key, unsigned int branching_chunk);
 120 static bpt_key_t bpt_prefix_of_key(bpt_key_t key, unsigned int branching_chunk);
 121 static inline unsigned int bpt_branching_chunk(bpt_t bpt);
 122 static unsigned int bpt_find_diverging_chunk(bpt_key_t key1, bpt_key_t key2);
 123 static void bpt_for_children(bpt_t bpt, void (*thunk)(bpt_t));
 124
 125
 126 static void bpt_for_children(bpt_t bpt, void (*thunk)(bpt_t)) {
 127   if (bpt && bpt->tag == BPT_INNER_NODE) {
 128     bpt_node_t b = (bpt_node_t)bpt;
 129     bpt_t *iter = b->children;
 130     bpt_t *children_end = b->children + bpt_popcount(b->bitmask);
 131     while (iter < children_end) {
 132       thunk(*iter);
 133       iter++;
 134     }
 135   }
 136 }
 137
 138 void *bpt_get(bpt_t bpt, bpt_key_t key) {
 139   void **pointer = bpt_get_pointer(bpt, key);
 140   if (pointer) {
 141     return *pointer;
 142   } else {
 143     return NULL;
 144   }
 145 }
 146
 147 bpt_leaf_t bpt_get_leaf(bpt_t bpt, bpt_key_t key)
 148 {
 149   if (!bpt) {
 150     return NULL;
 151   } else if (bpt->tag == BPT_LEAF) {
 152     bpt_leaf_t b = (bpt_leaf_t)bpt;
 153     if (bpt->prefix == key) {
 154       return b;
 155     } else {
 156       return NULL;
 157     }
 158   } else {
 159     bpt_node_t b = (bpt_node_t)bpt;
 160     int child_number = bpt_offset_of_key(key, b->branching_chunk);
 161     if ((1 << child_number) & b->bitmask) {
 162       int child_index = bpt_compute_child_index(b->bitmask, child_number);
 163       return bpt_get_leaf(b->children[child_index], key);
 164     } else {
 165       return NULL;
 166     }
 167   }
 168 }
 169
 170 void **bpt_get_pointer(bpt_t bpt, bpt_key_t key)
 171 {
 172   bpt_leaf_t leaf = bpt_get_leaf(bpt, key);
 173   if (!leaf) {
 174     return NULL;
 175   } else {
 176     return &leaf->value;
 177   }
 178 }
 179
 180 bool bpt_has_key(bpt_t bpt, bpt_key_t key) {
 181   return (bpt_get_leaf(bpt, key) != NULL);
 182 }
 183
 184 bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *value) {
 185   if (!bpt) {
 186     return (bpt_t)bpt_make_leaf(key, value);
 187   } else {
 188     bpt_key_t prefix = bpt->prefix;
 189     if (bpt_prefix_of_key(key, bpt_branching_chunk(bpt)) != prefix) {
 190       unsigned int diverging_chunk = bpt_find_diverging_chunk(key, prefix);
 191       bpt_key_t my_number_in_parent = bpt_offset_of_key(prefix, diverging_chunk);
 192       bpt_key_t their_number_in_parent = bpt_offset_of_key(key, diverging_chunk);
 193       bpt_node_t new_node = bpt_make_node(bpt_prefix_of_key(prefix, diverging_chunk), diverging_chunk);
 194       new_node->bitmask = (1 << my_number_in_parent) | (1 << their_number_in_parent);
 195       new_node->children = malloc(sizeof (*new_node->children) * 2);
 196       if (my_number_in_parent < their_number_in_parent) {
 197         new_node->children[0] = bpt;
 198         new_node->children[1] = bpt_make_leaf(key, value);
 199       } else {
 200         new_node->children[0] = bpt_make_leaf(key, value);
 201         new_node->children[1] = bpt;
 202       }
 203       bpt_retain(bpt);
 204       return (bpt_t)new_node;
 205     } else {
 206       if (bpt->tag == BPT_LEAF) {
 207         bpt_leaf_t b = (bpt_leaf_t)bpt;
 208         if (bpt->mutable) {
 209           b->value = value;
 210           bpt_retain(bpt);
 211           return bpt;
 212         } else {
 213           return (bpt_t)bpt_make_leaf(key, value);
 214         }
 215       } else {
 216         bpt_node_t b = (bpt_node_t)bpt;
 217         uint_fast8_t child_number = bpt_offset_of_key(key, b->branching_chunk);
 218         unsigned int child_index = bpt_compute_child_index(b->bitmask, child_number);
 219         if ((1 << child_number) & b->bitmask) {
 220           // We already have a child to pass the value to.  Do that.
 221           bpt_t child = b->children[child_index];
 222           bpt_t new_child = bpt_assoc(child, key, value);
 223           if (new_child == child) {
 224             bpt_release(child);
 225             bpt_retain(bpt);
 226             return bpt;
 227           } else {
 228             if (bpt->mutable) {
 229               bpt_release(child);
 230               b->children[child_index] = new_child;
 231               bpt_retain(bpt);
 232               return bpt;
 233             } else {
 234               bpt_node_t new_node = malloc(sizeof *new_node);
 235               *new_node = *b;
 236               new_node->bpt.refcount = 1;
 237               new_node->bpt.mutable = true;
 238               unsigned int number_of_children = bpt_popcount(b->bitmask);
 239               size_t size_of_child_array = sizeof (*new_node->children) * number_of_children;
 240               new_node->children = malloc(size_of_child_array);
 241               memcpy(new_node->children, b->children, size_of_child_array);
 242               new_node->children[child_index] = new_child;
 243               // Retain the children copied into the new node.
 244               bpt_for_children((bpt_t)new_node, bpt_retain);
 245               bpt_release(new_child);
 246               return (bpt_t)new_node;
 247             }
 248           }
 249         } else {
 250           // Create a new child.
 251           unsigned int number_of_children = bpt_popcount(b->bitmask);
 252           size_t new_size_of_child_array = sizeof (*b->children) * (number_of_children + 1);
 253           if (bpt->mutable) {
 254             b->children = realloc(b->children, new_size_of_child_array);
 255             memmove(b->children + child_index + 1, b->children + child_index, sizeof (*b->children) * (number_of_children - child_index));
 256             b->children[child_index] = bpt_make_leaf(key, value);
 257             b->bitmask |= 1 << child_number;
 258             bpt_retain(bpt);
 259             return bpt;
 260           } else {
 261             bpt_t *new_children = malloc(new_size_of_child_array);
 262             memcpy(new_children, b->children, sizeof (*b->children) * child_index);
 263             memcpy(new_children + child_index + 1,
 264                    b->children + child_index,
 265                    sizeof (*b->children) * (number_of_children - child_index));
 266             new_children[child_index] = bpt_make_leaf(key, value);
 267             bpt_node_t new_node = bpt_make_node(b->bpt.prefix, b->branching_chunk);
 268             new_node->children = new_children;
 269             new_node->bitmask = b->bitmask | (1 << child_number);
 270             // Retain the children copied into the new node.
 271             bpt_for_children(bpt, bpt_retain);
 272             return (bpt_t)new_node;
 273           }
 274         }
 275       }
 276     }
 277   }
 278 }
 279
 280
 281 bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key) {
 282   if (!bpt || (bpt_prefix_of_key(key, bpt_branching_chunk(bpt)) != bpt->prefix)) {
 283     bpt_retain(bpt);
 284     return bpt;
 285   } else if (bpt->tag == BPT_LEAF) {
 286     // Key matches.
 287     return NULL;
 288   } else {
 289     // Prefix matches.
 290     bpt_node_t b = (bpt_node_t)bpt;
 291     uint_fast8_t child_number = bpt_offset_of_key(key, b->branching_chunk);
 292     if ((1 << child_number) & b->bitmask) {
 293       unsigned int child_index = bpt_compute_child_index(b->bitmask, child_number);
 294       bpt_t child = b->children[child_index];
 295       bpt_t new_child = bpt_dissoc(child, key);
 296       if (new_child == child) {
 297         bpt_release(child);
 298         bpt_retain(bpt);
 299         return bpt;
 300       } else {
 301         unsigned int number_of_children = bpt_popcount(b->bitmask);
 302         if (!new_child && number_of_children == 2) {
 303           // When there is only a single child left, we replace ourselves
 304           // with that child.
 305           bpt_t remaining_child = b->children[1-child_index];
 306           bpt_retain(remaining_child);
 307           return remaining_child;
 308         } else if (bpt->mutable) {
 309           bpt_release(child);
 310           if (!new_child) {
 311             // We don't reallocate the array because it wouldn't really
 312             // gain us anything (except maybe non-confusion of a
 313             // conservative GC).
 314             memmove(b->children + child_index, b->children + child_index + 1, sizeof(*b->children) * (number_of_children - child_index - 1));
 315             b->bitmask &= ~(1 << child_number);
 316             bpt_retain(bpt);
 317             return bpt;
 318           } else {
 319             b->children[child_index] = new_child;
 320             bpt_retain(bpt);
 321             return bpt;
 322           }
 323         } else {
 324           // If all else fails, allocate a new node.
 325           bpt_t *new_children;
 326           bpt_key_bitmask_t bitmask;
 327           if (!new_child) {
 328             new_children = malloc((sizeof *new_children) * (number_of_children - 1));
 329             memcpy(new_children, b->children, sizeof (*b->children) * child_index);
 330             memcpy(new_children + child_index,
 331                    b->children + child_index + 1,
 332                    sizeof (*b->children) * (number_of_children - child_index - 1));
 333             bitmask = b->bitmask & ~(1 << child_number);
 334           } else {
 335             new_children = malloc((sizeof *new_children) * number_of_children);
 336             memcpy(new_children, b->children, sizeof (*b->children) * number_of_children);
 337             new_children[child_index] = new_child;
 338             bitmask = b->bitmask;
 339           }
 340           bpt_node_t new_node = bpt_make_node(b->bpt.prefix, b->branching_chunk);
 341           new_node->children = new_children;
 342           new_node->bitmask = bitmask;
 343           // Retain the children copied into the new node.
 344           bpt_for_children((bpt_t)new_node, bpt_retain);
 345           bpt_release(new_child);
 346           return (bpt_t)new_node;
 347         }
 348       }
 349     } else {
 350       bpt_retain(bpt);
 351       return bpt;
 352     }
 353   }
 354 }
 355
 356
 357 void bpt_seal(bpt_t bpt) {
 358   if (bpt) {
 359     if (bpt->mutable) {
 360       bpt->mutable = false;
 361       if (bpt->tag == BPT_INNER_NODE) {
 362         bpt_for_children(bpt, bpt_seal);
 363       }
 364     }
 365   }
 366 }
 367
 368
 369 /////////////// Helper functions ///////////////
 370 static unsigned int bpt_compute_child_index(bpt_key_bitmask_t bitmask, unsigned int child_number) {
 371   // Compute the sparse array index given a flat array index.
 372   return bpt_popcount(bitmask & ((1 << child_number) - 1));
 373 }
 374
 375 static inline uint_fast8_t bpt_offset_of_key(bpt_key_t key, unsigned int chunk_number) {
 376   // Little-enidan:
 377   //return (key >> (chunk_number * CHUNK_LENGTH)) & OFFSET_MASK;
 378   // Big-endian:
 379   int shift = 0;
 380   if (chunk_number <= MAX_CHUNKS - 2) {
 381     shift += LAST_CHUNK_LENGTH;
 382   }
 383   if (chunk_number <= MAX_CHUNKS - 3) {
 384     shift += ((MAX_CHUNKS - 2 - chunk_number) * CHUNK_LENGTH);
 385   }
 386   return (key >> shift) & (chunk_number == MAX_CHUNKS - 1 ? ((1 << LAST_CHUNK_LENGTH) - 1) : OFFSET_MASK);
 387 }
 388
 389 static bpt_key_t bpt_prefix_of_key(bpt_key_t key, unsigned int chunk_number) {
 390   if (chunk_number == MAX_CHUNKS) {
 391     return key;
 392   } else {
 393     // Little-endian:
 394     //return key & ((1 << (chunk_number * CHUNK_LENGTH)) - 1)
 395     // Big-endian:
 396     return key & (((1 << (chunk_number * CHUNK_LENGTH)) - 1) << (KEY_LENGTH - (chunk_number * CHUNK_LENGTH)));
 397   }
 398 }
 399
 400 static inline unsigned int bpt_branching_chunk(bpt_t bpt) {
 401   assert(bpt);
 402   if (bpt->tag == BPT_LEAF) {
 403     return MAX_CHUNKS;
 404   } else {
 405     return ((bpt_node_t)bpt)->branching_chunk;
 406   }
 407 }
 408
 409 static inline unsigned int bpt_popcount(bpt_key_bitmask_t x) {
 410   return __builtin_popcountll(x);
 411 }
 412
 413 static inline unsigned int bpt_number_of_leading_zeros(bpt_key_t x) {
 414   return __builtin_clzll(x);
 415 }
 416
 417 static inline unsigned int bpt_number_of_trailing_zeros(bpt_key_t x) {
 418   return __builtin_ctzll(x);
 419 }
 420
 421 static unsigned int bpt_find_diverging_chunk(bpt_key_t a, bpt_key_t b) {
 422   // Little-endian:
 423   //return bpt_number_of_trailing_zeros(a ^ b) / CHUNK_LENGTH;
 424   // Big-endian:
 425   return bpt_number_of_leading_zeros(a ^ b) / CHUNK_LENGTH;
 426 }
 427
 428 void bpt_retain(bpt_t bpt) {
 429   if (bpt) {
 430     __sync_fetch_and_add(&bpt->refcount, 1);
 431   }
 432 }
 433
 434 void bpt_release(bpt_t bpt) {
 435   if (bpt) {
 436     if (__sync_sub_and_fetch(&bpt->refcount, 1) == 0) {
 437       bpt_dealloc(bpt);
 438     }
 439   }
 440 }
 441
 442 void bpt_dealloc(bpt_t bpt) {
 443   if (bpt) {
 444     if (bpt->tag == BPT_LEAF) {
 445       bpt_leaf_t b = (bpt_leaf_t)bpt;
 446 #ifdef BPT_ENABLE_DEALLOC_HOOKS
 447       if (b->dealloc_hook) {
 448         b->dealloc_hook(b->bpt.prefix, b->value);
 449       }
 450 #endif
 451       free(b);
 452     } else {
 453       bpt_node_t b = (bpt_node_t)bpt;
 454       bpt_for_children(bpt, bpt_release);
 455       free(b->children);
 456       free(b);
 457     }
 458   }
 459 }
 460
 461 #ifdef BPT_ENABLE_DEALLOC_HOOKS
 462 void bpt_leaf_set_dealloc_hook(bpt_leaf_t bpt, void (*hook)(bpt_key_t, void*)) {
 463   if (bpt) {
 464     bpt->dealloc_hook = hook;
 465   }
 466 }
 467
 468 void bpt_set_dealloc_hook(bpt_t bpt, bpt_key_t key, void (*hook)(bpt_key_t, void*)) {
 469   bpt_leaf_set_dealloc_hook(bpt_get_leaf(bpt, key), hook);
 470 }
 471 #endif