1 /* -*- c-basic-offset: 2 -*- */ 2 /* 3 Copyright(C) 2009-2016 Brazil 4 5 This library is free software; you can redistribute it and/or 6 modify it under the terms of the GNU Lesser General Public 7 License version 2.1 as published by the Free Software Foundation. 8 9 This library is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public 15 License along with this library; if not, write to the Free Software 16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA 17 */ 18 19 #pragma once 20 21 #include "grn.h" 22 #include "grn_ctx.h" 23 24 #ifdef __cplusplus 25 extern "C" { 26 #endif 27 28 /**** grn_tiny_array ****/ 29 30 /* 31 * grn_tiny_array_init() accepts a logical OR of the following flags. 32 * Note that other flags, such as (1 << 30), will be ignored. 33 * 34 * - GRN_TINY_ARRAY_CLEAR specifies to initialize a new block with zeros. 35 * It is valid only iff specified with GRN_TINY_ARRAY_USE_MALLOC. 36 * - GRN_TINY_ARRAY_THREADSAFE specifies to create a critical section when 37 * allocating memory. 38 * - GRN_TINY_ARRAY_USE_MALLOC specifies to use GRN_MALLOC/CALLOC/FREE instead 39 * of GRN_CTX_ALLOC/FREE. 40 */ 41 #define GRN_TINY_ARRAY_CLEAR (1 << 0) 42 #define GRN_TINY_ARRAY_THREADSAFE (1 << 1) 43 #define GRN_TINY_ARRAY_USE_MALLOC (1 << 2) 44 45 /* 46 * - GRN_TINY_ARRAY_FACTOR is the global parameter of grn_tiny_array. 47 * - GRN_TINY_ARRAY_GET_OFFSET() returns the offset of a specified block. 48 * - GRN_TINY_ARRAY_BASE_BLOCK_SIZE is the number of elements in the first 49 * block. 50 * - GRN_TINY_ARRAY_GET_BLOCK_SIZE() returns the number of elements in a 51 * specified block. 52 * - GRN_TINY_ARRAY_NUM_BLOCKS is the maximum number of blocks. 53 */ 54 #define GRN_TINY_ARRAY_FACTOR 0 55 #define GRN_TINY_ARRAY_GET_OFFSET(block_id) \ 56 (1 << ((block_id) << GRN_TINY_ARRAY_FACTOR)) 57 #define GRN_TINY_ARRAY_BASE_BLOCK_SIZE \ 58 (GRN_TINY_ARRAY_GET_OFFSET(1) - GRN_TINY_ARRAY_GET_OFFSET(0)) 59 #define GRN_TINY_ARRAY_GET_BLOCK_SIZE(block_id) \ 60 (GRN_TINY_ARRAY_BASE_BLOCK_SIZE * GRN_TINY_ARRAY_GET_OFFSET(block_id)) 61 #define GRN_TINY_ARRAY_NUM_BLOCKS (32 >> GRN_TINY_ARRAY_FACTOR) 62 63 /* 64 * grn_tiny_array uses several blocks to emulate an array. 65 * The k-th block, blocks[k - 1], consists of 2^(k-1) elements. 66 */ 67 typedef struct _grn_tiny_array grn_tiny_array; 68 69 struct _grn_tiny_array { 70 grn_ctx *ctx; 71 grn_id max; 72 uint16_t element_size; 73 uint16_t flags; 74 void *blocks[GRN_TINY_ARRAY_NUM_BLOCKS]; 75 grn_critical_section lock; 76 }; 77 78 #define GRN_TINY_ARRAY_EACH(array, head, tail, key, value, block) do { \ 79 int _block_id; \ 80 const grn_id _head = (head); \ 81 const grn_id _tail = (tail); \ 82 for (_block_id = 0, (key) = (_head); \ 83 _block_id < GRN_TINY_ARRAY_NUM_BLOCKS && (key) <= (_tail); \ 84 _block_id++) { \ 85 int _id = GRN_TINY_ARRAY_GET_BLOCK_SIZE(_block_id); \ 86 (value) = (array)->blocks[_block_id]; \ 87 if (value) { \ 88 while (_id-- && (key) <= (_tail)) { \ 89 { \ 90 block \ 91 } \ 92 (key)++; \ 93 (value) = (void *)((byte *)(value) + (array)->element_size); \ 94 } \ 95 } else { \ 96 (key) += _id; \ 97 } \ 98 } \ 99 } while (0) 100 101 GRN_API void grn_tiny_array_init(grn_ctx *ctx, grn_tiny_array *array, 102 uint16_t element_size, uint16_t flags); 103 GRN_API void grn_tiny_array_fin(grn_tiny_array *array); 104 GRN_API void *grn_tiny_array_at(grn_tiny_array *array, grn_id id); 105 GRN_API grn_id grn_tiny_array_id(grn_tiny_array *array, 106 const void *element_address); 107 108 /**** grn_tiny_bitmap ****/ 109 110 typedef struct _grn_tiny_bitmap grn_tiny_bitmap; 111 112 struct _grn_tiny_bitmap { 113 grn_ctx *ctx; 114 void *blocks[GRN_TINY_ARRAY_NUM_BLOCKS]; 115 }; 116 117 /**** grn_array ****/ 118 119 #define GRN_ARRAY_TINY (0x01<<6) 120 121 /* 122 * grn_array uses grn_io or grn_tiny_array to represent an array. 123 * 124 * To create a grn_tiny_array-based grn_array, specify the GRN_ARRAY_TINY flag 125 * to grn_array_create(). Note that a grn_tiny_array-based grn_array is not 126 * backed by a file. 127 */ 128 struct _grn_array { 129 grn_db_obj obj; 130 grn_ctx *ctx; 131 uint32_t value_size; 132 int32_t n_keys; 133 grn_table_sort_key *keys; 134 uint32_t *n_garbages; 135 uint32_t *n_entries; 136 137 /* For grn_io_array. */ 138 grn_io *io; 139 struct grn_array_header *header; 140 uint32_t *lock; 141 142 /* For grn_tiny_array. */ 143 uint32_t n_garbages_buf; 144 uint32_t n_entries_buf; 145 grn_id garbages; 146 grn_tiny_array array; 147 grn_tiny_bitmap bitmap; 148 }; 149 150 struct _grn_array_cursor { 151 grn_db_obj obj; 152 grn_array *array; 153 grn_ctx *ctx; 154 grn_id curr_rec; 155 grn_id tail; 156 unsigned int rest; 157 int dir; 158 }; 159 160 /* 161 * grn_array_size() returns the number of entries in an array. 162 * If the array was truncated by another process but `array` still refers to 163 * the old one, this function returns 0. 164 */ 165 uint32_t grn_array_size(grn_ctx *ctx, grn_array *array); 166 167 uint32_t grn_array_get_flags(grn_ctx *ctx, grn_array *array); 168 169 grn_rc grn_array_truncate(grn_ctx *ctx, grn_array *array); 170 grn_rc grn_array_copy_sort_key(grn_ctx *ctx, grn_array *array, 171 grn_table_sort_key *keys, int n_keys); 172 173 /* grn_table_queue */ 174 175 typedef struct _grn_table_queue grn_table_queue; 176 177 struct _grn_table_queue { 178 grn_mutex mutex; 179 grn_cond cond; 180 grn_id head; 181 grn_id tail; 182 grn_id cap; 183 grn_bool unblock_requested; 184 }; 185 186 GRN_API void grn_array_queue_lock_clear(grn_ctx *ctx, grn_array *array); 187 GRN_API void grn_array_clear_curr_rec(grn_ctx *ctx, grn_array *array); 188 GRN_API grn_table_queue *grn_array_queue(grn_ctx *ctx, grn_array *array); 189 GRN_API uint32_t grn_table_queue_size(grn_table_queue *queue); 190 GRN_API void grn_table_queue_head_increment(grn_table_queue *queue); 191 GRN_API void grn_table_queue_tail_increment(grn_table_queue *queue); 192 GRN_API grn_id grn_table_queue_head(grn_table_queue *queue); 193 GRN_API grn_id grn_table_queue_tail(grn_table_queue *queue); 194 195 /**** grn_hash ****/ 196 197 #define GRN_HASH_MAX_KEY_SIZE_NORMAL GRN_TABLE_MAX_KEY_SIZE 198 #define GRN_HASH_MAX_KEY_SIZE_LARGE (0xffff) 199 200 #define GRN_HASH_IS_LARGE_KEY(hash)\ 201 ((hash)->key_size > GRN_HASH_MAX_KEY_SIZE_NORMAL) 202 203 typedef struct _grn_hash_header_common grn_hash_header_common; 204 typedef struct _grn_hash_header_normal grn_hash_header_normal; 205 typedef struct _grn_hash_header_large grn_hash_header_large; 206 207 struct _grn_hash { 208 grn_db_obj obj; 209 grn_ctx *ctx; 210 uint32_t key_size; 211 grn_encoding encoding; 212 uint32_t value_size; 213 uint32_t entry_size; 214 uint32_t *n_garbages; 215 uint32_t *n_entries; 216 uint32_t *max_offset; 217 grn_obj *tokenizer; 218 grn_obj *normalizer; 219 grn_obj token_filters; 220 221 /* For grn_io_hash. */ 222 grn_io *io; 223 union { 224 grn_hash_header_common *common; 225 grn_hash_header_normal *normal; 226 grn_hash_header_large *large; 227 } header; 228 uint32_t *lock; 229 // uint32_t nref; 230 // unsigned int max_n_subrecs; 231 // unsigned int record_size; 232 // unsigned int subrec_size; 233 // grn_rec_unit record_unit; 234 // grn_rec_unit subrec_unit; 235 // uint8_t arrayp; 236 // grn_recordh *curr_rec; 237 // grn_set_cursor *cursor; 238 // int limit; 239 // void *userdata; 240 // grn_id subrec_id; 241 242 /* For grn_tiny_hash. */ 243 uint32_t max_offset_; 244 uint32_t n_garbages_; 245 uint32_t n_entries_; 246 grn_id *index; 247 grn_id garbages; 248 grn_tiny_array a; 249 grn_tiny_bitmap bitmap; 250 }; 251 252 #define GRN_HASH_HEADER_COMMON_FIELDS\ 253 uint32_t flags;\ 254 grn_encoding encoding;\ 255 uint32_t key_size;\ 256 uint32_t value_size;\ 257 grn_id tokenizer;\ 258 uint32_t curr_rec;\ 259 uint32_t curr_key_normal;\ 260 uint32_t idx_offset;\ 261 uint32_t entry_size;\ 262 uint32_t max_offset;\ 263 uint32_t n_entries;\ 264 uint32_t n_garbages;\ 265 uint32_t lock;\ 266 grn_id normalizer;\ 267 uint32_t truncated;\ 268 uint64_t curr_key_large;\ 269 uint32_t reserved[12] 270 271 struct _grn_hash_header_common { 272 GRN_HASH_HEADER_COMMON_FIELDS; 273 }; 274 275 struct _grn_hash_header_normal { 276 GRN_HASH_HEADER_COMMON_FIELDS; 277 grn_id garbages[GRN_HASH_MAX_KEY_SIZE_NORMAL]; 278 grn_table_queue queue; 279 }; 280 281 struct _grn_hash_header_large { 282 GRN_HASH_HEADER_COMMON_FIELDS; 283 grn_id garbages[GRN_HASH_MAX_KEY_SIZE_LARGE]; 284 grn_table_queue queue; 285 }; 286 287 struct _grn_hash_cursor { 288 grn_db_obj obj; 289 grn_hash *hash; 290 grn_ctx *ctx; 291 grn_id curr_rec; 292 grn_id tail; 293 unsigned int rest; 294 int dir; 295 }; 296 297 /* deprecated */ 298 299 #define GRN_TABLE_SORT_BY_KEY 0 300 #define GRN_TABLE_SORT_BY_ID (1L<<1) 301 #define GRN_TABLE_SORT_BY_VALUE (1L<<2) 302 #define GRN_TABLE_SORT_RES_ID 0 303 #define GRN_TABLE_SORT_RES_KEY (1L<<3) 304 #define GRN_TABLE_SORT_AS_BIN 0 305 #define GRN_TABLE_SORT_AS_NUMBER (1L<<4) 306 #define GRN_TABLE_SORT_AS_SIGNED 0 307 #define GRN_TABLE_SORT_AS_UNSIGNED (1L<<5) 308 #define GRN_TABLE_SORT_AS_INT32 0 309 #define GRN_TABLE_SORT_AS_INT64 (1L<<6) 310 #define GRN_TABLE_SORT_NO_PROC 0 311 #define GRN_TABLE_SORT_WITH_PROC (1L<<7) 312 313 typedef struct _grn_table_sort_optarg grn_table_sort_optarg; 314 315 struct _grn_table_sort_optarg { 316 grn_table_sort_flags flags; 317 int (*compar)(grn_ctx *ctx, 318 grn_obj *table1, void *target1, unsigned int target1_size, 319 grn_obj *table2, void *target2, unsigned int target2_size, 320 void *compare_arg); 321 void *compar_arg; 322 grn_obj *proc; 323 int offset; 324 }; 325 326 GRN_API int grn_hash_sort(grn_ctx *ctx, grn_hash *hash, int limit, 327 grn_array *result, grn_table_sort_optarg *optarg); 328 329 grn_rc grn_hash_lock(grn_ctx *ctx, grn_hash *hash, int timeout); 330 grn_rc grn_hash_unlock(grn_ctx *ctx, grn_hash *hash); 331 grn_rc grn_hash_clear_lock(grn_ctx *ctx, grn_hash *hash); 332 333 #define GRN_HASH_SIZE(hash) (*((hash)->n_entries)) 334 335 /* private */ 336 typedef enum { 337 grn_rec_document = 0, 338 grn_rec_section, 339 grn_rec_position, 340 grn_rec_userdef, 341 grn_rec_none 342 } grn_rec_unit; 343 344 GRN_API grn_rc grn_hash_truncate(grn_ctx *ctx, grn_hash *hash); 345 346 int grn_rec_unit_size(grn_rec_unit unit, int rec_size); 347 348 const char * _grn_hash_key(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *key_size); 349 350 int grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id, 351 void *keybuf, int bufsize, void *valuebuf); 352 353 int _grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id, 354 void **key, void **value); 355 356 grn_id grn_hash_next(grn_ctx *ctx, grn_hash *hash, grn_id id); 357 358 /* only valid for hash tables, GRN_OBJ_KEY_VAR_SIZE && GRN_HASH_TINY */ 359 const char *_grn_hash_strkey_by_val(void *v, uint16_t *size); 360 361 const char *grn_hash_get_value_(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *size); 362 363 grn_rc grn_hash_remove(grn_ctx *ctx, const char *path); 364 grn_rc grn_array_remove(grn_ctx *ctx, const char *path); 365 366 grn_id grn_hash_at(grn_ctx *ctx, grn_hash *hash, grn_id id); 367 grn_id grn_array_at(grn_ctx *ctx, grn_array *array, grn_id id); 368 369 void grn_hash_check(grn_ctx *ctx, grn_hash *hash); 370 371 grn_bool grn_hash_is_large_total_key_size(grn_ctx *ctx, grn_hash *hash); 372 373 uint64_t grn_hash_total_key_size(grn_ctx *ctx, grn_hash *hash); 374 uint64_t grn_hash_max_total_key_size(grn_ctx *ctx, grn_hash *hash); 375 376 #ifdef __cplusplus 377 } 378 #endif 379