parser_st.h

   1 /* This is a public domain general purpose hash table package
   2    originally written by Peter Moore @ UCB.
   3
   4    The hash table data structures were redesigned and the package was
   5    rewritten by Vladimir Makarov <vmakarov@redhat.com>.  */
   6
   7 #ifndef RUBY_ST2_H
   8 #define RUBY_ST2_H 1
   9
  10 #if defined(__cplusplus)
  11 extern "C" {
  12 #if 0
  13 } /* satisfy cc-mode */
  14 #endif
  15 #endif
  16
  17 #include <stddef.h>
  18 #include <stdint.h>
  19 #include "ruby/config.h"
  20 #include "ruby/backward/2/long_long.h"
  21 #include "ruby/defines.h"
  22
  23 RUBY_SYMBOL_EXPORT_BEGIN
  24
  25 #if SIZEOF_LONG == SIZEOF_VOIDP
  26 typedef unsigned long parser_st_data_t;
  27 #elif SIZEOF_LONG_LONG == SIZEOF_VOIDP
  28 typedef unsigned LONG_LONG parser_st_data_t;
  29 #else
  30 # error ---->> parser_st.c requires sizeof(void*) == sizeof(long) or sizeof(LONG_LONG) to be compiled. <<----
  31 #endif
  32 #define ST2_DATA_T_DEFINED
  33
  34 #ifndef CHAR_BIT
  35 # ifdef HAVE_LIMITS_H
  36 #  include <limits.h>
  37 # else
  38 #  define CHAR_BIT 8
  39 # endif
  40 #endif
  41 #ifndef _
  42 # define _(args) args
  43 #endif
  44 #ifndef ANYARGS
  45 # ifdef __cplusplus
  46 #   define ANYARGS ...
  47 # else
  48 #   define ANYARGS
  49 # endif
  50 #endif
  51
  52 typedef struct parser_st_table parser_st_table;
  53
  54 typedef parser_st_data_t parser_st_index_t;
  55
  56 /* Maximal value of unsigned integer type parser_st_index_t.  */
  57 #define MAX_ST2_INDEX_VAL (~(parser_st_index_t) 0)
  58
  59 typedef int parser_st_compare_func(parser_st_data_t, parser_st_data_t);
  60 typedef parser_st_index_t parser_st_hash_func(parser_st_data_t);
  61
  62 typedef char st_check_for_sizeof_parser_st_index_t[SIZEOF_VOIDP == (int)sizeof(parser_st_index_t) ? 1 : -1];
  63 #define SIZEOF_ST_INDEX_T SIZEOF_VOIDP
  64
  65 struct parser_st_hash_type {
  66     int (*compare)(parser_st_data_t, parser_st_data_t); /* parser_st_compare_func* */
  67     parser_st_index_t (*hash)(parser_st_data_t);        /* parser_st_hash_func* */
  68 };
  69
  70 #define ST_INDEX_BITS (SIZEOF_ST_INDEX_T * CHAR_BIT)
  71
  72 #if defined(HAVE_BUILTIN___BUILTIN_CHOOSE_EXPR) && defined(HAVE_BUILTIN___BUILTIN_TYPES_COMPATIBLE_P)
  73 # define ST2_DATA_COMPATIBLE_P(type) \
  74    __builtin_choose_expr(__builtin_types_compatible_p(type, parser_st_data_t), 1, 0)
  75 #else
  76 # define ST2_DATA_COMPATIBLE_P(type) 0
  77 #endif
  78
  79 typedef struct parser_st_table_entry parser_st_table_entry;
  80
  81 struct parser_st_table_entry; /* defined in parser_st.c */
  82
  83 struct parser_st_table {
  84     /* Cached features of the table -- see st.c for more details.  */
  85     unsigned char entry_power, bin_power, size_ind;
  86     /* How many times the table was rebuilt.  */
  87     unsigned int rebuilds_num;
  88     const struct parser_st_hash_type *type;
  89     /* Number of entries currently in the table.  */
  90     parser_st_index_t num_entries;
  91     /* Array of bins used for access by keys.  */
  92     parser_st_index_t *bins;
  93     /* Start and bound index of entries in array entries.
  94        entries_starts and entries_bound are in interval
  95        [0,allocated_entries].  */
  96     parser_st_index_t entries_start, entries_bound;
  97     /* Array of size 2^entry_power.  */
  98     parser_st_table_entry *entries;
  99 };
 100
 101 #define parser_st_is_member(table,key) rb_parser_st_lookup((table),(key),(parser_st_data_t *)0)
 102
 103 enum parser_st_retval {ST2_CONTINUE, ST2_STOP, ST2_DELETE, ST2_CHECK, ST2_REPLACE};
 104
 105 size_t rb_parser_st_table_size(const struct parser_st_table *tbl);
 106 parser_st_table *rb_parser_st_init_table(const struct parser_st_hash_type *);
 107 parser_st_table *rb_parser_st_init_table_with_size(const struct parser_st_hash_type *, parser_st_index_t);
 108 parser_st_table *rb_parser_st_init_existing_table_with_size(parser_st_table *, const struct parser_st_hash_type *, parser_st_index_t);
 109 parser_st_table *rb_parser_st_init_numtable(void);
 110 parser_st_table *rb_parser_st_init_numtable_with_size(parser_st_index_t);
 111 parser_st_table *rb_parser_st_init_strtable(void);
 112 parser_st_table *rb_parser_st_init_strtable_with_size(parser_st_index_t);
 113 parser_st_table *rb_parser_st_init_strcasetable(void);
 114 parser_st_table *rb_parser_st_init_strcasetable_with_size(parser_st_index_t);
 115 int rb_parser_st_delete(parser_st_table *, parser_st_data_t *, parser_st_data_t *); /* returns 0:notfound 1:deleted */
 116 int rb_parser_st_delete_safe(parser_st_table *, parser_st_data_t *, parser_st_data_t *, parser_st_data_t);
 117 int rb_parser_st_shift(parser_st_table *, parser_st_data_t *, parser_st_data_t *); /* returns 0:notfound 1:deleted */
 118 int rb_parser_st_insert(parser_st_table *, parser_st_data_t, parser_st_data_t);
 119 int rb_parser_st_insert2(parser_st_table *, parser_st_data_t, parser_st_data_t, parser_st_data_t (*)(parser_st_data_t));
 120 int rb_parser_st_lookup(parser_st_table *, parser_st_data_t, parser_st_data_t *);
 121 int rb_parser_st_get_key(parser_st_table *, parser_st_data_t, parser_st_data_t *);
 122 typedef int parser_st_update_callback_func(parser_st_data_t *key, parser_st_data_t *value, parser_st_data_t arg, int existing);
 123 /* *key may be altered, but must equal to the old key, i.e., the
 124  * results of hash() are same and compare() returns 0, otherwise the
 125  * behavior is undefined */
 126 int rb_parser_st_update(parser_st_table *table, parser_st_data_t key, parser_st_update_callback_func *func, parser_st_data_t arg);
 127 typedef int parser_st_foreach_callback_func(parser_st_data_t, parser_st_data_t, parser_st_data_t);
 128 typedef int parser_st_foreach_check_callback_func(parser_st_data_t, parser_st_data_t, parser_st_data_t, int);
 129 int rb_parser_st_foreach_with_replace(parser_st_table *tab, parser_st_foreach_check_callback_func *func, parser_st_update_callback_func *replace, parser_st_data_t arg);
 130 int rb_parser_st_foreach(parser_st_table *, parser_st_foreach_callback_func *, parser_st_data_t);
 131 int rb_parser_st_foreach_check(parser_st_table *, parser_st_foreach_check_callback_func *, parser_st_data_t, parser_st_data_t);
 132 parser_st_index_t rb_parser_st_keys(parser_st_table *table, parser_st_data_t *keys, parser_st_index_t size);
 133 parser_st_index_t rb_parser_st_keys_check(parser_st_table *table, parser_st_data_t *keys, parser_st_index_t size, parser_st_data_t never);
 134 parser_st_index_t rb_parser_st_values(parser_st_table *table, parser_st_data_t *values, parser_st_index_t size);
 135 parser_st_index_t rb_parser_st_values_check(parser_st_table *table, parser_st_data_t *values, parser_st_index_t size, parser_st_data_t never);
 136 void rb_parser_st_add_direct(parser_st_table *, parser_st_data_t, parser_st_data_t);
 137 void rb_parser_st_free_table(parser_st_table *);
 138 void rb_parser_st_cleanup_safe(parser_st_table *, parser_st_data_t);
 139 void rb_parser_st_clear(parser_st_table *);
 140 parser_st_table *rb_parser_st_replace(parser_st_table *, parser_st_table *);
 141 parser_st_table *rb_parser_st_copy(parser_st_table *);
 142 CONSTFUNC(int rb_parser_st_numcmp(parser_st_data_t, parser_st_data_t));
 143 CONSTFUNC(parser_st_index_t rb_parser_st_numhash(parser_st_data_t));
 144 PUREFUNC(int rb_parser_st_locale_insensitive_strcasecmp(const char *s1, const char *s2));
 145 PUREFUNC(int rb_parser_st_locale_insensitive_strncasecmp(const char *s1, const char *s2, size_t n));
 146 PUREFUNC(size_t rb_parser_st_memsize(const parser_st_table *));
 147 PUREFUNC(parser_st_index_t rb_parser_st_hash(const void *ptr, size_t len, parser_st_index_t h));
 148 CONSTFUNC(parser_st_index_t rb_parser_st_hash_uint32(parser_st_index_t h, uint32_t i));
 149 CONSTFUNC(parser_st_index_t rb_parser_st_hash_uint(parser_st_index_t h, parser_st_index_t i));
 150 CONSTFUNC(parser_st_index_t rb_parser_st_hash_end(parser_st_index_t h));
 151 CONSTFUNC(parser_st_index_t rb_parser_st_hash_start(parser_st_index_t h));
 152
 153 RUBY_SYMBOL_EXPORT_END
 154
 155 #if defined(__cplusplus)
 156 #if 0
 157 { /* satisfy cc-mode */
 158 #endif
 159 }  /* extern "C" { */
 160 #endif
 161
 162 #endif /* RUBY_ST2_H */