nanocoat/lib/base/circleBuffer.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/circleBuffer.h"
  13 #include "sjme/debug.h"
  14
  15 /**
  16  * Generic operation for circle buffers.
  17  *
  18  * @since 2024/08/25
  19  */
  20 typedef enum sjme_circleBuffer_operation
  21 {
  22         /** Push operation, queue. */
  23         SJME_CIRCLE_BUFFER_PUSH_QUEUE,
  24
  25         /** Push operation, window. */
  26         SJME_CIRCLE_BUFFER_PUSH_WINDOW,
  27
  28         /** Pop operation. */
  29         SJME_CIRCLE_BUFFER_POP,
  30
  31         /** Get operation. */
  32         SJME_CIRCLE_BUFFER_GET,
  33
  34         /** The number of operations that can be performed. */
  35         SJME_CIRCLE_BUFFER_NUM_OPERATIONS
  36 } sjme_circleBuffer_operation;
  37
  38 /**
  39  * A slice for accessing a buffer.
  40  *
  41  * @since 2024/08/25
  42  */
  43 typedef struct sjme_circleBuffer_slice
  44 {
  45         /** Non-circle buffer pointer? */
  46         sjme_pointer externalBuf;
  47
  48         /** The base position. */
  49         sjme_jint base;
  50
  51         /** The length. */
  52         sjme_jint len;
  53 } sjme_circleBuffer_slice;
  54
  55 /**
  56  * Stores the calculated result of the operation.
  57  *
  58  * @since 2024/08/25
  59  */
  60 typedef struct sjme_circleBuffer_calcResult
  61 {
  62         /** The new ready. */
  63         sjme_jint newReady;
  64
  65         /** The new write head. */
  66         sjme_jint newWriteHead;
  67
  68         /** The new read head. */
  69         sjme_jint newReadHead;
  70
  71         /** The source data slice. */
  72         sjme_circleBuffer_slice src[2];
  73
  74         /** The destination data slice. */
  75         sjme_circleBuffer_slice dest[2];
  76 } sjme_circleBuffer_calcResult;
  77
  78 static sjme_errorCode sjme_circleBuffer_calc(
  79         sjme_attrInNotNull sjme_circleBuffer* buffer,
  80         sjme_attrOutNotNull sjme_circleBuffer_calcResult* result,
  81         sjme_attrInValue sjme_circleBuffer_operation operation,
  82         sjme_attrInNotNullBuf(length) sjme_pointer opData,
  83         sjme_attrInPositiveNonZero sjme_jint length,
  84         sjme_attrInValue sjme_circleBuffer_seekEnd seekType,
  85         sjme_attrInPositiveNonZero sjme_jint seekPos)
  86 {
  87         sjme_circleBuffer_slice (*circleSl)[2];
  88         sjme_circleBuffer_slice (*externSl)[2];
  89         sjme_jint cutLen, cutPos;
  90
  91         if (buffer == NULL || result == NULL || opData == NULL)
  92                 return SJME_ERROR_NULL_ARGUMENTS;
  93
  94         if (seekType != SJME_CIRCLE_BUFFER_HEAD &&
  95                 seekType != SJME_CIRCLE_BUFFER_TAIL)
  96                 return SJME_ERROR_INVALID_ARGUMENT;
  97
  98         if (operation != SJME_CIRCLE_BUFFER_GET && seekPos != 0)
  99                 return SJME_ERROR_INVALID_ARGUMENT;
 100
 101         if (seekPos < 0 || length < 0 || (seekPos + length) < 0)
 102                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 103
 104         /* Clear result first. */
 105         memset(result, 0, sizeof(*result));
 106
 107         /* Pushing? */
 108         if (operation == SJME_CIRCLE_BUFFER_PUSH_QUEUE ||
 109                 operation == SJME_CIRCLE_BUFFER_PUSH_WINDOW)
 110         {
 111                 /* Source slice is the data we want to put in. */
 112                 result->src[0].externalBuf = opData;
 113                 result->src[0].base = 0;
 114                 result->src[0].len = length;
 115
 116                 /* Should always be the same. */
 117                 result->dest[0].len = length;
 118
 119                 /* Calculate new current data in the buffer. */
 120                 result->newReady = buffer->ready + length;
 121                 if (result->newReady > buffer->size)
 122                 {
 123                         if (operation != SJME_CIRCLE_BUFFER_PUSH_WINDOW)
 124                                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 125
 126                         /* Cannot add more than what the buffer can contain. */
 127                         if (length > buffer->size)
 128                                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 129
 130                         /* Clip back into bounds. */
 131                         result->newReady = buffer->size;
 132
 133                         /* Completely erasing the entire buffer? */
 134                         if (length == buffer->size)
 135                         {
 136                                 /* Write over everything. */
 137                                 result->dest[0].base = 0;
 138                                 result->dest[0].len = length;
 139
 140                                 /* Set new details. */
 141                                 result->newReadHead = 0;
 142                                 result->newWriteHead = 0;
 143
 144                                 /* Success! */
 145                                 return SJME_ERROR_NONE;
 146                         }
 147                 }
 148
 149                 /* Writing at end */
 150                 if (seekType == SJME_CIRCLE_BUFFER_LAST)
 151                 {
 152                         result->newWriteHead = buffer->writeHead + length;
 153                         result->dest[0].base = buffer->writeHead;
 154                 }
 155
 156                 /* Writing at start */
 157                 else
 158                 {
 159                         result->newReadHead = buffer->readHead - length;
 160                         result->dest[0].base = result->newReadHead;
 161                 }
 162         }
 163
 164         /* Popping? */
 165         else if (operation == SJME_CIRCLE_BUFFER_POP)
 166         {
 167                 sjme_todo("Impl?");
 168                 return sjme_error_notImplemented(0);
 169         }
 170
 171         /* Getting? */
 172         else if (operation == SJME_CIRCLE_BUFFER_GET)
 173         {
 174                 /* Cannot get more data than exists in the buffer. */
 175                 if (seekPos + length < 0 ||
 176                         seekPos + length > buffer->ready)
 177                         return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 178
 179                 /* We want to copy to the destination output buffer. */
 180                 result->dest[0].externalBuf = opData;
 181                 result->dest[0].base = 0;
 182                 result->dest[0].len = length;
 183
 184                 /* The positions in the circle buffer are relative to the heads. */
 185                 result->src[0].len = length;
 186                 if (seekType == SJME_CIRCLE_BUFFER_LAST)
 187                         result->src[0].base = buffer->writeHead - seekPos;
 188                 else
 189                         result->src[0].base = buffer->readHead + seekPos;
 190         }
 191
 192         /* Invalid. */
 193         else
 194                 return SJME_ERROR_INVALID_ARGUMENT;
 195
 196         /* Get appropriate slice for clipping. */
 197         if (result->src[0].externalBuf)
 198         {
 199                 externSl = &result->src;
 200                 circleSl = &result->dest;
 201         }
 202         else
 203         {
 204                 externSl = &result->dest;
 205                 circleSl = &result->src;
 206         }
 207
 208         /* Slice lower region? */
 209         if ((*circleSl)[0].base < 0)
 210         {
 211                 /* How much to cut? */
 212                 cutLen = -((*circleSl)[0].base);
 213
 214                 /* Second slice gets what was trimmed off. */
 215                 (*circleSl)[1].base = buffer->size - cutLen;
 216                 (*circleSl)[1].len = cutLen;
 217                 (*externSl)[1].base = length - cutLen;
 218                 (*externSl)[1].len = cutLen;
 219
 220                 /* Make sure second slice gets the buffer! */
 221                 (*externSl)[1].externalBuf = (*externSl)[0].externalBuf;
 222
 223                 /* First slice is adjusted accordingly. */
 224                 (*circleSl)[0].base = 0;
 225                 (*circleSl)[0].len = (*circleSl)[0].len - cutLen;
 226                 (*externSl)[0].base = 0;
 227                 (*externSl)[0].len = (*externSl)[1].base;
 228         }
 229
 230         /* Slice higher region? */
 231         else if ((*circleSl)[0].base + (*circleSl)[0].len > buffer->size)
 232         {
 233                 /* How much to cut? */
 234                 cutLen = buffer->size - ((*circleSl)[0].base);
 235                 cutPos = length - cutLen;
 236
 237                 /* Second slice gets what was trimmed off. */
 238                 (*circleSl)[1].base = 0;
 239                 (*circleSl)[1].len = cutLen;
 240                 (*externSl)[1].base = cutPos;
 241                 (*externSl)[1].len = cutLen;
 242
 243                 /* Make sure second slice gets the buffer! */
 244                 (*externSl)[1].externalBuf = (*externSl)[0].externalBuf;
 245
 246                 /* First slice is adjusted accordingly. */
 247                 (*circleSl)[0].base = (*circleSl)[0].base;
 248                 (*circleSl)[0].len = buffer->size - cutLen;
 249                 (*externSl)[0].base = (*externSl)[0].base;
 250                 (*externSl)[0].len = cutPos;
 251         }
 252
 253         /* Make sure read/write heads are wrapped properly. */
 254         /* From negative position. */
 255         while (result->newReadHead < 0)
 256                 result->newReadHead += buffer->size;
 257         while (result->newWriteHead < 0)
 258                 result->newWriteHead += buffer->size;
 259
 260         /* From positive position. */
 261         while (result->newReadHead >= buffer->size)
 262                 result->newReadHead -= buffer->size;
 263         while (result->newWriteHead >= buffer->size)
 264                 result->newWriteHead -= buffer->size;
 265
 266         /* Success! */
 267         return SJME_ERROR_NONE;
 268 }
 269
 270 static sjme_errorCode sjme_circleBuffer_operate(
 271         sjme_attrInNotNull sjme_circleBuffer* buffer,
 272         sjme_attrInNotNull sjme_circleBuffer_calcResult* result)
 273 {
 274         sjme_jint i;
 275         sjme_circleBuffer_slice* src;
 276         sjme_circleBuffer_slice* dest;
 277
 278         if (buffer == NULL || result == NULL)
 279                 return SJME_ERROR_NULL_ARGUMENTS;
 280
 281         /* These must be in range. */
 282         if (result->newReady < 0 || result->newReady > buffer->size ||
 283                 result->newReadHead < 0 || result->newReadHead > buffer->size ||
 284                 result->newWriteHead < 0 || result->newWriteHead > buffer->size)
 285                 return SJME_ERROR_ILLEGAL_STATE;
 286
 287         /* Copy each slice, if valid. */
 288         for (i = 0; i < 2; i++)
 289         {
 290                 src = &result->src[i];
 291                 dest = &result->dest[i];
 292
 293                 /* Skip if nothing here. */
 294                 if (src->len == 0 && dest->len == 0)
 295                         continue;
 296
 297                 /* Fail if both external or both internal. */
 298                 if ((src->externalBuf == NULL) == (dest->externalBuf == NULL))
 299                         return SJME_ERROR_ILLEGAL_STATE;
 300
 301                 /* These must always be the same. */
 302                 if (src->len != dest->len)
 303                         return SJME_ERROR_ILLEGAL_STATE;
 304
 305                 /* External to internal. */
 306                 if (src->externalBuf != NULL && dest->externalBuf == NULL)
 307                         memmove(&buffer->buffer[dest->base],
 308                                 SJME_POINTER_OFFSET(src->externalBuf, src->base),
 309                                 src->len);
 310
 311                 /* Internal to external. */
 312                 else if (src->externalBuf == NULL && dest->externalBuf != NULL)
 313                         memmove(SJME_POINTER_OFFSET(dest->externalBuf, dest->base),
 314                                 &buffer->buffer[src->base],
 315                                 src->len);
 316
 317                 /* Should not occur. */
 318                 else
 319                         return SJME_ERROR_ILLEGAL_STATE;
 320         }
 321
 322         /* Set new heads. */
 323         buffer->ready = result->newReady;
 324         buffer->readHead = result->newReadHead;
 325         buffer->writeHead = result->newWriteHead;
 326
 327         /* Success! */
 328         return SJME_ERROR_NONE;
 329 }
 330
 331 sjme_errorCode sjme_circleBuffer_available(
 332         sjme_attrInNotNull sjme_circleBuffer* buffer,
 333         sjme_attrOutNotNull sjme_jint* outAvailable)
 334 {
 335         if (buffer == NULL || outAvailable == NULL)
 336                 return SJME_ERROR_NULL_ARGUMENTS;
 337
 338         *outAvailable = buffer->size - buffer->ready;
 339         return SJME_ERROR_NONE;
 340 }
 341
 342 sjme_errorCode sjme_circleBuffer_destroy(
 343         sjme_attrInNotNull sjme_circleBuffer* buffer)
 344 {
 345         sjme_errorCode error;
 346
 347         if (buffer == NULL)
 348                 return SJME_ERROR_NULL_ARGUMENTS;
 349
 350         /* Free storage first. */
 351         if (buffer->buffer != NULL)
 352         {
 353                 if (sjme_error_is(error = sjme_alloc_free(buffer->buffer)))
 354                         return sjme_error_default(error);
 355                 buffer->buffer = NULL;
 356         }
 357
 358         /* Then the buffer info. */
 359         return sjme_alloc_free(buffer);
 360 }
 361
 362 sjme_errorCode sjme_circleBuffer_get(
 363         sjme_attrInNotNull sjme_circleBuffer* buffer,
 364         sjme_attrOutNotNullBuf(outDataLen) sjme_pointer outData,
 365         sjme_attrInPositiveNonZero sjme_jint length,
 366         sjme_attrInValue sjme_circleBuffer_seekEnd seekType,
 367         sjme_attrInPositiveNonZero sjme_jint seekPos)
 368 {
 369         sjme_errorCode error;
 370         sjme_circleBuffer_calcResult result;
 371
 372         if (buffer == NULL)
 373                 return SJME_ERROR_NULL_ARGUMENTS;
 374
 375         /* Calculate result. */
 376         memset(&result, 0, sizeof(result));
 377         if (sjme_error_is(error = sjme_circleBuffer_calc(
 378                 buffer, &result,
 379                 SJME_CIRCLE_BUFFER_GET,
 380                 outData, length, seekType, seekPos)))
 381                 return sjme_error_default(error);
 382
 383         /* Operate on it. */
 384         return sjme_circleBuffer_operate(buffer, &result);
 385 }
 386
 387 sjme_errorCode sjme_circleBuffer_new(
 388         sjme_attrInNotNull sjme_alloc_pool* inPool,
 389         sjme_attrOutNotNull sjme_circleBuffer** outBuffer,
 390         sjme_attrInValue sjme_circleBuffer_mode inMode,
 391         sjme_attrInPositiveNonZero sjme_jint length)
 392 {
 393         sjme_errorCode error;
 394         sjme_pointer storage;
 395         sjme_circleBuffer* result;
 396
 397         if (inPool == NULL || outBuffer == NULL)
 398                 return SJME_ERROR_NULL_ARGUMENTS;
 399
 400         if (inMode != SJME_CIRCLE_BUFFER_QUEUE &&
 401                 inMode != SJME_CIRCLE_BUFFER_WINDOW)
 402                 return SJME_ERROR_INVALID_ARGUMENT;
 403
 404         if (length <= 0)
 405                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 406
 407         /* Make sure we can allocate the buffer first. */
 408         storage = NULL;
 409         if (sjme_error_is(error = sjme_alloc(inPool,
 410                 length, (sjme_pointer*)&storage)) || storage == NULL)
 411                 goto fail_allocStorage;
 412
 413         /* Then the actual buffer info. */
 414         result = NULL;
 415         if (sjme_error_is(error = sjme_alloc(inPool,
 416                 sizeof(*result), (sjme_pointer*)&result)) || result == NULL)
 417                 goto fail_allocResult;
 418
 419         /* Setup information. */
 420         result->size = length;
 421         result->mode = inMode;
 422         result->buffer = storage;
 423
 424         /* Success! */
 425         *outBuffer = result;
 426         return SJME_ERROR_NONE;
 427
 428 fail_allocResult:
 429         if (result != NULL)
 430                 sjme_alloc_free(result);
 431 fail_allocStorage:
 432         if (storage != NULL)
 433                 sjme_alloc_free(storage);
 434
 435         return sjme_error_default(error);
 436 }
 437
 438 sjme_errorCode sjme_circleBuffer_pop(
 439         sjme_attrInNotNull sjme_circleBuffer* buffer,
 440         sjme_attrOutNotNullBuf(outDataLen) sjme_pointer outData,
 441         sjme_attrInPositiveNonZero sjme_jint length,
 442         sjme_attrInValue sjme_circleBuffer_seekEnd seekType)
 443 {
 444         sjme_errorCode error;
 445         sjme_circleBuffer_calcResult result;
 446
 447         if (buffer == NULL)
 448                 return SJME_ERROR_NULL_ARGUMENTS;
 449
 450         /* Calculate result. */
 451         memset(&result, 0, sizeof(result));
 452         if (sjme_error_is(error = sjme_circleBuffer_calc(
 453                 buffer, &result,
 454                 SJME_CIRCLE_BUFFER_POP,
 455                 outData, length, seekType, 0)))
 456                 return sjme_error_default(error);
 457
 458         /* Operate on it. */
 459         return sjme_circleBuffer_operate(buffer, &result);
 460 }
 461
 462 sjme_errorCode sjme_circleBuffer_push(
 463         sjme_attrInNotNull sjme_circleBuffer* buffer,
 464         sjme_attrInNotNullBuf(outDataLen) sjme_cpointer inData,
 465         sjme_attrInPositiveNonZero sjme_jint length,
 466         sjme_attrInValue sjme_circleBuffer_seekEnd seekType)
 467 {
 468         sjme_errorCode error;
 469         sjme_circleBuffer_calcResult result;
 470
 471         if (buffer == NULL)
 472                 return SJME_ERROR_NULL_ARGUMENTS;
 473
 474         /* Calculate result. */
 475         memset(&result, 0, sizeof(result));
 476         if (sjme_error_is(error = sjme_circleBuffer_calc(
 477                 buffer, &result,
 478                 (buffer->mode == SJME_CIRCLE_BUFFER_WINDOW ?
 479                         SJME_CIRCLE_BUFFER_PUSH_WINDOW : SJME_CIRCLE_BUFFER_PUSH_QUEUE),
 480                 inData, length, seekType, 0)))
 481                 return sjme_error_default(error);
 482
 483         /* Operate on it. */
 484         return sjme_circleBuffer_operate(buffer, &result);
 485 }
 486
 487 sjme_errorCode sjme_circleBuffer_stored(
 488         sjme_attrInNotNull sjme_circleBuffer* buffer,
 489         sjme_attrOutNotNull sjme_jint* outStored)
 490 {
 491         if (buffer == NULL || outStored == NULL)
 492                 return SJME_ERROR_NULL_ARGUMENTS;
 493
 494         *outStored = buffer->ready;
 495         return SJME_ERROR_NONE;
 496 }