flatcc_refmap.h (4819B)
1 /* 2 * The flatcc builder supports storing a pointer to a refmap 3 * and wraps some operations to make them work as a dummy 4 * even if no refmap has been set. This enables optional 5 * DAG preservation possible during clone operations. 6 * 7 * A refmap maps a source address to a builder reference. 8 * 9 * This is just a map, but the semantics are important: 10 * 11 * The map thus preserves identity of the source. It is not a 12 * cache because cache eviction would fail to properly track 13 * identity. 14 * 15 * The map is used for memoization during object cloning are and 16 * may also be used by user logic doing similar operations. 17 * This ensures that identity is preserved so a source object is 18 * not duplicated which could lead to either loss of semantic 19 * information, or an explosion in size, or both. In some, or 20 * even most, cases this concern may not be important, but when 21 * it is important, it is important. 22 * 23 * The source address must not be reused for different content 24 * for the lifetime of the map, although the content doest not 25 * have to be valid or event exist at that location since source 26 * address is just used as a key. 27 * 28 * The lifetime may be a single clone operation which then 29 * tracks child object references as well, or it may be the 30 * lifetime of the buffer builder. 31 * 32 * The map may be flushed explicitly when the source addresses 33 * are no longer unique, such as when reusing a memory buffer, 34 * and when identity preservation is no longer important. 35 * Flushing a map is esentially the same as ending a lifetime. 36 * 37 * Multiple maps may exist concurrently for example if cloning 38 * an object twice into two new objects that should have 39 * separate identities. This is especially true and necessary 40 * when creating a new nested buffer because the nested buffer 41 * cannot share references with the parent. Cloning and object 42 * that contains a nested buffer does not require multiple maps 43 * because the nested buffer is then opaque. 44 */ 45 46 #ifndef FLATCC_REFMAP_H 47 #define FLATCC_REFMAP_H 48 49 #ifdef __cplusplus 50 extern "C" { 51 #endif 52 53 #include "flatcc_types.h" 54 55 #ifndef FLATCC_REFMAP_MIN_BUCKETS 56 /* 8 buckets gives us 5 useful initial entries with a load factor of 0.7 */ 57 #define FLATCC_REFMAP_MIN_BUCKETS 8 58 #endif 59 60 #define FLATCC_REFMAP_LOAD_FACTOR 0.7f 61 62 typedef struct flatcc_refmap flatcc_refmap_t; 63 typedef flatbuffers_soffset_t flatcc_refmap_ref_t; 64 65 static const flatcc_refmap_ref_t flatcc_refmap_not_found = 0; 66 67 struct flatcc_refmap_item { 68 const void *src; 69 flatcc_refmap_ref_t ref; 70 }; 71 72 struct flatcc_refmap { 73 size_t count; 74 size_t buckets; 75 struct flatcc_refmap_item *table; 76 /* Use stack allocation for small maps. */ 77 struct flatcc_refmap_item min_table[FLATCC_REFMAP_MIN_BUCKETS]; 78 }; 79 80 /* 81 * Fast zero initialization - does not allocate any memory. 82 * May be replaced by memset 0, but `init` avoids clearing the 83 * stack allocated initial hash table until it is needed. 84 */ 85 static inline int flatcc_refmap_init(flatcc_refmap_t *refmap) 86 { 87 refmap->count = 0; 88 refmap->buckets = 0; 89 refmap->table = 0; 90 return 0; 91 } 92 93 /* 94 * Removes all items and deallocates memory. 95 * Not required unless `insert` or `resize` took place. The map can be 96 * reused subsequently without calling `init`. 97 */ 98 void flatcc_refmap_clear(flatcc_refmap_t *refmap); 99 100 /* 101 * Keeps allocated memory as is, but removes all items. The map 102 * must intialized first. 103 */ 104 void flatcc_refmap_reset(flatcc_refmap_t *refmap); 105 106 /* 107 * Returns the inserted reference if the `src` pointer was found, 108 * without inspecting the content of the `src` pointer. 109 * 110 * Returns flatcc_refmap_not_found (default 0) if the `src` pointer was 111 * not found. 112 */ 113 flatcc_refmap_ref_t flatcc_refmap_find(flatcc_refmap_t *refmap, const void *src); 114 115 /* 116 * Inserts a `src` source pointer and its associated `ref` reference 117 * into the refmap without inspecting the `src` pointer content. The 118 * `ref` value will be replaced if the the `src` pointer already exists. 119 * 120 * Inserting null will just return the ref without updating the map. 121 * 122 * There is no delete operation which simplifies an open 123 * addressing hash table, and it isn't needed for this use case. 124 * 125 * Returns the input ref or not_found on allocation error. 126 */ 127 flatcc_refmap_ref_t flatcc_refmap_insert(flatcc_refmap_t *refmap, const void *src, flatcc_refmap_ref_t ref); 128 129 /* 130 * Set the hash table to accommodate at least `count` items while staying 131 * within the predefined load factor. 132 * 133 * Resize is primarily an internal operation, but the user may resize 134 * ahead of a large anticipated load, or after a large load to shrink 135 * the table using 0 as the `count` argument. The table never shrinks 136 * on its own account. 137 */ 138 int flatcc_refmap_resize(flatcc_refmap_t *refmap, size_t count); 139 140 #ifdef __cplusplus 141 } 142 #endif 143 144 #endif /* FLATCC_REFMAP_H */