algo.h

#pragma once
 
#include <stdint.h>
#define BINARY_SEARCH(_ARRAY, _KEY, _VALUE, _SIZE) \
({\
    unsigned lower = 0, upper = (_SIZE);\
    /* Binary search until range is small */\
    while (upper - lower > 8) {\
        unsigned mid = lower + ((upper - lower) >> 1);\
        if (_ARRAY[mid]._KEY < _VALUE)\
            lower = mid + 1;\
            else\
                upper = mid;\
    }\
    /* Linear scan for final elements */\
    while (lower < upper && _ARRAY[lower]._KEY < _VALUE) {\
        lower++;\
    }\
    lower;\
})
 
#define ARRAY_INSERT(_ARRAY, _POS, _SIZE) \
    for (unsigned q = _SIZE; q > _POS; --q)\
    {\
        _ARRAY[q] = _ARRAY[q - 1];\
    }\
    _SIZE++;
 
#define ARRAY_DELETE(_ARRAY, _POS, _SIZE) \
    for (unsigned _q = _POS + 1; _q < _SIZE; ++_q)\
    {\
        _ARRAY[_q - 1] = _ARRAY[_q];\
    }\
    _SIZE--;
 
#define INSERT_SORT(_ARRAY, _KEY, _VALUE, _SIZE, _MAX) \
({\
    unsigned pos = BINARY_SEARCH(_ARRAY, _KEY, _VALUE, _SIZE);\
    if (((_ARRAY[pos]._KEY != _VALUE) || (pos == _SIZE)) \
        && (_SIZE < _MAX)) \
    {\
        for (unsigned q = _SIZE; q > pos; --q)\
        {\
            _ARRAY[q] = _ARRAY[q - 1];\
        }\
        _SIZE++;\
    }\
    pos;\
})
 
#ifndef CMRX_USE_FAST_HASH
/* Prospector-generated hash function.
 * Source for constants: https://github.com/skeeto/hash-prospector/issues/19 */
inline uint32_t os_hash_key(uint32_t key) {
    key ^= key >> 16;
    key *= 0x21f0aaadU;
    key ^= key >> 15;
    key *= 0xf35a2d97U;
    key ^= key >> 15;
    return key;
}
#else
/* Minimal mixer */
inline uint32_t os_hash_key(uint32_t key)
{
    key ^= key >> 16;
    key *= 0x45D9F3BU;
    key ^= key >> 16;
    return key;
}
#endif
 
#define HASH_EMPTY 0xFFFFFFFFU
 
#define HASH_SEARCH(_HASHTABLE, _KEY, _VALUE, _MAX) \
({\
    _Static_assert(((_MAX) & ((_MAX) - 1)) == 0 && (_MAX) != 0, "HASH_SEARCH: _MAX must be a power of 2");\
    const uint32_t hash = os_hash_key((uint32_t)_VALUE);\
    const uint32_t mask = (_MAX) - 1;\
    uint32_t pos = hash & mask;\
    uint32_t stride = 1;\
    while (_HASHTABLE[pos]._KEY != _VALUE && _HASHTABLE[pos]._KEY != (typeof(_HASHTABLE[0]._KEY)) HASH_EMPTY) {\
        pos = (pos + stride) & mask;\
        stride++;\
    }\
    pos;\
})
 
#define BITMAP_SET(_BITMAP, _POS, _SIZE) _BITMAP[(_POS) >> 5] |= (1U << ((_POS) & 31));
 
#define BITMAP_CLEAR(_BITMAP, _POS, _SIZE) _BITMAP[(_POS) >> 5] &= ~(1U << ((_POS) & 31));
 
#define BITMAP_TEST(_BITMAP, _POS, _SIZE) ((_BITMAP[(_POS) >> 5] & (1U << ((_POS) & 31))) != 0)
 
#define BITMAP_FIRST(_BITMAP, _SIZE) \
({\
    uint32_t first = ~0;\
    for (unsigned word = 0; word < _SIZE; ++word) {\
        uint32_t ready = _BITMAP[word];\
        if (ready) {\
            uint8_t bit = __builtin_ctz(ready);\
            first = (word << 5) + bit;\
            break;\
        }\
    }\
    first;\
})
#define BITMAP_COPY(_TARGET, _SOURCE, _SIZE) \
    for (unsigned q = 0; q < _SIZE; ++q) _TARGET[q] = _SOURCE[q];
 
 
/* }@ */