Ruby  2.5.0dev(2017-10-22revision60238)
Data Structures | Macros | Typedefs | Functions | Variables
st.c File Reference
#include "internal.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>

Go to the source code of this file.

Data Structures

struct  st_table_entry
 
struct  st_features
 

Macros

#define PREFETCH(addr, write_p)
 
#define EXPECT(expr, val)   (expr)
 
#define ATTRIBUTE_UNUSED
 
#define st_assert(cond)   ((void)(0 && (cond)))
 
#define type_numhash   st_hashtype_num
 
#define ST_INIT_VAL   0xafafafafafafafaf
 
#define ST_INIT_VAL_BYTE   0xafa
 
#define malloc   ruby_xmalloc
 
#define calloc   ruby_xcalloc
 
#define realloc   ruby_xrealloc
 
#define free   ruby_xfree
 
#define EQUAL(tab, x, y)   ((x) == (y) || (*(tab)->type->compare)((x),(y)) == 0)
 
#define PTR_EQUAL(tab, ptr, hash_val, key_)   ((ptr)->hash == (hash_val) && EQUAL((tab), (key_), (ptr)->key))
 
#define MAX_POWER2   30
 
#define RESERVED_HASH_VAL   (~(st_hash_t) 0)
 
#define RESERVED_HASH_SUBSTITUTION_VAL   ((st_hash_t) 0)
 
#define MINIMAL_POWER2   2
 
#define MAX_POWER2_FOR_TABLES_WITHOUT_BINS   4
 
#define EMPTY_BIN   0
 
#define DELETED_BIN   1
 
#define ENTRY_BASE   2
 
#define MARK_BIN_EMPTY(tab, i)   (set_bin((tab)->bins, get_size_ind(tab), i, EMPTY_BIN))
 
#define UNDEFINED_ENTRY_IND   (~(st_index_t) 0)
 
#define UNDEFINED_BIN_IND   (~(st_index_t) 0)
 
#define MARK_BIN_DELETED(tab, i)
 
#define EMPTY_BIN_P(b)   ((b) == EMPTY_BIN)
 
#define DELETED_BIN_P(b)   ((b) == DELETED_BIN)
 
#define EMPTY_OR_DELETED_BIN_P(b)   ((b) <= DELETED_BIN)
 
#define IND_EMPTY_BIN_P(tab, i)   (EMPTY_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))
 
#define IND_DELETED_BIN_P(tab, i)   (DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))
 
#define IND_EMPTY_OR_DELETED_BIN_P(tab, i)   (EMPTY_OR_DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))
 
#define MARK_ENTRY_DELETED(e_ptr)   ((e_ptr)->hash = RESERVED_HASH_VAL)
 
#define DELETED_ENTRY_P(e_ptr)   ((e_ptr)->hash == RESERVED_HASH_VAL)
 
#define COLLISION
 
#define FOUND_BIN
 
#define REBUILD_THRESHOLD   4
 
#define FNV1_32A_INIT   0x811c9dc5
 
#define FNV_32_PRIME   0x01000193
 
#define BIG_CONSTANT(x, y)   ((st_index_t)(x)<<32|(st_index_t)(y))
 
#define ROTL(x, n)   ((x)<<(n)|(x)>>(SIZEOF_ST_INDEX_T*CHAR_BIT-(n)))
 
#define C1   (st_index_t)0xcc9e2d51
 
#define C2   (st_index_t)0x1b873593
 
#define r1   (17)
 
#define r2   (11)
 
#define r1   (16)
 
#define r2   (13)
 
#define r3   (16)
 
#define data_at(n)   (st_index_t)((unsigned char)data[(n)])
 
#define UNALIGNED_ADD_4   UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
 
#define UNALIGNED_ADD_ALL   UNALIGNED_ADD_4
 
#define UNALIGNED_ADD(n)
 
#define UNALIGNED_ADD(n)
 
#define SKIP_TAIL   1
 
#define UNALIGNED_ADD(n)
 

Typedefs

typedef st_index_t st_hash_t
 

Functions

