1 #ifndef MAPPING_H__ 2 #define MAPPING_H__ 1 3 4 #include "driver.h" 5 #include "typedefs.h" 6 #include "svalue.h" 7 8 /* --- Types --- */ 9 10 /* Local typedefs */ 11 12 typedef struct mapping_hash_s mapping_hash_t; 13 typedef struct mapping_cond_s mapping_cond_t; 14 15 /* --- struct mapping_s: the mapping datatypes --- */ 16 17 /* The main structure of a mapping 18 */ 19 20 struct mapping_s { 21 p_int ref; /* Number of references */ 22 wiz_list_t *user; /* Who made the mapping */ 23 p_int num_values; /* Number of values for a key */ 24 p_int num_entries; /* Number of valid entries */ 25 struct mapping_cond_s * cond; /* Condensed entries */ 26 struct mapping_hash_s * hash; /* Hashed entries */ 27 mapping_t *next; 28 /* Next mapping - for use by the cleanup code and 29 * the garbage collector. 30 */ 31 }; 32 33 /* --- struct mapping_hash_s: the hashed index --- 34 * 35 * New entries in a mapping are stored in a hash structure for fast 36 * access. The hash grows dynamically with the number of entries - 37 * the structure is then reallocated to fit - the goal is to keep 38 * on average two entries per hash bucket. 39 * 40 * This structure is exported so that interpret.c can use it to 41 * build protectors. 42 */ 43 44 struct mapping_hash_s { 45 p_int used; /* Number of entries in the hash */ 46 p_int mask; 47 /* Index mask for chains[], converting the raw hash value into 48 * the valid index number using a bit-and operation. 49 * Incremented by one, it's the number of chains. 50 */ 51 p_int ref; 52 /* Refcount if this mapping is part of a T_PROTECTOR_MAPPING svalue. 53 * The value is <= the mappings main refcount. 54 */ 55 mp_int last_used; 56 /* Time of the last change (add or delete) to the mapping. 57 */ 58 p_int cond_deleted; 59 /* Number of entries deleted from the condensed part 60 */ 61 struct map_chain_s *deleted; 62 /* Protector mappings only: list of deleted entries, which are kept 63 * pending because the they may still be used as destination for 64 * a lvalue. 65 */ 66 struct map_chain_s * chains[ 1 /* +.mask */ ]; 67 /* The hash chain heads ('hash buckets') 68 */ 69 }; 70 71 #define SIZEOF_MH_ALL(hm, nv) ( \ 72 sizeof(*(hm)) + sizeof(map_chain_t *) * (hm)->mask \ 73 + (sizeof(map_chain_t) + sizeof(svalue_t) * (nv)) * ((hm)->used) \ 74 ) 75 /* Allocation size of a given mapping_hash_t structure for a mapping 76 * with <nv> values per key, including map_chain structures. 77 */ 78 79 #define SIZEOF_MH(hm) ( \ 80 sizeof(*(hm)) + sizeof(map_chain_t *) * (hm)->mask \ 81 ) 82 /* Allocation size of a given mapping_hash_t structure, excluding 83 * the map_chain structures. 84 */ 85 86 87 /* --- struct mapping_cond_s: the condensed block --- 88 * 89 * When a mapping is compacted, the entries are stored in sorted order 90 * in this structure (allocated to size). 91 * If later a key is deleted, it's .type is set to T_INVALID. 92 * 93 * The structure is exported so that the swapper can use it. 94 */ 95 96 struct mapping_cond_s { 97 size_t size; /* Number of allocated entries */ 98 svalue_t data[1 /* .size * (m->num_values+1) */]; 99 }; 100 101 #define SIZEOF_MC(cm, nv) ( \ 102 sizeof(*(cm)) + sizeof(svalue_t) * (((cm)->size * ((nv)+1)) - 1) \ 103 ) 104 /* Allocation size of a given mapping_cond_t structure for 105 * a mapping with <nv> values per key. 106 */ 107 108 #define COND_DATA(cm, ix, nv) ( \ 109 &((cm)->data[(cm)->size + (ix) * (nv)]) \ 110 ) 111 /* For key entry [<ix>] in a given mapping_cond_t for a mapping 112 * with <nv> values per key, return pointer to the first assocated value. 113 */ 114 115 116 /* --- struct mvf_info: structure used by m_values()/unmkmapping() --- 117 * 118 * This structure is passed by reference to the filter functions used 119 * by the two efuns and passes information from one filter call to the 120 * next. 121 */ 122 struct mvf_info 123 { 124 svalue_t * svp; 125 /* m_values_filter: Pointer to next result vector entry 126 * m_unmake_filter: Pointer to result array of svalues 127 */ 128 int num; 129 /* m_values_filter: Column to retrieve. 130 * m_unmake_filter: Next row to retrieve 131 */ 132 int width; 133 /* m_unmake_filter: width of the mapping 134 */ 135 }; 136 137 138 /* --- Macros --- */ 139 140 #define MAP_SIZE(m) ((m)->num_entries) 141 /* Size (number of keys) of a given mapping <m>. 142 */ 143 144 #define MAP_TOTAL_SIZE(m) ((m)->num_entries * (1+(m)->num_values)) 145 /* Size (number of keys and values) of a given mapping <m>. 146 */ 147 148 /* mapping_t *ref_mapping(mapping_t *m) 149 * Add another ref to mapping <m> and return the mapping <m>. 150 */ 151 152 #define ref_mapping(m) ((m)->ref++, (m)) 153 154 /* Bool free_mapping(mapping_t *m) 155 * Subtract one ref from mapping <m>, and free the mapping fully if 156 * the refcount reaches zero. 157 * Return TRUE if the mapping is deallocated, and FALSE if not. 158 */ 159 160 #define free_mapping(m) ( (--((m)->ref) <= 0) ? _free_mapping(m, MY_FALSE) : MY_FALSE ) 161 162 /* p_int deref_mapping(mapping_t *m) 163 * Subtract one ref from mapping <m>, but don't check if it needs to 164 * be freed. Result is the number of refs left. 165 */ 166 167 #define deref_mapping(m) (--(m)->ref) 168 169 /* --- Variables --- */ 170 171 extern mp_int num_mappings; 172 extern mp_int num_hash_mappings; 173 extern mp_int num_dirty_mappings; 174 175 /* --- Prototypes --- */ 176 177 extern mapping_t *allocate_mapping(mp_int size, mp_int num_values); 178 extern mapping_t *allocate_cond_mapping(wiz_list_t * user, mp_int size, mp_int num_values); 179 extern Bool _free_mapping(mapping_t *m, Bool no_data); 180 #define free_empty_mapping(m) _free_mapping(m, MY_TRUE) 181 extern void free_protector_mapping(mapping_t *m); 182 extern svalue_t *_get_map_lvalue(mapping_t *m, svalue_t *map_index, Bool need_lvalue, Bool check_size); 183 #define get_map_value(m,x) _get_map_lvalue(m,x,MY_FALSE, MY_TRUE) 184 #define get_map_lvalue(m,x) _get_map_lvalue(m,x,MY_TRUE, MY_TRUE) 185 #define get_map_lvalue_unchecked(m,x) _get_map_lvalue(m,x,MY_TRUE, MY_FALSE) 186 extern Bool mapping_references_objects (mapping_t *m); 187 extern void check_map_for_destr(mapping_t *m); 188 extern mapping_t *resize_mapping(mapping_t *m, mp_int new_width); 189 #define copy_mapping(m) resize_mapping((m), (m)->num_values) 190 extern mapping_t *add_mapping(mapping_t *m1, mapping_t *m2); 191 extern void walk_mapping(mapping_t *m, void (*func)(svalue_t *key, svalue_t *val, void *extra), void *extra); 192 extern Bool compact_mapping(mapping_t *m, Bool force); 193 extern mp_int total_mapping_size(void); 194 extern size_t mapping_overhead(mapping_t *m); 195 extern void set_mapping_user(mapping_t *m, object_t *owner); 196 197 extern svalue_t *f_m_allocate(svalue_t *sp); 198 extern svalue_t *v_m_contains(svalue_t *sp, int num_arg); 199 extern svalue_t *v_m_add(svalue_t *sp, int num_arg); 200 extern svalue_t *f_m_delete(svalue_t *sp); 201 extern vector_t *m_indices(mapping_t *m); 202 extern svalue_t *f_m_indices(svalue_t *sp); 203 extern svalue_t *f_m_values(svalue_t *sp); 204 extern svalue_t *v_mkmapping (svalue_t *sp, int num_arg); 205 extern void sub_from_mapping_filter(svalue_t *key, svalue_t *data, void *extra); 206 extern void add_to_mapping(mapping_t *m1, mapping_t *m2); 207 extern mapping_t *subtract_mapping(mapping_t *minuend, mapping_t *subtrahend); 208 extern mapping_t *map_intersect(mapping_t *m, svalue_t * val); 209 extern vector_t * map_intersect_array (vector_t *vec, mapping_t *map); 210 extern svalue_t *x_filter_mapping(svalue_t *sp, int num_arg, Bool bFull); 211 extern svalue_t *v_filter_indices (svalue_t *sp, int num_arg); 212 extern svalue_t *x_map_mapping(svalue_t *sp, int num_arg, Bool bFull); 213 extern svalue_t *v_map_indices (svalue_t *sp, int num_arg); 214 extern svalue_t *v_walk_mapping(svalue_t *sp, int num_arg); 215 extern svalue_t * f_m_entry (svalue_t *sp); 216 extern svalue_t *f_m_reallocate (svalue_t *sp); 217 extern svalue_t *f_unmkmapping (svalue_t *sp); 218 extern svalue_t *f_widthof (svalue_t *sp); 219 220 #ifdef GC_SUPPORT 221 extern void count_ref_in_mapping(mapping_t *m); 222 extern void clean_stale_mappings(void); 223 extern void clear_mapping_size (void); 224 extern void count_mapping_size (mapping_t *m); 225 #endif 226 227 #ifdef CHECK_MAPPING_TOTAL 228 extern void m_check_total_mapping_size (const char * file, int line); 229 #define check_total_mapping_size() m_check_total_mapping_size(__FILE__, __LINE__) 230 #else 231 #define check_total_mapping_size() NOOP 232 #endif 233 234 #endif /* MAPPING_H__ */ 235