st.c File Reference
`#include "ruby/ruby.h"`
`#include <stdio.h>`
`#include <string.h>`

Go to the source code of this file.

## Data Structures

struct | st_table_entry

## Macros

#define | ST_DEFAULT_MAX_DENSITY 5
#define | ST_DEFAULT_INIT_TABLE_SIZE 11
#define | numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
#define | alloc(type) (type*)malloc((size_t)sizeof(type))
#define | Calloc(n, s) (char*)calloc((n),(s))
#define | EQUAL(table, x, y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0)
#define | do_hash(key, table) (unsigned int)(st_index_t)(*(table)->type->hash)((key))
#define | do_hash_bin(key, table) (do_hash((key), (table))%(table)->num_bins)
#define | MINSIZE 8
#define | MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)
#define | PTR_NOT_EQUAL(table, ptr, hash_val, key) ((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
#define | COLLISION
#define | FOUND_ENTRY
#define | FIND_ENTRY(table, ptr, hash_val, bin_pos)
#define | collision_check 0
#define | collision_check 1
#define | MORE_PACKABLE_P(table)
#define | ADD_DIRECT(table, key, value, hash_val, bin_pos)
#define | REMOVE_ENTRY(table, ptr)
#define | FNV1_32A_INIT 0x811c9dc5
#define | FNV_32_PRIME 0x01000193
#define | UNALIGNED_WORD_ACCESS 0
#define | MURMUR 2
#define | MurmurMagic_1 (st_index_t)0xc6a4a793
#define | MurmurMagic_2 (st_index_t)0x5bd1e995
#define | MurmurMagic MurmurMagic_2
#define | murmur_step(h, k) murmur((h), (k), 16)
#define | murmur1(h) murmur_step((h), 24)
#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 | UNALIGNED_ADD(n)

## Typedefs

typedef struct st_table_entry | st_table_entry

## Functions

static st_index_t | strhash (st_data_t)
static st_index_t | strcasehash (st_data_t)
static void | rehash (st_table *)
static st_index_t | new_size (st_index_t size)
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 *table)
void | st_free_table (st_table *table)
size_t | st_memsize (const st_table *table)
int | st_lookup (st_table *table, register st_data_t key, st_data_t *value)
int | st_get_key (st_table *table, register st_data_t key, st_data_t *result)
static void | unpack_entries (register st_table *table)
int | st_insert (register st_table *table, register st_data_t key, st_data_t value)
int | st_insert2 (register st_table *table, register st_data_t key, st_data_t value, st_data_t(*func)(st_data_t))
void | st_add_direct (st_table *table, st_data_t key, st_data_t value)
static void | rehash (register st_table *table)
st_table * | st_copy (st_table *old_table)
int | st_delete (register st_table *table, register st_data_t *key, st_data_t *value)
int | st_delete_safe (register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never)
void | st_cleanup_safe (st_table *table, st_data_t never)
int | st_foreach (st_table *table, int(*func)(ANYARGS), st_data_t arg)
static st_index_t | murmur (st_index_t h, st_index_t k, int r)
static st_index_t | murmur_finish (st_index_t h)
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_strcasecmp (const char *s1, const char *s2)
int | st_strncasecmp (const char *s1, const char *s2, size_t n)
int | st_numcmp (st_data_t x, st_data_t y)
st_index_t | st_numhash (st_data_t n)

## Variables

static struct st_hash_type | type_numhash
static struct st_hash_type | type_strhash
static struct st_hash_type | type_strcasehash
static const unsigned int | primes []

## Macro Definition Documentation

#define ADD_DIRECT | ( |  | table,
|  |  | key,
|  |  | value,
|  |  | hash_val,
|  |  | bin_pos
| ) |  |

