nanocoat/include/sjme/traverse.h

   1 /* -*- Mode: C; indent-tabs-mode: t; tab-width: 4 -*-
   2 // ---------------------------------------------------------------------------
   3 // SquirrelJME
   4 //     Copyright (C) Stephanie Gawroriski <xer@multiphasicapps.net>
   5 // ---------------------------------------------------------------------------
   6 // SquirrelJME is under the Mozilla Public License Version 2.0.
   7 // See license.mkd for licensing and copyright information.
   8 // -------------------------------------------------------------------------*/
   9
  10 /**
  11  * Binary bit based traversal tree.
  12  *
  13  * @since 2024/09/01
  14  */
  15
  16 #ifndef SQUIRRELJME_TRAVERSE_H
  17 #define SQUIRRELJME_TRAVERSE_H
  18
  19 #include "sjme/stdTypes.h"
  20 #include "sjme/tokenUtils.h"
  21 #include "sjme/error.h"
  22
  23 /* Anti-C++. */
  24 #ifdef __cplusplus
  25         #ifndef SJME_CXX_IS_EXTERNED
  26                 #define SJME_CXX_IS_EXTERNED
  27                 #define SJME_CXX_SQUIRRELJME_BITTRAVERSE_H
  28 extern "C"
  29 {
  30         #endif /* #ifdef SJME_CXX_IS_EXTERNED */
  31 #endif /* #ifdef __cplusplus */
  32
  33 /*--------------------------------------------------------------------------*/
  34
  35 /**
  36  * This specifies how nodes should be created.
  37  *
  38  * @since 2024/09/05
  39  */
  40 typedef enum sjme_traverse_createMode
  41 {
  42         /** Normal creation. */
  43         SJME_TRAVERSE_NORMAL,
  44
  45         /** Allow branches to replace leaves. */
  46         SJME_TRAVERSE_BRANCH_REPLACE,
  47
  48         /** Turn leaf into branch and leaf off of branch. */
  49         SJME_TRAVERSE_BRANCH_FROM_LEAF,
  50
  51         /** The number of modes. */
  52         SJME_TRAVERSE_NUM_CREATE_MODE,
  53 } sjme_traverse_createMode;
  54
  55 /**
  56  * Traversal tree node.
  57  *
  58  * @since 2024/08/22
  59  */
  60 typedef union sjme_alignPointer sjme_traverse_node
  61         sjme_traverse_node;
  62
  63 #if SJME_CONFIG_HAS_POINTER == 64
  64         /** Key for leaf values. */
  65         #define SJME_TRAVERSE_LEAF_KEY \
  66                 ((sjme_intPointer)UINT64_C(0x6C4541664C656146))
  67 #elif SJME_CONFIG_HAS_POINTER == 32
  68         /** Key for leaf values. */
  69         #define SJME_TRAVERSE_LEAF_KEY \
  70                 ((sjme_intPointer)UINT32_C(0x6C454166))
  71 #elif SJME_CONFIG_HAS_POINTER == 16
  72         /** Key for leaf values. */
  73         #define SJME_TRAVERSE_LEAF_KEY \
  74                 ((sjme_intPointer)UINT16_C(0x6C45))
  75 #else
  76         #error Unknown pointer size for node leaf?
  77 #endif
  78
  79 /** Key for whiteout nodes. */
  80 #define SJME_TRAVERSE_WHITEOUT_KEY (~SJME_TRAVERSE_LEAF_KEY)
  81
  82 /**
  83  * Node type storage.
  84  *
  85  * @since 2024/09/02
  86  */
  87 typedef sjme_alignPointer struct sjme_traverse_nodeNode
  88 {
  89         /** Zero branch. */
  90         sjme_traverse_node* zero;
  91
  92         /** One branch. */
  93         sjme_traverse_node* one;
  94 } sjme_traverse_nodeNode;
  95
  96 /**
  97  * Leaf type storage.
  98  *
  99  * @since 2024/09/02
 100  */
 101 typedef sjme_alignPointer struct sjme_traverse_nodeLeaf
 102 {
 103         /** Node type identifier. */
 104         sjme_intPointer key;
 105
 106         /** Leaf value. */
 107         sjme_alignPointer sjme_jubyte value[sjme_flexibleArrayCountUnion];
 108 } sjme_traverse_nodeLeaf;
 109
 110 union sjme_alignPointer sjme_traverse_node
 111 {
 112         /** Data if a node. */
 113         sjme_alignPointer sjme_traverse_nodeNode node;
 114
 115         /** Data if a leaf. */
 116         sjme_alignPointer sjme_traverse_nodeLeaf leaf;
 117 };
 118
 119 /**
 120  * Traversal tree.
 121  *
 122  * @since 2024/08/20
 123  */
 124 typedef struct sjme_traverse_base
 125 {
 126         /** The root node. */
 127         sjme_traverse_node* root;
 128
 129         /** Next free node. */
 130         sjme_traverse_node* next;
 131
 132         /** The start of the storage tree. */
 133         sjme_traverse_node* start;
 134
 135         /** Final end of tree. */
 136         sjme_traverse_node* end;
 137
 138         /** The actual size of node structures. */
 139         sjme_jint structSize;
 140
 141         /** The size of leaf values. */
 142         sjme_jint leafLength;
 143
 144         /** The number of bytes in storage. */
 145         sjme_jint storageBytes;
 146
 147         /** Storage for tree nodes. */
 148         sjme_alignPointer sjme_jubyte storage[sjme_flexibleArrayCount];
 149 } sjme_traverse_base;
 150
 151 /**
 152  * Base traversal tree binary type.
 153  *
 154  * @since 2024/09/01
 155  */
 156 typedef sjme_traverse_base* sjme_traverse;
 157
 158 /** The type as a traversal tree. */
 159 #define SJME_AS_TRAVERSE(x) ((sjme_traverse)(x))
 160
 161 /**
 162  * Tree traversal iterator.
 163  *
 164  * @since 2024/09/01
 165  */
 166 typedef struct sjme_traverse_iterator
 167 {
 168         /** Which node are we at. */
 169         sjme_traverse_node* atNode;
 170
 171         /** The bit sequence to reach this node. */
 172         sjme_juint bits;
 173
 174         /** The number of bits in the sequence. */
 175         sjme_jint bitCount;
 176 } sjme_traverse_iterator;
 177
 178 /**
 179  * Determines the basic type name for a traversal tree.
 180  *
 181  * @param type The type used.
 182  * @param numPointerStars The number of pointer stars.
 183  * @since 2024/09/01
 184  */
 185 #define SJME_TRAVERSE_TYPE_NAME(type, numPointerStars) \
 186         SJME_TOKEN_PASTE_PP(type, \
 187                 SJME_TOKEN_SINGLE(SJME_TOKEN_STARS_C##numPointerStars))
 188
 189 /**
 190  * Determines the name of a traversal tree for the given type.
 191  *
 192  * @param type The type to store within the tree.
 193  * @param numPointerStars The number of pointer stars.
 194  * @return The resultant name.
 195  * @since 2024/09/01
 196  */
 197 #define SJME_TRAVERSE_NAME(type, numPointerStars) \
 198         SJME_TOKEN_PASTE_PP(sjme_traverse_, \
 199                 SJME_TRAVERSE_TYPE_NAME(type, numPointerStars))
 200
 201 /**
 202  * Declares a traversal tree type.
 203  *
 204  * @param type The type to store within the tree.
 205  * @param numPointerStars The number of pointer stars.
 206  * @return The resultant type declaration.
 207  * @since 2024/09/01
 208  */
 209 #define SJME_TRAVERSE_DECLARE(type, numPointerStars) \
 210         typedef sjme_traverse SJME_TRAVERSE_NAME(type, numPointerStars)
 211
 212 SJME_TRAVERSE_DECLARE(sjme_jint, 0);
 213
 214 /**
 215  * Clears the traversal tree, making it empty.
 216  *
 217  * @param traverse The tree to empty.
 218  * @return Any resultant error, if any.
 219  * @since 2024/09/02
 220  */
 221 sjme_errorCode sjme_traverse_clear(
 222         sjme_attrInNotNull sjme_traverse traverse);
 223
 224 /**
 225  * Destroys the traversal tree.
 226  *
 227  * @param traverse The tree to destroy.
 228  * @return On any resultant error, if any.
 229  * @since 2024/09/01
 230  */
 231 sjme_errorCode sjme_traverse_destroy(
 232         sjme_attrInNotNull sjme_traverse traverse);
 233
 234 /**
 235  * Starts iteration of the traversal tree.
 236  *
 237  * @param traverse The tree to iterate.
 238  * @param iterator The resultant iterator state.
 239  * @return On any resultant error, if any.
 240  * @since 2024/09/01
 241  */
 242 sjme_errorCode sjme_traverse_iterate(
 243         sjme_attrInNotNull sjme_traverse traverse,
 244         sjme_attrOutNotNull sjme_traverse_iterator* iterator);
 245
 246 /**
 247  * Iterates the next set of values down the tree, reaching a node potentially.
 248  *
 249  * @param traverse The tree to iterate.
 250  * @param iterator The current iterator state.
 251  * @param leafValue Pointer to the leaf value, if the node is a leaf then this
 252  * will be set to the value, otherwise it will be set to null.
 253  * @param leafLength The length of the leaf value.
 254  * @param bits The bit values to traverse with.
 255  * @param numBits The number of bits in the traversal value.
 256  * @return On any resultant error, if any.
 257  * @since 2024/09/01
 258  */
 259 sjme_errorCode sjme_traverse_iterateNextR(
 260         sjme_attrInNotNull sjme_traverse traverse,
 261         sjme_attrOutNotNull sjme_traverse_iterator* iterator,
 262         sjme_attrOutNotNull sjme_pointer* leafValue,
 263         sjme_attrInPositiveNonZero sjme_jint leafLength,
 264         sjme_attrInPositive sjme_juint bits,
 265         sjme_attrInPositiveNonZero sjme_jint numBits);
 266
 267 /**
 268  * Iterates the next set of values down the tree, reaching a node potentially.
 269  *
 270  * @param traverse The tree to iterate.
 271  * @param iterator The current iterator state.
 272  * @param leafValue Pointer to the leaf value, if the node is a leaf then this
 273  * will be set to the value, otherwise it will be set to null.
 274  * @param bits The bit values to traverse with.
 275  * @param numBits The number of bits in the traversal value.
 276  * @param type The type being stored.
 277  * @param numPointerStars the pointer star count for the stored type.
 278  * @return On any resultant error, if any.
 279  * @since 2024/09/02
 280  */
 281 #define sjme_traverse_iterateNext(traverse, iterator, leafValue, bits, \
 282         numBits, type, numPointerStars) \
 283         (sjme_traverse_iterateNextR(SJME_AS_TRAVERSE((traverse)), (iterator), \
 284         ((sjme_pointer*)(leafValue)), \
 285         sizeof((**(leafValue))), (bits), (numBits)))
 286
 287 /**
 288  * Allocates a new traversal tree.
 289  *
 290  * @param inPool The pool to allocate within.
 291  * @param outTraverse The resultant traversal tree.
 292  * @param leafLength The size of the tree elements.
 293  * @param maxElements The maximum number of elements permitted in the tree.
 294  * @return On any resultant error, if any.
 295  * @since 2024/09/01
 296  */
 297 sjme_errorCode sjme_traverse_newR(
 298         sjme_attrInNotNull sjme_alloc_pool* inPool,
 299         sjme_attrOutNotNull sjme_traverse* outTraverse,
 300         sjme_attrInPositiveNonZero sjme_jint leafLength,
 301         sjme_attrInPositiveNonZero sjme_jint maxElements);
 302
 303 /**
 304  * Allocates a new traversal tree.
 305  *
 306  * @param inPool The pool to allocate within.
 307  * @param outTraverse The resultant traversal tree.
 308  * @param maxElements The maximum number of elements permitted in the tree.
 309  * @param type The type being stored.
 310  * @param numPointerStars the pointer star count for the stored type.
 311  * @return On any resultant error, if any.
 312  * @since 2024/09/02
 313  */
 314 #define sjme_traverse_new(inPool, outTraverse, maxElements, \
 315         type, numPointerStars) \
 316         (sjme_traverse_newR((inPool), ((sjme_traverse*)(outTraverse)), \
 317         sizeof(SJME_TOKEN_TYPE(type, numPointerStars)), maxElements))
 318
 319 /**
 320  * Puts a value into the traversal tree.
 321  *
 322  * @param traverse The traversal tree to write into.
 323  * @param createMode The creation mode.
 324  * @param leafValue The pointer to the leaf's value.
 325  * @param leafLength The length of the leaf value.
 326  * @param bits The bit values to get to the leaf.
 327  * @param numBits The number of bits in the value.
 328  * @return On any resultant error, if any.
 329  * @since 2024/09/01
 330  */
 331 sjme_errorCode sjme_traverse_putMR(
 332         sjme_attrInNotNull sjme_traverse traverse,
 333         sjme_attrInValue sjme_traverse_createMode createMode,
 334         sjme_attrInNotNullBuf(leafLength) sjme_pointer leafValue,
 335         sjme_attrInPositiveNonZero sjme_jint leafLength,
 336         sjme_attrInPositive sjme_juint bits,
 337         sjme_attrInPositiveNonZero sjme_jint numBits);
 338
 339 /**
 340  * Puts a value into the traversal tree.
 341  *
 342  * @param traverse The traversal tree to write into.
 343  * @param leafValue The pointer to the leaf's value.
 344  * @param bits The bit values to get to the leaf.
 345  * @param numBits The number of bits in the value.
 346  * @param type The type being stored.
 347  * @param numPointerStars the pointer star count for the stored type.
 348  * @return On any resultant error, if any.
 349  * @since 2024/09/02
 350  */
 351 #define sjme_traverse_put(traverse, leafValue, bits, numBits, \
 352         type, numPointerStars) \
 353         (sjme_traverse_putMR((traverse), (SJME_TRAVERSE_NORMAL), \
 354         ((sjme_pointer)(leafValue)), \
 355         sizeof((*(leafValue))), (bits), (numBits)))
 356
 357 /**
 358  * Puts a value into the traversal tree.
 359  *
 360  * @param traverse The traversal tree to write into.
 361  * @param createMode The creation mode.
 362  * @param leafValue The pointer to the leaf's value.
 363  * @param bits The bit values to get to the leaf.
 364  * @param numBits The number of bits in the value.
 365  * @param type The type being stored.
 366  * @param numPointerStars the pointer star count for the stored type.
 367  * @return On any resultant error, if any.
 368  * @since 2024/09/05
 369  */
 370 #define sjme_traverse_putM(traverse, createMode, leafValue, bits, numBits, \
 371         type, numPointerStars) \
 372         (sjme_traverse_putMR((traverse), (createMode), \
 373         ((sjme_pointer)(leafValue)), \
 374         sizeof((*(leafValue))), (bits), (numBits)))
 375
 376 /**
 377  * Removes the given leaf and/or node from a tree, if this is a node then all
 378  * children will be removed as well.
 379  *
 380  * @param traverse The tree to remove from.
 381  * @param bits The bit values to remove.
 382  * @param numBits The number of bits in the value.
 383  * @return On any resultant error, if any.
 384  * @since 2024/09/01
 385  */
 386 sjme_errorCode sjme_traverse_remove(
 387         sjme_attrInNotNull sjme_traverse traverse,
 388         sjme_attrInPositive sjme_juint bits,
 389         sjme_attrInPositiveNonZero sjme_jint numBits);
 390
 391 /*--------------------------------------------------------------------------*/
 392
 393 /* Anti-C++. */
 394 #ifdef __cplusplus
 395         #ifdef SJME_CXX_SQUIRRELJME_BITTRAVERSE_H
 396 }
 397                 #undef SJME_CXX_SQUIRRELJME_BITTRAVERSE_H
 398                 #undef SJME_CXX_IS_EXTERNED
 399         #endif /* #ifdef SJME_CXX_SQUIRRELJME_BITTRAVERSE_H */
 400 #endif /* #ifdef __cplusplus */
 401
 402 #endif /* SQUIRRELJME_TRAVERSE_H */