1 // -*- mode: c; coding: utf-8 -*- */
3 // Copyright 2010, 2011, Matthias Andreas Benkard.
4 // Modifications for lazy eval: Copyright 2011, Christoph-Simon Senjak
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.
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.
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 //-----------------------------------------------------------------------------
22 // An implementation of a bitmapped Patricia tree.
24 #ifndef __BITMAPPED_PATRICIA_TREE_H
25 #define __BITMAPPED_PATRICIA_TREE_H
33 #define BPT_ENABLE_DEALLOC_HOOKS 1
35 /* these values are normally set by the configure script of mulklib */
37 typedef intptr_t bpt_key_t;
38 typedef intptr_t bpt_key_bitmask_t;
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))
52 typedef struct bpt *bpt_t;
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);
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));