Value:
do {\
st_table_entry *entry;\
if ((table)->num_entries > ST_DEFAULT_MAX_DENSITY * (table)->num_bins) {\
rehash(table);\
(bin_pos) = (hash_val) % (table)->num_bins;\
}\
\
entry = alloc(st_table_entry);\
\
entry->hash = (hash_val);\
entry->key = (key);\
entry->record = (value);\
entry->next = (table)->bins[(bin_pos)];\
if ((table)->head != 0) {\
entry->fore = 0;\
(entry->back = (table)->tail)->fore = entry;\
(table)->tail = entry;\
}\
else {\
(table)->head = (table)->tail = entry;\
entry->fore = entry->back = 0;\
}\
(table)->bins[(bin_pos)] = entry;\
(table)->num_entries++;\
} while (0)

Definition at line 389 of file st.c.

Referenced by st_add_direct(), st_insert(), and st_insert2().

#define alloc | ( |  | type | ) | (type*)malloc((size_t)sizeof(type))

Definition at line 69 of file st.c.

Referenced by get_special_folder(), name_add(), onig_reg_init(), scan_env_add_mem_entry(), st_copy(), and st_init_table_with_size().

#define Calloc | ( |  | n,
|  |  | s
| ) |  | (char*)calloc((n),(s))

Definition at line 70 of file st.c.

Referenced by st_copy(), and st_init_table_with_size().

#define COLLISION

Definition at line 305 of file st.c.

#define collision_check 0

Definition at line 383 of file st.c.

#define collision_check 1

Definition at line 383 of file st.c.

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

#define do_hash | ( |  | key,
|  |  | table
| ) |  | (unsigned int)(st_index_t)(*(table)->type->hash)((key))

Definition at line 75 of file st.c.

Referenced by st_add_direct(), st_get_key(), st_insert(), st_insert2(), and st_lookup().

#define do_hash_bin | ( |  | key,
|  |  | table
| ) |  | (do_hash((key), (table))%(table)->num_bins)

Definition at line 76 of file st.c.

Referenced by st_delete(), and st_delete_safe().

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

Definition at line 72 of file st.c.

Referenced by st_delete(), and st_delete_safe().

#define FIND_ENTRY | ( |  | table,
|  |  | ptr,
|  |  | hash_val,
|  |  | bin_pos
| ) |  |

Value:
do {\
(bin_pos) = (hash_val)%(table)->num_bins;\
(ptr) = (table)->bins[(bin_pos)];\
FOUND_ENTRY;\
if (PTR_NOT_EQUAL((table), (ptr), (hash_val), key)) {\
COLLISION;\
while (PTR_NOT_EQUAL((table), (ptr)->next, (hash_val), key)) {\
(ptr) = (ptr)->next;\
}\
(ptr) = (ptr)->next;\
}\
} while (0)

Definition at line 309 of file st.c.

Referenced by st_foreach(), st_get_key(), st_insert(), st_insert2(), and st_lookup().

#define FNV1_32A_INIT 0x811c9dc5

Definition at line 976 of file st.c.

Referenced by strcasehash(), and strhash().

#define FNV_32_PRIME 0x01000193

Definition at line 981 of file st.c.

Referenced by strcasehash().

#define FOUND_ENTRY

Definition at line 306 of file st.c.

#define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)

Definition at line 164 of file st.c.

Referenced by st_init_table_with_size(), and unpack_entries().

#define MINSIZE 8

Definition at line 82 of file st.c.

Referenced by new_size().

#define MORE_PACKABLE_P | ( |  | table | ) |

Value:
((st_index_t)((table)->num_entries+1) * 2 <= (table)->num_bins && \
(table)->num_entries+1 <= MAX_PACKED_NUMHASH)

Definition at line 385 of file st.c.

Referenced by st_add_direct(), st_insert(), and st_insert2().

#define MURMUR 2

Definition at line 1017 of file st.c.

#define murmur1 | ( |  | h | ) | murmur_step((h), 24)

Definition at line 1070 of file st.c.

Referenced by st_hash_uint().

#define murmur_step | ( |  | h,
|  |  | k
| ) |  | murmur((h), (k), 16)

Definition at line 1065 of file st.c.

Referenced by st_hash(), st_hash_end(), and st_hash_uint32().

#define MurmurMagic MurmurMagic_2

