utils.h File Reference

#include <stdint.h>
#include <emmintrin.h>
#include <derive-c/core/math.h>
#include <derive-c/core/prelude.h>

Go to the source code of this file.

Macros
#define	DC_SWISS_INITIAL_CAPACITY   256
#define	_DC_SWISS_SIMD_PROBE_SIZE   sizeof(_dc_swiss_ctrl_group)
#define	DC_SWISS_VAL_SENTINEL   0b11111111
#define	DC_SWISS_VAL_DELETED   0b11111110
#define	DC_SWISS_VAL_EMPTY   0b10000000
#define	_DC_SWISS_NO_INDEX   ((size_t)-1)
#define	_DC_SWISS_BITMASK_FOR_EACH(mask, idx_var)

Typedefs
typedef __m128i	_dc_swiss_ctrl_group
typedef uint8_t	_dc_swiss_ctrl
typedef size_t	_dc_swiss_ctrl_group_index
typedef uint16_t	_dc_swiss_ctrl_group_offset
typedef uint16_t	_dc_swiss_ctrl_group_bitmask
typedef size_t	_dc_swiss_optional_index

Enumerations
enum	_dc_swiss_rehash_action { DC_SWISS_DOUBLE_CAPACITY , DC_SWISS_CLEANUP_TOMBSONES , DC_SWISS_DO_NOTHING }

Functions
	DC_STATIC_ASSERT (DC_MATH_IS_POWER_OF_2(_DC_SWISS_SIMD_PROBE_SIZE))
DC_INTERNAL static DC_PURE bool	_dc_swiss_is_present (_dc_swiss_ctrl ctrl)
static DC_INTERNAL _dc_swiss_ctrl	_dc_swiss_ctrl_from_hash (size_t hash)
static DC_INTERNAL size_t	dc_swiss_capacity (size_t for_items)
static DC_INTERNAL void	_dc_swiss_ctrl_set_at (_dc_swiss_ctrl *self, size_t capacity, size_t index, _dc_swiss_ctrl val)
static DC_INTERNAL _dc_swiss_rehash_action	_dc_swiss_heuristic_should_extend (size_t tombstones, size_t count, size_t capacity)
static DC_INTERNAL _dc_swiss_ctrl_group	_dc_swiss_group_load (const _dc_swiss_ctrl *group_ptr)
static DC_INTERNAL _dc_swiss_ctrl_group_bitmask	_dc_swiss_group_match (_dc_swiss_ctrl_group group, uint8_t value)
static DC_INTERNAL _dc_swiss_ctrl_group_offset	_dc_swiss_ctrl_group_bitmask_lowest (_dc_swiss_ctrl_group_bitmask mask)
static DC_INTERNAL _dc_swiss_ctrl_group_bitmask	_dc_swiss_ctrl_group_bitmask_clear_lowest (_dc_swiss_ctrl_group_bitmask mask)
static DC_INTERNAL size_t	_dc_swiss_group_index_to_slot (size_t group_start, _dc_swiss_ctrl_group_offset idx, size_t capacity)

Variables
static size_t const	_dc_swiss_index_capacity = SIZE_MAX - (1 + _DC_SWISS_SIMD_PROBE_SIZE)

Macro Definition Documentation

_DC_SWISS_BITMASK_FOR_EACH

#define _DC_SWISS_BITMASK_FOR_EACH	(		mask,
			idx_var )

Value:

    for (_dc_swiss_ctrl_group_bitmask _m = (mask); _m != 0;                                        \
         _m = _dc_swiss_ctrl_group_bitmask_clear_lowest(_m))                                       \
        for (_dc_swiss_ctrl_group_offset idx_var = _dc_swiss_ctrl_group_bitmask_lowest(_m),        \
                                         _once = 1;                                                \
             _once; _once = 0)

Definition at line 129 of file utils.h.