st_table * st_init_table_with_size (const struct st_hash_type *type, st_index_t size)
 
st_table * st_init_table (const struct st_hash_type *type)
 
st_table * st_init_numtable (void)
 
st_table * st_init_numtable_with_size (st_index_t size)
 
st_table * st_init_strtable (void)
 
st_table * st_init_strtable_with_size (st_index_t size)
 
st_table * st_init_strcasetable (void)
 
st_table * st_init_strcasetable_with_size (st_index_t size)
 
void st_clear (st_table *tab)
 
void st_free_table (st_table *tab)
 
size_t st_memsize (const st_table *tab)
 
int st_lookup (st_table *tab, st_data_t key, st_data_t *value)
 
int st_get_key (st_table *tab, st_data_t key, st_data_t *result)
 
int st_insert (st_table *tab, st_data_t key, st_data_t value)
 
void st_add_direct (st_table *tab, st_data_t key, st_data_t value)
 
int st_insert2 (st_table *tab, st_data_t key, st_data_t value, st_data_t(*func)(st_data_t))
 
st_table * st_copy (st_table *old_tab)
 
int st_delete (st_table *tab, st_data_t *key, st_data_t *value)
 
int st_delete_safe (st_table *tab, st_data_t *key, st_data_t *value, st_data_t never ATTRIBUTE_UNUSED)
 
int st_shift (st_table *tab, st_data_t *key, st_data_t *value)
 
void st_cleanup_safe (st_table *tab ATTRIBUTE_UNUSED, st_data_t never ATTRIBUTE_UNUSED)
 
int st_update (st_table *tab, st_data_t key, st_update_callback_func *func, st_data_t arg)
 
int st_foreach (st_table *tab, int(*func)(ANYARGS), st_data_t arg)
 
int st_foreach_check (st_table *tab, int(*func)(ANYARGS), st_data_t arg, st_data_t never ATTRIBUTE_UNUSED)
 
st_index_t st_keys (st_table *tab, st_data_t *keys, st_index_t size)
 
st_index_t st_keys_check (st_table *tab, st_data_t *keys, st_index_t size, st_data_t never ATTRIBUTE_UNUSED)
 
st_index_t st_values (st_table *tab, st_data_t *values, st_index_t size)
 
st_index_t st_values_check (st_table *tab, st_data_t *values, st_index_t size, st_data_t never ATTRIBUTE_UNUSED)
 
st_index_t st_hash (const void *ptr, size_t len, st_index_t h)
 
st_index_t st_hash_uint32 (st_index_t h, uint32_t i)
 
st_index_t st_hash_uint (st_index_t h, st_index_t i)
 
st_index_t st_hash_end (st_index_t h)
 
st_index_t st_hash_start (st_index_t h)
 
int st_locale_insensitive_strcasecmp (const char *s1, const char *s2)
 
int st_locale_insensitive_strncasecmp (const char *s1, const char *s2, size_t n)
 
 PUREFUNC (static st_index_t strcasehash(st_data_t))
 
int st_numcmp (st_data_t x, st_data_t y)
 
st_index_t st_numhash (st_data_t n)
 
void rb_hash_bulk_insert (long argc, const VALUE *argv, VALUE hash)
 

Variables

const struct st_hash_type st_hashtype_num
 

Macro Definition Documentation

◆ ATTRIBUTE_UNUSED

#define ATTRIBUTE_UNUSED

Definition at line 119 of file st.c.

◆ BIG_CONSTANT

#define BIG_CONSTANT (   x,
  y 
)    ((st_index_t)(x)<<32|(st_index_t)(y))

Definition at line 1665 of file st.c.

◆ C1

#define C1   (st_index_t)0xcc9e2d51

Definition at line 1669 of file st.c.

◆ C2

#define C2   (st_index_t)0x1b873593

Definition at line 1670 of file st.c.

◆ calloc

#define calloc   ruby_xcalloc

Definition at line 168 of file st.c.

◆ COLLISION

#define COLLISION

Definition at line 716 of file st.c.

◆ data_at

#define data_at (   n)    (st_index_t)((unsigned char)data[(n)])