Definition at line 1028 of file st.c.

Referenced by murmur(), murmur_finish(), and st_hash().

#define MurmurMagic_1 (st_index_t)0xc6a4a793

Definition at line 1020 of file st.c.

#define MurmurMagic_2 (st_index_t)0x5bd1e995

Definition at line 1021 of file st.c.

#define numberof | ( |  | array | ) | (int)(sizeof(array) / sizeof((array)[0]))

Definition at line 67 of file st.c.

Referenced by new_size().

#define PTR_NOT_EQUAL | ( |  | table,
|  |  | ptr,
|  |  | hash_val,
|  |  | key
| ) |  | ((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))

Definition at line 284 of file st.c.

#define REMOVE_ENTRY | ( |  | table,
|  |  | ptr
| ) |  |

Value:
do \
{ \
if ((ptr)->fore == 0 && (ptr)->back == 0) { \
(table)->head = 0; \
(table)->tail = 0; \
} \
else { \
st_table_entry *fore = (ptr)->fore, *back = (ptr)->back; \
if (fore) fore->back = back; \
if (back) back->fore = fore; \
if ((ptr) == (table)->head) (table)->head = fore; \
if ((ptr) == (table)->tail) (table)->tail = back; \
} \
(table)->num_entries--; \
} while (0)

Definition at line 607 of file st.c.

Referenced by st_delete(), st_delete_safe(), and st_foreach().

#define ST_DEFAULT_INIT_TABLE_SIZE 11

Definition at line 29 of file st.c.

#define ST_DEFAULT_MAX_DENSITY 5

Definition at line 28 of file st.c.

#define UNALIGNED_ADD | ( |  | n | ) |

Value:
case SIZEOF_ST_INDEX_T - (n) - 1: \
t |= data_at(n) << CHAR_BIT*(n)

#define UNALIGNED_ADD | ( |  | n | ) |

Value:
case (n) + 1: \
d |= data_at(n) << CHAR_BIT*(n)

#define UNALIGNED_ADD | ( |  | n | ) |

Value:
case (n) + 1: \
t |= data_at(n) << CHAR_BIT*(n)

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

#define UNALIGNED_ADD_ALL UNALIGNED_ADD_4

Referenced by st_hash().

#define UNALIGNED_WORD_ACCESS 0

Definition at line 1012 of file st.c.

## Typedef Documentation

typedef struct st_table_entry st_table_entry

Definition at line 18 of file st.c.

## Function Documentation

static st_index_t murmur | ( | st_index_t | h,
|  | st_index_t | k,
|  | int | r
| ) |  |

inline static

Definition at line 1033 of file st.c.

References MurmurMagic.

Referenced by murmur_finish().

static st_index_t murmur_finish | ( | st_index_t | h | ) |

inline static

Definition at line 1052 of file st.c.

References murmur(), and MurmurMagic.

Referenced by st_hash().

static st_index_t new_size | ( | st_index_t | size | ) |

static

Definition at line 120 of file st.c.

References i, MINSIZE, numberof, primes, rb_eRuntimeError, and rb_raise().

Referenced by onigenc_property_list_add_property(), rehash(), resize_property_list(), and st_init_table_with_size().

static void rehash | ( | st_table * |  | ) |

static

static void rehash | ( | register st_table * | table | ) |

static

Definition at line 536 of file st.c.

References st_table::bins, st_table_entry::fore, st_table_entry::hash, st_table::head, i, new_size(), st_table_entry::next, st_table::num_bins, and xrealloc.

void st_add_direct | ( | st_table * | table,
|  | st_data_t | key,
|  | st_data_t | value
| ) |  |

Definition at line 513 of file st.c.

References ADD_DIRECT, st_table::bins, do_hash, st_table::entries_packed, i, MORE_PACKABLE_P, st_table::num_bins, st_table::num_entries, and unpack_entries().

void st_cleanup_safe | ( | st_table * | table,
|  | st_data_t | never
| ) |  |

Definition at line 699 of file st.c.

