[ tor-browser ].git.dasho

Vector.c (25761B)
      1 /***************************************************************************************************
      2 
      3  Zyan Core Library (Zycore-C)
      4 
      5  Original Author : Florian Bernd
      6 
      7 * Permission is hereby granted, free of charge, to any person obtaining a copy
      8 * of this software and associated documentation files (the "Software"), to deal
      9 * in the Software without restriction, including without limitation the rights
     10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
     11 * copies of the Software, and to permit persons to whom the Software is
     12 * furnished to do so, subject to the following conditions:
     13 *
     14 * The above copyright notice and this permission notice shall be included in all
     15 * copies or substantial portions of the Software.
     16 *
     17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
     20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
     22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
     23 * SOFTWARE.
     24 
     25 ***************************************************************************************************/
     26 
     27 #include "zydis/Zycore/LibC.h"
     28 #include "zydis/Zycore/Vector.h"
     29 
     30 /* ============================================================================================== */
     31 /* Internal macros                                                                                */
     32 /* ============================================================================================== */
     33 
     34 /**
     35 * Checks, if the passed vector should grow.
     36 *
     37 * @param   size        The desired size of the vector.
     38 * @param   capacity    The current capacity of the vector.
     39 *
     40 * @return  `ZYAN_TRUE`, if the vector should grow or `ZYAN_FALSE`, if not.
     41 */
     42 #define ZYCORE_VECTOR_SHOULD_GROW(size, capacity) \
     43    ((size) > (capacity))
     44 
     45 /**
     46 * Checks, if the passed vector should shrink.
     47 *
     48 * @param   size        The desired size of the vector.
     49 * @param   capacity    The current capacity of the vector.
     50 * @param   threshold   The shrink threshold.
     51 *
     52 * @return  `ZYAN_TRUE`, if the vector should shrink or `ZYAN_FALSE`, if not.
     53 */
     54 #define ZYCORE_VECTOR_SHOULD_SHRINK(size, capacity, threshold) \
     55    (((threshold) != 0) && ((size) * (threshold) < (capacity)))
     56 
     57 /**
     58 * Returns the offset of the element at the given `index`.
     59 *
     60 * @param   vector  A pointer to the `ZyanVector` instance.
     61 * @param   index   The element index.
     62 *
     63 * @return  The offset of the element at the given `index`.
     64 */
     65 #define ZYCORE_VECTOR_OFFSET(vector, index) \
     66    ((void*)((ZyanU8*)(vector)->data + ((index) * (vector)->element_size)))
     67 
     68 /* ============================================================================================== */
     69 /* Internal functions                                                                             */
     70 /* ============================================================================================== */
     71 
     72 /* ---------------------------------------------------------------------------------------------- */
     73 /* Helper functions                                                                               */
     74 /* ---------------------------------------------------------------------------------------------- */
     75 
     76 /**
     77 * Reallocates the internal buffer of the vector.
     78 *
     79 * @param   vector      A pointer to the `ZyanVector` instance.
     80 * @param   capacity    The new capacity.
     81 *
     82 * @return  A zyan status code.
     83 */
     84 static ZyanStatus ZyanVectorReallocate(ZyanVector* vector, ZyanUSize capacity)
     85 {
     86    ZYAN_ASSERT(vector);
     87    ZYAN_ASSERT(vector->capacity >= ZYAN_VECTOR_MIN_CAPACITY);
     88    ZYAN_ASSERT(vector->element_size);
     89    ZYAN_ASSERT(vector->data);
     90 
     91    if (!vector->allocator)
     92    {
     93        if (vector->capacity < capacity)
     94        {
     95            return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
     96        }
     97        return ZYAN_STATUS_SUCCESS;
     98    }
     99 
    100    ZYAN_ASSERT(vector->allocator);
    101    ZYAN_ASSERT(vector->allocator->reallocate);
    102 
    103    if (capacity < ZYAN_VECTOR_MIN_CAPACITY)
    104    {
    105        if (vector->capacity > ZYAN_VECTOR_MIN_CAPACITY)
    106        {
    107            capacity = ZYAN_VECTOR_MIN_CAPACITY;
    108        } else
    109        {
    110            return ZYAN_STATUS_SUCCESS;
    111        }
    112    }
    113 
    114    vector->capacity = capacity;
    115    ZYAN_CHECK(vector->allocator->reallocate(vector->allocator, &vector->data,
    116        vector->element_size, vector->capacity));
    117 
    118    return ZYAN_STATUS_SUCCESS;
    119 }
    120 
    121 /**
    122 * Shifts all elements starting at the specified `index` by the amount of `count` to the left.
    123 *
    124 * @param   vector  A pointer to the `ZyanVector` instance.
    125 * @param   index   The start index.
    126 * @param   count   The amount of shift operations.
    127 *
    128 * @return  A zyan status code.
    129 */
    130 static ZyanStatus ZyanVectorShiftLeft(ZyanVector* vector, ZyanUSize index, ZyanUSize count)
    131 {
    132    ZYAN_ASSERT(vector);
    133    ZYAN_ASSERT(vector->element_size);
    134    ZYAN_ASSERT(vector->data);
    135    ZYAN_ASSERT(count > 0);
    136    //ZYAN_ASSERT((ZyanISize)count - (ZyanISize)index + 1 >= 0);
    137 
    138    const void* const source = ZYCORE_VECTOR_OFFSET(vector, index + count);
    139    void* const dest         = ZYCORE_VECTOR_OFFSET(vector, index);
    140    const ZyanUSize size     = (vector->size - index - count) * vector->element_size;
    141    ZYAN_MEMMOVE(dest, source, size);
    142 
    143    return ZYAN_STATUS_SUCCESS;
    144 }
    145 
    146 /**
    147 * Shifts all elements starting at the specified `index` by the amount of `count` to the right.
    148 *
    149 * @param   vector  A pointer to the `ZyanVector` instance.
    150 * @param   index   The start index.
    151 * @param   count   The amount of shift operations.
    152 *
    153 * @return  A zyan status code.
    154 */
    155 static ZyanStatus ZyanVectorShiftRight(ZyanVector* vector, ZyanUSize index, ZyanUSize count)
    156 {
    157    ZYAN_ASSERT(vector);
    158    ZYAN_ASSERT(vector->element_size);
    159    ZYAN_ASSERT(vector->data);
    160    ZYAN_ASSERT(count > 0);
    161    ZYAN_ASSERT(vector->size + count <= vector->capacity);
    162 
    163    const void* const source = ZYCORE_VECTOR_OFFSET(vector, index);
    164    void* const dest         = ZYCORE_VECTOR_OFFSET(vector, index + count);
    165    const ZyanUSize size     = (vector->size - index) * vector->element_size;
    166    ZYAN_MEMMOVE(dest, source, size);
    167 
    168    return ZYAN_STATUS_SUCCESS;
    169 }
    170 
    171 /* ---------------------------------------------------------------------------------------------- */
    172 
    173 /* ============================================================================================== */
    174 /* Exported functions                                                                             */
    175 /* ============================================================================================== */
    176 
    177 /* ---------------------------------------------------------------------------------------------- */
    178 /* Constructor and destructor                                                                     */
    179 /* ---------------------------------------------------------------------------------------------- */
    180 
    181 #ifndef ZYAN_NO_LIBC
    182 
    183 ZyanStatus ZyanVectorInit(ZyanVector* vector, ZyanUSize element_size, ZyanUSize capacity,
    184    ZyanMemberProcedure destructor)
    185 {
    186    return ZyanVectorInitEx(vector, element_size, capacity, destructor, ZyanAllocatorDefault(),
    187        ZYAN_VECTOR_DEFAULT_GROWTH_FACTOR, ZYAN_VECTOR_DEFAULT_SHRINK_THRESHOLD);
    188 }
    189 
    190 #endif // ZYAN_NO_LIBC
    191 
    192 ZyanStatus ZyanVectorInitEx(ZyanVector* vector, ZyanUSize element_size, ZyanUSize capacity,
    193    ZyanMemberProcedure destructor, ZyanAllocator* allocator, ZyanU8 growth_factor,
    194    ZyanU8 shrink_threshold)
    195 {
    196    if (!vector || !element_size || !allocator || (growth_factor < 1))
    197    {
    198        return ZYAN_STATUS_INVALID_ARGUMENT;
    199    }
    200 
    201    ZYAN_ASSERT(allocator->allocate);
    202 
    203    vector->allocator        = allocator;
    204    vector->growth_factor    = growth_factor;
    205    vector->shrink_threshold = shrink_threshold;
    206    vector->size             = 0;
    207    vector->capacity         = ZYAN_MAX(ZYAN_VECTOR_MIN_CAPACITY, capacity);
    208    vector->element_size     = element_size;
    209    vector->destructor       = destructor;
    210    vector->data             = ZYAN_NULL;
    211 
    212    return allocator->allocate(vector->allocator, &vector->data, vector->element_size,
    213        vector->capacity);
    214 }
    215 
    216 ZyanStatus ZyanVectorInitCustomBuffer(ZyanVector* vector, ZyanUSize element_size,
    217    void* buffer, ZyanUSize capacity, ZyanMemberProcedure destructor)
    218 {
    219    if (!vector || !element_size || !buffer || !capacity)
    220    {
    221        return ZYAN_STATUS_INVALID_ARGUMENT;
    222    }
    223 
    224    vector->allocator        = ZYAN_NULL;
    225    vector->growth_factor    = 1;
    226    vector->shrink_threshold = 0;
    227    vector->size             = 0;
    228    vector->capacity         = capacity;
    229    vector->element_size     = element_size;
    230    vector->destructor       = destructor;
    231    vector->data             = buffer;
    232 
    233    return ZYAN_STATUS_SUCCESS;
    234 }
    235 
    236 ZyanStatus ZyanVectorDestroy(ZyanVector* vector)
    237 {
    238    if (!vector)
    239    {
    240        return ZYAN_STATUS_INVALID_ARGUMENT;
    241    }
    242 
    243    ZYAN_ASSERT(vector->element_size);
    244    ZYAN_ASSERT(vector->data);
    245 
    246    if (vector->destructor)
    247    {
    248        for (ZyanUSize i = 0; i < vector->size; ++i)
    249        {
    250            vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i));
    251        }
    252    }
    253 
    254    if (vector->allocator && vector->capacity)
    255    {
    256        ZYAN_ASSERT(vector->allocator->deallocate);
    257        ZYAN_CHECK(vector->allocator->deallocate(vector->allocator, vector->data,
    258            vector->element_size, vector->capacity));
    259    }
    260 
    261    vector->data = ZYAN_NULL;
    262    return ZYAN_STATUS_SUCCESS;
    263 }
    264 
    265 /* ---------------------------------------------------------------------------------------------- */
    266 /* Duplication                                                                                    */
    267 /* ---------------------------------------------------------------------------------------------- */
    268 
    269 #ifndef ZYAN_NO_LIBC
    270 
    271 ZyanStatus ZyanVectorDuplicate(ZyanVector* destination, const ZyanVector* source,
    272    ZyanUSize capacity)
    273 {
    274    return ZyanVectorDuplicateEx(destination, source, capacity, ZyanAllocatorDefault(),
    275        ZYAN_VECTOR_DEFAULT_GROWTH_FACTOR, ZYAN_VECTOR_DEFAULT_SHRINK_THRESHOLD);
    276 }
    277 
    278 #endif // ZYAN_NO_LIBC
    279 
    280 ZyanStatus ZyanVectorDuplicateEx(ZyanVector* destination, const ZyanVector* source,
    281    ZyanUSize capacity, ZyanAllocator* allocator, ZyanU8 growth_factor, ZyanU8 shrink_threshold)
    282 {
    283    if (!source)
    284    {
    285        return ZYAN_STATUS_INVALID_ARGUMENT;
    286    }
    287 
    288    const ZyanUSize len = source->size;
    289 
    290    capacity = ZYAN_MAX(capacity, len);
    291    ZYAN_CHECK(ZyanVectorInitEx(destination, source->element_size, capacity, source->destructor,
    292        allocator, growth_factor, shrink_threshold));
    293    ZYAN_ASSERT(destination->capacity >= len);
    294 
    295    ZYAN_MEMCPY(destination->data, source->data, len * source->element_size);
    296    destination->size = len;
    297 
    298    return ZYAN_STATUS_SUCCESS;
    299 }
    300 
    301 ZyanStatus ZyanVectorDuplicateCustomBuffer(ZyanVector* destination, const ZyanVector* source,
    302    void* buffer, ZyanUSize capacity)
    303 {
    304    if (!source)
    305    {
    306        return ZYAN_STATUS_INVALID_ARGUMENT;
    307    }
    308 
    309    const ZyanUSize len = source->size;
    310 
    311    if (capacity < len)
    312    {
    313        return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
    314    }
    315 
    316    ZYAN_CHECK(ZyanVectorInitCustomBuffer(destination, source->element_size, buffer, capacity,
    317        source->destructor));
    318    ZYAN_ASSERT(destination->capacity >= len);
    319 
    320    ZYAN_MEMCPY(destination->data, source->data, len * source->element_size);
    321    destination->size = len;
    322 
    323    return ZYAN_STATUS_SUCCESS;
    324 }
    325 
    326 /* ---------------------------------------------------------------------------------------------- */
    327 /* Element access                                                                                 */
    328 /* ---------------------------------------------------------------------------------------------- */
    329 
    330 const void* ZyanVectorGet(const ZyanVector* vector, ZyanUSize index)
    331 {
    332    if (!vector || (index >= vector->size))
    333    {
    334        return ZYAN_NULL;
    335    }
    336 
    337    ZYAN_ASSERT(vector->element_size);
    338    ZYAN_ASSERT(vector->data);
    339 
    340    return ZYCORE_VECTOR_OFFSET(vector, index);
    341 }
    342 
    343 void* ZyanVectorGetMutable(const ZyanVector* vector, ZyanUSize index)
    344 {
    345    if (!vector || (index >= vector->size))
    346    {
    347        return ZYAN_NULL;
    348    }
    349 
    350    ZYAN_ASSERT(vector->element_size);
    351    ZYAN_ASSERT(vector->data);
    352 
    353    return ZYCORE_VECTOR_OFFSET(vector, index);
    354 }
    355 
    356 ZyanStatus ZyanVectorGetPointer(const ZyanVector* vector, ZyanUSize index, const void** value)
    357 {
    358    if (!vector || !value)
    359    {
    360        return ZYAN_STATUS_INVALID_ARGUMENT;
    361    }
    362    if (index >= vector->size)
    363    {
    364        return ZYAN_STATUS_OUT_OF_RANGE;
    365    }
    366 
    367    ZYAN_ASSERT(vector->element_size);
    368    ZYAN_ASSERT(vector->data);
    369 
    370    *value = (const void*)ZYCORE_VECTOR_OFFSET(vector, index);
    371 
    372    return ZYAN_STATUS_SUCCESS;
    373 }
    374 
    375 ZyanStatus ZyanVectorGetPointerMutable(const ZyanVector* vector, ZyanUSize index, void** value)
    376 {
    377    if (!vector || !value)
    378    {
    379        return ZYAN_STATUS_INVALID_ARGUMENT;
    380    }
    381    if (index >= vector->size)
    382    {
    383        return ZYAN_STATUS_OUT_OF_RANGE;
    384    }
    385 
    386    ZYAN_ASSERT(vector->element_size);
    387    ZYAN_ASSERT(vector->data);
    388 
    389    *value = ZYCORE_VECTOR_OFFSET(vector, index);
    390 
    391    return ZYAN_STATUS_SUCCESS;
    392 }
    393 
    394 ZyanStatus ZyanVectorSet(ZyanVector* vector, ZyanUSize index, const void* value)
    395 {
    396    if (!vector || !value)
    397    {
    398        return ZYAN_STATUS_INVALID_ARGUMENT;
    399    }
    400    if (index >= vector->size)
    401    {
    402        return ZYAN_STATUS_OUT_OF_RANGE;
    403    }
    404 
    405    ZYAN_ASSERT(vector->element_size);
    406    ZYAN_ASSERT(vector->data);
    407 
    408    void* const offset = ZYCORE_VECTOR_OFFSET(vector, index);
    409    if (vector->destructor)
    410    {
    411        vector->destructor(offset);
    412    }
    413    ZYAN_MEMCPY(offset, value, vector->element_size);
    414 
    415    return ZYAN_STATUS_SUCCESS;
    416 }
    417 
    418 /* ---------------------------------------------------------------------------------------------- */
    419 /* Insertion                                                                                      */
    420 /* ---------------------------------------------------------------------------------------------- */
    421 
    422 ZyanStatus ZyanVectorPushBack(ZyanVector* vector, const void* element)
    423 {
    424    if (!vector || !element)
    425    {
    426        return ZYAN_STATUS_INVALID_ARGUMENT;
    427    }
    428 
    429    ZYAN_ASSERT(vector->element_size);
    430    ZYAN_ASSERT(vector->data);
    431 
    432    if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + 1, vector->capacity))
    433    {
    434        ZYAN_CHECK(ZyanVectorReallocate(vector,
    435            ZYAN_MAX(1, (ZyanUSize)((vector->size + 1) * vector->growth_factor))));
    436    }
    437 
    438    void* const offset = ZYCORE_VECTOR_OFFSET(vector, vector->size);
    439    ZYAN_MEMCPY(offset, element, vector->element_size);
    440 
    441    ++vector->size;
    442 
    443    return ZYAN_STATUS_SUCCESS;
    444 }
    445 
    446 ZyanStatus ZyanVectorInsert(ZyanVector* vector, ZyanUSize index, const void* element)
    447 {
    448    return ZyanVectorInsertRange(vector, index, element, 1);
    449 }
    450 
    451 ZyanStatus ZyanVectorInsertRange(ZyanVector* vector, ZyanUSize index, const void* elements,
    452    ZyanUSize count)
    453 {
    454    if (!vector || !elements || !count)
    455    {
    456        return ZYAN_STATUS_INVALID_ARGUMENT;
    457    }
    458    if (index > vector->size)
    459    {
    460        return ZYAN_STATUS_OUT_OF_RANGE;
    461    }
    462 
    463    ZYAN_ASSERT(vector->element_size);
    464    ZYAN_ASSERT(vector->data);
    465 
    466    if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + count, vector->capacity))
    467    {
    468        ZYAN_CHECK(ZyanVectorReallocate(vector,
    469            ZYAN_MAX(1, (ZyanUSize)((vector->size + count) * vector->growth_factor))));
    470    }
    471 
    472    if (index < vector->size)
    473    {
    474        ZYAN_CHECK(ZyanVectorShiftRight(vector, index, count));
    475    }
    476 
    477    void* const offset = ZYCORE_VECTOR_OFFSET(vector, index);
    478    ZYAN_MEMCPY(offset, elements, count * vector->element_size);
    479    vector->size += count;
    480 
    481    return ZYAN_STATUS_SUCCESS;
    482 }
    483 
    484 ZyanStatus ZyanVectorEmplace(ZyanVector* vector, void** element, ZyanMemberFunction constructor)
    485 {
    486    if (!vector)
    487    {
    488        return ZYAN_STATUS_INVALID_ARGUMENT;
    489    }
    490 
    491    return ZyanVectorEmplaceEx(vector, vector->size, element, constructor);
    492 }
    493 
    494 ZyanStatus ZyanVectorEmplaceEx(ZyanVector* vector, ZyanUSize index, void** element,
    495    ZyanMemberFunction constructor)
    496 {
    497    if (!vector)
    498    {
    499        return ZYAN_STATUS_INVALID_ARGUMENT;
    500    }
    501    if (index > vector->size)
    502    {
    503        return ZYAN_STATUS_OUT_OF_RANGE;
    504    }
    505 
    506    ZYAN_ASSERT(vector->element_size);
    507    ZYAN_ASSERT(vector->data);
    508 
    509    if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + 1, vector->capacity))
    510    {
    511        ZYAN_CHECK(ZyanVectorReallocate(vector,
    512            ZYAN_MAX(1, (ZyanUSize)((vector->size + 1) * vector->growth_factor))));
    513    }
    514 
    515    if (index < vector->size)
    516    {
    517        ZYAN_CHECK(ZyanVectorShiftRight(vector, index, 1));
    518    }
    519 
    520    *element = ZYCORE_VECTOR_OFFSET(vector, index);
    521    if (constructor)
    522    {
    523        ZYAN_CHECK(constructor(*element));
    524    }
    525 
    526    ++vector->size;
    527 
    528    return ZYAN_STATUS_SUCCESS;
    529 }
    530 
    531 /* ---------------------------------------------------------------------------------------------- */
    532 /* Utils                                                                                          */
    533 /* ---------------------------------------------------------------------------------------------- */
    534 
    535 ZyanStatus ZyanVectorSwapElements(ZyanVector* vector, ZyanUSize index_first, ZyanUSize index_second)
    536 {
    537    if (!vector)
    538    {
    539        return ZYAN_STATUS_INVALID_ARGUMENT;
    540    }
    541    if ((index_first >= vector->size) || (index_second >= vector->size))
    542    {
    543        return ZYAN_STATUS_OUT_OF_RANGE;
    544    }
    545 
    546    if (vector->size == vector->capacity)
    547    {
    548        return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
    549    }
    550 
    551    ZYAN_ASSERT(vector->element_size);
    552    ZYAN_ASSERT(vector->data);
    553 
    554    ZyanU64* const t = ZYCORE_VECTOR_OFFSET(vector, vector->size);
    555    ZyanU64* const a = ZYCORE_VECTOR_OFFSET(vector, index_first);
    556    ZyanU64* const b = ZYCORE_VECTOR_OFFSET(vector, index_second);
    557    ZYAN_MEMCPY(t, a, vector->element_size);
    558    ZYAN_MEMCPY(a, b, vector->element_size);
    559    ZYAN_MEMCPY(b, t, vector->element_size);
    560 
    561    return ZYAN_STATUS_SUCCESS;
    562 }
    563 
    564 /* ---------------------------------------------------------------------------------------------- */
    565 /* Deletion                                                                                       */
    566 /* ---------------------------------------------------------------------------------------------- */
    567 
    568 ZyanStatus ZyanVectorDelete(ZyanVector* vector, ZyanUSize index)
    569 {
    570    return ZyanVectorDeleteRange(vector, index, 1);
    571 }
    572 
    573 ZyanStatus ZyanVectorDeleteRange(ZyanVector* vector, ZyanUSize index, ZyanUSize count)
    574 {
    575    if (!vector || !count)
    576    {
    577        return ZYAN_STATUS_INVALID_ARGUMENT;
    578    }
    579    if (index + count > vector->size)
    580    {
    581        return ZYAN_STATUS_OUT_OF_RANGE;
    582    }
    583 
    584    if (vector->destructor)
    585    {
    586        for (ZyanUSize i = index; i < index + count; ++i)
    587        {
    588            vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i));
    589        }
    590    }
    591 
    592    if (index + count < vector->size)
    593    {
    594        ZYAN_CHECK(ZyanVectorShiftLeft(vector, index, count));
    595    }
    596 
    597    vector->size -= count;
    598    if (ZYCORE_VECTOR_SHOULD_SHRINK(vector->size, vector->capacity, vector->shrink_threshold))
    599    {
    600        return ZyanVectorReallocate(vector,
    601            ZYAN_MAX(1, (ZyanUSize)(vector->size * vector->growth_factor)));
    602    }
    603 
    604    return ZYAN_STATUS_SUCCESS;
    605 }
    606 
    607 ZyanStatus ZyanVectorPopBack(ZyanVector* vector)
    608 {
    609    if (!vector)
    610    {
    611        return ZYAN_STATUS_INVALID_ARGUMENT;
    612    }
    613    if (vector->size == 0)
    614    {
    615        return ZYAN_STATUS_OUT_OF_RANGE;
    616    }
    617 
    618    if (vector->destructor)
    619    {
    620         vector->destructor(ZYCORE_VECTOR_OFFSET(vector, vector->size - 1));
    621    }
    622 
    623    --vector->size;
    624    if (ZYCORE_VECTOR_SHOULD_SHRINK(vector->size, vector->capacity, vector->shrink_threshold))
    625    {
    626        return ZyanVectorReallocate(vector,
    627            ZYAN_MAX(1, (ZyanUSize)(vector->size * vector->growth_factor)));
    628    }
    629 
    630    return ZYAN_STATUS_SUCCESS;
    631 }
    632 
    633 ZyanStatus ZyanVectorClear(ZyanVector* vector)
    634 {
    635    return ZyanVectorResizeEx(vector, 0, ZYAN_NULL);
    636 }
    637 
    638 /* ---------------------------------------------------------------------------------------------- */
    639 /* Searching                                                                                      */
    640 /* ---------------------------------------------------------------------------------------------- */
    641 
    642 ZyanStatus ZyanVectorFind(const ZyanVector* vector, const void* element, ZyanISize* found_index,
    643    ZyanEqualityComparison comparison)
    644 {
    645    if (!vector)
    646    {
    647        return ZYAN_STATUS_INVALID_ARGUMENT;
    648    }
    649 
    650    return ZyanVectorFindEx(vector, element, found_index, comparison, 0, vector->size);
    651 }
    652 
    653 ZyanStatus ZyanVectorFindEx(const ZyanVector* vector, const void* element, ZyanISize* found_index,
    654    ZyanEqualityComparison comparison, ZyanUSize index, ZyanUSize count)
    655 {
    656    if (!vector)
    657    {
    658        return ZYAN_STATUS_INVALID_ARGUMENT;
    659    }
    660    if ((index + count > vector->size) || (index == vector->size))
    661    {
    662        return ZYAN_STATUS_OUT_OF_RANGE;
    663    }
    664 
    665    if (!count)
    666    {
    667        *found_index = -1;
    668        return ZYAN_STATUS_FALSE;
    669    }
    670 
    671    ZYAN_ASSERT(vector->element_size);
    672    ZYAN_ASSERT(vector->data);
    673 
    674    for (ZyanUSize i = index; i < index + count; ++i)
    675    {
    676        if (comparison(ZYCORE_VECTOR_OFFSET(vector, i), element))
    677        {
    678            *found_index = i;
    679            return ZYAN_STATUS_TRUE;
    680        }
    681    }
    682 
    683    *found_index = -1;
    684    return ZYAN_STATUS_FALSE;
    685 }
    686 
    687 ZyanStatus ZyanVectorBinarySearch(const ZyanVector* vector, const void* element,
    688    ZyanUSize* found_index, ZyanComparison comparison)
    689 {
    690    if (!vector)
    691    {
    692        return ZYAN_STATUS_INVALID_ARGUMENT;
    693    }
    694 
    695    return ZyanVectorBinarySearchEx(vector, element, found_index, comparison, 0, vector->size);
    696 }
    697 
    698 ZyanStatus ZyanVectorBinarySearchEx(const ZyanVector* vector, const void* element,
    699    ZyanUSize* found_index, ZyanComparison comparison, ZyanUSize index, ZyanUSize count)
    700 {
    701    if (!vector)
    702    {
    703        return ZYAN_STATUS_INVALID_ARGUMENT;
    704    }
    705    if (((index >= vector->size) && (count > 0)) || (index + count > vector->size))
    706    {
    707        return ZYAN_STATUS_OUT_OF_RANGE;
    708    }
    709 
    710    if (!count)
    711    {
    712        *found_index = index;
    713        return ZYAN_STATUS_FALSE;
    714    }
    715 
    716    ZYAN_ASSERT(vector->element_size);
    717    ZYAN_ASSERT(vector->data);
    718 
    719    ZyanStatus status = ZYAN_STATUS_FALSE;
    720    ZyanISize l = index;
    721    ZyanISize h = index + count - 1;
    722    while (l <= h)
    723    {
    724        const ZyanUSize mid = l + ((h - l) >> 1);
    725        const ZyanI32 cmp = comparison(ZYCORE_VECTOR_OFFSET(vector, mid), element);
    726        if (cmp < 0)
    727        {
    728            l = mid + 1;
    729        } else
    730        {
    731            h = mid - 1;
    732            if (cmp == 0)
    733            {
    734                status = ZYAN_STATUS_TRUE;
    735            }
    736        }
    737    }
    738 
    739    *found_index = l;
    740    return status;
    741 }
    742 
    743 /* ---------------------------------------------------------------------------------------------- */
    744 /* Memory management                                                                              */
    745 /* ---------------------------------------------------------------------------------------------- */
    746 
    747 ZyanStatus ZyanVectorResize(ZyanVector* vector, ZyanUSize size)
    748 {
    749    return ZyanVectorResizeEx(vector, size, ZYAN_NULL);
    750 }
    751 
    752 ZyanStatus ZyanVectorResizeEx(ZyanVector* vector, ZyanUSize size, const void* initializer)
    753 {
    754    if (!vector)
    755    {
    756        return ZYAN_STATUS_INVALID_ARGUMENT;
    757    }
    758    if (size == vector->size)
    759    {
    760        return ZYAN_STATUS_SUCCESS;
    761    }
    762 
    763    if (vector->destructor && (size < vector->size))
    764    {
    765        for (ZyanUSize i = size; i < vector->size; ++i)
    766        {
    767            vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i));
    768        }
    769    }
    770 
    771    if (ZYCORE_VECTOR_SHOULD_GROW(size, vector->capacity) ||
    772        ZYCORE_VECTOR_SHOULD_SHRINK(size, vector->capacity, vector->shrink_threshold))
    773    {
    774        ZYAN_ASSERT(vector->growth_factor >= 1);
    775        ZYAN_CHECK(ZyanVectorReallocate(vector, (ZyanUSize)(size * vector->growth_factor)));
    776    }
    777 
    778    if (initializer && (size > vector->size))
    779    {
    780        for (ZyanUSize i = vector->size; i < size; ++i)
    781        {
    782            ZYAN_MEMCPY(ZYCORE_VECTOR_OFFSET(vector, i), initializer, vector->element_size);
    783        }
    784    }
    785 
    786    vector->size = size;
    787 
    788    return ZYAN_STATUS_SUCCESS;
    789 }
    790 
    791 ZyanStatus ZyanVectorReserve(ZyanVector* vector, ZyanUSize capacity)
    792 {
    793    if (!vector)
    794    {
    795        return ZYAN_STATUS_INVALID_ARGUMENT;
    796    }
    797 
    798    if (capacity > vector->capacity)
    799    {
    800        ZYAN_CHECK(ZyanVectorReallocate(vector, capacity));
    801    }
    802 
    803    return ZYAN_STATUS_SUCCESS;
    804 }
    805 
    806 ZyanStatus ZyanVectorShrinkToFit(ZyanVector* vector)
    807 {
    808    if (!vector)
    809    {
    810        return ZYAN_STATUS_INVALID_ARGUMENT;
    811    }
    812 
    813    return ZyanVectorReallocate(vector, vector->size);
    814 }
    815 
    816 /* ---------------------------------------------------------------------------------------------- */
    817 /* Information                                                                                    */
    818 /* ---------------------------------------------------------------------------------------------- */
    819 
    820 ZyanStatus ZyanVectorGetCapacity(const ZyanVector* vector, ZyanUSize* capacity)
    821 {
    822    if (!vector)
    823    {
    824        return ZYAN_STATUS_INVALID_ARGUMENT;
    825    }
    826 
    827    *capacity = vector->capacity;
    828 
    829    return ZYAN_STATUS_SUCCESS;
    830 }
    831 
    832 ZyanStatus ZyanVectorGetSize(const ZyanVector* vector, ZyanUSize* size)
    833 {
    834    if (!vector)
    835    {
    836        return ZYAN_STATUS_INVALID_ARGUMENT;
    837    }
    838 
    839    *size = vector->size;
    840 
    841    return ZYAN_STATUS_SUCCESS;
    842 }
    843 
    844 /* ---------------------------------------------------------------------------------------------- */
    845 
    846 /* ============================================================================================== */
	tor-browser The Tor Browser
	git clone https://git.dasho.dev/tor-browser.git
	Log \| Files \| Refs \| README \| LICENSE