◆ DELETED_BIN

#define DELETED_BIN   1

Definition at line 370 of file st.c.

◆ DELETED_BIN_P

#define DELETED_BIN_P (   b)    ((b) == DELETED_BIN)

Definition at line 396 of file st.c.

◆ DELETED_ENTRY_P

#define DELETED_ENTRY_P (   e_ptr)    ((e_ptr)->hash == RESERVED_HASH_VAL)

Definition at line 408 of file st.c.

Referenced by st_shift().

◆ EMPTY_BIN

#define EMPTY_BIN   0

Definition at line 369 of file st.c.

◆ EMPTY_BIN_P

#define EMPTY_BIN_P (   b)    ((b) == EMPTY_BIN)

Definition at line 395 of file st.c.

◆ EMPTY_OR_DELETED_BIN_P

#define EMPTY_OR_DELETED_BIN_P (   b)    ((b) <= DELETED_BIN)

Definition at line 397 of file st.c.

◆ ENTRY_BASE

#define ENTRY_BASE   2

Definition at line 372 of file st.c.

◆ EQUAL

#define EQUAL (   tab,
  x,
  y 
)    ((x) == (y) || (*(tab)->type->compare)((x),(y)) == 0)

Definition at line 173 of file st.c.

◆ EXPECT

#define EXPECT (   expr,
  val 
)    (expr)

Definition at line 118 of file st.c.

◆ FNV1_32A_INIT

#define FNV1_32A_INIT   0x811c9dc5

Definition at line 1643 of file st.c.

◆ FNV_32_PRIME

#define FNV_32_PRIME   0x01000193

Definition at line 1648 of file st.c.

◆ FOUND_BIN

#define FOUND_BIN

Definition at line 717 of file st.c.

◆ free

#define free   ruby_xfree

Definition at line 170 of file st.c.

Referenced by st_free_table().

◆ IND_DELETED_BIN_P

#define IND_DELETED_BIN_P (   tab,
  i 
)    (DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))

Definition at line 402 of file st.c.

◆ IND_EMPTY_BIN_P

#define IND_EMPTY_BIN_P (   tab,
  i 
)    (EMPTY_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))

Definition at line 401 of file st.c.

◆ IND_EMPTY_OR_DELETED_BIN_P

#define IND_EMPTY_OR_DELETED_BIN_P (   tab,
  i 
)    (EMPTY_OR_DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))

Definition at line 403 of file st.c.

◆ malloc

#define malloc   ruby_xmalloc

Definition at line 167 of file st.c.

Referenced by st_copy().

◆ MARK_BIN_DELETED

#define MARK_BIN_DELETED (   tab,
  i 
)
Value:
do { \
st_assert(i != UNDEFINED_BIN_IND); \
st_assert(! IND_EMPTY_OR_DELETED_BIN_P(tab, i)); \
set_bin((tab)->bins, get_size_ind(tab), i, DELETED_BIN); \
} while (0)
DELETED_BIN
#define DELETED_BIN
Definition: st.c:370
IND_EMPTY_OR_DELETED_BIN_P
#define IND_EMPTY_OR_DELETED_BIN_P(tab, i)
Definition: st.c:403
UNDEFINED_BIN_IND
#define UNDEFINED_BIN_IND
Definition: st.c:381

Definition at line 386 of file st.c.

◆ MARK_BIN_EMPTY

#define MARK_BIN_EMPTY (   tab,
  i 
)    (set_bin((tab)->bins, get_size_ind(tab), i, EMPTY_BIN))

Definition at line 376 of file st.c.

◆ MARK_ENTRY_DELETED

#define MARK_ENTRY_DELETED (   e_ptr)    ((e_ptr)->hash = RESERVED_HASH_VAL)

Definition at line 407 of file st.c.

◆ MAX_POWER2

#define MAX_POWER2   30

Definition at line 262 of file st.c.

◆ MAX_POWER2_FOR_TABLES_WITHOUT_BINS

#define MAX_POWER2_FOR_TABLES_WITHOUT_BINS   4

Definition at line 324 of file st.c.