#define _DC_SWISS_BITMASK_FOR_EACH(mask, idx_var)                                                  \
    for (_dc_swiss_ctrl_group_bitmask _m = (mask); _m != 0;                                        \
         _m = _dc_swiss_ctrl_group_bitmask_clear_lowest(_m))                                       \
        for (_dc_swiss_ctrl_group_offset idx_var = _dc_swiss_ctrl_group_bitmask_lowest(_m),        \
                                         _once = 1;                                                \
             _once; _once = 0)

_DC_SWISS_NO_INDEX

#define _DC_SWISS_NO_INDEX   ((size_t)-1)

Definition at line 98 of file utils.h.

_DC_SWISS_SIMD_PROBE_SIZE

#define _DC_SWISS_SIMD_PROBE_SIZE   sizeof(_dc_swiss_ctrl_group)

Definition at line 28 of file utils.h.

DC_SWISS_INITIAL_CAPACITY

#define DC_SWISS_INITIAL_CAPACITY   256

Definition at line 13 of file utils.h.

DC_SWISS_VAL_DELETED

#define DC_SWISS_VAL_DELETED   0b11111110

Definition at line 36 of file utils.h.

DC_SWISS_VAL_EMPTY

#define DC_SWISS_VAL_EMPTY   0b10000000

Definition at line 37 of file utils.h.

DC_SWISS_VAL_SENTINEL

#define DC_SWISS_VAL_SENTINEL   0b11111111

Definition at line 35 of file utils.h.

Typedef Documentation

_dc_swiss_ctrl

typedef uint8_t _dc_swiss_ctrl

Definition at line 19 of file utils.h.

_dc_swiss_ctrl_group

typedef __m128i _dc_swiss_ctrl_group

Definition at line 18 of file utils.h.

_dc_swiss_ctrl_group_bitmask

typedef uint16_t _dc_swiss_ctrl_group_bitmask

Definition at line 26 of file utils.h.

_dc_swiss_ctrl_group_index

typedef size_t _dc_swiss_ctrl_group_index

Definition at line 22 of file utils.h.

_dc_swiss_ctrl_group_offset

typedef uint16_t _dc_swiss_ctrl_group_offset

Definition at line 23 of file utils.h.

_dc_swiss_optional_index

typedef size_t _dc_swiss_optional_index

Definition at line 99 of file utils.h.

Enumeration Type Documentation

_dc_swiss_rehash_action

enum _dc_swiss_rehash_action

Enumerator
DC_SWISS_DOUBLE_CAPACITY
DC_SWISS_CLEANUP_TOMBSONES
DC_SWISS_DO_NOTHING

Definition at line 75 of file utils.h.

             {
    DC_SWISS_DOUBLE_CAPACITY,
    DC_SWISS_CLEANUP_TOMBSONES,
    DC_SWISS_DO_NOTHING,
} _dc_swiss_rehash_action;

Function Documentation

_dc_swiss_ctrl_from_hash()

DC_INTERNAL _dc_swiss_ctrl _dc_swiss_ctrl_from_hash ( size_t hash )

static

Definition at line 51 of file utils.h.

                                                                        {
    // Taking the top 7 bits for `H2`
    return (uint8_t)(hash >> (sizeof(size_t) * 8 - 7));
}

_dc_swiss_ctrl_group_bitmask_clear_lowest()

DC_INTERNAL _dc_swiss_ctrl_group_bitmask _dc_swiss_ctrl_group_bitmask_clear_lowest ( _dc_swiss_ctrl_group_bitmask mask )

static

Definition at line 124 of file utils.h.

                                                                             {
    return mask & (mask - 1);
}

_dc_swiss_ctrl_group_bitmask_lowest()

DC_INTERNAL _dc_swiss_ctrl_group_offset _dc_swiss_ctrl_group_bitmask_lowest ( _dc_swiss_ctrl_group_bitmask mask )

static

Definition at line 118 of file utils.h.

                                                                       {
    DC_ASSUME(mask != 0);
    return (_dc_swiss_ctrl_group_offset)__builtin_ctz(mask);
}

_dc_swiss_ctrl_set_at()

