aboutsummaryrefslogtreecommitdiff
path: root/bitmapped_patricia_tree.h
blob: 48072564914e94cf21cce1998b1c9173f0b92b0d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// -*- mode: c; coding: utf-8 -*- */
//
// Copyright 2010, 2011, Matthias Andreas Benkard.
//
//-----------------------------------------------------------------------------
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//-----------------------------------------------------------------------------
//

// An implementation of a bitmapped Patricia tree.

#ifndef __BITMAPPED_PATRICIA_TREE_H
#define __BITMAPPED_PATRICIA_TREE_H

#include <stdbool.h>
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

#define BPT_ENABLE_DEALLOC_HOOKS 1

#ifdef BPT_EXPLICIT_CONFIGURATION
typedef BPT_KEY_T         bpt_key_t;
typedef BPT_KEY_BITMASK_T bpt_key_bitmask_t;
#else
typedef int32_t bpt_key_t;
typedef int32_t bpt_key_bitmask_t;
#endif  //!BPT_EXPLICIT_CONFIGURATION

enum bpt_tag {
  BPT_LEAF,
  BPT_INNER_NODE
};

struct bpt;
typedef struct bpt *bpt_t;

// Base functionality.
void *bpt_get(bpt_t bpt, bpt_key_t key);
bool bpt_has_key(bpt_t bpt, bpt_key_t key);
void **bpt_get_pointer(bpt_t bpt, bpt_key_t key);
bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *item);
bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key);
void bpt_retain(bpt_t bpt);
void bpt_release(bpt_t bpt);
void bpt_dealloc(bpt_t bpt);
void bpt_seal(bpt_t bpt);

// Utilities
void bpt_for_mappings(bpt_t bpt, void (*thunk)(bpt_key_t, void*, void*), void *user_data);
#ifdef BPT_ENABLE_DEALLOC_HOOKS
void bpt_set_dealloc_hook(bpt_t bpt, bpt_key_t key, void (*hook)(bpt_key_t key, void* value));
#endif

#ifdef __cplusplus
}
#endif
#endif