References st_table::bins, st_table::entries_packed, free(), i, st_table_entry::key, last, st_table_entry::next, st_table::num_bins, and st_table::num_entries.

void st_clear | ( | st_table * | table | ) |

Definition at line 241 of file st.c.

References st_table::bins, st_table::entries_packed, free(), st_table::head, i, st_table_entry::next, st_table::num_bins, st_table::num_entries, and st_table::tail.

Referenced by rb_hash_clear(), rb_thread_atfork_internal(), and st_free_table().

st_table* st_copy | ( | st_table * | old_table | ) |

Definition at line 558 of file st.c.

References alloc, st_table_entry::back, st_table::bins, Calloc, st_table::entries_packed, st_table_entry::fore, free(), st_table_entry::hash, st_table::head, st_table_entry::next, st_table::num_bins, st_free_table, and st_table::tail.

int st_delete | ( | register st_table * | table,
|  | register st_data_t * | key,
|  | st_data_t * | value
| ) |  |

Definition at line 624 of file st.c.

References st_table::bins, do_hash_bin, st_table::entries_packed, EQUAL, free(), i, st_table_entry::key, memmove(), st_table_entry::next, st_table::num_entries, st_table_entry::record, and REMOVE_ENTRY.

int st_delete_safe | ( | register st_table * | table,
|  | register st_data_t * | key,
|  | st_data_t * | value,
|  | st_data_t | never
| ) |  |

Definition at line 663 of file st.c.

References st_table::bins, do_hash_bin, st_table::entries_packed, EQUAL, i, st_table_entry::key, st_table_entry::next, st_table::num_entries, st_table_entry::record, and REMOVE_ENTRY.

int st_foreach | ( | st_table * | table,
|  | int(*)(ANYARGS) | func,
|  | st_data_t | arg
| ) |  |

Definition at line 735 of file st.c.

References arg, st_table::bins, st_table::entries_packed, FIND_ENTRY, st_table_entry::fore, free(), st_table_entry::hash, st_table::head, i, st_table_entry::key, last, memmove(), st_table_entry::next, st_table::num_bins, st_table::num_entries, st_table_entry::record, REMOVE_ENTRY, ST_CHECK, ST_CONTINUE, ST_DELETE, and ST_STOP.

void st_free_table | ( | st_table * | table | ) |

Definition at line 266 of file st.c.

References st_table::bins, free(), and st_clear().

int st_get_key | ( | st_table * | table,
|  | register st_data_t | key,
|  | st_data_t * | result
| ) |  |

Definition at line 354 of file st.c.

References st_table::bins, do_hash, st_table::entries_packed, FIND_ENTRY, i, st_table_entry::key, and st_table::num_entries.

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

Definition at line 1074 of file st.c.

References CHAR_BIT, murmur_finish(), murmur_step, MurmurMagic, SIZEOF_ST_INDEX_T, and UNALIGNED_ADD_ALL.

Referenced by hash_i(), rb_memhash(), and strhash().

st_index_t st_hash_end | ( | st_index_t | h | ) |

Definition at line 1238 of file st.c.

References murmur_step.

st_index_t st_hash_start | ( | st_index_t | h | ) |

Definition at line 1247 of file st.c.

st_index_t st_hash_uint | ( | st_index_t | h,
|  | st_index_t | i
| ) |  |

Definition at line 1207 of file st.c.

References i, murmur1, and v.

st_index_t st_hash_uint32 | ( | st_index_t | h,
|  | uint32_t | i
| ) |  |

Definition at line 1201 of file st.c.

References murmur_step.

st_table* st_init_numtable | ( | void |  | ) |

Definition at line 205 of file st.c.

References st_init_table.

st_table* st_init_numtable_with_size | ( | st_index_t | size | ) |

Definition at line 211 of file st.c.

References st_init_table_with_size.

st_table* st_init_strcasetable | ( | void |  | ) |

Definition at line 229 of file st.c.

References st_init_table.

Referenced by Init_transcode(), make_transcoder_entry(), rb_enc_init(), transcode_search_path(), and w_encoding().

