Ruby  1.9.3p547(2014-05-14revision45962)
Data Structures | Macros | Typedefs | Functions | Variables
st.c File Reference
#include "ruby/ruby.h"
#include <stdio.h>
#include <string.h>
Include dependency graph for st.c:

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_tablest_init_table_with_size (const struct st_hash_type *type, st_index_t size)
 
st_tablest_init_table (const struct st_hash_type *type)
 
st_tablest_init_numtable (void)
 
st_tablest_init_numtable_with_size (st_index_t size)
 
st_tablest_init_strtable (void)
 
st_tablest_init_strtable_with_size (st_index_t size)
 
st_tablest_init_strcasetable (void)
 
st_tablest_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_tablest_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)
 
int st_shift (register st_table *table, register st_data_t *key, st_data_t *value)
 
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 const struct st_hash_type type_numhash
 
static const struct st_hash_type type_strhash
 
static const 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 {\
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)
if(len<=MAX_WORD_LENGTH &&len >=MIN_WORD_LENGTH)
Definition: name2ctype.h:23841
struct st_table_entry st_table_entry
Definition: st.c:18
#define ST_DEFAULT_MAX_DENSITY
Definition: st.c:28
Definition: st.c:20
static void rehash(st_table *)
#define alloc(type)
Definition: st.c:69
uint8_t key[16]
Definition: random.c:1284

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))
#define Calloc (   n,
 
)    (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(), st_delete_safe(), and st_shift().

#define EQUAL (   table,
  x,
 
)    ((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)];\
if (PTR_NOT_EQUAL((table), (ptr), (hash_val), key)) {\
while (PTR_NOT_EQUAL((table), (ptr)->next, (hash_val), key)) {\
(ptr) = (ptr)->next;\
}\
(ptr) = (ptr)->next;\
}\
} while (0)
if(len<=MAX_WORD_LENGTH &&len >=MIN_WORD_LENGTH)
Definition: name2ctype.h:23841
#define PTR_NOT_EQUAL(table, ptr, hash_val, key)
Definition: st.c:284
uint8_t key[16]
Definition: random.c:1284
#define FOUND_ENTRY
Definition: st.c:306
#define COLLISION
Definition: st.c:305

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

Referenced by strcasehash(), and strhash().

#define FNV_32_PRIME   0x01000193

Definition at line 1020 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)
st_data_t st_index_t
Definition: st.h:63
#define MAX_PACKED_NUMHASH
Definition: st.c:164

Definition at line 385 of file st.c.

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

#define MURMUR   2

Definition at line 1056 of file st.c.

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

Definition at line 1109 of file st.c.

Referenced by st_hash_uint().

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

Definition at line 1104 of file st.c.

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

#define MurmurMagic   MurmurMagic_2

Definition at line 1067 of file st.c.

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

#define MurmurMagic_1   (st_index_t)0xc6a4a793

Definition at line 1059 of file st.c.

#define MurmurMagic_2   (st_index_t)0x5bd1e995

Definition at line 1060 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)
if(len<=MAX_WORD_LENGTH &&len >=MIN_WORD_LENGTH)
Definition: name2ctype.h:23841
struct st_table_entry st_table_entry
Definition: st.c:18
st_table_entry * back
Definition: st.c:25

Definition at line 607 of file st.c.

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

#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 SIZEOF_ST_INDEX_T
Definition: st.h:68
#define CHAR_BIT
Definition: ruby.h:192
#define data_at(n)
#define UNALIGNED_ADD (   n)
Value:
case (n) + 1: \
d |= data_at(n) << CHAR_BIT*(n)
#define CHAR_BIT
Definition: ruby.h:192
#define data_at(n)
#define UNALIGNED_ADD (   n)
Value:
case (n) + 1: \
t |= data_at(n) << CHAR_BIT*(n)
#define CHAR_BIT
Definition: ruby.h:192
#define data_at(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 1051 of file st.c.

Typedef Documentation

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 
)
inlinestatic

Definition at line 1072 of file st.c.

References MurmurMagic.

Referenced by murmur_finish().

static st_index_t murmur_finish ( st_index_t  h)
inlinestatic

Definition at line 1091 of file st.c.

References murmur(), and MurmurMagic.

Referenced by st_hash().

static st_index_t new_size ( st_index_t  size)
static
static void rehash ( st_table )
static
static void rehash ( register st_table table)
static
void st_add_direct ( st_table table,
st_data_t  key,
st_data_t  value 
)
void st_cleanup_safe ( st_table table,
st_data_t  never 
)
void st_clear ( 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 
)
int st_foreach ( st_table table,
int(*)(ANYARGS func,
st_data_t  arg 
)
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 st_copy().

int st_get_key ( st_table table,
register st_data_t  key,
st_data_t result 
)
st_index_t st_hash ( const void *  ptr,
size_t  len,
st_index_t  h 
)

Definition at line 1113 of file st.c.

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

Referenced by hash_i(), and strhash().

st_index_t st_hash_end ( st_index_t  h)

Definition at line 1277 of file st.c.

References murmur_step.

st_index_t st_hash_start ( st_index_t  h)

Definition at line 1286 of file st.c.

st_index_t st_hash_uint ( st_index_t  h,
st_index_t  i 
)

Definition at line 1246 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 1240 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  )
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().

Referenced by 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 
)
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(*)(st_data_t func 
)
int st_lookup ( st_table table,
register st_data_t  key,
st_data_t value 
)
size_t st_memsize ( const st_table table)
int st_numcmp ( st_data_t  x,
st_data_t  y 
)

Definition at line 1369 of file st.c.

st_index_t st_numhash ( st_data_t  n)

Definition at line 1375 of file st.c.

int st_shift ( register st_table table,
register st_data_t key,
st_data_t value 
)
int st_strcasecmp ( const char *  s1,
const char *  s2 
)

Definition at line 1300 of file st.c.

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

Definition at line 1324 of file st.c.

static st_index_t strcasehash ( st_data_t  arg)
static

Definition at line 1349 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 1292 of file st.c.

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

static void unpack_entries ( register st_table table)
static

Variable Documentation

const unsigned int primes[]
static

Definition at line 87 of file st.c.

Referenced by new_size().

const struct st_hash_type type_numhash
static
Initial value:
= {
}
st_index_t st_numhash(st_data_t n)
Definition: st.c:1375
int st_numcmp(st_data_t x, st_data_t y)
Definition: st.c:1369

Definition at line 41 of file st.c.

const struct st_hash_type type_strcasehash
static
Initial value:
= {
}
int st_strcasecmp(const char *s1, const char *s2)
Definition: st.c:1300
static st_index_t strcasehash(st_data_t)
Definition: st.c:1349

Definition at line 54 of file st.c.

const struct st_hash_type type_strhash
static
Initial value:
= {
strcmp,
}
static st_index_t strhash(st_data_t)
Definition: st.c:1292

Definition at line 48 of file st.c.