DC_INTERNAL void _dc_swiss_ctrl_set_at ( _dc_swiss_ctrl * self, size_t capacity, size_t index, _dc_swiss_ctrl val )

static

Definition at line 63 of file utils.h.

                                                                  {
    // JUSTIFY: Setting index past capacity
    // ctrl[..capacity) = (empty or value)
    // ctrl[capacity] = SENTINEL
    // ctrl[capacity+1+i] = ctrl[i] for (_DC_SWISS_PROBE_SIZE - 1)
    self[index] = val;
    if (index < (_DC_SWISS_SIMD_PROBE_SIZE - 1)) {
        self[capacity + 1 + index] = val;
    }
}

_dc_swiss_group_index_to_slot()

DC_INTERNAL size_t _dc_swiss_group_index_to_slot ( size_t group_start, _dc_swiss_ctrl_group_offset idx, size_t capacity )

static

Definition at line 136 of file utils.h.

                                                                         {
    size_t pos = group_start + idx;
    if (pos < capacity) {
        return pos;
    }
    if (pos == capacity) {
        // On the sentinel value
        return _DC_SWISS_NO_INDEX;
    }
 
    // After the sentinel
    return pos - capacity - 1;
}

_dc_swiss_group_load()

DC_INTERNAL _dc_swiss_ctrl_group _dc_swiss_group_load ( const _dc_swiss_ctrl * group_ptr )

static

Definition at line 106 of file utils.h.

                                                                                              {
    // Deal with unaligned loads - can be optimised away in release
    return _mm_loadu_si128((const __m128i_u*)group_ptr);
}

_dc_swiss_group_match()

DC_INTERNAL _dc_swiss_ctrl_group_bitmask _dc_swiss_group_match ( _dc_swiss_ctrl_group group, uint8_t value )

static

Definition at line 111 of file utils.h.

                                                                                     {
    __m128i cmp = _mm_cmpeq_epi8(group, _mm_set1_epi8((char)value));
    return (_dc_swiss_ctrl_group_bitmask)_mm_movemask_epi8(cmp);
}

_dc_swiss_heuristic_should_extend()

DC_INTERNAL _dc_swiss_rehash_action _dc_swiss_heuristic_should_extend ( size_t tombstones, size_t count, size_t capacity )

static

Definition at line 82 of file utils.h.

                                                                                    {
    DC_ASSUME(capacity > 0);
 
    const size_t max_load = capacity - (capacity / 8);
 
    if (count + tombstones >= max_load) {
        return tombstones > 0 ? DC_SWISS_CLEANUP_TOMBSONES : DC_SWISS_DOUBLE_CAPACITY;
    }
 
    if (tombstones > (count / 2)) {
        return DC_SWISS_CLEANUP_TOMBSONES;
    }
 
    return DC_SWISS_DO_NOTHING;
}

_dc_swiss_is_present()

DC_INTERNAL static DC_PURE bool _dc_swiss_is_present ( _dc_swiss_ctrl ctrl )

static

Definition at line 40 of file utils.h.

                                                                          {
    switch (ctrl) {
    case DC_SWISS_VAL_EMPTY:
    case DC_SWISS_VAL_DELETED:
    case DC_SWISS_VAL_SENTINEL:
        return false;
    default:
        return true;
    }
}

DC_STATIC_ASSERT()

DC_STATIC_ASSERT

(

DC_MATH_IS_POWER_OF_2(_DC_SWISS_SIMD_PROBE_SIZE)

)

dc_swiss_capacity()

DC_INTERNAL size_t dc_swiss_capacity ( size_t for_items )

static

Definition at line 56 of file utils.h.

                                                              {
    if (for_items < _DC_SWISS_SIMD_PROBE_SIZE) {
        return _DC_SWISS_SIMD_PROBE_SIZE;
    }
    return dc_math_next_power_of_2(for_items);
}

Variable Documentation

_dc_swiss_index_capacity

size_t const _dc_swiss_index_capacity = SIZE_MAX - (1 + _DC_SWISS_SIMD_PROBE_SIZE)

static

Definition at line 104 of file utils.h.