◆ MINIMAL_POWER2

#define MINIMAL_POWER2   2

Definition at line 316 of file st.c.

◆ PREFETCH

#define PREFETCH (   addr,
  write_p 
)

Definition at line 117 of file st.c.

◆ PTR_EQUAL

#define PTR_EQUAL (   tab,
  ptr,
  hash_val,
  key_ 
)    ((ptr)->hash == (hash_val) && EQUAL((tab), (key_), (ptr)->key))

Definition at line 174 of file st.c.

◆ r1 [1/2]

#define r1   (17)

Referenced by BIGNUM_1c().

◆ r1 [2/2]

#define r1   (16)

◆ r2 [1/2]

#define r2   (11)

Referenced by BIGNUM_1c().

◆ r2 [2/2]

#define r2   (13)

◆ r3

#define r3   (16)

◆ realloc

#define realloc   ruby_xrealloc

Definition at line 169 of file st.c.

◆ REBUILD_THRESHOLD

#define REBUILD_THRESHOLD   4

Definition at line 723 of file st.c.

◆ RESERVED_HASH_SUBSTITUTION_VAL

#define RESERVED_HASH_SUBSTITUTION_VAL   ((st_hash_t) 0)

Definition at line 302 of file st.c.

◆ RESERVED_HASH_VAL

#define RESERVED_HASH_VAL   (~(st_hash_t) 0)

Definition at line 301 of file st.c.

◆ ROTL

#define ROTL (   x,
  n 
)    ((x)<<(n)|(x)>>(SIZEOF_ST_INDEX_T*CHAR_BIT-(n)))

Definition at line 1666 of file st.c.

◆ SKIP_TAIL

#define SKIP_TAIL   1

◆ st_assert

#define st_assert (   cond)    ((void)(0 && (cond)))

Definition at line 125 of file st.c.

Referenced by rb_hash_bulk_insert().

◆ ST_INIT_VAL

#define ST_INIT_VAL   0xafafafafafafafaf

Definition at line 159 of file st.c.

◆ ST_INIT_VAL_BYTE

#define ST_INIT_VAL_BYTE   0xafa

Definition at line 160 of file st.c.

◆ type_numhash

#define type_numhash   st_hashtype_num

Definition at line 137 of file st.c.

Referenced by st_init_numtable(), and st_init_numtable_with_size().

◆ UNALIGNED_ADD [1/3]

#define UNALIGNED_ADD (   n)
Value:
case SIZEOF_ST_INDEX_T - (n) - 1: \
t |= data_at(n) << CHAR_BIT*(n)
SIZEOF_ST_INDEX_T
#define SIZEOF_ST_INDEX_T
Definition: st.h:59
CHAR_BIT
#define CHAR_BIT
Definition: ruby.h:196
data_at
#define data_at(n)

◆ UNALIGNED_ADD [2/3]

#define UNALIGNED_ADD (   n)
Value:
case (n) + 1: \
d |= data_at(n) << CHAR_BIT*(n)
CHAR_BIT
#define CHAR_BIT
Definition: ruby.h:196
data_at
#define data_at(n)

◆ UNALIGNED_ADD [3/3]

#define UNALIGNED_ADD (   n)
Value:
case (n) + 1: \
t |= data_at(n) << CHAR_BIT*(n)
CHAR_BIT
#define CHAR_BIT
Definition: ruby.h:196
data_at
#define data_at(n)

◆ UNALIGNED_ADD_4

#define UNALIGNED_ADD_4   UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)

◆ UNALIGNED_ADD_ALL

#define UNALIGNED_ADD_ALL   UNALIGNED_ADD_4

Referenced by st_hash().

◆ UNDEFINED_BIN_IND

#define UNDEFINED_BIN_IND   (~(st_index_t) 0)

Definition at line 381 of file st.c.

◆ UNDEFINED_ENTRY_IND

#define UNDEFINED_ENTRY_IND   (~(st_index_t) 0)

Definition at line 380 of file st.c.

Typedef Documentation

◆ st_hash_t

typedef st_index_t st_hash_t

