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 /**
  80  * Node type storage.
  81  *
  82  * @since 2024/09/02
  83  */
  84 typedef sjme_alignPointer struct sjme_traverse_nodeNode
  85 {
  86         /** Zero branch. */
  87         sjme_traverse_node* zero;
  88
  89         /** One branch. */
  90         sjme_traverse_node* one;
  91 } sjme_traverse_nodeNode;
  92
  93 /**
  94  * Leaf type storage.
  95  *
  96  * @since 2024/09/02
  97  */
  98 typedef sjme_alignPointer struct sjme_traverse_nodeLeaf
  99 {
 100         /** Node type identifier. */
 101         sjme_intPointer key;
 102
 103         /** Leaf value. */
 104         sjme_alignPointer sjme_jubyte value[sjme_flexibleArrayCountUnion];
 105 } sjme_traverse_nodeLeaf;
 106
 107 union sjme_alignPointer sjme_traverse_node
 108 {
 109         /** Data if a node. */
 110         sjme_alignPointer sjme_traverse_nodeNode node;
 111
 112         /** Data if a leaf. */
 113         sjme_alignPointer sjme_traverse_nodeLeaf leaf;
 114 };
 115
 116 /**
 117  * Traversal tree.
 118  *
 119  * @since 2024/08/20
 120  */
 121 typedef struct sjme_traverse_base
 122 {
 123         /** The root node. */
 124         sjme_traverse_node* root;
 125
 126         /** Next free node. */
 127         sjme_traverse_node* next;
 128
 129         /** The start of the storage tree. */
 130         sjme_traverse_node* start;
 131
 132         /** Final end of tree. */
 133         sjme_traverse_node* end;
 134
 135         /** The actual size of node structures. */
 136         sjme_jint structSize;
 137
 138         /** The size of leaf values. */
 139         sjme_jint leafLength;
 140
 141         /** The number of bytes in storage. */
 142         sjme_jint storageBytes;
 143
 144         /** Storage for tree nodes. */
 145         sjme_alignPointer sjme_jubyte storage[sjme_flexibleArrayCount];
 146 } sjme_traverse_base;
 147
 148 /**
 149  * Base traversal tree binary type.
 150  *
 151  * @since 2024/09/01
 152  */
 153 typedef sjme_traverse_base* sjme_traverse;
 154
 155 /** The type as a traversal tree. */
 156 #define SJME_AS_TRAVERSE(x) ((sjme_traverse)(x))
 157
 158 /**
 159  * Tree traversal iterator.
 160  *
 161  * @since 2024/09/01
 162  */
 163 typedef struct sjme_traverse_iterator
 164 {
 165         /** Which node are we at. */
 166         sjme_traverse_node* atNode;
 167
 168         /** The bit sequence to reach this node. */
 169         sjme_juint bits;
 170
 171         /** The number of bits in the sequence. */
 172         sjme_jint bitCount;
 173 } sjme_traverse_iterator;
 174
 175 /**
 176  * Determines the basic type name for a traversal tree.
 177  *
 178  * @param type The type used.
 179  * @param numPointerStars The number of pointer stars.
 180  * @since 2024/09/01
 181  */
 182 #define SJME_TRAVERSE_TYPE_NAME(type, numPointerStars) \
 183         SJME_TOKEN_PASTE_PP(type, \
 184                 SJME_TOKEN_SINGLE(SJME_TOKEN_STARS_C##numPointerStars))
 185
 186 /**
 187  * Determines the name of a traversal tree for the given type.
 188  *
 189  * @param type The type to store within the tree.
 190  * @param numPointerStars The number of pointer stars.
 191  * @return The resultant name.
 192  * @since 2024/09/01
 193  */
 194 #define SJME_TRAVERSE_NAME(type, numPointerStars) \
 195         SJME_TOKEN_PASTE_PP(sjme_traverse_, \
 196                 SJME_TRAVERSE_TYPE_NAME(type, numPointerStars))
 197
 198 /**
 199  * Declares a traversal tree type.
 200  *
 201  * @param type The type to store within the tree.
 202  * @param numPointerStars The number of pointer stars.
 203  * @return The resultant type declaration.
 204  * @since 2024/09/01
 205  */
 206 #define SJME_TRAVERSE_DECLARE(type, numPointerStars) \
 207         typedef sjme_traverse SJME_TRAVERSE_NAME(type, numPointerStars)
 208
 209 SJME_TRAVERSE_DECLARE(sjme_jint, 0);
 210
 211 /**
 212  * Clears the traversal tree, making it empty.
 213  *
 214  * @param traverse The tree to empty.
 215  * @return Any resultant error, if any.
 216  * @since 2024/09/02
 217  */
 218 sjme_errorCode sjme_traverse_clear(
 219         sjme_attrInNotNull sjme_traverse traverse);
 220
 221 /**
 222  * Destroys the traversal tree.
 223  *
 224  * @param traverse The tree to destroy.
 225  * @return On any resultant error, if any.
 226  * @since 2024/09/01
 227  */
 228 sjme_errorCode sjme_traverse_destroy(
 229         sjme_attrInNotNull sjme_traverse traverse);
 230
 231 /**
 232  * Starts iteration of the traversal tree.
 233  *
 234  * @param traverse The tree to iterate.
 235  * @param iterator The resultant iterator state.
 236  * @return On any resultant error, if any.
 237  * @since 2024/09/01
 238  */
 239 sjme_errorCode sjme_traverse_iterate(
 240         sjme_attrInNotNull sjme_traverse traverse,
 241         sjme_attrOutNotNull sjme_traverse_iterator* iterator);
 242
 243 /**
 244  * Iterates the next set of values down the tree, reaching a node potentially.
 245  *
 246  * @param traverse The tree to iterate.
 247  * @param iterator The current iterator state.
 248  * @param leafValue Pointer to the leaf value, if the node is a leaf then this
 249  * will be set to the value, otherwise it will be set to null.
 250  * @param leafLength The length of the leaf value.
 251  * @param bits The bit values to traverse with.
 252  * @param numBits The number of bits in the traversal value.
 253  * @return On any resultant error, if any.
 254  * @since 2024/09/01
 255  */
 256 sjme_errorCode sjme_traverse_iterateNextR(
 257         sjme_attrInNotNull sjme_traverse traverse,
 258         sjme_attrOutNotNull sjme_traverse_iterator* iterator,
 259         sjme_attrOutNotNull sjme_pointer* leafValue,
 260         sjme_attrInPositiveNonZero sjme_jint leafLength,
 261         sjme_attrInPositive sjme_juint bits,
 262         sjme_attrInPositiveNonZero sjme_jint numBits);
 263
 264 /**
 265  * Iterates the next set of values down the tree, reaching a node potentially.
 266  *
 267  * @param traverse The tree to iterate.
 268  * @param iterator The current iterator state.
 269  * @param leafValue Pointer to the leaf value, if the node is a leaf then this
 270  * will be set to the value, otherwise it will be set to null.
 271  * @param bits The bit values to traverse with.
 272  * @param numBits The number of bits in the traversal value.
 273  * @param type The type being stored.
 274  * @param numPointerStars the pointer star count for the stored type.
 275  * @return On any resultant error, if any.
 276  * @since 2024/09/02
 277  */
 278 #define sjme_traverse_iterateNext(traverse, iterator, leafValue, bits, \
 279         numBits, type, numPointerStars) \
 280         (sjme_traverse_iterateNextR(SJME_AS_TRAVERSE((traverse)), (iterator), \
 281         ((sjme_pointer*)(leafValue)), \
 282         sizeof((**(leafValue))), (bits), (numBits)))
 283
 284 /**
 285  * Allocates a new traversal tree.
 286  *
 287  * @param inPool The pool to allocate within.
 288  * @param outTraverse The resultant traversal tree.
 289  * @param leafLength The size of the tree elements.
 290  * @param maxElements The maximum number of elements permitted in the tree.
 291  * @return On any resultant error, if any.
 292  * @since 2024/09/01
 293  */
 294 sjme_errorCode sjme_traverse_newR(
 295         sjme_attrInNotNull sjme_alloc_pool* inPool,
 296         sjme_attrOutNotNull sjme_traverse* outTraverse,
 297         sjme_attrInPositiveNonZero sjme_jint leafLength,
 298         sjme_attrInPositiveNonZero sjme_jint maxElements);
 299
 300 /**
 301  * Allocates a new traversal tree.
 302  *
 303  * @param inPool The pool to allocate within.
 304  * @param outTraverse The resultant traversal tree.
 305  * @param maxElements The maximum number of elements permitted in the tree.
 306  * @param type The type being stored.
 307  * @param numPointerStars the pointer star count for the stored type.
 308  * @return On any resultant error, if any.
 309  * @since 2024/09/02
 310  */
 311 #define sjme_traverse_new(inPool, outTraverse, maxElements, \
 312         type, numPointerStars) \
 313         (sjme_traverse_newR((inPool), ((sjme_traverse*)(outTraverse)), \
 314         sizeof(SJME_TOKEN_TYPE(type, numPointerStars)), maxElements))
 315
 316 /**
 317  * Puts a value into the traversal tree.
 318  *
 319  * @param traverse The traversal tree to write into.
 320  * @param createMode The creation mode.
 321  * @param leafValue The pointer to the leaf's value.
 322  * @param leafLength The length of the leaf value.
 323  * @param bits The bit values to get to the leaf.
 324  * @param numBits The number of bits in the value.
 325  * @return On any resultant error, if any.
 326  * @since 2024/09/01
 327  */
 328 sjme_errorCode sjme_traverse_putMR(
 329         sjme_attrInNotNull sjme_traverse traverse,
 330         sjme_attrInValue sjme_traverse_createMode createMode,
 331         sjme_attrInNotNullBuf(leafLength) sjme_pointer leafValue,
 332         sjme_attrInPositiveNonZero sjme_jint leafLength,
 333         sjme_attrInPositive sjme_juint bits,
 334         sjme_attrInPositiveNonZero sjme_jint numBits);
 335
 336 /**
 337  * Puts a value into the traversal tree.
 338  *
 339  * @param traverse The traversal tree to write into.
 340  * @param leafValue The pointer to the leaf's value.
 341  * @param bits The bit values to get to the leaf.
 342  * @param numBits The number of bits in the value.
 343  * @param type The type being stored.
 344  * @param numPointerStars the pointer star count for the stored type.
 345  * @return On any resultant error, if any.
 346  * @since 2024/09/02
 347  */
 348 #define sjme_traverse_put(traverse, leafValue, bits, numBits, \
 349         type, numPointerStars) \
 350         (sjme_traverse_putMR((traverse), (SJME_TRAVERSE_NORMAL), \
 351         ((sjme_pointer)(leafValue)), \
 352         sizeof((*(leafValue))), (bits), (numBits)))
 353
 354 /**
 355  * Puts a value into the traversal tree.
 356  *
 357  * @param traverse The traversal tree to write into.
 358  * @param createMode The creation mode.
 359  * @param leafValue The pointer to the leaf's value.
 360  * @param bits The bit values to get to the leaf.
 361  * @param numBits The number of bits in the value.
 362  * @param type The type being stored.
 363  * @param numPointerStars the pointer star count for the stored type.
 364  * @return On any resultant error, if any.
 365  * @since 2024/09/05
 366  */
 367 #define sjme_traverse_putM(traverse, createMode, leafValue, bits, numBits, \
 368         type, numPointerStars) \
 369         (sjme_traverse_putMR((traverse), (createMode), \
 370         ((sjme_pointer)(leafValue)), \
 371         sizeof((*(leafValue))), (bits), (numBits)))
 372
 373 /**
 374  * Removes the given leaf and/or node from a tree, if this is a node then all
 375  * children will be removed as well.
 376  *
 377  * @param traverse The tree to remove from.
 378  * @param bits The bit values to remove.
 379  * @param numBits The number of bits in the value.
 380  * @return On any resultant error, if any.
 381  * @since 2024/09/01
 382  */
 383 sjme_errorCode sjme_traverse_remove(
 384         sjme_attrInNotNull sjme_traverse traverse,
 385         sjme_attrInPositive sjme_juint bits,
 386         sjme_attrInPositiveNonZero sjme_jint numBits);
 387
 388 /*--------------------------------------------------------------------------*/
 389
 390 /* Anti-C++. */
 391 #ifdef __cplusplus
 392         #ifdef SJME_CXX_SQUIRRELJME_BITTRAVERSE_H
 393 }
 394                 #undef SJME_CXX_SQUIRRELJME_BITTRAVERSE_H
 395                 #undef SJME_CXX_IS_EXTERNED
 396         #endif /* #ifdef SJME_CXX_SQUIRRELJME_BITTRAVERSE_H */
 397 #endif /* #ifdef __cplusplus */
 398
 399 #endif /* SQUIRRELJME_TRAVERSE_H */