nanocoat/lib/base/traverse.c

   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 #include <string.h>
  11
  12 #include "sjme/traverse.h"
  13 #include "sjme/debug.h"
  14 #include "sjme/alloc.h"
  15 #include "sjme/util.h"
  16
  17 static sjme_errorCode sjme_traverse_next(
  18         sjme_attrInNotNull sjme_traverse traverse,
  19         sjme_attrOutNotNull sjme_traverse_node** outNode)
  20 {
  21         sjme_traverse_node* result;
  22
  23         if (traverse == NULL || outNode == NULL)
  24                 return SJME_ERROR_NULL_ARGUMENTS;
  25
  26         /* Is the tree already full? */
  27         if ((intptr_t)traverse->next > (intptr_t)traverse->end)
  28         {
  29                 /* Find a whiteout key we can take. */
  30                 for (result = traverse->start;
  31                         (intptr_t)result < (intptr_t)traverse->end; result++)
  32                         if (result->leaf.key == SJME_TRAVERSE_WHITEOUT_KEY)
  33                         {
  34                                 /* Wipe it. */
  35                                 memset(result, 0, traverse->structSize);
  36
  37                                 /* Success! */
  38                                 *outNode = result;
  39                                 return SJME_ERROR_NONE;
  40                         }
  41
  42                 /* Tree is truly full. */
  43                 return SJME_ERROR_TRAVERSE_FULL;
  44         }
  45
  46         /* Next node is the actual next node, make sure it is cleared. */
  47         result = traverse->next;
  48         memset(result, 0, traverse->structSize);
  49
  50         /* Then shift forward to the next node. */
  51         traverse->next = SJME_POINTER_OFFSET(result, traverse->structSize);
  52
  53         /* Count up. */
  54         traverse->usedElements += 1;
  55
  56         /* Success! */
  57         *outNode = result;
  58         return SJME_ERROR_NONE;
  59 }
  60
  61 static sjme_errorCode sjme_traverse_traverse(
  62         sjme_attrInNotNull sjme_traverse traverse,
  63         sjme_attrOutNotNull sjme_traverse_node** outNode,
  64         sjme_attrOutNullable sjme_traverse_node** outParent,
  65         sjme_attrInValue sjme_jboolean create,
  66         sjme_attrInValue sjme_traverse_createMode createMode,
  67         sjme_attrInPositive sjme_juint bits,
  68         sjme_attrInPositiveNonZero sjme_jint numBits)
  69 {
  70         sjme_errorCode error;
  71         sjme_traverse_node* at;
  72         sjme_traverse_node* atParent;
  73         sjme_traverse_node* clone;
  74         sjme_traverse_node** next;
  75         sjme_traverse_node** other;
  76         sjme_juint sh;
  77         sjme_jboolean finalShift;
  78
  79         if (traverse == NULL || outNode == NULL)
  80                 return SJME_ERROR_NULL_ARGUMENTS;
  81
  82         if (create)
  83         {
  84                 if (createMode != SJME_TRAVERSE_NORMAL &&
  85                         createMode != SJME_TRAVERSE_BRANCH_REPLACE &&
  86                         createMode != SJME_TRAVERSE_BRANCH_FROM_LEAF)
  87                         return SJME_ERROR_INVALID_ARGUMENT;
  88         }
  89
  90         /* Go through all bits in the shift. */
  91         at = traverse->root;
  92         atParent = traverse->root;
  93         for (sh = sjme_util_intOverShiftU(1, numBits - 1);
  94                 sh >= 1 && at != NULL; sh >>= 1)
  95         {
  96                 /* Is this the final shift? */
  97                 finalShift = (sh == 1);
  98
  99                 /* Are we going zero or one? */
 100                 next = (((bits & sh) != 0) ? &at->node.one : &at->node.zero);
 101                 other = (((bits & sh) == 0) ? &at->node.one : &at->node.zero);
 102
 103                 /* Are we at a leaf? We should never be on one. */
 104                 if (at->leaf.key == SJME_TRAVERSE_LEAF_KEY)
 105                 {
 106                         if (!create)
 107                                 return SJME_ERROR_NO_SUCH_ELEMENT;
 108
 109                         /* Not turning into a branch? */
 110                         if (createMode != SJME_TRAVERSE_BRANCH_REPLACE &&
 111                                 createMode != SJME_TRAVERSE_BRANCH_FROM_LEAF)
 112                                 return SJME_ERROR_TREE_COLLISION;
 113
 114                         /* Make copy of this leaf and set it to the other sub-node. */
 115                         if (createMode == SJME_TRAVERSE_BRANCH_FROM_LEAF)
 116                         {
 117                                 /* Get new entry which will contain this leaf. */
 118                                 clone = NULL;
 119                                 if (sjme_error_is(error = sjme_traverse_next(
 120                                         traverse, &clone)) || clone == NULL)
 121                                         return sjme_error_default(error);
 122
 123                                 /* Copy leaf directly. */
 124                                 memmove(clone, at, traverse->structSize);
 125
 126                                 /* Make this a branch and point to the new leaf. */
 127                                 (*next) = clone;
 128                                 (*other) = NULL;
 129                         }
 130
 131                         /* Just wipe the values here. */
 132                         else
 133                         {
 134                                 at->node.zero = NULL;
 135                                 at->node.one = NULL;
 136                         }
 137                 }
 138
 139                 /* If there is no node here, create it, possibly. */
 140                 if ((*next) == NULL)
 141                 {
 142                         /* Not creating, so fail here. */
 143                         if (!create)
 144                                 return SJME_ERROR_NO_SUCH_ELEMENT;
 145
 146                         /* Allocate node. */
 147                         if (sjme_error_is(error = sjme_traverse_next(traverse,
 148                                 next)) || (*next) == NULL)
 149                                 return sjme_error_default(error);
 150
 151                         /* If this is the last item, it becomes a leaf. */
 152                         if (finalShift)
 153                                 (*next)->leaf.key = SJME_TRAVERSE_LEAF_KEY;
 154                 }
 155
 156                 /* Go the next node. */
 157                 atParent = at;
 158                 at = (*next);
 159         }
 160
 161         /* Nothing here? This means the tree might be corrupted, or it may */
 162         /* actually be missing. */
 163         if (at == NULL)
 164                 return SJME_ERROR_NO_SUCH_ELEMENT;
 165
 166         /* Return the target node. */
 167         *outNode = at;
 168         if (outParent != NULL)
 169                 *outParent = atParent;
 170         return SJME_ERROR_NONE;
 171 }
 172
 173 sjme_errorCode sjme_traverse_clear(
 174         sjme_attrInNotNull sjme_traverse traverse)
 175 {
 176         if (traverse == NULL)
 177                 return SJME_ERROR_NULL_ARGUMENTS;
 178
 179         /* Reset nodes to initial state. */
 180         traverse->root = NULL;
 181         traverse->next = traverse->start;
 182         traverse->usedElements = 0;
 183         memset(&traverse->storage[0], 0, traverse->storageBytes);
 184
 185         /* Success! */
 186         return SJME_ERROR_NONE;
 187 }
 188
 189 sjme_errorCode sjme_traverse_destroy(
 190         sjme_attrInNotNull sjme_traverse traverse)
 191 {
 192         if (traverse == NULL)
 193                 return SJME_ERROR_NULL_ARGUMENTS;
 194
 195         /* Wipe entire structure. */
 196         memset(traverse, 0, sizeof(*traverse));
 197
 198         /* Then free it. */
 199         return sjme_alloc_free(traverse);
 200 }
 201
 202 sjme_errorCode sjme_traverse_iterate(
 203         sjme_attrInNotNull sjme_traverse traverse,
 204         sjme_attrOutNotNull sjme_traverse_iterator* iterator)
 205 {
 206         if (traverse == NULL || iterator == NULL)
 207                 return SJME_ERROR_NULL_ARGUMENTS;
 208
 209         /* Start traversal. */
 210         memset(iterator, 0, sizeof(*iterator));
 211         iterator->atNode = traverse->root;
 212
 213         /* Success! */
 214         return SJME_ERROR_NONE;
 215 }
 216
 217 sjme_errorCode sjme_traverse_iterateNextR(
 218         sjme_attrInNotNull sjme_traverse traverse,
 219         sjme_attrOutNotNull sjme_traverse_iterator* iterator,
 220         sjme_attrOutNotNull sjme_pointer* leafValue,
 221         sjme_attrInPositiveNonZero sjme_jint leafLength,
 222         sjme_attrInPositive sjme_juint bits,
 223         sjme_attrInPositiveNonZero sjme_jint numBits)
 224 {
 225         sjme_traverse_node* at;
 226         sjme_traverse_node** next;
 227         sjme_juint sh;
 228         sjme_jboolean finalShift, set;
 229
 230         if (traverse == NULL || iterator == NULL || leafValue == NULL)
 231                 return SJME_ERROR_NULL_ARGUMENTS;
 232
 233         if (leafLength <= 0 || numBits <= 0)
 234                 return SJME_ERROR_INVALID_ARGUMENT;
 235
 236         /* Wrong length for this tree? */
 237         if (traverse->leafLength != leafLength)
 238                 return SJME_ERROR_INVALID_ARGUMENT;
 239
 240         /* Invalid? */
 241         at = iterator->atNode;
 242         if (at == NULL)
 243                 return SJME_ERROR_NO_SUCH_ELEMENT;
 244
 245         /* We cannot iterate past a leaf. */
 246         if ((sjme_intPointer)at == SJME_TRAVERSE_LEAF_KEY)
 247                 return SJME_ERROR_NO_SUCH_ELEMENT;
 248
 249         /* Continue where this was left off. */
 250         for (sh = sjme_util_intOverShiftU(1, numBits - 1);
 251                 sh >= 1 && at != NULL; sh >>= 1)
 252         {
 253                 /* Is this the final shift? */
 254                 finalShift = (sh == 1);
 255
 256                 /* Is this set? */
 257                 set = ((bits & sh) != 0);
 258
 259                 /* In too deep? */
 260                 if (iterator->bitCount >= 32)
 261                         return SJME_ERROR_TREE_TOO_DEEP;
 262
 263                 /* Shift in bit. */
 264                 iterator->bits <<= 1;
 265                 iterator->bits |= (set ? 1 : 0);
 266                 iterator->bitCount += 1;
 267
 268                 /* We cannot iterate past a leaf. */
 269                 if ((sjme_intPointer)at == SJME_TRAVERSE_LEAF_KEY)
 270                         return SJME_ERROR_NO_SUCH_ELEMENT;
 271
 272                 /* Are we going zero or one? */
 273                 next = (set ? &at->node.one : &at->node.zero);
 274
 275                 /* Nothing here? */
 276                 if ((*next) == NULL)
 277                         return SJME_ERROR_NO_SUCH_ELEMENT;
 278
 279                 /* Next is a leaf? */
 280                 if ((sjme_intPointer)((*next)->leaf.key) == SJME_TRAVERSE_LEAF_KEY)
 281                 {
 282                         /* Must be the final bit! */
 283                         if (!finalShift)
 284                                 return SJME_ERROR_NO_SUCH_ELEMENT;
 285
 286                         /* Set leaf value. */
 287                         *leafValue = &((*next)->leaf.value[0]);
 288                 }
 289
 290                 /* Go the next node. */
 291                 at = (*next);
 292         }
 293
 294         /* Not valid? */
 295         if (at == NULL)
 296                 return SJME_ERROR_NO_SUCH_ELEMENT;
 297
 298         /* Set at this position. */
 299         iterator->atNode = at;
 300
 301         /* Success! */
 302         return SJME_ERROR_NONE;
 303 }
 304
 305 sjme_errorCode sjme_traverse_newR(
 306         sjme_attrInNotNull sjme_alloc_pool* inPool,
 307         sjme_attrOutNotNull sjme_traverse* outTraverse,
 308         sjme_attrInPositiveNonZero sjme_jint leafLength,
 309         sjme_attrInPositiveNonZero sjme_jint maxElements)
 310 {
 311         sjme_errorCode error;
 312         sjme_jint structSize, nodeSize, leafSize;
 313         sjme_jint storageSize, pointerBytes;
 314         sjme_traverse result;
 315
 316         if (inPool == NULL || outTraverse == NULL)
 317                 return SJME_ERROR_NULL_ARGUMENTS;
 318
 319         if (leafLength <= 0 || maxElements <= 0)
 320                 return SJME_ERROR_INVALID_ARGUMENT;
 321
 322         /* Determine the size for nodes and leaves, then determine struct size. */
 323         nodeSize = sizeof(sjme_traverse_nodeNode);
 324         leafSize = sizeof(sjme_traverse_nodeLeaf) + leafLength;
 325         structSize = (nodeSize > leafSize ? nodeSize : leafSize);
 326
 327         /* If not divisible by the pointer bits, round up. */
 328         /* The nodes themselves are pointers, but our container data might */
 329         /* also be pointers. */
 330         pointerBytes = (SJME_CONFIG_HAS_POINTER / 8);
 331         if ((structSize % pointerBytes) != 0)
 332                 structSize += pointerBytes - (structSize % pointerBytes);
 333
 334         /* Make sure calculated sizes are valid. */
 335         if (nodeSize <= 0 || leafSize <= 0 || structSize <= 0)
 336                 return SJME_ERROR_OUT_OF_MEMORY;
 337
 338         /* Then make sure we can actually store this many. */
 339         storageSize = structSize * maxElements;
 340         if (storageSize <= 0)
 341                 return SJME_ERROR_OUT_OF_MEMORY;
 342
 343         /* Allocate entire tree with storage. */
 344         result = NULL;
 345         if (sjme_error_is(error = sjme_alloc(inPool,
 346                 offsetof(sjme_traverse_base, storage) + storageSize,
 347                 (sjme_pointer*)&result)) || result == NULL)
 348                 goto fail_allocResult;
 349
 350         /* Setup tree parameters. */
 351         result->structSize = structSize;
 352         result->leafLength = leafLength;
 353         result->storageBytes = storageSize;
 354         result->maxElements = maxElements;
 355         result->usedElements = 0;
 356         result->start = (sjme_traverse_node*)&result->storage[0];
 357         result->end = (sjme_traverse_node*)SJME_POINTER_OFFSET(result->start,
 358                 storageSize - structSize);
 359         result->next = result->start;
 360
 361         /* Success! */
 362         *outTraverse = result;
 363         return SJME_ERROR_NONE;
 364
 365 fail_allocResult:
 366         if (result != NULL)
 367                 sjme_alloc_free(result);
 368
 369         return sjme_error_default(error);
 370 }
 371
 372 sjme_errorCode sjme_traverse_putMR(
 373         sjme_attrInNotNull sjme_traverse traverse,
 374         sjme_attrInValue sjme_traverse_createMode createMode,
 375         sjme_attrInNotNullBuf(leafLength) sjme_pointer leafValue,
 376         sjme_attrInPositiveNonZero sjme_jint leafLength,
 377         sjme_attrInPositive sjme_juint bits,
 378         sjme_attrInPositiveNonZero sjme_jint numBits)
 379 {
 380         sjme_errorCode error;
 381         sjme_traverse_node* at;
 382
 383         if (traverse == NULL || leafValue == NULL)
 384                 return SJME_ERROR_NULL_ARGUMENTS;
 385
 386         if (leafLength <= 0 || numBits <= 0)
 387                 return SJME_ERROR_INVALID_ARGUMENT;
 388
 389         if (createMode != SJME_TRAVERSE_NORMAL &&
 390                 createMode != SJME_TRAVERSE_BRANCH_REPLACE &&
 391                 createMode != SJME_TRAVERSE_BRANCH_FROM_LEAF)
 392                 return SJME_ERROR_INVALID_ARGUMENT;
 393
 394         /* Wrong length for this tree? */
 395         if (traverse->leafLength != leafLength)
 396                 return SJME_ERROR_INVALID_ARGUMENT;
 397
 398         /* Is a root node needed? */
 399         if (traverse->root == NULL)
 400                 if (sjme_error_is(error = sjme_traverse_next(traverse,
 401                         &traverse->root)) || traverse->root == NULL)
 402                         return sjme_error_default(error);
 403
 404         /* Traverse the tree. */
 405         at = NULL;
 406         if (sjme_error_is(error = sjme_traverse_traverse(
 407                 traverse, &at, NULL,
 408                 SJME_JNI_TRUE, createMode, bits, numBits)) ||
 409                 at == NULL)
 410                 return sjme_error_default(error);
 411
 412         /* The leaf key must be set to be a leaf! */
 413         if (at->leaf.key != SJME_TRAVERSE_LEAF_KEY)
 414         {
 415                 /* Not replacing it. */
 416                 if (createMode != SJME_TRAVERSE_BRANCH_REPLACE &&
 417                         createMode != SJME_TRAVERSE_BRANCH_FROM_LEAF)
 418                         return SJME_ERROR_TREE_COLLISION;
 419         }
 420
 421         /* Initialize leaf. */
 422         at->leaf.key = SJME_TRAVERSE_LEAF_KEY;
 423         memmove(&at->leaf.value[0], leafValue, traverse->leafLength);
 424
 425         /* Success! */
 426         return SJME_ERROR_NONE;
 427 }
 428
 429 sjme_errorCode sjme_traverse_remove(
 430         sjme_attrInNotNull sjme_traverse traverse,
 431         sjme_attrInPositive sjme_juint bits,
 432         sjme_attrInPositiveNonZero sjme_jint numBits)
 433 {
 434         sjme_errorCode error;
 435         sjme_traverse_node* at;
 436         sjme_traverse_node* atParent;
 437
 438         if (traverse == NULL)
 439                 return SJME_ERROR_NULL_ARGUMENTS;
 440
 441         if (numBits <= 0)
 442                 return SJME_ERROR_INVALID_ARGUMENT;
 443
 444         /* Traverse the tree. */
 445         at = NULL;
 446         atParent = NULL;
 447         if (sjme_error_is(error = sjme_traverse_traverse(
 448                 traverse, &at, &atParent,
 449                 SJME_JNI_FALSE, 0, bits, numBits)))
 450                 return sjme_error_default(error);
 451
 452         /* Nothing is here? */
 453         if (at == NULL)
 454                 return SJME_ERROR_NO_SUCH_ELEMENT;
 455
 456         /* Clear it out. */
 457         if (atParent != NULL)
 458         {
 459                 if (atParent->node.zero == at)
 460                         atParent->node.zero = NULL;
 461                 else if (atParent->node.one == at)
 462                         atParent->node.one = NULL;
 463         }
 464
 465         /* Wipe as long as this is not a leaf. */
 466         if ((sjme_intPointer)at != SJME_TRAVERSE_LEAF_KEY)
 467                 memset(at, 0, sizeof(*at));
 468
 469         /* Success! */
 470         return SJME_ERROR_NONE;
 471 }