Definition at line 129 of file st.c.

Function Documentation

◆ PUREFUNC()

PUREFUNC ( static st_index_t   strcasehashst_data_t)

Referenced by st_locale_insensitive_strncasecmp().

◆ rb_hash_bulk_insert()

void rb_hash_bulk_insert ( long  argc,
const VALUE *  argv,
VALUE  hash 
)

Definition at line 2169 of file st.c.

References NULL, st_table::num_entries, rb_hash_new_with_size(), RBASIC_CLEAR_CLASS, RHASH, and st_assert.

◆ st_add_direct()

void st_add_direct ( st_table *  tab,
st_data_t  key,
st_data_t  value 
)

Definition at line 1173 of file st.c.

◆ st_cleanup_safe()

void st_cleanup_safe ( st_table *tab  ATTRIBUTE_UNUSED,
st_data_t never  ATTRIBUTE_UNUSED 
)

Definition at line 1379 of file st.c.

◆ st_clear()

void st_clear ( st_table *  tab)

Definition at line 655 of file st.c.

◆ st_copy()

st_table* st_copy ( st_table *  old_tab)

Definition at line 1237 of file st.c.

References st_table::bins, malloc, and NULL.

◆ st_delete()

int st_delete ( st_table *  tab,
st_data_t *  key,
st_data_t *  value 
)

Definition at line 1313 of file st.c.

◆ st_delete_safe()

int st_delete_safe ( st_table *  tab,
st_data_t *  key,
st_data_t *  value,
st_data_t never  ATTRIBUTE_UNUSED 
)

Definition at line 1324 of file st.c.

◆ st_foreach()

int st_foreach ( st_table *  tab,
int(*)(ANYARGS)  func,
st_data_t  arg 
)

Definition at line 1554 of file st.c.

◆ st_foreach_check()

int st_foreach_check ( st_table *  tab,
int(*)(ANYARGS)  func,
st_data_t  arg,
st_data_t never  ATTRIBUTE_UNUSED 
)

Definition at line 1561 of file st.c.

◆ st_free_table()

void st_free_table ( st_table *  tab)

Definition at line 666 of file st.c.

References st_table::bins, st_table::entries, free, and NULL.

◆ st_get_key()

int st_get_key ( st_table *  tab,
st_data_t  key,
st_data_t *  result 
)

Definition at line 1062 of file st.c.

◆ st_hash()

st_index_t st_hash ( const void *  ptr,
size_t  len,
st_index_t  h 
)

Definition at line 1728 of file st.c.

References CHAR_BIT, len, SIZEOF_ST_INDEX_T, st_data_t, and UNALIGNED_ADD_ALL.

◆ st_hash_end()

st_index_t st_hash_end ( st_index_t  h)

Definition at line 1886 of file st.c.

◆ st_hash_start()

st_index_t st_hash_start ( st_index_t  h)

Definition at line 1894 of file st.c.

Referenced by rb_hash_start().

◆ st_hash_uint()

st_index_t st_hash_uint ( st_index_t  h,
st_index_t  i 
)

Definition at line 1873 of file st.c.

◆ st_hash_uint32()

st_index_t st_hash_uint32 ( st_index_t  h,
uint32_t  i 
)

Definition at line 1867 of file st.c.

◆ st_init_numtable()

st_table* st_init_numtable ( void  )

Definition at line 610 of file st.c.

References st_init_table(), and type_numhash.

◆ st_init_numtable_with_size()

st_table* st_init_numtable_with_size ( st_index_t  size)

Definition at line 617 of file st.c.

References st_init_table_with_size(), and type_numhash.

◆ st_init_strcasetable()

st_table* st_init_strcasetable ( void  )

Definition at line 640 of file st.c.

References st_init_table().

Referenced by Init_transcode().

◆ st_init_strcasetable_with_size()

st_table* st_init_strcasetable_with_size ( st_index_t  size)

Definition at line 648 of file st.c.

References st_init_table_with_size().

◆ st_init_strtable()

st_table* st_init_strtable ( void  )

Definition at line 625 of file st.c.

References st_init_table().

