utils.h File Reference

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

Go to the source code of this file.

Macros
#define	DC_SWISS_INITIAL_CAPACITY   256
#define	DC_SWISS_SIMD_PROBE_SIZE   16
#define	DC_SWISS_VAL_ID_MASK   0b01111111
#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)

Typedefs
typedef uint8_t	dc_swiss_id
typedef uint8_t	dc_swiss_ctrl
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))
static bool	dc_swiss_is_present (dc_swiss_ctrl ctrl)
static uint8_t	dc_swiss_ctrl_get_id (dc_swiss_ctrl ctrl)
static dc_swiss_id	dc_swiss_id_from_hash (size_t hash)
static size_t	dc_swiss_capacity (size_t for_items)
static void	dc_swiss_ctrl_set_at (dc_swiss_ctrl *self, size_t capacity, size_t index, dc_swiss_ctrl val)
static dc_swiss_rehash_action	dc_swiss_heuristic_should_extend (size_t tombstones, size_t count, size_t capacity)

Macro Definition Documentation

DC_SWISS_INITIAL_CAPACITY

#define DC_SWISS_INITIAL_CAPACITY   256

Definition at line 7 of file utils.h.

DC_SWISS_NO_INDEX

#define DC_SWISS_NO_INDEX   ((size_t)-1)

Definition at line 81 of file utils.h.

DC_SWISS_SIMD_PROBE_SIZE

#define DC_SWISS_SIMD_PROBE_SIZE   16

Definition at line 8 of file utils.h.

DC_SWISS_VAL_DELETED

#define DC_SWISS_VAL_DELETED   0b11111110

Definition at line 17 of file utils.h.

DC_SWISS_VAL_EMPTY

#define DC_SWISS_VAL_EMPTY   0b10000000

Definition at line 18 of file utils.h.

DC_SWISS_VAL_ID_MASK

#define DC_SWISS_VAL_ID_MASK   0b01111111

Definition at line 15 of file utils.h.

DC_SWISS_VAL_SENTINEL

#define DC_SWISS_VAL_SENTINEL   0b11111111

Definition at line 16 of file utils.h.

Typedef Documentation

dc_swiss_ctrl

typedef uint8_t dc_swiss_ctrl

Definition at line 22 of file utils.h.

dc_swiss_id

typedef uint8_t dc_swiss_id

Definition at line 21 of file utils.h.

dc_swiss_optional_index

typedef size_t dc_swiss_optional_index

Definition at line 82 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 59 of file utils.h.

             {
    DC_SWISS_DOUBLE_CAPACITY,
    DC_SWISS_CLEANUP_TOMBSONES,
    DC_SWISS_DO_NOTHING,
} dc_swiss_rehash_action;

Function Documentation

DC_STATIC_ASSERT()

DC_STATIC_ASSERT

(

DC_MATH_IS_POWER_OF_2(DC_SWISS_SIMD_PROBE_SIZE)

)

dc_swiss_capacity()

size_t dc_swiss_capacity ( size_t for_items )

static

Definition at line 44 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);
}

dc_swiss_ctrl_get_id()

uint8_t dc_swiss_ctrl_get_id ( dc_swiss_ctrl ctrl )

static

Definition at line 35 of file utils.h.

                                                        {
    DC_ASSUME(dc_swiss_is_present(ctrl));
    return ctrl & DC_SWISS_VAL_ID_MASK;
}

dc_swiss_ctrl_set_at()

void dc_swiss_ctrl_set_at ( dc_swiss_ctrl * self, size_t capacity, size_t index, dc_swiss_ctrl val )

static

Definition at line 51 of file utils.h.

                                                    {
    self[index] = val;
    if (index < (DC_SWISS_SIMD_PROBE_SIZE - 1)) {
        self[capacity + 1 + index] = val;
    }
}

dc_swiss_heuristic_should_extend()

dc_swiss_rehash_action dc_swiss_heuristic_should_extend ( size_t tombstones, size_t count, size_t capacity )

static

Definition at line 65 of file utils.h.

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

dc_swiss_id_from_hash()

dc_swiss_id dc_swiss_id_from_hash ( size_t hash )

static

Definition at line 40 of file utils.h.

                                                      {
    return (uint8_t)(hash & DC_SWISS_VAL_ID_MASK);
}

dc_swiss_is_present()

bool dc_swiss_is_present ( dc_swiss_ctrl ctrl )

static

Definition at line 24 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;
    }
}