bitmapped_patricia_tree.h

   1 // -*- mode: c; coding: utf-8 -*- */
   2 //
   3 // Copyright 2010, 2011, Matthias Andreas Benkard.
   4 // Modifications for lazy eval: Copyright 2011, Christoph-Simon Senjak
   5 //
   6 //-----------------------------------------------------------------------------
   7 // This program is free software: you can redistribute it and/or modify
   8 // it under the terms of the GNU Affero General Public License as published by
   9 // the Free Software Foundation, either version 3 of the License, or
  10 // (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU Affero General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU Affero General Public License
  18 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 //-----------------------------------------------------------------------------
  20 //
  21
  22 // An implementation of a bitmapped Patricia tree.
  23
  24 #ifndef __BITMAPPED_PATRICIA_TREE_H
  25 #define __BITMAPPED_PATRICIA_TREE_H
  26
  27 #include <stdbool.h>
  28 #include <stdint.h>
  29 #include <stdlib.h>
  30 #include <stdint.h>
  31 #include <math.h>
  32
  33 #define BPT_ENABLE_DEALLOC_HOOKS 1
  34
  35 /* these values are normally set by the configure script of mulklib */
  36
  37 typedef intptr_t bpt_key_t;
  38 typedef intptr_t bpt_key_bitmask_t;
  39
  40 #define CHUNK_LENGTH ((int)log2(sizeof(bpt_key_bitmask_t)*8))
  41 #define KEY_LENGTH (sizeof(bpt_key_t)*8)
  42 #define OFFSET_MASK ((1 << CHUNK_LENGTH) - 1)
  43 #define MAX_CHUNKS (KEY_LENGTH / CHUNK_LENGTH + ((KEY_LENGTH % CHUNK_LENGTH == 0) ? 0 : 1))
  44 #define LAST_CHUNK_LENGTH (KEY_LENGTH - ((MAX_CHUNKS - 1) * CHUNK_LENGTH))
  45
  46 enum bpt_tag {
  47   BPT_LEAF,
  48   BPT_INNER_NODE
  49 };
  50
  51 struct bpt;
  52 typedef struct bpt *bpt_t;
  53
  54 void *bpt_get(bpt_t bpt, bpt_key_t key);
  55 bool bpt_has_key(bpt_t bpt, bpt_key_t key);
  56 void **bpt_get_pointer(bpt_t bpt, bpt_key_t key);
  57 bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *item);
  58 bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key);
  59 void init_bpt_leaf(bpt_t leaf, bpt_key_t key, void *value);
  60 bpt_t bpt_make_leaf(bpt_key_t key, void *value);
  61 void bpt_retain(bpt_t bpt);
  62 void bpt_release(bpt_t bpt);
  63 void bpt_dealloc(bpt_t bpt);
  64 void bpt_seal(bpt_t bpt);
  65
  66 #ifdef BPT_ENABLE_DEALLOC_HOOKS
  67 void bpt_set_dealloc_hook(bpt_t bpt, bpt_key_t key, void (*hook)(bpt_key_t key, void* value));
  68 #endif
  69 #endif