◆ st_init_strtable_with_size()

st_table* st_init_strtable_with_size ( st_index_t  size)

Definition at line 632 of file st.c.

References st_init_table_with_size().

◆ st_init_table()

st_table* st_init_table ( const struct st_hash_type *  type)

Definition at line 602 of file st.c.

References st_init_table_with_size().

Referenced by st_init_numtable(), st_init_strcasetable(), and st_init_strtable().

◆ st_init_table_with_size()

st_table* st_init_table_with_size ( const struct st_hash_type *  type,
st_index_t  size 
)

Definition at line 555 of file st.c.

References getenv.

Referenced by st_init_numtable_with_size(), st_init_strcasetable_with_size(), st_init_strtable_with_size(), and st_init_table().

◆ st_insert()

int st_insert ( st_table *  tab,
st_data_t  key,
st_data_t  value 
)

Definition at line 1098 of file st.c.

References bin.

◆ st_insert2()

int st_insert2 ( st_table *  tab,
st_data_t  key,
st_data_t  value,
st_data_t(*)(st_data_t)  func 
)

Definition at line 1185 of file st.c.

References bin.

◆ st_keys()

st_index_t st_keys ( st_table *  tab,
st_data_t *  keys,
st_index_t  size 
)

Definition at line 1592 of file st.c.

Referenced by rb_hash_keys().

◆ st_keys_check()

st_index_t st_keys_check ( st_table *  tab,
st_data_t *  keys,
st_index_t  size,
st_data_t never  ATTRIBUTE_UNUSED 
)

Definition at line 1599 of file st.c.

◆ st_locale_insensitive_strcasecmp()

int st_locale_insensitive_strcasecmp ( const char *  s1,
const char *  s2 
)

Definition at line 1907 of file st.c.

◆ st_locale_insensitive_strncasecmp()

int st_locale_insensitive_strncasecmp ( const char *  s1,
const char *  s2,
size_t  n 
)

Definition at line 1931 of file st.c.

References PUREFUNC().

◆ st_lookup()

int st_lookup ( st_table *  tab,
st_data_t  key,
st_data_t *  value 
)

Definition at line 1038 of file st.c.

References bin, and st_table_entry::hash.

◆ st_memsize()

size_t st_memsize ( const st_table *  tab)

Definition at line 676 of file st.c.

References st_table::bins, and NULL.

◆ st_numcmp()

int st_numcmp ( st_data_t  x,
st_data_t  y 
)

Definition at line 1977 of file st.c.

◆ st_numhash()

st_index_t st_numhash ( st_data_t  n)

Definition at line 1983 of file st.c.

◆ st_shift()

int st_shift ( st_table *  tab,
st_data_t *  key,
st_data_t *  value 
)

Definition at line 1335 of file st.c.

References bin, st_table::bins, DELETED_ENTRY_P, st_table::entries, st_table::entries_bound, st_table::entries_start, st_table_entry::key, NULL, and st_table_entry::record.

◆ st_update()

int st_update ( st_table *  tab,
st_data_t  key,
st_update_callback_func *  func,
st_data_t  arg 
)

Definition at line 1393 of file st.c.

References bin, st_table_entry::hash, NULL, and st_data_t.

◆ st_values()

st_index_t st_values ( st_table *  tab,
st_data_t *  values,
st_index_t  size 
)

Definition at line 1630 of file st.c.

Referenced by rb_hash_values().

◆ st_values_check()

st_index_t st_values_check ( st_table *  tab,
st_data_t *  values,
st_index_t  size,
st_data_t never  ATTRIBUTE_UNUSED 
)

Definition at line 1637 of file st.c.

Variable Documentation

◆ st_hashtype_num

const struct st_hash_type st_hashtype_num
Initial value:
= {
st_numcmp,
st_numhash,
}
st_numhash
st_index_t st_numhash(st_data_t n)
Definition: st.c:1983
st_numcmp
int st_numcmp(st_data_t x, st_data_t y)
Definition: st.c:1977

Definition at line 138 of file st.c.

Generated by   doxygen 1.8.13