#include "ruby/ruby.h"
#include <stdio.h>
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | st_table_entry |
Defines | |
#define | ST_DEFAULT_MAX_DENSITY 5 |
#define | ST_DEFAULT_INIT_TABLE_SIZE 11 |
#define | malloc xmalloc |
#define | calloc xcalloc |
#define | free(x) xfree(x) |
#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 0x5bd1e995 |
#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 [] |
#define ADD_DIRECT | ( | table, | ||
key, | ||||
value, | ||||
hash_val, | ||||
bin_pos | ||||
) |
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().
Definition at line 69 of file st.c.
Referenced by onig_reg_init(), 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 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 | ||||
) |
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_get_key(), st_insert(), st_insert2(), and st_lookup().
#define free | ( | x | ) | xfree(x) |
Definition at line 64 of file st.c.
Referenced by st_cleanup_safe(), st_clear(), st_copy(), st_delete(), st_foreach(), and st_free_table().
#define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2) |
Definition at line 164 of file st.c.
Referenced by unpack_entries().
#define MINSIZE 8 |
Definition at line 82 of file st.c.
Referenced by new_size().
#define MORE_PACKABLE_P | ( | table | ) |
((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 murmur1 | ( | h | ) | murmur_step(h, 24) |
Definition at line 1054 of file st.c.
Referenced by st_hash_uint().
#define murmur_step | ( | h, | ||
k | ||||
) | murmur(h, k, 16) |
Definition at line 1049 of file st.c.
Referenced by st_hash(), st_hash_end(), and st_hash_uint32().
#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))) |
#define REMOVE_ENTRY | ( | table, | ||
ptr | ||||
) |
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 UNALIGNED_ADD | ( | n | ) |
case SIZEOF_ST_INDEX_T - (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 |
typedef struct st_table_entry st_table_entry |
static st_index_t murmur | ( | st_index_t | h, | |
st_index_t | k, | |||
int | r | |||
) | [inline, static] |
Definition at line 1017 of file st.c.
Referenced by murmur_finish().
static st_index_t murmur_finish | ( | st_index_t | h | ) | [inline, static] |
static st_index_t new_size | ( | st_index_t | size | ) | [static] |
Definition at line 120 of file st.c.
References MINSIZE, numberof, primes, rb_eRuntimeError, and rb_raise().
Referenced by onigenc_property_list_add_property(), rehash(), 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, new_size(), st_table_entry::next, st_table::num_bins, and xrealloc.
Definition at line 513 of file st.c.
References ADD_DIRECT, st_table::bins, do_hash, st_table::entries_packed, MORE_PACKABLE_P, st_table::num_bins, st_table::num_entries, and unpack_entries().
Referenced by boot_defclass(), define_final(), generic_ivar_set(), init_case_fold_table(), make_transcoder_entry(), method_entry(), rb_alias_variable(), rb_autoload(), rb_copy_generic_ivar(), rb_define_class(), rb_define_module(), rb_global_entry(), rb_ivar_set(), register_symid(), set_syserr(), transcode_search_path(), transcode_search_path_i(), w_object(), w_symbol(), and zone_str().
Definition at line 699 of file st.c.
References st_table::bins, st_table::entries_packed, free, st_table_entry::key, last, st_table_entry::next, st_table::num_bins, and st_table::num_entries.
Referenced by hash_foreach_ensure().
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, 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().
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.
Referenced by init_copy(), rb_copy_generic_ivar(), rb_hash_dup(), rb_hash_s_create(), rb_mod_init_copy(), and rb_singleton_class_clone().
Definition at line 624 of file st.c.
References st_table::bins, do_hash_bin, st_table::entries_packed, EQUAL, free, 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, st_table_entry::key, st_table_entry::next, st_table::num_entries, st_table_entry::record, and REMOVE_ENTRY.
Definition at line 735 of file st.c.
References st_table::bins, st_table::entries_packed, st_table_entry::fore, free, st_table_entry::hash, st_table::head, 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.
Referenced by class_instance_method_list(), clear_coverage(), count_nodes(), count_objects(), count_objects_size(), count_tdata_objects(), enc_names(), fc_i(), hash2kv(), hash2kv_enc(), hash_foreach_call(), mark_hash(), mark_m_tbl(), mark_marshal_compat_t(), mark_set(), mark_tbl(), proc_waitall(), rb_ary_uniq(), rb_ary_uniq_bang(), rb_check_deadlock(), rb_check_exec_env(), rb_check_exec_options(), rb_clear_trace_func(), rb_coverage_result(), rb_econv_asciicompat_encoding(), rb_enc_aliases(), rb_enc_name_list(), rb_feature_p(), rb_free_m_table(), rb_mod_init_copy(), rb_obj_singleton_methods(), rb_objspace_call_finalizer(), rb_singleton_class_clone(), rb_sym_all_symbols(), rb_thread_atfork_internal(), rb_thread_keys(), rb_thread_list(), rb_thread_terminate_all(), rb_vm_mark(), rb_waitpid(), set_threads_event_flags(), st_foreach_safe(), syck_emitter_st_free(), syck_free_parser(), syck_mark_parser(), syck_st_free(), thgroup_list(), tk_symbolkey2str(), and transcode_search_path().
void st_free_table | ( | st_table * | table | ) |
Definition at line 266 of file st.c.
References st_table::bins, free, and st_clear().
Referenced by ary_recycle_hash(), autoload_free(), class_instance_method_list(), clear_dump_arg(), clear_load_arg(), exit_handler(), fiber_free(), flatten(), free_enc2cp(), generic_ivar_remove(), init_copy(), Init_win32ole(), iseq_build_body(), iseq_data_to_ary(), obj_free(), rb_const_list(), rb_copy_generic_ivar(), rb_free_generic_ivar(), rb_free_m_table(), rb_hash_rehash(), rb_mod_init_copy(), rb_obj_singleton_methods(), rb_objspace_call_finalizer(), ruby_vm_destruct(), st_copy(), syck_emitter_st_free(), syck_free_parser(), syck_st_free(), thread_free(), and transcode_search_path().
Definition at line 354 of file st.c.
References st_table::bins, do_hash, st_table::entries_packed, FIND_ENTRY, 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 1058 of file st.c.
References CHAR_BIT, murmur_finish(), murmur_step, and SIZEOF_ST_INDEX_T.
Referenced by rb_memhash(), and strhash().
st_index_t st_hash_end | ( | st_index_t | h | ) |
Definition at line 1222 of file st.c.
References murmur_step.
st_index_t st_hash_start | ( | st_index_t | h | ) |
st_index_t st_hash_uint | ( | st_index_t | h, | |
st_index_t | i | |||
) |
st_index_t st_hash_uint32 | ( | st_index_t | h, | |
uint32_t | i | |||
) |
Definition at line 1185 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().
Referenced by class_instance_method_list(), define_final(), fiber_init(), find_class_path(), flatten(), generic_ivar_set(), include_class_new(), init_constants(), init_enc2cp(), Init_Exception(), Init_marshal(), Init_var_tables(), Init_VM(), Init_win32ole(), insn_make_insn_table(), iseq_data_to_ary(), iseq_load(), marshal_dump(), marshal_load(), mod_av_set(), rb_autoload(), rb_class_boot(), rb_iseq_build_from_ary(), rb_ivar_set(), rb_mod_const_at(), rb_mod_init_copy(), rb_module_new(), rb_obj_freeze(), rb_obj_singleton_methods(), rb_singleton_class_attached(), rb_singleton_class_clone(), rb_thread_local_aset(), rb_waitpid(), StartSockets(), syck_add_sym(), syck_emit(), syck_emitter_mark_node(), and vm_init_redefined_flag().
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().
Referenced by init_case_fold_table(), and Init_sym().
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().
Referenced by load_lock(), syck_hdlr_add_anchor(), syck_hdlr_get_anchor(), syck_hdlr_remove_anchor(), and zone_str().
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().
Referenced by rb_hash_tbl(), st_init_numtable(), st_init_strcasetable(), and st_init_strtable().
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, new_size(), st_table::num_bins, st_table::num_entries, st_table::tail, and st_table::type.
Referenced by init_case_fold_table(), Init_sym(), rb_hash_rehash(), st_init_numtable_with_size(), st_init_strcasetable_with_size(), st_init_strtable_with_size(), and st_init_table().
Definition at line 435 of file st.c.
References ADD_DIRECT, st_table::bins, do_hash, st_table::entries_packed, FIND_ENTRY, 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, MORE_PACKABLE_P, st_table::num_entries, st_table_entry::record, and unpack_entries().
Definition at line 325 of file st.c.
References st_table::bins, do_hash, st_table::entries_packed, FIND_ENTRY, 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().
st_index_t st_numhash | ( | st_data_t | n | ) |
int st_strncasecmp | ( | const char * | s1, | |
const char * | s2, | |||
size_t | n | |||
) |
static st_index_t strcasehash | ( | st_data_t | arg | ) | [static] |
static st_index_t strhash | ( | st_data_t | arg | ) | [static] |
Definition at line 1237 of file st.c.
References FNV1_32A_INIT, and st_hash().
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, MAX_PACKED_NUMHASH, st_table::num_bins, st_table::num_entries, and st_insert().
Referenced by st_add_direct(), st_insert(), and st_insert2().
const unsigned int primes[] [static] |
Definition at line 87 of file st.c.
Referenced by new_size().
struct st_hash_type type_numhash [static] |
struct st_hash_type type_strcasehash [static] |
struct st_hash_type type_strhash [static] |