Ruby
2.0.0p247(2013-06-27revision41674)
|
00001 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */ 00002 00003 /* @(#) st.h 5.1 89/12/14 */ 00004 00005 #ifndef RUBY_ST_H 00006 #define RUBY_ST_H 1 00007 00008 #if defined(__cplusplus) 00009 extern "C" { 00010 #if 0 00011 } /* satisfy cc-mode */ 00012 #endif 00013 #endif 00014 00015 #include "ruby/defines.h" 00016 00017 #if defined STDC_HEADERS 00018 #include <stddef.h> 00019 #elif defined HAVE_STDLIB_H 00020 #include <stdlib.h> 00021 #endif 00022 00023 #ifdef HAVE_STDINT_H 00024 # include <stdint.h> 00025 #endif 00026 #ifdef HAVE_INTTYPES_H 00027 # include <inttypes.h> 00028 #endif 00029 00030 #if defined __GNUC__ && __GNUC__ >= 4 00031 #pragma GCC visibility push(default) 00032 #endif 00033 00034 #if SIZEOF_LONG == SIZEOF_VOIDP 00035 typedef unsigned long st_data_t; 00036 #elif SIZEOF_LONG_LONG == SIZEOF_VOIDP 00037 typedef unsigned LONG_LONG st_data_t; 00038 #else 00039 # error ---->> st.c requires sizeof(void*) == sizeof(long) or sizeof(LONG_LONG) to be compiled. <<---- 00040 #endif 00041 #define ST_DATA_T_DEFINED 00042 00043 #ifndef CHAR_BIT 00044 # ifdef HAVE_LIMITS_H 00045 # include <limits.h> 00046 # else 00047 # define CHAR_BIT 8 00048 # endif 00049 #endif 00050 #ifndef _ 00051 # define _(args) args 00052 #endif 00053 #ifndef ANYARGS 00054 # ifdef __cplusplus 00055 # define ANYARGS ... 00056 # else 00057 # define ANYARGS 00058 # endif 00059 #endif 00060 00061 typedef struct st_table st_table; 00062 00063 typedef st_data_t st_index_t; 00064 typedef int st_compare_func(st_data_t, st_data_t); 00065 typedef st_index_t st_hash_func(st_data_t); 00066 00067 typedef char st_check_for_sizeof_st_index_t[SIZEOF_VOIDP == (int)sizeof(st_index_t) ? 1 : -1]; 00068 #define SIZEOF_ST_INDEX_T SIZEOF_VOIDP 00069 00070 struct st_hash_type { 00071 int (*compare)(ANYARGS /*st_data_t, st_data_t*/); /* st_compare_func* */ 00072 st_index_t (*hash)(ANYARGS /*st_data_t*/); /* st_hash_func* */ 00073 }; 00074 00075 #define ST_INDEX_BITS (sizeof(st_index_t) * CHAR_BIT) 00076 00077 struct st_table { 00078 const struct st_hash_type *type; 00079 st_index_t num_bins; 00080 unsigned int entries_packed : 1; 00081 #ifdef __GNUC__ 00082 /* 00083 * C spec says, 00084 * A bit-field shall have a type that is a qualified or unqualified 00085 * version of _Bool, signed int, unsigned int, or some other 00086 * implementation-defined type. It is implementation-defined whether 00087 * atomic types are permitted. 00088 * In short, long and long long bit-field are implementation-defined 00089 * feature. Therefore we want to supress a warning explicitly. 00090 */ 00091 __extension__ 00092 #endif 00093 st_index_t num_entries : ST_INDEX_BITS - 1; 00094 union { 00095 struct { 00096 struct st_table_entry **bins; 00097 struct st_table_entry *head, *tail; 00098 } big; 00099 struct { 00100 struct st_packed_entry *entries; 00101 st_index_t real_entries; 00102 } packed; 00103 } as; 00104 }; 00105 00106 #define st_is_member(table,key) st_lookup((table),(key),(st_data_t *)0) 00107 00108 enum st_retval {ST_CONTINUE, ST_STOP, ST_DELETE, ST_CHECK}; 00109 00110 st_table *st_init_table(const struct st_hash_type *); 00111 st_table *st_init_table_with_size(const struct st_hash_type *, st_index_t); 00112 st_table *st_init_numtable(void); 00113 st_table *st_init_numtable_with_size(st_index_t); 00114 st_table *st_init_strtable(void); 00115 st_table *st_init_strtable_with_size(st_index_t); 00116 st_table *st_init_strcasetable(void); 00117 st_table *st_init_strcasetable_with_size(st_index_t); 00118 int st_delete(st_table *, st_data_t *, st_data_t *); /* returns 0:notfound 1:deleted */ 00119 int st_delete_safe(st_table *, st_data_t *, st_data_t *, st_data_t); 00120 int st_insert(st_table *, st_data_t, st_data_t); 00121 int st_insert2(st_table *, st_data_t, st_data_t, st_data_t (*)(st_data_t)); 00122 int st_lookup(st_table *, st_data_t, st_data_t *); 00123 int st_get_key(st_table *, st_data_t, st_data_t *); 00124 typedef int st_update_callback_func(st_data_t *key, st_data_t *value, st_data_t arg, int existing); 00125 int st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data_t arg); 00126 int st_foreach(st_table *, int (*)(ANYARGS), st_data_t); 00127 int st_foreach_check(st_table *, int (*)(ANYARGS), st_data_t, st_data_t); 00128 int st_reverse_foreach(st_table *, int (*)(ANYARGS), st_data_t); 00129 void st_add_direct(st_table *, st_data_t, st_data_t); 00130 void st_free_table(st_table *); 00131 void st_cleanup_safe(st_table *, st_data_t); 00132 void st_clear(st_table *); 00133 st_table *st_copy(st_table *); 00134 int st_numcmp(st_data_t, st_data_t); 00135 st_index_t st_numhash(st_data_t); 00136 int st_strcasecmp(const char *s1, const char *s2); 00137 int st_strncasecmp(const char *s1, const char *s2, size_t n); 00138 size_t st_memsize(const st_table *); 00139 st_index_t st_hash(const void *ptr, size_t len, st_index_t h); 00140 st_index_t st_hash_uint32(st_index_t h, uint32_t i); 00141 st_index_t st_hash_uint(st_index_t h, st_index_t i); 00142 st_index_t st_hash_end(st_index_t h); 00143 st_index_t st_hash_start(st_index_t h); 00144 #define st_hash_start(h) ((st_index_t)(h)) 00145 00146 #if defined __GNUC__ && __GNUC__ >= 4 00147 #pragma GCC visibility pop 00148 #endif 00149 00150 #if defined(__cplusplus) 00151 #if 0 00152 { /* satisfy cc-mode */ 00153 #endif 00154 } /* extern "C" { */ 00155 #endif 00156 00157 #endif /* RUBY_ST_H */ 00158