svx_buffer.h (9079B)
1 /* Copyright (C) 2018, 2020-2025 |Méso|Star> (contact@meso-star.com) 2 * Copyright (C) 2018 Université Paul Sabatier 3 * 4 * This program is free software: you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation, either version 3 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program. If not, see <http://www.gnu.org/licenses/>. */ 16 17 #ifndef SVX_BUFFER_H 18 #define SVX_BUFFER_H 19 20 #include "svx_c.h" 21 #include <rsys/dynamic_array.h> 22 23 /* 24 * Buffer containing the data of a tree. These data are partitioned in fixed 25 * size memory pages whose capacity is defined on buffer initialisation with 26 * respect to the page size of the system. 27 * 28 * The children of a node are stored consecutively into a page. The parent node 29 * directly references its first valid children excepted if they lie in a 30 * different page. In this case, the node references a `struct buffer_index', 31 * stored into the same page, that defines the absolute position of its first 32 * valid child into the whole list of node pages 33 * 34 * The data of the nodes are stored in their own memory pages. The attribs of 35 * the children of a node are stored consecutively into a page. If the page 36 * identifier of the attribs is the same of the page into which their parent 37 * node lies, then the node saves the index toward the first valid attrib into 38 * the page of attribs. In the other case, the node references a `struct 39 * buffer_index', stored into the same page of the node, that defines the 40 * absolute position of its first valid attrib into the buffer of attribs. 41 */ 42 43 #define BUFFER_XNODE_FLAG_FAR_INDEX (1u<<15) 44 #define BUFFER_XNODE_MAX_CHILDREN_OFFSET (BUFFER_XNODE_FLAG_FAR_INDEX-1) 45 #define BUFFER_XNODE_MASK BUFFER_XNODE_MAX_CHILDREN_OFFSET 46 47 struct buffer_xnode { 48 /* Offset to retrieve the children. If the BUFFER_XNODE_FLAG_FAR_INDEX bit is 49 * not set, the children are stored in the same page at the position `offset 50 * & BUFFER_XNODE_MASK'. If BUFFER_XNODE_FLAG_FAR_INDEX is set, `offset & 51 * BUFFER_XNODE_MASK' reference a buffer_index toward the node children */ 52 uint16_t node_offset; 53 uint16_t attr_offset; 54 uint8_t is_valid; /* Mask defining if the children are valid */ 55 uint8_t is_leaf; /* Mask defining if the children are leaves */ 56 uint16_t dummy__; /* Ensure a size of 8 Bytes */ 57 }; 58 STATIC_ASSERT(sizeof(struct buffer_xnode) == 8, 59 Unexpected_sizeof_buffer_xnode); 60 61 #define BUFFER_INDEX_IPAGE_MAX UINT32_MAX 62 #define BUFFER_INDEX_INODE_MAX UINT16_MAX 63 64 struct buffer_index { 65 uint32_t ipage; /* Identifier of the page */ 66 uint16_t inode; /* Identifier of the node in the page */ 67 uint16_t dummy__; /* Padding to ensure the tree index is 8 bytes lenght */ 68 }; 69 STATIC_ASSERT(sizeof(struct buffer_index) == 8, 70 Unexpected_sizeof_buffer_index); 71 #define BUFFER_INDEX_NULL__ {UINT32_MAX, UINT16_MAX, UINT16_MAX} 72 static const struct buffer_index BUFFER_INDEX_NULL = BUFFER_INDEX_NULL__; 73 #define BUFFER_INDEX_EQ(A, B) ((A)->inode==(B)->inode && (A)->ipage==(B)->ipage) 74 75 /* Define the dynamic array of pages */ 76 #define DARRAY_NAME page 77 #define DARRAY_DATA char* 78 #include <rsys/dynamic_array.h> 79 80 /* Current version the buffer index data structure */ 81 static const int BUFFER_VERSION = 0; 82 83 struct buffer { 84 size_t pagesize; /* Memory page size in bytes */ 85 size_t voxsize; /* Memory size of a voxel in bytes */ 86 87 struct darray_page node_pages; /* List of pages storing nodes */ 88 struct darray_page attr_pages; /* List of pages storing node attributes */ 89 struct buffer_index node_head; /* Index of the next valid node */ 90 struct buffer_index attr_head; /* Index of the next valid attr */ 91 92 struct mem_allocator* allocator; 93 }; 94 95 extern LOCAL_SYM void 96 buffer_init 97 (struct mem_allocator* allocator, 98 const size_t sizeof_voxel, /* Size in bytes of a voxel */ 99 struct buffer* buf); 100 101 extern LOCAL_SYM void 102 buffer_release 103 (struct buffer* buf); 104 105 extern LOCAL_SYM res_T 106 buffer_alloc_nodes 107 (struct buffer* buf, 108 const size_t nnodes, 109 struct buffer_index* first_node); /* Index toward the 1st allocated node */ 110 111 extern LOCAL_SYM res_T 112 buffer_alloc_attrs 113 (struct buffer* buf, 114 const size_t nattrs, 115 struct buffer_index* first_attr); /* Index toward the 1st allocated attrib */ 116 117 /* Allocate a buffer_index in the current buffer page. Return RES_MEM_ERR if 118 * the node index cannot be allocated in the current page. In this case one 119 * have to alloc new nodes */ 120 extern LOCAL_SYM res_T 121 buffer_alloc_far_index 122 (struct buffer* buf, 123 struct buffer_index* id); /* Index toward the allocated far index */ 124 125 extern LOCAL_SYM void 126 buffer_clear 127 (struct buffer* buf); 128 129 extern LOCAL_SYM res_T 130 buffer_write 131 (const struct buffer* buf, 132 FILE* stream); 133 134 extern LOCAL_SYM res_T 135 buffer_read 136 (struct buffer* buf, 137 FILE* stream); 138 139 /* Check buffer data regarding a given tree root and tree dimension */ 140 extern LOCAL_SYM res_T 141 buffer_check_tree 142 (struct buffer* buffer, 143 const struct buffer_index root, /* Root of the tree */ 144 const size_t tree_dimension, /* Dimension of the tree */ 145 size_t* nleaves); /* Overall #leaves of the tree */ 146 147 static FINLINE int 148 buffer_is_empty(const struct buffer* buf) 149 { 150 ASSERT(buf); 151 return darray_page_size_get(&buf->node_pages) == 0; 152 } 153 154 static FINLINE struct buffer_xnode* 155 buffer_get_node 156 (struct buffer* buf, 157 const struct buffer_index id) 158 { 159 char* mem; 160 ASSERT(buf && id.inode < buf->pagesize/sizeof(struct buffer_xnode)); 161 ASSERT(id.ipage < darray_page_size_get(&buf->node_pages)); 162 mem = darray_page_data_get(&buf->node_pages)[id.ipage]; 163 mem += id.inode * sizeof(struct buffer_xnode); 164 return (struct buffer_xnode*)mem; 165 } 166 167 static FINLINE void* 168 buffer_get_attr 169 (struct buffer* buf, 170 const struct buffer_index id) 171 { 172 char* mem; 173 ASSERT(buf && id.inode < buf->pagesize/buf->voxsize); 174 ASSERT(id.ipage < darray_page_size_get(&buf->attr_pages)); 175 mem = darray_page_data_get(&buf->attr_pages)[id.ipage]; 176 mem += id.inode * buf->voxsize; 177 return mem; 178 } 179 180 static FINLINE struct buffer_index* 181 buffer_get_far_index 182 (struct buffer* buf, 183 const struct buffer_index id) 184 { 185 char* mem; 186 ASSERT(buf && id.inode < buf->pagesize/sizeof(struct buffer_xnode)); 187 ASSERT(id.ipage < darray_page_size_get(&buf->node_pages)); 188 mem = darray_page_data_get(&buf->node_pages)[id.ipage]; 189 mem += id.inode * sizeof(struct buffer_xnode); 190 return (struct buffer_index*)mem; 191 } 192 193 static FINLINE struct buffer_index 194 buffer_get_child_node_index 195 (struct buffer* buf, 196 const struct buffer_index id, 197 const int ichild) /* in [0, 7] */ 198 { 199 struct buffer_index child_id = BUFFER_INDEX_NULL; 200 struct buffer_xnode* node = NULL; 201 uint16_t offset; 202 const int ichild_flag = BIT(ichild); 203 int ichild_off; 204 uint8_t mask; 205 206 ASSERT(ichild >= 0 && ichild < 8 && buf); 207 208 node = buffer_get_node(buf, id); 209 mask = (uint8_t)(node->is_valid & ~node->is_leaf); 210 ASSERT(mask & ichild_flag); 211 212 /* Compute the child offset from the first child node */ 213 ichild_off = popcount((uint8_t)((ichild_flag-1) & (int)mask)); 214 215 offset = node->node_offset & BUFFER_XNODE_MASK; 216 if(!(node->node_offset & BUFFER_XNODE_FLAG_FAR_INDEX)) { 217 child_id.ipage = id.ipage; 218 child_id.inode = (uint16_t)(offset + ichild_off); 219 } else { 220 char* mem = darray_page_data_get(&buf->node_pages)[id.ipage]; 221 child_id = *(struct buffer_index*)(mem+offset*(sizeof(struct buffer_xnode))); 222 child_id.inode = (uint16_t)(child_id.inode + ichild_off); 223 } 224 return child_id; 225 } 226 227 static FINLINE struct buffer_index 228 buffer_get_child_attr_index 229 (struct buffer* buf, 230 const struct buffer_index id, 231 const int ichild) /* In [0, 7] */ 232 { 233 struct buffer_index child_id = BUFFER_INDEX_NULL; 234 struct buffer_xnode* node = NULL; 235 uint16_t offset; 236 const int ichild_flag = BIT(ichild); 237 int ichild_off; 238 uint8_t mask; 239 240 ASSERT(ichild >= 0 && ichild < 8 && buf); 241 242 node = buffer_get_node(buf, id); 243 mask = node->is_valid; 244 ASSERT(mask & ichild_flag); 245 246 /* Compute the attr offset from the first child node */ 247 ichild_off = popcount((uint8_t)((ichild_flag-1) & (int)mask)); 248 249 offset = node->attr_offset & BUFFER_XNODE_MASK; 250 if(!(node->attr_offset & BUFFER_XNODE_FLAG_FAR_INDEX)) { 251 child_id.ipage = id.ipage; 252 child_id.inode = (uint16_t)(offset + ichild_off); 253 } else { 254 char* mem = darray_page_data_get(&buf->node_pages)[id.ipage]; 255 child_id = *(struct buffer_index*)(mem+offset*(sizeof(struct buffer_xnode))); 256 child_id.inode = (uint16_t)(child_id.inode + ichild_off); 257 } 258 return child_id; 259 } 260 261 static FINLINE size_t 262 buffer_absolute_attr_index 263 (const struct buffer* buf, 264 const struct buffer_index index) 265 { 266 ASSERT(buf); 267 return index.ipage * buf->pagesize/buf->voxsize + index.inode; 268 } 269 270 #endif /* SVX_BUFFER_H */