st_table* st_init_strcasetable_with_size | ( | st_index_t | size | ) |

Definition at line 235 of file st.c.

References st_init_table_with_size.

st_table* st_init_strtable | ( | void |  | ) |

Definition at line 217 of file st.c.

References st_init_table.

st_table* st_init_strtable_with_size | ( | st_index_t | size | ) |

Definition at line 223 of file st.c.

References st_init_table_with_size.

st_table* st_init_table | ( | const struct st_hash_type * | type | ) |

Definition at line 199 of file st.c.

References 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 167 of file st.c.

References alloc, st_table::bins, Calloc, st_table::entries_packed, getenv(), st_table::head, MAX_PACKED_NUMHASH, new_size(), st_table::num_bins, st_table::num_entries, size, st_table::tail, st_table::type, and type.

int st_insert | ( | register st_table * | table,
|  | register st_data_t | key,
|  | st_data_t | value
| ) |  |

Definition at line 435 of file st.c.

References ADD_DIRECT, st_table::bins, do_hash, st_table::entries_packed, FIND_ENTRY, i, MORE_PACKABLE_P, st_table::num_entries, st_table_entry::record, and unpack_entries().

int st_insert2 | ( | register st_table * | table,
|  | register st_data_t | key,
|  | st_data_t | value,
|  | st_data_t(*)(st_data_t) | func
| ) |  |

Definition at line 473 of file st.c.

References ADD_DIRECT, st_table::bins, do_hash, st_table::entries_packed, FIND_ENTRY, i, st_table_entry::key, MORE_PACKABLE_P, st_table::num_entries, st_table_entry::record, and unpack_entries().

int st_lookup | ( | st_table * | table,
|  | register st_data_t | key,
|  | st_data_t * | value
| ) |  |

Definition at line 325 of file st.c.

References st_table::bins, do_hash, st_table::entries_packed, FIND_ENTRY, i, st_table::num_entries, and st_table_entry::record.

size_t st_memsize | ( | const st_table * | table | ) |

Definition at line 274 of file st.c.

References st_table::entries_packed, st_table::num_bins, and st_table::num_entries.

Referenced by autoload_memsize(), fiber_memsize(), memsize_of(), rb_generic_ivar_memsize(), thread_memsize(), and vm_memsize().

int st_numcmp | ( | st_data_t | x,
|  | st_data_t | y
| ) |  |

Definition at line 1330 of file st.c.

st_index_t st_numhash | ( | st_data_t | n | ) |

Definition at line 1336 of file st.c.

int st_strcasecmp | ( | const char * | s1,
|  | const char * | s2
| ) |  |

Definition at line 1261 of file st.c.

int st_strncasecmp | ( | const char * | s1,
|  | const char * | s2,
|  | size_t | n
| ) |  |

Definition at line 1285 of file st.c.

static st_index_t strcasehash | ( | st_data_t | arg | ) |

static

Definition at line 1310 of file st.c.

References FNV1_32A_INIT, and FNV_32_PRIME.

static st_index_t strhash | ( | st_data_t | arg | ) |

static

Definition at line 1253 of file st.c.

References FNV1_32A_INIT, st_hash(), and strlen().

static void unpack_entries | ( | register st_table * | table | ) |

static

Definition at line 417 of file st.c.

References st_table::bins, st_table::entries_packed, i, MAX_PACKED_NUMHASH, st_table::num_bins, st_table::num_entries, and st_insert.

Referenced by st_add_direct(), st_insert(), and st_insert2().

## Variable Documentation

const unsigned int primes[]

static

Definition at line 87 of file st.c.

Referenced by new_size().

struct st_hash_type type_numhash

static

Initial value:
= {
st_numcmp,
st_numhash,
}

Definition at line 41 of file st.c.

struct st_hash_type type_strcasehash

static

Initial value:
= {
st_strcasecmp,
strcasehash,
}

Definition at line 54 of file st.c.

struct st_hash_type type_strhash

static

Initial value:
= {
strcmp,
strhash,
}

Definition at line 48 of file st.c.