| 1 | #ifndef OIDTREE_H |
| 2 | #define OIDTREE_H |
| 3 | |
| 4 | #include "cbtree.h" |
| 5 | #include "hash.h" |
| 6 | #include "mem-pool.h" |
| 7 | |
| 8 | /* |
| 9 | * OID trees are an efficient storage for object IDs that use a critbit tree |
| 10 | * internally. Common prefixes are duplicated and object IDs are stored in a |
| 11 | * way that allow easy iteration over the objects in lexicographic order. As a |
| 12 | * consequence, operations that want to enumerate all object IDs that match a |
| 13 | * given prefix can be answered efficiently. |
| 14 | * |
| 15 | * Note that it is not (yet) possible to store data other than the object IDs |
| 16 | * themselves in this tree. |
| 17 | */ |
| 18 | struct oidtree { |
| 19 | struct cb_tree tree; |
| 20 | struct mem_pool mem_pool; |
| 21 | }; |
| 22 | |
| 23 | /* Initialize the oidtree so that it is ready for use. */ |
| 24 | void oidtree_init(struct oidtree *ot); |
| 25 | |
| 26 | /* |
| 27 | * Release all memory associated with the oidtree and reinitialize it for |
| 28 | * subsequent use. |
| 29 | */ |
| 30 | void oidtree_clear(struct oidtree *ot); |
| 31 | |
| 32 | /* |
| 33 | * Insert the object ID into the tree and store the given pointer alongside |
| 34 | * with it. The data pointer of any preexisting entry will be overwritten. |
| 35 | */ |
| 36 | void oidtree_insert(struct oidtree *ot, const struct object_id *oid, |
| 37 | void *data); |
| 38 | |
| 39 | /* Check whether the tree contains the given object ID. */ |
| 40 | bool oidtree_contains(struct oidtree *ot, const struct object_id *oid); |
| 41 | |
| 42 | /* Get the payload stored with the given object ID. */ |
| 43 | void *oidtree_get(struct oidtree *ot, const struct object_id *oid); |
| 44 | |
| 45 | /* |
| 46 | * Callback function used for `oidtree_each()`. Returning a non-zero exit code |
| 47 | * will cause iteration to stop. The exit code will be propagated to the caller |
| 48 | * of `oidtree_each()`. |
| 49 | */ |
| 50 | typedef int (*oidtree_each_cb)(const struct object_id *oid, |
| 51 | void *node_data, |
| 52 | void *cb_data); |
| 53 | |
| 54 | /* |
| 55 | * Iterate through all object IDs in the tree whose prefix matches the given |
| 56 | * object ID prefix and invoke the callback function on each of them. |
| 57 | * |
| 58 | * Returns any non-zero exit code from the provided callback function. |
| 59 | */ |
| 60 | int oidtree_each(struct oidtree *ot, |
| 61 | const struct object_id *prefix, size_t prefix_hex_len, |
| 62 | oidtree_each_cb cb, void *cb_data); |
| 63 | |
| 64 | #endif /* OIDTREE_H */ |