internal/hash.h

   1 #ifndef INTERNAL_HASH_H                                  /*-*-C-*-vi:se ft=c:*/
   2 #define INTERNAL_HASH_H
   3 /**
   4  * @author     Ruby developers <ruby-core@ruby-lang.org>
   5  * @copyright  This  file  is   a  part  of  the   programming  language  Ruby.
   6  *             Permission  is hereby  granted,  to  either redistribute  and/or
   7  *             modify this file, provided that  the conditions mentioned in the
   8  *             file COPYING are met.  Consult the file for details.
   9  * @brief      Internal header for Hash.
  10  */
  11 #include "ruby/internal/config.h"
  12 #include <stddef.h>             /* for size_t */
  13 #include "ruby/internal/stdbool.h"     /* for bool */
  14 #include "ruby/ruby.h"          /* for struct RBasic */
  15 #include "ruby/st.h"            /* for struct st_table */
  16
  17 #define RHASH_AR_TABLE_MAX_SIZE SIZEOF_VALUE
  18
  19 struct ar_table_struct;
  20 typedef unsigned char ar_hint_t;
  21
  22 enum ruby_rhash_flags {
  23     RHASH_PASS_AS_KEYWORDS = FL_USER1,                                   /* FL 1 */
  24     RHASH_PROC_DEFAULT = FL_USER2,                                       /* FL 2 */
  25     RHASH_ST_TABLE_FLAG = FL_USER3,                                      /* FL 3 */
  26     RHASH_AR_TABLE_SIZE_MASK = (FL_USER4|FL_USER5|FL_USER6|FL_USER7),    /* FL 4..7 */
  27     RHASH_AR_TABLE_SIZE_SHIFT = (FL_USHIFT+4),
  28     RHASH_AR_TABLE_BOUND_MASK = (FL_USER8|FL_USER9|FL_USER10|FL_USER11), /* FL 8..11 */
  29     RHASH_AR_TABLE_BOUND_SHIFT = (FL_USHIFT+8),
  30
  31 #if USE_TRANSIENT_HEAP
  32     RHASH_TRANSIENT_FLAG = FL_USER12,                                    /* FL 12 */
  33 #endif
  34
  35     // we can not put it in "enum" because it can exceed "int" range.
  36 #define RHASH_LEV_MASK (FL_USER13 | FL_USER14 | FL_USER15 |                /* FL 13..19 */ \
  37                         FL_USER16 | FL_USER17 | FL_USER18 | FL_USER19)
  38
  39     RHASH_LEV_SHIFT = (FL_USHIFT + 13),
  40     RHASH_LEV_MAX = 127, /* 7 bits */
  41 };
  42
  43 struct RHash {
  44     struct RBasic basic;
  45     union {
  46         st_table *st;
  47         struct ar_table_struct *ar; /* possibly 0 */
  48     } as;
  49     const VALUE ifnone;
  50     union {
  51         ar_hint_t ary[RHASH_AR_TABLE_MAX_SIZE];
  52         VALUE word;
  53     } ar_hint;
  54 };
  55
  56 #define RHASH(obj) ((struct RHash *)(obj))
  57
  58 #ifdef RHASH_IFNONE
  59 # undef RHASH_IFNONE
  60 #endif
  61
  62 #ifdef RHASH_SIZE
  63 # undef RHASH_SIZE
  64 #endif
  65
  66 #ifdef RHASH_EMPTY_P
  67 # undef RHASH_EMPTY_P
  68 #endif
  69
  70 /* hash.c */
  71 void rb_hash_st_table_set(VALUE hash, st_table *st);
  72 VALUE rb_hash_default_value(VALUE hash, VALUE key);
  73 VALUE rb_hash_set_default_proc(VALUE hash, VALUE proc);
  74 long rb_dbl_long_hash(double d);
  75 st_table *rb_init_identtable(void);
  76 st_index_t rb_any_hash(VALUE a);
  77 int rb_any_cmp(VALUE a, VALUE b);
  78 VALUE rb_to_hash_type(VALUE obj);
  79 VALUE rb_hash_key_str(VALUE);
  80 VALUE rb_hash_values(VALUE hash);
  81 VALUE rb_hash_rehash(VALUE hash);
  82 int rb_hash_add_new_element(VALUE hash, VALUE key, VALUE val);
  83 VALUE rb_hash_set_pair(VALUE hash, VALUE pair);
  84 int rb_hash_stlike_delete(VALUE hash, st_data_t *pkey, st_data_t *pval);
  85 int rb_hash_stlike_foreach_with_replace(VALUE hash, st_foreach_check_callback_func *func, st_update_callback_func *replace, st_data_t arg);
  86 int rb_hash_stlike_update(VALUE hash, st_data_t key, st_update_callback_func *func, st_data_t arg);
  87 VALUE rb_ident_hash_new_with_size(st_index_t size);
  88
  89 static inline unsigned RHASH_AR_TABLE_SIZE_RAW(VALUE h);
  90 static inline VALUE RHASH_IFNONE(VALUE h);
  91 static inline size_t RHASH_SIZE(VALUE h);
  92 static inline bool RHASH_EMPTY_P(VALUE h);
  93 static inline bool RHASH_AR_TABLE_P(VALUE h);
  94 static inline bool RHASH_ST_TABLE_P(VALUE h);
  95 static inline struct ar_table_struct *RHASH_AR_TABLE(VALUE h);
  96 static inline st_table *RHASH_ST_TABLE(VALUE h);
  97 static inline size_t RHASH_ST_SIZE(VALUE h);
  98 static inline void RHASH_ST_CLEAR(VALUE h);
  99 static inline bool RHASH_TRANSIENT_P(VALUE h);
 100 static inline void RHASH_SET_TRANSIENT_FLAG(VALUE h);
 101 static inline void RHASH_UNSET_TRANSIENT_FLAG(VALUE h);
 102
 103 RUBY_SYMBOL_EXPORT_BEGIN
 104 /* hash.c (export) */
 105 VALUE rb_hash_delete_entry(VALUE hash, VALUE key);
 106 VALUE rb_ident_hash_new(void);
 107 int rb_hash_stlike_foreach(VALUE hash, st_foreach_callback_func *func, st_data_t arg);
 108 RUBY_SYMBOL_EXPORT_END
 109
 110 VALUE rb_hash_new_with_size(st_index_t size);
 111 VALUE rb_hash_resurrect(VALUE hash);
 112 int rb_hash_stlike_lookup(VALUE hash, st_data_t key, st_data_t *pval);
 113 VALUE rb_hash_keys(VALUE hash);
 114 VALUE rb_hash_has_key(VALUE hash, VALUE key);
 115 VALUE rb_hash_compare_by_id_p(VALUE hash);
 116
 117 st_table *rb_hash_tbl_raw(VALUE hash, const char *file, int line);
 118 #define RHASH_TBL_RAW(h) rb_hash_tbl_raw(h, __FILE__, __LINE__)
 119
 120 VALUE rb_hash_compare_by_id(VALUE hash);
 121
 122 static inline bool
 123 RHASH_AR_TABLE_P(VALUE h)
 124 {
 125     return ! FL_TEST_RAW(h, RHASH_ST_TABLE_FLAG);
 126 }
 127
 128 static inline struct ar_table_struct *
 129 RHASH_AR_TABLE(VALUE h)
 130 {
 131     return RHASH(h)->as.ar;
 132 }
 133
 134 static inline st_table *
 135 RHASH_ST_TABLE(VALUE h)
 136 {
 137     return RHASH(h)->as.st;
 138 }
 139
 140 static inline VALUE
 141 RHASH_IFNONE(VALUE h)
 142 {
 143     return RHASH(h)->ifnone;
 144 }
 145
 146 static inline size_t
 147 RHASH_SIZE(VALUE h)
 148 {
 149     if (RHASH_AR_TABLE_P(h)) {
 150         return RHASH_AR_TABLE_SIZE_RAW(h);
 151     }
 152     else {
 153         return RHASH_ST_SIZE(h);
 154     }
 155 }
 156
 157 static inline bool
 158 RHASH_EMPTY_P(VALUE h)
 159 {
 160     return RHASH_SIZE(h) == 0;
 161 }
 162
 163 static inline bool
 164 RHASH_ST_TABLE_P(VALUE h)
 165 {
 166     return ! RHASH_AR_TABLE_P(h);
 167 }
 168
 169 static inline size_t
 170 RHASH_ST_SIZE(VALUE h)
 171 {
 172     return RHASH_ST_TABLE(h)->num_entries;
 173 }
 174
 175 static inline void
 176 RHASH_ST_CLEAR(VALUE h)
 177 {
 178     RHASH(h)->as.st = NULL;
 179     FL_UNSET_RAW(h, RHASH_ST_TABLE_FLAG);
 180 }
 181
 182 static inline unsigned
 183 RHASH_AR_TABLE_SIZE_RAW(VALUE h)
 184 {
 185     VALUE ret = FL_TEST_RAW(h, RHASH_AR_TABLE_SIZE_MASK);
 186     ret >>= RHASH_AR_TABLE_SIZE_SHIFT;
 187     return (unsigned)ret;
 188 }
 189
 190 static inline bool
 191 RHASH_TRANSIENT_P(VALUE h)
 192 {
 193 #if USE_TRANSIENT_HEAP
 194     return FL_TEST_RAW(h, RHASH_TRANSIENT_FLAG);
 195 #else
 196     return false;
 197 #endif
 198 }
 199
 200 static inline void
 201 RHASH_SET_TRANSIENT_FLAG(VALUE h)
 202 {
 203 #if USE_TRANSIENT_HEAP
 204     FL_SET_RAW(h, RHASH_TRANSIENT_FLAG);
 205 #endif
 206 }
 207
 208 static inline void
 209 RHASH_UNSET_TRANSIENT_FLAG(VALUE h)
 210 {
 211 #if USE_TRANSIENT_HEAP
 212     FL_UNSET_RAW(h, RHASH_TRANSIENT_FLAG);
 213 #endif
 214 }
 215
 216 #endif /* INTERNAL_HASH_H */