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-1301 USA
17*/
18
19#pragma once
20
21#include "grn.h"
22#include "grn_ctx.h"
23
24#ifdef __cplusplus
25extern "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 */
67typedef struct _grn_tiny_array grn_tiny_array;
68
69struct _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
101GRN_API void grn_tiny_array_init(grn_ctx *ctx, grn_tiny_array *array,
102 uint16_t element_size, uint16_t flags);
103GRN_API void grn_tiny_array_fin(grn_tiny_array *array);
104GRN_API void *grn_tiny_array_at(grn_tiny_array *array, grn_id id);
105GRN_API grn_id grn_tiny_array_id(grn_tiny_array *array,
106 const void *element_address);
107
108/**** grn_tiny_bitmap ****/
109
110typedef struct _grn_tiny_bitmap grn_tiny_bitmap;
111
112struct _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 */
128struct _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
150struct _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 */
165uint32_t grn_array_size(grn_ctx *ctx, grn_array *array);
166
167uint32_t grn_array_get_flags(grn_ctx *ctx, grn_array *array);
168
169grn_rc grn_array_truncate(grn_ctx *ctx, grn_array *array);
170grn_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
175typedef struct _grn_table_queue grn_table_queue;
176
177struct _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
186GRN_API void grn_array_queue_lock_clear(grn_ctx *ctx, grn_array *array);
187GRN_API void grn_array_clear_curr_rec(grn_ctx *ctx, grn_array *array);
188GRN_API grn_table_queue *grn_array_queue(grn_ctx *ctx, grn_array *array);
189GRN_API uint32_t grn_table_queue_size(grn_table_queue *queue);
190GRN_API void grn_table_queue_head_increment(grn_table_queue *queue);
191GRN_API void grn_table_queue_tail_increment(grn_table_queue *queue);
192GRN_API grn_id grn_table_queue_head(grn_table_queue *queue);
193GRN_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
203typedef struct _grn_hash_header_common grn_hash_header_common;
204typedef struct _grn_hash_header_normal grn_hash_header_normal;
205typedef struct _grn_hash_header_large grn_hash_header_large;
206
207struct _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
271struct _grn_hash_header_common {
272 GRN_HASH_HEADER_COMMON_FIELDS;
273};
274
275struct _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
281struct _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
287struct _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
313typedef struct _grn_table_sort_optarg grn_table_sort_optarg;
314
315struct _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
326GRN_API int grn_hash_sort(grn_ctx *ctx, grn_hash *hash, int limit,
327 grn_array *result, grn_table_sort_optarg *optarg);
328
329grn_rc grn_hash_lock(grn_ctx *ctx, grn_hash *hash, int timeout);
330grn_rc grn_hash_unlock(grn_ctx *ctx, grn_hash *hash);
331grn_rc grn_hash_clear_lock(grn_ctx *ctx, grn_hash *hash);
332
333#define GRN_HASH_SIZE(hash) (*((hash)->n_entries))
334
335/* private */
336typedef 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
344GRN_API grn_rc grn_hash_truncate(grn_ctx *ctx, grn_hash *hash);
345
346int grn_rec_unit_size(grn_rec_unit unit, int rec_size);
347
348const char * _grn_hash_key(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *key_size);
349
350int grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id,
351 void *keybuf, int bufsize, void *valuebuf);
352
353int _grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id,
354 void **key, void **value);
355
356grn_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 */
359const char *_grn_hash_strkey_by_val(void *v, uint16_t *size);
360
361const char *grn_hash_get_value_(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *size);
362
363grn_rc grn_hash_remove(grn_ctx *ctx, const char *path);
364grn_rc grn_array_remove(grn_ctx *ctx, const char *path);
365
366grn_id grn_hash_at(grn_ctx *ctx, grn_hash *hash, grn_id id);
367grn_id grn_array_at(grn_ctx *ctx, grn_array *array, grn_id id);
368
369void grn_hash_check(grn_ctx *ctx, grn_hash *hash);
370
371grn_bool grn_hash_is_large_total_key_size(grn_ctx *ctx, grn_hash *hash);
372
373uint64_t grn_hash_total_key_size(grn_ctx *ctx, grn_hash *hash);
374uint64_t grn_hash_max_total_key_size(grn_ctx *ctx, grn_hash *hash);
375
376#ifdef __cplusplus
377}
378#endif
379