1/*
2 * particle_map.c
3 *
4 * Copyright (C) 2015-2018 Aerospike, Inc.
5 *
6 * Portions may be licensed to Aerospike, Inc. under one or more contributor
7 * license agreements.
8 *
9 * This program is free software: you can redistribute it and/or modify it under
10 * the terms of the GNU Affero General Public License as published by the Free
11 * Software Foundation, either version 3 of the License, or (at your option) any
12 * later version.
13 *
14 * This program is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
17 * details.
18 *
19 * You should have received a copy of the GNU Affero General Public License
20 * along with this program. If not, see http://www.gnu.org/licenses/
21 */
22
23#include <stddef.h>
24#include <stdint.h>
25#include <stdlib.h>
26#include <string.h>
27
28#include "aerospike/as_buffer.h"
29#include "aerospike/as_msgpack.h"
30#include "aerospike/as_serializer.h"
31#include "aerospike/as_val.h"
32#include "citrusleaf/alloc.h"
33#include "citrusleaf/cf_byte_order.h"
34
35#include "bits.h"
36#include "fault.h"
37
38#include "base/cdt.h"
39#include "base/datamodel.h"
40#include "base/msgpack_in.h"
41#include "base/particle.h"
42#include "base/particle_blob.h"
43#include "base/proto.h"
44
45
46//==========================================================
47// MAP particle interface - function declarations.
48//
49
50// Destructor, etc.
51void map_destruct(as_particle *p);
52uint32_t map_size(const as_particle *p);
53
54// Handle "wire" format.
55int32_t map_concat_size_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
56int map_append_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
57int map_prepend_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
58int map_incr_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
59int32_t map_size_from_wire(const uint8_t *wire_value, uint32_t value_size);
60int map_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
61int map_compare_from_wire(const as_particle *p, as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size);
62uint32_t map_wire_size(const as_particle *p);
63uint32_t map_to_wire(const as_particle *p, uint8_t *wire);
64
65// Handle as_val translation.
66uint32_t map_size_from_asval(const as_val *val);
67void map_from_asval(const as_val *val, as_particle **pp);
68as_val *map_to_asval(const as_particle *p);
69uint32_t map_asval_wire_size(const as_val *val);
70uint32_t map_asval_to_wire(const as_val *val, uint8_t *wire);
71
72// Handle msgpack translation.
73uint32_t map_size_from_msgpack(const uint8_t *packed, uint32_t packed_size);
74void map_from_msgpack(const uint8_t *packed, uint32_t packed_size, as_particle **pp);
75
76// Handle on-device "flat" format.
77const uint8_t *map_from_flat(const uint8_t *flat, const uint8_t *end, as_particle **pp);
78uint32_t map_flat_size(const as_particle *p);
79uint32_t map_to_flat(const as_particle *p, uint8_t *flat);
80
81
82//==========================================================
83// MAP particle interface - vtable.
84//
85
86const as_particle_vtable map_vtable = {
87 map_destruct,
88 map_size,
89
90 map_concat_size_from_wire,
91 map_append_from_wire,
92 map_prepend_from_wire,
93 map_incr_from_wire,
94 map_size_from_wire,
95 map_from_wire,
96 map_compare_from_wire,
97 map_wire_size,
98 map_to_wire,
99
100 map_size_from_asval,
101 map_from_asval,
102 map_to_asval,
103 map_asval_wire_size,
104 map_asval_to_wire,
105
106 map_size_from_msgpack,
107 map_from_msgpack,
108
109 blob_skip_flat,
110 blob_cast_from_flat,
111 map_from_flat,
112 map_flat_size,
113 map_to_flat
114};
115
116
117//==========================================================
118// Typedefs & constants.
119//
120
121#if defined(CDT_DEBUG_VERIFY)
122#define MAP_DEBUG_VERIFY
123#endif
124
125#define LINEAR_FIND_RANK_MAX_COUNT 16 // switch to linear search when the count drops to this number
126
127#define AS_PACKED_MAP_FLAG_RESERVED_0 0x04 // placeholder for multimap
128#define AS_PACKED_MAP_FLAG_OFF_IDX 0x10 // has list offset index
129#define AS_PACKED_MAP_FLAG_ORD_IDX 0x20 // has value order index
130#define AS_PACKED_MAP_FLAG_ON_STACK 0x40 // map on stack
131
132#define AS_PACKED_MAP_FLAG_VALID_MASK AS_PACKED_MAP_FLAG_KV_ORDERED
133
134struct packed_map_s;
135
136typedef void (*packed_map_get_by_idx_func)(const struct packed_map_s *userdata, cdt_payload *contents, uint32_t index);
137
138typedef struct packed_map_s {
139 const uint8_t *packed;
140 const uint8_t *contents; // where elements start (excludes ext)
141 uint32_t packed_sz;
142 uint32_t content_sz;
143
144 // Mutable field member (Is considered mutable in const objects).
145 offset_index offidx; // offset start at contents (excluding ext metadata pair)
146 uint8_t flags;
147 // Mutable field member.
148 order_index ordidx;
149
150 uint32_t ele_count; // excludes ext pair
151} packed_map;
152
153typedef struct packed_map_op_s {
154 const packed_map *map;
155
156 uint32_t new_ele_count;
157 uint32_t ele_removed;
158
159 uint32_t seg1_sz;
160 uint32_t seg2_offset;
161 uint32_t seg2_sz;
162
163 uint32_t key1_offset;
164 uint32_t key1_sz;
165 uint32_t key2_offset;
166 uint32_t key2_sz;
167} packed_map_op;
168
169typedef struct map_packer_s {
170 uint8_t *write_ptr;
171 const uint8_t *contents;
172
173 offset_index offidx; // offset start at contents (excluding ext metadata pair)
174 order_index ordidx;
175
176 uint32_t ele_count;
177 uint32_t content_sz; // does not include map header or ext
178 uint32_t ext_content_sz;
179
180 uint32_t ext_sz;
181 uint32_t ext_header_sz;
182
183 uint8_t flags;
184} map_packer;
185
186typedef struct map_mem_s {
187 uint8_t type;
188 uint32_t sz;
189 uint8_t data[];
190} __attribute__ ((__packed__)) map_mem;
191
192typedef struct map_flat_s {
193 uint8_t type;
194 uint32_t sz;
195 uint8_t data[];
196} __attribute__ ((__packed__)) map_flat;
197
198typedef enum {
199 MAP_EMPTY_MAP_HDR = 0,
200 MAP_EMPTY_EXT_HDR,
201 MAP_EMPTY_EXT_SZ,
202 MAP_EMPTY_EXT_FLAGS,
203 MAP_EMPTY_NIL,
204 MAP_EMPTY_FLAGED_SIZE
205} map_empty_bytes;
206
207#define MAP_MEM_EMPTY_FLAGGED_ENTRY(__flags) \
208 .type = AS_PARTICLE_TYPE_MAP, \
209 .sz = MAP_EMPTY_FLAGED_SIZE, \
210 .data = { \
211 [MAP_EMPTY_MAP_HDR] = 0x81, \
212 [MAP_EMPTY_EXT_HDR] = 0xC7, \
213 [MAP_EMPTY_EXT_SZ] = 0, \
214 [MAP_EMPTY_EXT_FLAGS] = __flags, \
215 [MAP_EMPTY_NIL] = 0xC0 \
216 }
217
218static const map_mem map_mem_empty_k = {
219 MAP_MEM_EMPTY_FLAGGED_ENTRY(AS_PACKED_MAP_FLAG_K_ORDERED | AS_PACKED_MAP_FLAG_OFF_IDX)
220};
221
222static const map_mem map_mem_empty_kv = {
223 MAP_MEM_EMPTY_FLAGGED_ENTRY(AS_PACKED_MAP_FLAG_KV_ORDERED | AS_PACKED_MAP_FLAG_OFF_IDX | AS_PACKED_MAP_FLAG_ORD_IDX)
224};
225
226static const map_mem map_mem_empty = {
227 .type = AS_PARTICLE_TYPE_MAP,
228 .sz = 1,
229 .data = {0x80}
230};
231
232typedef enum sort_by_e {
233 SORT_BY_KEY,
234 SORT_BY_VALUE
235} sort_by_t;
236
237typedef struct index_sort_userdata_s {
238 const offset_index *offsets;
239 order_index *order;
240 const uint8_t *contents;
241 uint32_t content_sz;
242 sort_by_t sort_by;
243} index_sort_userdata;
244
245typedef struct map_add_control_s {
246 bool allow_overwrite; // if key exists and map is unique-keyed - may overwrite
247 bool allow_create; // if key does not exist - may create
248 bool no_fail; // do not fail on policy violation
249 bool do_partial; // do the parts that did not fail
250} map_add_control;
251
252typedef struct map_ele_find_s {
253 bool found_key;
254 bool found_value;
255
256 uint32_t idx;
257 uint32_t rank;
258
259 uint32_t key_offset; // offset start at map header
260 uint32_t value_offset; // offset start at map header
261 uint32_t sz;
262
263 uint32_t upper;
264 uint32_t lower;
265} map_ele_find;
266
267typedef struct {
268 offset_index *offidx;
269 uint8_t mem_temp[];
270} __attribute__ ((__packed__)) map_vla_offidx_cast;
271
272typedef struct {
273 offset_index *offidx;
274 order_index *ordidx;
275 uint8_t mem_temp[];
276} __attribute__ ((__packed__)) map_vla_offord_cast;
277
278#define setup_map_must_have_offidx(__name, __map_p, __alloc) \
279 uint8_t __name ## __vlatemp[sizeof(offset_index *) + offset_index_vla_sz(&(__map_p)->offidx)]; \
280 map_vla_offidx_cast *__name = (map_vla_offidx_cast *)__name ## __vlatemp; \
281 __name->offidx = (offset_index *)&(__map_p)->offidx; \
282 offset_index_alloc_temp(__name->offidx, __name->mem_temp, __alloc)
283
284#define setup_map_must_have_all_idx(__name, __map_p, __alloc) \
285 uint8_t __name ## __vlatemp[sizeof(offset_index *) + sizeof(order_index *) + map_allidx_vla_sz(__map_p)]; \
286 map_vla_offord_cast *__name = (map_vla_offord_cast *)__name ## __vlatemp; \
287 __name->offidx = (offset_index *)&(__map_p)->offidx; \
288 __name->ordidx = (order_index *)&(__map_p)->ordidx; \
289 map_allidx_alloc_temp(__map_p, __name->mem_temp, __alloc)
290
291#define define_map_unpacker(__name, __map_ptr) \
292 as_unpacker __name = { \
293 .buffer = (__map_ptr)->contents, \
294 .length = (__map_ptr)->content_sz \
295 }
296
297#define define_map_msgpack_in(__name, __map_ptr) \
298 msgpack_in __name = { \
299 .buf = (__map_ptr)->contents, \
300 .buf_sz = (__map_ptr)->content_sz \
301 }
302
303#define define_packed_map_op(__name, __map_ptr) \
304 packed_map_op __name; \
305 packed_map_op_init(&__name, __map_ptr)
306
307#define define_map_packer(__name, __ele_count, __flags, __content_sz) \
308 map_packer __name; \
309 map_packer_init(&__name, __ele_count, __flags, __content_sz)
310
311
312//==========================================================
313// Forward declarations.
314//
315
316static inline bool is_map_type(uint8_t type);
317static inline bool is_k_ordered(uint8_t flags);
318static inline bool is_kv_ordered(uint8_t flags);
319static uint32_t map_calc_ext_content_sz(uint8_t flags, uint32_t ele_count, uint32_t content_sz);
320static uint8_t map_adjust_incoming_flags(uint8_t flags);
321
322static inline uint32_t map_allidx_vla_sz(const packed_map *map);
323static inline void map_allidx_alloc_temp(const packed_map *map, uint8_t *mem_temp, rollback_alloc *alloc);
324
325static inline uint32_t map_ext_content_sz(const packed_map *map);
326static inline bool map_is_k_ordered(const packed_map *map);
327static inline bool map_is_kv_ordered(const packed_map *map);
328static inline bool map_has_offidx(const packed_map *map);
329
330// cdt_context
331static inline void cdt_context_use_static_map_if_notinuse(cdt_context *ctx, uint8_t flags);
332static inline void cdt_context_set_empty_packed_map(cdt_context *ctx, uint8_t flags);
333static inline void cdt_context_set_by_map_idx(cdt_context *ctx, const packed_map *map, uint32_t idx);
334
335static inline void cdt_context_map_push(cdt_context *ctx, const packed_map *map, uint32_t idx);
336
337// map_packer
338static as_particle *map_packer_create_particle(map_packer *mpk, rollback_alloc *alloc_buf);
339static void map_packer_create_particle_ctx(map_packer *mpk, cdt_context *ctx);
340static void map_packer_init(map_packer *mpk, uint32_t ele_count, uint8_t flags, uint32_t content_sz);
341
342static void map_packer_setup_bin(map_packer *mpk, cdt_op_mem *com);
343
344static void map_packer_write_hdridx(map_packer *mpk);
345static void map_packer_fill_offset_index(map_packer *mpk);
346static int map_packer_fill_index_sort_compare(const void *x, const void *y, void *p);
347static void map_packer_fill_ordidx(map_packer *mpk, const uint8_t *contents, uint32_t content_sz);
348static void map_packer_add_op_copy_index(map_packer *mpk, const packed_map_op *add_op, map_ele_find *remove_info, uint32_t kv_sz, const cdt_payload *value);
349static inline void map_packer_write_seg1(map_packer *mpk, const packed_map_op *op);
350static inline void map_packer_write_seg2(map_packer *mpk, const packed_map_op *op);
351static inline void map_packer_write_msgpack_seg(map_packer *mpk, const cdt_payload *seg);
352
353// map_op
354static int map_set_flags(cdt_op_mem *com, uint8_t set_flags);
355static int map_increment(cdt_op_mem *com, const cdt_payload *key, const cdt_payload *delta_value, bool is_decrement);
356
357static int map_add(cdt_op_mem *com, const cdt_payload *key, const cdt_payload *value, const map_add_control *control, bool set_result);
358static int map_add_items(cdt_op_mem *com, const cdt_payload *items, const map_add_control *control);
359static int map_add_items_ordered(const packed_map *map, cdt_op_mem *com, const offset_index *val_off, order_index *val_ord, const map_add_control *control);
360static int map_add_items_unordered(const packed_map *map, cdt_op_mem *com, const offset_index *val_off, order_index *val_ord, const map_add_control *control);
361
362static int map_remove_by_key_interval(cdt_op_mem *com, const cdt_payload *key_start, const cdt_payload *key_end);
363static int map_remove_by_index_range(cdt_op_mem *com, int64_t index, uint64_t count);
364static int map_remove_by_value_interval(cdt_op_mem *com, const cdt_payload *value_start, const cdt_payload *value_end);
365static int map_remove_by_rank_range(cdt_op_mem *com, int64_t rank, uint64_t count);
366
367static int map_remove_by_rel_index_range(cdt_op_mem *com, const cdt_payload *value, int64_t index, uint64_t count);
368static int map_remove_by_rel_rank_range(cdt_op_mem *com, const cdt_payload *value, int64_t rank, uint64_t count);
369
370static int map_remove_all_by_key_list(cdt_op_mem *com, const cdt_payload *key_list);
371static int map_remove_all_by_value_list(cdt_op_mem *com, const cdt_payload *value_list);
372
373static int map_clear(cdt_op_mem *com);
374
375// packed_map
376static bool packed_map_init(packed_map *map, const uint8_t *buf, uint32_t sz, bool fill_idxs);
377static inline bool packed_map_init_from_particle(packed_map *map, const as_particle *p, bool fill_idxs);
378static bool packed_map_init_from_bin(packed_map *map, const as_bin *b, bool fill_idxs);
379static bool packed_map_init_from_ctx(packed_map *map, const cdt_context *ctx, bool fill_idxs);
380static inline bool packed_map_init_from_com(packed_map *map, cdt_op_mem *com, bool fill_idxs);
381static bool packed_map_unpack_hdridx(packed_map *map, bool fill_idxs);
382
383static void packed_map_init_indexes(const packed_map *map, as_packer *pk, offset_index *offidx, order_index *ordidx);
384
385static void packed_map_ensure_ordidx_filled(const packed_map *map);
386static bool packed_map_check_and_fill_offidx(const packed_map *map);
387
388static uint32_t packed_map_find_index_by_idx_unordered(const packed_map *map, uint32_t idx);
389static uint32_t packed_map_find_index_by_key_unordered(const packed_map *map, const cdt_payload *key);
390
391static void packed_map_find_rank_indexed_linear(const packed_map *map, map_ele_find *find, uint32_t start, uint32_t len);
392static void packed_map_find_rank_indexed(const packed_map *map, map_ele_find *find);
393static void packed_map_find_rank_by_value_indexed(const packed_map *map, map_ele_find *find, const cdt_payload *value);
394static void packed_map_find_rank_range_by_value_interval_indexed(const packed_map *map, const cdt_payload *value_start, const cdt_payload *value_end, uint32_t *rank, uint32_t *count, bool is_multi);
395static void packed_map_find_rank_range_by_value_interval_unordered(const packed_map *map, const cdt_payload *value_start, const cdt_payload *value_end, uint32_t *rank, uint32_t *count, uint64_t *mask, bool is_multi);
396static void packed_map_find_key_indexed(const packed_map *map, map_ele_find *find, const cdt_payload *key);
397static bool packed_map_find_key(const packed_map *map, map_ele_find *find, const cdt_payload *key);
398
399static int packed_map_get_remove_by_key_interval(const packed_map *map, cdt_op_mem *com, const cdt_payload *key_start, const cdt_payload *key_end);
400static int packed_map_trim_ordered(const packed_map *map, cdt_op_mem *com, uint32_t index, uint32_t count);
401static int packed_map_get_remove_by_index_range(const packed_map *map, cdt_op_mem *com, int64_t index, uint64_t count);
402
403static int packed_map_get_remove_by_value_interval(const packed_map *map, cdt_op_mem *com, const cdt_payload *value_start, const cdt_payload *value_end);
404static int packed_map_get_remove_by_rank_range(const packed_map *map, cdt_op_mem *com, int64_t rank, uint64_t count);
405
406static int packed_map_get_remove_all_by_key_list(const packed_map *map, cdt_op_mem *com, const cdt_payload *key_list);
407static int packed_map_get_remove_all_by_key_list_ordered(const packed_map *map, cdt_op_mem *com, as_unpacker *items_pk, uint32_t items_count);
408static int packed_map_get_remove_all_by_key_list_unordered(const packed_map *map, cdt_op_mem *com, as_unpacker *items_pk, uint32_t items_count);
409static int packed_map_get_remove_all_by_value_list(const packed_map *map, cdt_op_mem *com, const cdt_payload *value_list);
410static int packed_map_get_remove_all_by_value_list_ordered(const packed_map *map, cdt_op_mem *com, as_unpacker *items_pk, uint32_t items_count);
411
412static int packed_map_get_remove_by_rel_index_range(const packed_map *map, cdt_op_mem *com, const cdt_payload *key, int64_t index, uint64_t count);
413static int packed_map_get_remove_by_rel_rank_range(const packed_map *map, cdt_op_mem *com, const cdt_payload *value, int64_t rank, uint64_t count);
414
415static int packed_map_get_remove_all(const packed_map *map, cdt_op_mem *com);
416
417static void packed_map_remove_by_mask(const packed_map *map, cdt_op_mem *com, const uint64_t *rm_mask, uint32_t count, uint32_t *rm_sz_r);
418static void packed_map_remove_idx_range(const packed_map *map, cdt_op_mem *com, uint32_t idx, uint32_t count);
419
420
421static void packed_map_get_range_by_key_interval_unordered(const packed_map *map, const cdt_payload *key_start, const cdt_payload *key_end, uint32_t *index, uint32_t *count, uint64_t *mask);
422static void packed_map_get_range_by_key_interval_ordered(const packed_map *map, const cdt_payload *key_start, const cdt_payload *key_end, uint32_t *index, uint32_t *count);
423static void packed_map_build_rank_result_by_ele_idx(const packed_map *map, const order_index *ele_idx, uint32_t start, uint32_t count, cdt_result_data *result);
424static void packed_map_build_rank_result_by_mask(const packed_map *map, const uint64_t *mask, uint32_t count, cdt_result_data *result);
425static void packed_map_build_rank_result_by_index_range(const packed_map *map, uint32_t index, uint32_t count, cdt_result_data *result);
426
427static void packed_map_get_key_by_idx(const packed_map *map, cdt_payload *key, uint32_t index);
428static void packed_map_get_value_by_idx(const packed_map *map, cdt_payload *value, uint32_t idx);
429static void packed_map_get_pair_by_idx(const packed_map *map, cdt_payload *value, uint32_t index);
430
431static void packed_map_build_index_result_by_ele_idx(const packed_map *map, const order_index *ele_idx, uint32_t start, uint32_t count, cdt_result_data *result);
432static void packed_map_build_index_result_by_mask(const packed_map *map, const uint64_t *mask, uint32_t count, cdt_result_data *result);
433static bool packed_map_build_ele_result_by_idx_range(const packed_map *map, uint32_t start_idx, uint32_t count, cdt_result_data *result);
434static bool packed_map_build_ele_result_by_ele_idx(const packed_map *map, const order_index *ele_idx, uint32_t start, uint32_t count, uint32_t rm_sz, cdt_result_data *result);
435static bool packed_map_build_ele_result_by_mask(const packed_map *map, const uint64_t *mask, uint32_t count, uint32_t rm_sz, cdt_result_data *result);
436static int packed_map_build_result_by_key(const packed_map *map, const cdt_payload *key, uint32_t idx, uint32_t count, cdt_result_data *result);
437
438static uint32_t packed_map_get_rank_by_idx(const packed_map *map, uint32_t idx);
439static void packed_map_build_rank_result_by_idx(const packed_map *map, uint32_t idx, cdt_result_data *result);
440static void packed_map_build_rank_result_by_idx_range(const packed_map *map, uint32_t idx, uint32_t count, cdt_result_data *result);
441
442static msgpack_compare_t packed_map_compare_key_by_idx(const void *ptr, uint32_t idx1, uint32_t idx2);
443static msgpack_compare_t packed_map_compare_values(msgpack_in *pk1, msgpack_in *pk2);
444static msgpack_compare_t packed_map_compare_value_by_idx(const void *ptr, uint32_t idx1, uint32_t idx2);
445
446static void packed_map_write_k_ordered(const packed_map *map, uint8_t *write_ptr, offset_index *offsets_new);
447
448// packed_map_op
449static void packed_map_op_init(packed_map_op *op, const packed_map *map);
450static uint32_t packed_map_op_add(packed_map_op *op, const map_ele_find *found);
451static uint32_t packed_map_op_remove(packed_map_op *op, const map_ele_find *found, uint32_t count, uint32_t remove_sz);
452
453static uint8_t *packed_map_op_write_seg1(const packed_map_op *op, uint8_t *buf);
454static uint8_t *packed_map_op_write_seg2(const packed_map_op *op, uint8_t *buf);
455static void packed_map_op_write_new_offidx(const packed_map_op *op, const map_ele_find *remove_info, const map_ele_find *add_info, offset_index *new_offidx, uint32_t kv_sz);
456static void packed_map_op_write_new_ordidx(const packed_map_op *op, const map_ele_find *remove_info, const map_ele_find *add_info, order_index *new_ordidx);
457
458// map_particle
459static as_particle *map_particle_create(rollback_alloc *alloc_buf, uint32_t ele_count, const uint8_t *buf, uint32_t content_sz, uint8_t flags);
460static uint32_t map_particle_strip_indexes(const as_particle *p, uint8_t *dest);
461
462// map_ele_find
463static void map_ele_find_init(map_ele_find *find, const packed_map *map);
464static void map_ele_find_continue_from_lower(map_ele_find *find, const map_ele_find *found, uint32_t ele_count);
465static void map_ele_find_init_from_idx(map_ele_find *find, const packed_map *map, uint32_t idx);
466
467// map_offset_index
468static bool map_offset_index_check_and_fill(offset_index *offidx, uint32_t index);
469
470static void map_offset_index_copy_rm_mask(offset_index *dest, const offset_index *src, const uint64_t *rm_mask, uint32_t rm_count);
471static void map_offset_index_copy_rm_range(offset_index *dest, const offset_index *src, uint32_t rm_idx, uint32_t rm_count);
472
473// order_index
474static void order_index_sort(order_index *ordidx, const offset_index *offsets, const uint8_t *contents, uint32_t content_sz, sort_by_t sort_by);
475static inline void order_index_set_sorted(order_index *ordidx, const offset_index *offsets, const uint8_t *ele_start, uint32_t tot_ele_sz, sort_by_t sort_by);
476static void order_index_set_sorted_with_offsets(order_index *ordidx, const offset_index *offsets, sort_by_t sort_by);
477
478static uint32_t order_index_find_idx(const order_index *ordidx, uint32_t idx, uint32_t start, uint32_t len);
479
480// order_index_adjust
481static uint32_t order_index_adjust_lower(const order_index_adjust *via, uint32_t src);
482
483// order_index_op
484static inline void order_index_op_add(order_index *dest, const order_index *src, uint32_t add_idx, uint32_t add_rank);
485static inline void order_index_op_replace1_internal(order_index *dest, const order_index *src, uint32_t add_idx, uint32_t add_rank, uint32_t remove_rank, const order_index_adjust *adjust);
486static inline void order_index_op_replace1(order_index *dest, const order_index *src, uint32_t add_rank, uint32_t remove_rank);
487static void order_index_op_remove_idx_mask(order_index *dest, const order_index *src, const uint64_t *mask, uint32_t count);
488
489// result_data
490static bool result_data_set_key_not_found(cdt_result_data *rd, int64_t index);
491static bool result_data_set_value_not_found(cdt_result_data *rd, int64_t rank);
492
493// Debugging support
494void map_print(const packed_map *map, const char *name);
495
496
497//==========================================================
498// MAP particle interface - function definitions.
499//
500
501//------------------------------------------------
502// Destructor, etc.
503//
504
505void
506map_destruct(as_particle *p)
507{
508 cf_free(p);
509}
510
511uint32_t
512map_size(const as_particle *p)
513{
514 const map_mem *p_map_mem = (const map_mem *)p;
515 return (uint32_t)sizeof(map_mem) + p_map_mem->sz;
516}
517
518//------------------------------------------------
519// Handle "wire" format.
520//
521
522int32_t
523map_concat_size_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
524 uint32_t value_size, as_particle **pp)
525{
526 cf_warning(AS_PARTICLE, "concat size for map");
527 return -AS_ERR_INCOMPATIBLE_TYPE;
528}
529
530int
531map_append_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
532 uint32_t value_size, as_particle **pp)
533{
534 cf_warning(AS_PARTICLE, "append to map");
535 return -AS_ERR_INCOMPATIBLE_TYPE;
536}
537
538int
539map_prepend_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
540 uint32_t value_size, as_particle **pp)
541{
542 cf_warning(AS_PARTICLE, "prepend to map");
543 return -AS_ERR_INCOMPATIBLE_TYPE;
544}
545
546int
547map_incr_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
548 uint32_t value_size, as_particle **pp)
549{
550 cf_warning(AS_PARTICLE, "increment of map");
551 return -AS_ERR_INCOMPATIBLE_TYPE;
552}
553
554int32_t
555map_size_from_wire(const uint8_t *wire_value, uint32_t value_size)
556{
557 // TODO - CDT can't determine in memory or not.
558 packed_map map;
559
560 if (! packed_map_init(&map, wire_value, value_size, false)) {
561 cf_warning(AS_PARTICLE, "map_size_from_wire() invalid packed map");
562 return -AS_ERR_UNKNOWN;
563 }
564
565 if ((map.flags & AS_PACKED_MAP_FLAG_VALID_MASK) != map.flags) {
566 cf_warning(AS_PARTICLE, "map_size_from_wire() unsupported flags %x", map.flags);
567 return -AS_ERR_UNSUPPORTED_FEATURE;
568 }
569
570 if (map.flags == 0) {
571 return (int32_t)(sizeof(map_mem) + value_size);
572 }
573
574 uint32_t hdr_sz = map_ext_content_sz(&map);
575
576 hdr_sz += as_pack_ext_header_get_size(hdr_sz) + 1;
577 hdr_sz += as_pack_map_header_get_size(map.ele_count + 1);
578
579 return (int32_t)(sizeof(map_mem) + map.content_sz + hdr_sz);
580}
581
582int
583map_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
584 uint32_t value_size, as_particle **pp)
585{
586 // TODO - CDT can't determine in memory or not.
587 // It works for data-not-in-memory but we'll incur a memcpy that could be
588 // eliminated.
589 packed_map map;
590 bool is_valid = packed_map_init(&map, wire_value, value_size, false);
591
592 cf_assert(is_valid, AS_PARTICLE, "map_from_wire() invalid packed map");
593
594 map_mem *p_map_mem = (map_mem *)*pp;
595
596 p_map_mem->type = wire_type;
597
598 if (map.flags == 0) {
599 if (! cdt_check_storage_list_contents(map.contents, map.content_sz,
600 2 * map.ele_count)) {
601 cf_warning(AS_PARTICLE, "map_from_wire() invalid packed map");
602 return -AS_ERR_PARAMETER;
603 }
604
605 p_map_mem->sz = value_size;
606 memcpy(p_map_mem->data, wire_value, value_size);
607 return AS_OK;
608 }
609
610 uint32_t ext_content_sz = map_ext_content_sz(&map);
611 // 1 byte for header, 1 byte for type, 1 byte for length for existing ext.
612 uint32_t extra_sz = as_pack_ext_header_get_size(ext_content_sz) - 3;
613
614 as_packer pk = {
615 .buffer = p_map_mem->data,
616 .capacity = value_size + extra_sz
617 };
618
619 offset_index offidx;
620 order_index ordidx;
621
622 as_pack_map_header(&pk, map.ele_count + 1);
623 as_pack_ext_header(&pk, ext_content_sz,
624 map_adjust_incoming_flags(map.flags));
625
626 uint32_t hdr_sz = pk.offset + ext_content_sz + 1; // 1 for NIL
627
628 packed_map_init_indexes(&map, &pk, &offidx, &ordidx);
629 as_pack_val(&pk, &as_nil);
630 memcpy(pk.buffer + pk.offset, map.contents, map.content_sz);
631 p_map_mem->sz = map.content_sz + hdr_sz;
632
633 if (! offset_index_check_order_and_fill(&offidx, true)) {
634 cf_warning(AS_PARTICLE, "map_from_wire() invalid packed map");
635 return -AS_ERR_PARAMETER;
636 }
637
638#ifdef MAP_DEBUG_VERIFY
639 {
640 as_bin b;
641 b.particle = *pp;
642 as_bin_state_set_from_type(&b, AS_PARTICLE_TYPE_MAP);
643
644 const cdt_context ctx = {
645 .b = &b,
646 .orig = b.particle,
647 };
648
649 if (! map_verify(&ctx)) {
650 offset_index_print(&map.offidx, "verify");
651 cf_crash(AS_PARTICLE, "map_from_wire: pp=%p wire_value=%p", pp, wire_value);
652 }
653 }
654#endif
655
656 return AS_OK;
657}
658
659int
660map_compare_from_wire(const as_particle *p, as_particle_type wire_type,
661 const uint8_t *wire_value, uint32_t value_size)
662{
663 cf_warning(AS_PARTICLE, "map_compare_from_wire() not implemented");
664 return -AS_ERR_INCOMPATIBLE_TYPE;
665}
666
667uint32_t
668map_wire_size(const as_particle *p)
669{
670 packed_map map;
671
672 if (! packed_map_init_from_particle(&map, p, false)) {
673 cf_crash(AS_PARTICLE, "map_wire_size() invalid packed map");
674 }
675
676 if (map.flags == 0) {
677 return map.packed_sz;
678 }
679
680 uint32_t sz = map.content_sz;
681 sz += as_pack_list_header_get_size(map.ele_count + 1);
682 sz += 3 + 1; // 3 for min ext hdr and 1 for nil pair
683
684 return sz;
685}
686
687uint32_t
688map_to_wire(const as_particle *p, uint8_t *wire)
689{
690 return map_particle_strip_indexes(p, wire);
691}
692
693//------------------------------------------------
694// Handle as_val translation.
695//
696
697uint32_t
698map_size_from_asval(const as_val *val)
699{
700 as_serializer s;
701 as_msgpack_init(&s);
702
703 uint32_t sz = as_serializer_serialize_getsize(&s, (as_val *)val);
704
705 as_serializer_destroy(&s);
706
707 const as_map *map = (const as_map *)val;
708
709 if (map->flags == 0) {
710 return (uint32_t)sizeof(map_mem) + sz;
711 }
712
713 uint32_t ele_count = as_map_size(map);
714 uint32_t map_hdr_sz = as_pack_list_header_get_size(ele_count);
715 uint32_t content_sz = sz - map_hdr_sz;
716 uint32_t ext_content_sz = map_calc_ext_content_sz(map->flags, ele_count,
717 content_sz);
718
719 sz = (uint32_t)sizeof(map_mem);
720 sz += as_pack_list_header_get_size(ele_count + 1) + content_sz;
721 sz += as_pack_ext_header_get_size(ext_content_sz); // ext header and length field
722 sz += ext_content_sz; // ext content
723 sz++; // nil pair
724
725 return (uint32_t)sizeof(map_mem) + sz;
726}
727
728void
729map_from_asval(const as_val *val, as_particle **pp)
730{
731 map_mem *p_map_mem = (map_mem *)*pp;
732 const as_map *av_map = (const as_map *)val;
733
734 p_map_mem->type = AS_PARTICLE_TYPE_MAP;
735
736 as_serializer s;
737 as_msgpack_init(&s);
738
739 int32_t sz = as_serializer_serialize_presized(&s, val, p_map_mem->data);
740
741 cf_assert(sz >= 0, AS_PARTICLE, "map_from_asval() failed to presize");
742 as_serializer_destroy(&s);
743
744 if (av_map->flags == 0) {
745 p_map_mem->sz = (uint32_t)sz;
746 return;
747 }
748
749 uint8_t *temp_mem = NULL;
750 uint8_t buf[sizeof(packed_map) + (sz < CDT_MAX_STACK_OBJ_SZ ? sz : 0)];
751 packed_map *map = (packed_map *)buf;
752 bool success;
753
754 if (sz < CDT_MAX_STACK_OBJ_SZ) {
755 memcpy(buf + sizeof(packed_map), p_map_mem->data, sz);
756 success = packed_map_init(map, buf + sizeof(packed_map), sz, false);
757 }
758 else {
759 temp_mem = cf_malloc(sz);
760 memcpy(temp_mem, p_map_mem->data, sz);
761 success = packed_map_init(map, temp_mem, sz, false);
762 }
763
764 cf_assert(success, AS_PARTICLE, "map_from_asval() failed to unpack header");
765
766 uint8_t map_flags = map_adjust_incoming_flags(av_map->flags);
767 define_map_packer(mpk, map->ele_count, map_flags, map->content_sz);
768 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp indexes
769
770 mpk.write_ptr = p_map_mem->data;
771 map_packer_write_hdridx(&mpk);
772
773 setup_map_must_have_offidx(old, map, alloc_idx);
774 bool check = packed_map_check_and_fill_offidx(map);
775 cf_assert(check, AS_PARTICLE, "invalid map");
776
777 packed_map_write_k_ordered(map, mpk.write_ptr, &mpk.offidx);
778
779 p_map_mem->sz =
780 (uint32_t)(mpk.contents - p_map_mem->data + map->content_sz);
781
782 if (! order_index_is_null(&mpk.ordidx)) {
783 order_index_set(&mpk.ordidx, 0, map->ele_count);
784 }
785
786 cf_free(temp_mem);
787 rollback_alloc_rollback(alloc_idx);
788
789#ifdef MAP_DEBUG_VERIFY
790 {
791 as_bin b;
792 b.particle = (as_particle *)p_map_mem;
793 as_bin_state_set_from_type(&b, AS_PARTICLE_TYPE_MAP);
794
795 const cdt_context ctx = {
796 .b = &b,
797 .orig = b.particle,
798 };
799
800 if (! map_verify(&ctx)) {
801 cdt_bin_print(&b, "map_from_asval");
802 cf_crash(AS_PARTICLE, "map_from_asval: ele_count %u", map->ele_count);
803 }
804 }
805#endif
806}
807
808as_val *
809map_to_asval(const as_particle *p)
810{
811 map_mem *p_map_mem = (map_mem *)p;
812
813 as_buffer buf = {
814 .capacity = p_map_mem->sz,
815 .size = p_map_mem->sz,
816 .data = p_map_mem->data
817 };
818
819 as_serializer s;
820 as_msgpack_init(&s);
821
822 as_val *val = NULL;
823
824 as_serializer_deserialize(&s, &buf, &val);
825 as_serializer_destroy(&s);
826
827 if (! val) {
828 return (as_val *)as_hashmap_new(0);
829 }
830
831 packed_map map;
832
833 packed_map_init_from_particle(&map, p, false);
834 ((as_map *)val)->flags = (uint32_t)map.flags;
835
836 return val;
837}
838
839uint32_t
840map_asval_wire_size(const as_val *val)
841{
842 as_serializer s;
843 as_msgpack_init(&s);
844
845 uint32_t sz = as_serializer_serialize_getsize(&s, (as_val *)val);
846
847 as_serializer_destroy(&s);
848
849 return sz;
850}
851
852uint32_t
853map_asval_to_wire(const as_val *val, uint8_t *wire)
854{
855 as_serializer s;
856 as_msgpack_init(&s);
857
858 int32_t sz = as_serializer_serialize_presized(&s, val, wire);
859
860 as_serializer_destroy(&s);
861 cf_assert(sz > 0, AS_PARTICLE, "map_asval_to_wire() sz %d failed to serialize", sz);
862
863 return (uint32_t)sz;
864}
865
866//------------------------------------------------
867// Handle msgpack translation.
868//
869
870uint32_t
871map_size_from_msgpack(const uint8_t *packed, uint32_t packed_size)
872{
873 return (uint32_t)sizeof(map_mem) + packed_size;
874}
875
876void
877map_from_msgpack(const uint8_t *packed, uint32_t packed_size, as_particle **pp)
878{
879 map_mem *p_map_mem = (map_mem *)*pp;
880
881 p_map_mem->type = AS_PARTICLE_TYPE_MAP;
882 p_map_mem->sz = packed_size;
883 memcpy(p_map_mem->data, packed, p_map_mem->sz);
884}
885
886//------------------------------------------------
887// Handle on-device "flat" format.
888//
889
890const uint8_t *
891map_from_flat(const uint8_t *flat, const uint8_t *end, as_particle **pp)
892{
893 if (flat + sizeof(map_flat) > end) {
894 cf_warning(AS_PARTICLE, "incomplete flat map");
895 return NULL;
896 }
897
898 const map_flat *p_map_flat = (const map_flat *)flat;
899
900 flat += sizeof(map_flat) + p_map_flat->sz;
901
902 if (flat > end) {
903 cf_warning(AS_PARTICLE, "incomplete flat map");
904 return NULL;
905 }
906
907 packed_map map;
908
909 if (! packed_map_init(&map, p_map_flat->data, p_map_flat->sz, false)) {
910 cf_warning(AS_PARTICLE, "map_from_flat() invalid packed map");
911 return NULL;
912 }
913
914 uint8_t flags = map_adjust_incoming_flags(map.flags);
915 define_map_packer(mpk, map.ele_count, flags, map.content_sz);
916 as_particle *p = map_packer_create_particle(&mpk, NULL);
917
918 map_packer_write_hdridx(&mpk);
919 memcpy(mpk.write_ptr, map.contents, map.content_sz);
920
921 if (! offset_index_is_null(&mpk.offidx) &&
922 ! offset_index_check_order_and_fill(&mpk.offidx, true)) {
923 cf_warning(AS_PARTICLE, "map_from_flat() invalid packed map");
924 cf_free(p);
925 return NULL;
926 }
927
928 if (! order_index_is_null(&mpk.ordidx)) {
929 order_index_set_sorted(&mpk.ordidx, &mpk.offidx, map.contents,
930 map.content_sz, SORT_BY_VALUE);
931 }
932
933 *pp = p;
934
935 return flat;
936}
937
938uint32_t
939map_flat_size(const as_particle *p)
940{
941 const map_mem *p_map_mem = (const map_mem *)p;
942
943 packed_map map;
944
945 if (! packed_map_init_from_particle(&map, p, false)) {
946 const as_bin b = {
947 .particle = (as_particle *)p
948 };
949
950 cdt_bin_print(&b, "map");
951 cf_crash(AS_PARTICLE, "map_flat_size() invalid packed map");
952 }
953
954 if (map.flags == 0) {
955 return sizeof(map_flat) + p_map_mem->sz;
956 }
957
958 uint32_t sz = map.content_sz;
959 sz += as_pack_list_header_get_size(map.ele_count + 1);
960 sz += 3 + 1; // 3 for min ext hdr and 1 for nil pair
961
962 return (uint32_t)sizeof(map_flat) + sz;
963}
964
965uint32_t
966map_to_flat(const as_particle *p, uint8_t *flat)
967{
968 map_flat *p_map_flat = (map_flat *)flat;
969
970 p_map_flat->sz = map_particle_strip_indexes(p, p_map_flat->data);
971
972 // Already wrote the type.
973
974 return sizeof(map_flat) + p_map_flat->sz;
975}
976
977
978//==========================================================
979// Global API.
980//
981
982void
983as_bin_set_empty_packed_map(as_bin *b, rollback_alloc *alloc_buf, uint8_t flags)
984{
985 b->particle = map_particle_create(alloc_buf, 0, NULL, 0, flags);
986 as_bin_state_set_from_type(b, AS_PARTICLE_TYPE_MAP);
987}
988
989bool
990map_subcontext_by_index(cdt_context *ctx, as_unpacker *val)
991{
992 int64_t index;
993 packed_map map;
994 uint32_t uindex;
995 uint32_t count32;
996
997 if (as_unpack_int64(val, &index) != 0) {
998 cf_warning(AS_PARTICLE, "map_subcontext_by_index() invalid subcontext");
999 return false;
1000 }
1001
1002 if (! packed_map_init_from_ctx(&map, ctx, false)) {
1003 cf_warning(AS_PARTICLE, "map_subcontext_by_index() invalid packed map");
1004 return false;
1005 }
1006
1007 if (! calc_index_count(index, 1, map.ele_count, &uindex, &count32,
1008 false)) {
1009 cf_warning(AS_PARTICLE, "map_subcontext_by_index() index %ld out of bounds for ele_count %u", index, map.ele_count);
1010 return false;
1011 }
1012
1013 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp idx
1014 setup_map_must_have_offidx(u, &map, alloc_idx);
1015
1016 if (! packed_map_check_and_fill_offidx(&map)) {
1017 cf_warning(AS_PARTICLE, "map_subcontext_by_index() invalid packed map");
1018 rollback_alloc_rollback(alloc_idx);
1019 return false;
1020 }
1021
1022 uint32_t idx = uindex;
1023
1024 if (! map_is_k_ordered(&map)) {
1025 define_build_order_heap_by_range(heap, uindex, count32, map.ele_count,
1026 &map, packed_map_compare_key_by_idx, success, alloc_idx);
1027
1028 if (! success) {
1029 cf_warning(AS_PARTICLE, "map_subcontext_by_index() invalid packed map");
1030 rollback_alloc_rollback(alloc_idx);
1031 return false;
1032 }
1033
1034 idx = order_index_get(&heap._, heap.filled);
1035 }
1036 else {
1037 cdt_context_map_push(ctx, &map, idx);
1038 }
1039
1040 cdt_context_set_by_map_idx(ctx, &map, idx);
1041 rollback_alloc_rollback(alloc_idx);
1042
1043 return true;
1044}
1045
1046bool
1047map_subcontext_by_rank(cdt_context *ctx, as_unpacker *val)
1048{
1049 int64_t rank;
1050 packed_map map;
1051 uint32_t urank;
1052 uint32_t count32;
1053
1054 if (as_unpack_int64(val, &rank) != 0) {
1055 cf_warning(AS_PARTICLE, "map_subcontext_by_rank() invalid subcontext");
1056 return false;
1057 }
1058
1059 if (! packed_map_init_from_ctx(&map, ctx, false)) {
1060 cf_warning(AS_PARTICLE, "map_subcontext_by_rank() invalid packed map");
1061 return false;
1062 }
1063
1064 if (! calc_index_count(rank, 1, map.ele_count, &urank, &count32, false)) {
1065 cf_warning(AS_PARTICLE, "map_subcontext_by_rank() rank %ld out of bounds for ele_count %u", rank, map.ele_count);
1066 return false;
1067 }
1068
1069 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp idx
1070 setup_map_must_have_offidx(u, &map, alloc_idx);
1071 const order_index *ordidx = &map.ordidx;
1072
1073 if (! packed_map_check_and_fill_offidx(&map)) {
1074 cf_warning(AS_PARTICLE, "map_subcontext_by_rank() invalid packed map");
1075 rollback_alloc_rollback(alloc_idx);
1076 return false;
1077 }
1078
1079 uint32_t idx;
1080
1081 if (order_index_is_valid(ordidx)) {
1082 packed_map_ensure_ordidx_filled(&map);
1083 idx = order_index_get(ordidx, urank);
1084 }
1085 else {
1086 define_build_order_heap_by_range(heap, urank, count32, map.ele_count,
1087 &map, packed_map_compare_value_by_idx, success, alloc_idx);
1088
1089 if (! success) {
1090 cf_warning(AS_PARTICLE, "map_subcontext_by_rank() invalid packed map");
1091 rollback_alloc_rollback(alloc_idx);
1092 return false;
1093 }
1094
1095 idx = order_index_get(&heap._, heap.filled);
1096 }
1097
1098 cdt_context_map_push(ctx, &map, idx);
1099 cdt_context_set_by_map_idx(ctx, &map, idx);
1100 rollback_alloc_rollback(alloc_idx);
1101
1102 return true;
1103}
1104
1105bool
1106map_subcontext_by_key(cdt_context *ctx, as_unpacker *val)
1107{
1108 cdt_payload key;
1109 packed_map map;
1110
1111 key.ptr = val->buffer + val->offset;
1112
1113 int64_t key_sz = as_unpack_size(val);
1114
1115 if (key_sz <= 0) {
1116 cf_warning(AS_PARTICLE, "map_subcontext_by_key() invalid subcontext");
1117 return false;
1118 }
1119
1120 key.sz = (uint32_t)key_sz;
1121
1122 if (! packed_map_init_from_ctx(&map, ctx, false)) {
1123 cf_warning(AS_PARTICLE, "map_subcontext_by_key() invalid packed map");
1124 return false;
1125 }
1126
1127 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp idx
1128 setup_map_must_have_offidx(u, &map, alloc_idx);
1129 uint32_t index = 0;
1130 uint32_t count = 0;
1131 uint32_t hdr_sz = map.packed_sz - map.content_sz;
1132
1133 if (! packed_map_check_and_fill_offidx(&map)) {
1134 cf_warning(AS_PARTICLE, "map_subcontext_by_key() invalid packed map");
1135 rollback_alloc_rollback(alloc_idx);
1136 return false;
1137 }
1138
1139 if (map_is_k_ordered(&map)) {
1140 packed_map_get_range_by_key_interval_ordered(&map, &key, &key, &index,
1141 &count);
1142
1143 if (count == 0) {
1144 cf_warning(AS_PARTICLE, "map_subcontext_by_key() key not found");
1145 rollback_alloc_rollback(alloc_idx);
1146 return false;
1147 }
1148
1149 cdt_context_map_push(ctx, &map, index);
1150 cdt_context_set_by_map_idx(ctx, &map, index);
1151 }
1152 else {
1153 map_ele_find find_key;
1154
1155 map_ele_find_init(&find_key, &map);
1156 packed_map_find_key(&map, &find_key, &key);
1157
1158 if (! find_key.found_key) {
1159 cf_warning(AS_PARTICLE, "map_subcontext_by_key() key not found");
1160 rollback_alloc_rollback(alloc_idx);
1161 return false;
1162 }
1163
1164 ctx->data_offset += hdr_sz + find_key.value_offset;
1165 ctx->data_sz = find_key.sz -
1166 (find_key.value_offset - find_key.key_offset);
1167 }
1168
1169 rollback_alloc_rollback(alloc_idx);
1170
1171 return true;
1172}
1173
1174bool
1175map_subcontext_by_value(cdt_context *ctx, as_unpacker *val)
1176{
1177 cdt_payload value;
1178 packed_map map;
1179
1180 value.ptr = val->buffer + val->offset;
1181
1182 int64_t value_sz = as_unpack_size(val);
1183
1184 if (value_sz <= 0) {
1185 cf_warning(AS_PARTICLE, "map_subcontext_by_value() invalid subcontext");
1186 return false;
1187 }
1188
1189 value.sz = (uint32_t)value_sz;
1190
1191 if (! packed_map_init_from_ctx(&map, ctx, false)) {
1192 cf_warning(AS_PARTICLE, "map_subcontext_by_value() invalid packed map");
1193 return false;
1194 }
1195
1196 if (map.ele_count == 0) {
1197 cf_warning(AS_PARTICLE, "map_subcontext_by_value() map is empty");
1198 return false;
1199 }
1200
1201 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp idx
1202 setup_map_must_have_offidx(u, &map, alloc_idx);
1203
1204 if (! packed_map_check_and_fill_offidx(&map)) {
1205 cf_warning(AS_PARTICLE, "map_subcontext_by_value() invalid packed map");
1206 return false;
1207 }
1208
1209 uint32_t rank = 0;
1210 uint32_t count = 0;
1211 uint32_t idx;
1212
1213 if (order_index_is_valid(&map.ordidx)) {
1214 packed_map_ensure_ordidx_filled(&map);
1215 packed_map_find_rank_range_by_value_interval_indexed(&map, &value,
1216 &value, &rank, &count, false);
1217
1218 idx = order_index_get(&map.ordidx, rank);
1219 }
1220 else {
1221 uint64_t idx64;
1222
1223 packed_map_find_rank_range_by_value_interval_unordered(&map, &value,
1224 &value, &rank, &count, &idx64, false);
1225 idx = (uint32_t)idx64;
1226 }
1227
1228 if (count == 0) {
1229 cf_warning(AS_PARTICLE, "map_subcontext_by_value() value not found");
1230 rollback_alloc_rollback(alloc_idx);
1231 return false;
1232 }
1233
1234 cdt_context_map_push(ctx, &map, idx);
1235 cdt_context_set_by_map_idx(ctx, &map, idx);
1236 rollback_alloc_rollback(alloc_idx);
1237
1238 return true;
1239}
1240
1241void
1242cdt_context_unwind_map(cdt_context *ctx, cdt_ctx_list_stack_entry *p)
1243{
1244 packed_map map;
1245 packed_map orig;
1246
1247 packed_map_init_from_ctx(&map, ctx, false);
1248 packed_map_init_from_particle(&orig, ctx->orig, false);
1249
1250 offset_index_move_ele(&map.offidx, &orig.offidx, p->idx, p->idx);
1251
1252 if (! is_kv_ordered(orig.flags)) {
1253 return;
1254 }
1255
1256 if (! order_index_is_filled(&orig.ordidx)) { // no prior order index
1257 order_index_set_sorted(&map.ordidx, &map.offidx, map.contents,
1258 map.content_sz, SORT_BY_VALUE);
1259 return;
1260 }
1261
1262 uint32_t off = offset_index_get_const(&map.offidx, p->idx);
1263
1264 msgpack_in mp = {
1265 .buf = map.contents,
1266 .buf_sz = map.content_sz,
1267 .offset = off
1268 };
1269
1270 uint32_t check = msgpack_sz(&mp); // skip key
1271 cf_assert(check != 0, AS_PARTICLE, "invalid msgpack");
1272
1273 cdt_payload v = {
1274 .ptr = mp.buf + mp.offset,
1275 .sz = mp.buf_sz - mp.offset
1276 };
1277
1278 order_index_find find = {
1279 .target = p->idx,
1280 .count = map.ele_count
1281 };
1282
1283 order_index_find_rank_by_value(&orig.ordidx, &v, &orig.offidx, &find, true);
1284
1285 uint32_t add_rank = find.result;
1286 uint32_t rm_rank = order_index_find_idx(&orig.ordidx, p->idx, 0,
1287 orig.ele_count);
1288
1289 if (add_rank == rm_rank || add_rank == rm_rank + 1) {
1290 return;
1291 }
1292
1293 order_index_op_replace1(&map.ordidx, &orig.ordidx, add_rank, rm_rank);
1294}
1295
1296
1297//==========================================================
1298// Local helpers.
1299//
1300
1301static inline bool
1302is_map_type(uint8_t type)
1303{
1304 return type == AS_PARTICLE_TYPE_MAP;
1305}
1306
1307static inline bool
1308is_k_ordered(uint8_t flags)
1309{
1310 return flags & AS_PACKED_MAP_FLAG_K_ORDERED;
1311}
1312
1313static inline bool
1314is_kv_ordered(uint8_t flags)
1315{
1316 return (flags & AS_PACKED_MAP_FLAG_KV_ORDERED) ==
1317 AS_PACKED_MAP_FLAG_KV_ORDERED;
1318}
1319
1320static uint32_t
1321map_calc_ext_content_sz(uint8_t flags, uint32_t ele_count, uint32_t content_sz)
1322{
1323 uint32_t sz = 0;
1324
1325 if (is_k_ordered(flags)) {
1326 offset_index offidx;
1327
1328 offset_index_init(&offidx, NULL, ele_count, NULL, content_sz);
1329 sz += offset_index_size(&offidx);
1330 }
1331
1332 if (is_kv_ordered(flags)) {
1333 order_index ordidx;
1334
1335 order_index_init(&ordidx, NULL, ele_count);
1336
1337 if (ele_count > 1) {
1338 sz += order_index_size(&ordidx);
1339 }
1340 }
1341
1342 return sz;
1343}
1344
1345static uint8_t
1346map_adjust_incoming_flags(uint8_t flags)
1347{
1348 static const uint8_t mask = AS_PACKED_MAP_FLAG_KV_ORDERED |
1349 AS_PACKED_MAP_FLAG_OFF_IDX | AS_PACKED_MAP_FLAG_ORD_IDX;
1350
1351 if (is_k_ordered(flags)) {
1352 flags |= AS_PACKED_MAP_FLAG_OFF_IDX;
1353 }
1354
1355 if (is_kv_ordered(flags)) {
1356 flags |= AS_PACKED_MAP_FLAG_ORD_IDX;
1357 }
1358
1359 return flags & mask;
1360}
1361
1362static inline uint32_t
1363map_allidx_vla_sz(const packed_map *map)
1364{
1365 uint32_t sz = 0;
1366
1367 if (! offset_index_is_valid(&map->offidx)) {
1368 sz = offset_index_size(&map->offidx) +
1369 order_index_size(&map->ordidx);
1370 }
1371 else if (! order_index_is_valid(&map->ordidx)) {
1372 sz = order_index_size(&map->ordidx);
1373 }
1374
1375 return cdt_vla_sz(sz);
1376}
1377
1378static inline void
1379map_allidx_alloc_temp(const packed_map *map, uint8_t *mem_temp,
1380 rollback_alloc *alloc)
1381{
1382 offset_index *offidx = (offset_index *)&map->offidx;
1383 order_index *ordidx = (order_index *)&map->ordidx;
1384
1385 if (! offset_index_is_valid(offidx)) {
1386 uint32_t off_sz = offset_index_size(offidx);
1387 uint32_t ord_sz = order_index_size(ordidx);
1388
1389 if (off_sz + ord_sz > CDT_MAX_STACK_OBJ_SZ) {
1390 offidx->_.ptr = rollback_alloc_reserve(alloc, off_sz);
1391 ordidx->_.ptr = rollback_alloc_reserve(alloc, ord_sz);
1392 }
1393 else {
1394 offidx->_.ptr = mem_temp;
1395 ordidx->_.ptr = mem_temp + offset_index_size(offidx);
1396 }
1397
1398 offset_index_set_filled(offidx, 1);
1399 order_index_set(ordidx, 0, map->ele_count);
1400 }
1401 else if (! order_index_is_valid(ordidx)) {
1402 uint32_t ord_sz = order_index_size(ordidx);
1403
1404 if (ord_sz > CDT_MAX_STACK_OBJ_SZ) {
1405 ordidx->_.ptr = rollback_alloc_reserve(alloc, ord_sz);
1406 }
1407 else {
1408 ordidx->_.ptr = mem_temp;
1409 }
1410
1411 order_index_set(ordidx, 0, map->ele_count);
1412 }
1413}
1414
1415static inline uint32_t
1416map_ext_content_sz(const packed_map *map)
1417{
1418 return map_calc_ext_content_sz(map->flags, map->ele_count, map->content_sz);
1419}
1420
1421static inline bool
1422map_is_k_ordered(const packed_map *map)
1423{
1424 return is_k_ordered(map->flags);
1425}
1426
1427static inline bool
1428map_is_kv_ordered(const packed_map *map)
1429{
1430 return is_kv_ordered(map->flags);
1431}
1432
1433static inline bool
1434map_has_offidx(const packed_map *map)
1435{
1436 return offset_index_is_valid(&map->offidx);
1437}
1438
1439//------------------------------------------------
1440// cdt_context
1441//
1442
1443static inline void
1444cdt_context_use_static_map_if_notinuse(cdt_context *ctx, uint8_t flags)
1445{
1446 if (! as_bin_inuse(ctx->b)) {
1447 if (is_kv_ordered(flags)) {
1448 ctx->b->particle = (as_particle *)&map_mem_empty_kv;
1449 }
1450 else if (is_k_ordered(flags)) {
1451 ctx->b->particle = (as_particle *)&map_mem_empty_k;
1452 }
1453 else {
1454 ctx->b->particle = (as_particle *)&map_mem_empty;
1455 }
1456
1457 as_bin_state_set_from_type(ctx->b, AS_PARTICLE_TYPE_MAP);
1458 }
1459}
1460
1461static inline void
1462cdt_context_set_empty_packed_map(cdt_context *ctx, uint8_t flags)
1463{
1464 if (ctx->data_sz == 0) {
1465 as_bin_set_empty_packed_map(ctx->b, ctx->alloc_buf, flags);
1466 return;
1467 }
1468
1469 define_map_packer(mpk, 0, flags, 0);
1470
1471 map_packer_create_particle_ctx(&mpk, ctx);
1472 map_packer_write_hdridx(&mpk);
1473}
1474
1475static inline void
1476cdt_context_set_by_map_idx(cdt_context *ctx, const packed_map *map,
1477 uint32_t idx)
1478{
1479 msgpack_in mp = {
1480 .buf = map->contents,
1481 .buf_sz = map->content_sz,
1482 .offset = offset_index_get_const(&map->offidx, idx)
1483 };
1484
1485 uint32_t endoff = offset_index_get_const(&map->offidx, idx + 1);
1486
1487 msgpack_sz(&mp);
1488 ctx->data_offset += map->packed_sz - map->content_sz + mp.offset;
1489 ctx->data_sz = endoff - mp.offset;
1490}
1491
1492static inline void
1493cdt_context_map_push(cdt_context *ctx, const packed_map *map, uint32_t idx)
1494{
1495 if (cdt_context_is_modify(ctx) && cdt_context_is_toplvl(ctx) &&
1496 map->ele_count > 1 &&
1497 (map->flags & AS_PACKED_MAP_FLAG_OFF_IDX) != 0) {
1498 cdt_context_push(ctx, idx, NULL)->type = AS_MAP;
1499
1500 ctx->top_content_sz = map->content_sz;
1501 ctx->top_content_off = map->contents - map->packed;
1502 ctx->top_ele_count = map->ele_count;
1503 }
1504}
1505
1506//------------------------------------------------
1507// map_packer
1508
1509static as_particle *
1510map_packer_create_particle(map_packer *mpk, rollback_alloc *alloc_buf)
1511{
1512 uint32_t sz = mpk->ext_sz + mpk->content_sz +
1513 as_pack_map_header_get_size(mpk->ele_count + (mpk->flags ? 1 : 0));
1514 map_mem *p_map_mem = (map_mem *)(alloc_buf != NULL ?
1515 rollback_alloc_reserve(alloc_buf, sizeof(map_mem) + sz) :
1516 cf_malloc_ns(sizeof(map_mem) + sz));
1517
1518 p_map_mem->type = AS_PARTICLE_TYPE_MAP;
1519 p_map_mem->sz = sz;
1520 mpk->write_ptr = p_map_mem->data;
1521
1522 return (as_particle *)p_map_mem;
1523}
1524
1525static void
1526map_packer_create_particle_ctx(map_packer *mpk, cdt_context *ctx)
1527{
1528 if (ctx->data_sz == 0) {
1529 ctx->b->particle = map_packer_create_particle(mpk, ctx->alloc_buf);
1530 return;
1531 }
1532
1533 uint32_t map_sz = mpk->ext_sz + mpk->content_sz +
1534 as_pack_map_header_get_size(mpk->ele_count + (mpk->flags ? 1 : 0));
1535 mpk->write_ptr = cdt_context_create_new_particle(ctx, map_sz);
1536 mpk->ext_content_sz = 0; // no indexes for non-top context levels
1537 mpk->flags &= ~(AS_PACKED_MAP_FLAG_OFF_IDX | AS_PACKED_MAP_FLAG_ORD_IDX);
1538}
1539
1540static void
1541map_packer_init(map_packer *mpk, uint32_t ele_count, uint8_t flags,
1542 uint32_t content_sz)
1543{
1544 mpk->ele_count = ele_count;
1545 mpk->content_sz = content_sz;
1546 mpk->ext_content_sz = 0;
1547
1548 offset_index_init(&mpk->offidx, NULL, ele_count, NULL, content_sz);
1549
1550 if (flags & AS_PACKED_MAP_FLAG_OFF_IDX) {
1551 mpk->ext_content_sz += offset_index_size(&mpk->offidx);
1552 }
1553
1554 order_index_init(&mpk->ordidx, NULL, ele_count);
1555
1556 if ((flags & AS_PACKED_MAP_FLAG_ORD_IDX) != 0 && ele_count > 1) {
1557 mpk->ext_content_sz += order_index_size(&mpk->ordidx);
1558 }
1559
1560 mpk->flags = flags;
1561
1562 if (flags == AS_PACKED_MAP_FLAG_NONE) {
1563 mpk->ext_header_sz = 0;
1564 mpk->ext_sz = 0;
1565 }
1566 else {
1567 mpk->ext_header_sz = as_pack_ext_header_get_size(mpk->ext_content_sz);
1568 mpk->ext_sz = mpk->ext_header_sz + mpk->ext_content_sz + 1; // +1 for packed nil
1569 }
1570
1571 mpk->write_ptr = NULL;
1572 mpk->contents = NULL;
1573}
1574
1575static void
1576map_packer_setup_bin(map_packer *mpk, cdt_op_mem *com)
1577{
1578 map_packer_create_particle_ctx(mpk, &com->ctx);
1579 map_packer_write_hdridx(mpk);
1580}
1581
1582static void
1583map_packer_write_hdridx(map_packer *mpk)
1584{
1585 as_packer write = {
1586 .buffer = mpk->write_ptr,
1587 .capacity = INT_MAX
1588 };
1589
1590 as_pack_map_header(&write, mpk->ele_count +
1591 (mpk->flags == AS_PACKED_MAP_FLAG_NONE ? 0 : 1));
1592
1593 if (mpk->flags == AS_PACKED_MAP_FLAG_NONE) {
1594 mpk->write_ptr += write.offset;
1595 mpk->contents = mpk->write_ptr;
1596 mpk->offidx.contents = mpk->contents;
1597 return;
1598 }
1599
1600 as_pack_ext_header(&write, mpk->ext_content_sz, mpk->flags);
1601
1602 if (mpk->ext_content_sz > 0) {
1603 uint8_t *ptr = mpk->write_ptr + write.offset;
1604 uint32_t index_sz_left = mpk->ext_content_sz;
1605 uint32_t sz = offset_index_size(&mpk->offidx);
1606
1607 if ((mpk->flags & AS_PACKED_MAP_FLAG_OFF_IDX) && index_sz_left >= sz &&
1608 sz != 0) {
1609 offset_index_set_ptr(&mpk->offidx, ptr,
1610 ptr + mpk->ext_content_sz + 1); // +1 for nil pair
1611 ptr += sz;
1612 index_sz_left -= sz;
1613 offset_index_set_filled(&mpk->offidx, 1);
1614 }
1615
1616 sz = order_index_size(&mpk->ordidx);
1617
1618 if ((mpk->flags & AS_PACKED_MAP_FLAG_ORD_IDX) && index_sz_left >= sz &&
1619 sz != 0 && mpk->ele_count > 1) {
1620 order_index_set_ptr(&mpk->ordidx, ptr);
1621 order_index_set(&mpk->ordidx, 0, mpk->ele_count);
1622 }
1623 }
1624
1625 // Pack nil.
1626 write.offset += mpk->ext_content_sz;
1627 write.buffer[write.offset++] = msgpack_nil[0];
1628
1629 mpk->write_ptr += write.offset;
1630 mpk->contents = mpk->write_ptr;
1631 mpk->offidx.contents = mpk->contents;
1632}
1633
1634static void
1635map_packer_fill_offset_index(map_packer *mpk)
1636{
1637 cf_assert(offset_index_is_valid(&mpk->offidx), AS_PARTICLE, "invalid offidx");
1638 offset_index_set_filled(&mpk->offidx, 1);
1639
1640 bool check = map_offset_index_check_and_fill(&mpk->offidx, mpk->ele_count);
1641 cf_assert(check, AS_PARTICLE, "invalid offidx");
1642}
1643
1644// qsort_r callback function.
1645static int
1646map_packer_fill_index_sort_compare(const void *x, const void *y, void *p)
1647{
1648 index_sort_userdata *udata = (index_sort_userdata *)p;
1649 order_index *ordidx = udata->order;
1650 uint32_t x_idx = order_index_ptr2value(ordidx, x);
1651 uint32_t y_idx = order_index_ptr2value(ordidx, y);
1652 const offset_index *offidx = udata->offsets;
1653 const uint8_t *contents = udata->contents;
1654 uint32_t content_sz = udata->content_sz;
1655 uint32_t x_off = offset_index_get_const(offidx, x_idx);
1656 uint32_t y_off = offset_index_get_const(offidx, y_idx);
1657
1658 msgpack_in x_pk = {
1659 .buf = contents,
1660 .buf_sz = content_sz,
1661 .offset = x_off
1662 };
1663
1664 msgpack_in y_pk = {
1665 .buf = contents,
1666 .buf_sz = content_sz,
1667 .offset = y_off
1668 };
1669
1670 msgpack_compare_t cmp;
1671
1672 if (udata->sort_by == SORT_BY_VALUE) {
1673 // Skip keys.
1674 if (msgpack_sz(&x_pk) == 0) {
1675 cf_crash(AS_PARTICLE, "invalid msgpack");
1676 }
1677
1678 if (msgpack_sz(&y_pk) == 0) {
1679 cf_crash(AS_PARTICLE, "invalid msgpack");
1680 }
1681
1682 cmp = msgpack_cmp_peek(&x_pk, &y_pk);
1683 }
1684 else if ((cmp = msgpack_cmp(&x_pk, &y_pk)) == MSGPACK_COMPARE_EQUAL) {
1685 cmp = msgpack_cmp_peek(&x_pk, &y_pk);
1686 }
1687
1688 if (cmp == MSGPACK_COMPARE_LESS) {
1689 return -1;
1690 }
1691
1692 if (cmp == MSGPACK_COMPARE_GREATER) {
1693 return 1;
1694 }
1695
1696 return 0;
1697}
1698
1699static void
1700map_packer_fill_ordidx(map_packer *mpk, const uint8_t *contents,
1701 uint32_t content_sz)
1702{
1703 if (order_index_is_null(&mpk->ordidx)) {
1704 return;
1705 }
1706
1707 order_index_set_sorted(&mpk->ordidx, &mpk->offidx, contents, content_sz,
1708 SORT_BY_VALUE);
1709}
1710
1711static void
1712map_packer_add_op_copy_index(map_packer *mpk, const packed_map_op *add_op,
1713 map_ele_find *remove_info, uint32_t kv_sz, const cdt_payload *value)
1714{
1715 if (add_op->new_ele_count == 0) { // no elements left
1716 return;
1717 }
1718
1719 map_ele_find add_info;
1720
1721 map_ele_find_init(&add_info, add_op->map);
1722 add_info.idx = remove_info->idx; // Find closest matching position for multiple same values.
1723
1724 if (! offset_index_is_null(&mpk->offidx)) {
1725 if (! offset_index_is_full(&add_op->map->offidx)) {
1726 map_packer_fill_offset_index(mpk);
1727 }
1728 else {
1729 packed_map_op_write_new_offidx(add_op, remove_info, &add_info,
1730 &mpk->offidx, kv_sz);
1731 }
1732 }
1733
1734 if (! order_index_is_null(&mpk->ordidx)) {
1735 if (! order_index_is_filled(&add_op->map->ordidx)) {
1736 map_packer_fill_ordidx(mpk, mpk->contents, mpk->content_sz);
1737 return;
1738 }
1739
1740 if (remove_info->found_key) {
1741 packed_map_find_rank_indexed(add_op->map, remove_info);
1742 cf_assert(remove_info->found_value, AS_PARTICLE, "map_packer_add_op_copy_index() remove_info rank not found: idx=%u found=%d ele_count=%u", remove_info->idx, remove_info->found_key, add_op->map->ele_count);
1743 }
1744
1745 packed_map_find_rank_by_value_indexed(add_op->map, &add_info, value);
1746 packed_map_op_write_new_ordidx(add_op, remove_info, &add_info,
1747 &mpk->ordidx);
1748 }
1749}
1750
1751static inline void
1752map_packer_write_seg1(map_packer *mpk, const packed_map_op *op)
1753{
1754 mpk->write_ptr = packed_map_op_write_seg1(op, mpk->write_ptr);
1755}
1756
1757static inline void
1758map_packer_write_seg2(map_packer *mpk, const packed_map_op *op)
1759{
1760 mpk->write_ptr = packed_map_op_write_seg2(op, mpk->write_ptr);
1761}
1762
1763static inline void
1764map_packer_write_msgpack_seg(map_packer *mpk, const cdt_payload *seg)
1765{
1766 memcpy(mpk->write_ptr, seg->ptr, seg->sz);
1767 mpk->write_ptr += seg->sz;
1768}
1769
1770//------------------------------------------------
1771// map_op
1772
1773static int
1774map_set_flags(cdt_op_mem *com, uint8_t set_flags)
1775{
1776 packed_map map;
1777
1778 if (! packed_map_init_from_com(&map, com, false)) {
1779 cf_warning(AS_PARTICLE, "packed_map_set_flags() invalid packed map");
1780 return -AS_ERR_PARAMETER;
1781 }
1782
1783 uint8_t map_flags = map.flags;
1784 uint32_t ele_count = map.ele_count;
1785 bool reorder = false;
1786
1787 if ((set_flags & AS_PACKED_MAP_FLAG_KV_ORDERED) ==
1788 AS_PACKED_MAP_FLAG_V_ORDERED) {
1789 cf_warning(AS_PARTICLE, "packed_map_set_flags() invalid flags 0x%x", set_flags);
1790 return -AS_ERR_OP_NOT_APPLICABLE;
1791 }
1792
1793 if (is_kv_ordered(set_flags)) {
1794 if (! is_kv_ordered(map_flags)) {
1795 if (ele_count > 1 && ! is_k_ordered(map_flags)) {
1796 reorder = true;
1797 }
1798
1799 map_flags |= AS_PACKED_MAP_FLAG_KV_ORDERED;
1800
1801 if (cdt_context_is_toplvl(&com->ctx)) {
1802 map_flags |= AS_PACKED_MAP_FLAG_OFF_IDX;
1803 map_flags |= AS_PACKED_MAP_FLAG_ORD_IDX;
1804 }
1805 }
1806 }
1807 else if (is_k_ordered(set_flags)) {
1808 if (is_kv_ordered(map_flags)) {
1809 map_flags &= ~AS_PACKED_MAP_FLAG_V_ORDERED;
1810 map_flags &= ~AS_PACKED_MAP_FLAG_ORD_IDX;
1811 }
1812 else if (! is_k_ordered(map_flags)) {
1813 if (ele_count > 1) {
1814 reorder = true;
1815 }
1816
1817 map_flags |= AS_PACKED_MAP_FLAG_K_ORDERED;
1818
1819 if (cdt_context_is_toplvl(&com->ctx)) {
1820 map_flags |= AS_PACKED_MAP_FLAG_OFF_IDX;
1821 }
1822 }
1823 }
1824 else if ((set_flags & AS_PACKED_MAP_FLAG_KV_ORDERED) == 0) {
1825 map_flags &= ~AS_PACKED_MAP_FLAG_KV_ORDERED;
1826 map_flags &= ~AS_PACKED_MAP_FLAG_OFF_IDX;
1827 map_flags &= ~AS_PACKED_MAP_FLAG_ORD_IDX;
1828 }
1829
1830 define_map_packer(mpk, ele_count, map_flags, map.content_sz);
1831
1832 map_packer_setup_bin(&mpk, com);
1833
1834 if (reorder) {
1835 setup_map_must_have_offidx(u, &map, com->alloc_idx);
1836
1837 if (! packed_map_check_and_fill_offidx(&map)) {
1838 cf_warning(AS_PARTICLE, "map_set_flags() invalid packed map");
1839 return -AS_ERR_PARAMETER;
1840 }
1841
1842 packed_map_write_k_ordered(&map, mpk.write_ptr, &mpk.offidx);
1843 }
1844 else {
1845 memcpy(mpk.write_ptr, map.contents, map.content_sz);
1846
1847 if (! offset_index_is_null(&mpk.offidx)) {
1848 setup_map_must_have_offidx(u, &map, com->alloc_idx);
1849
1850 if (! packed_map_check_and_fill_offidx(&map)) {
1851 cf_warning(AS_PARTICLE, "map_set_flags() invalid packed map");
1852 return -AS_ERR_PARAMETER;
1853 }
1854
1855 offset_index_copy(&mpk.offidx, &map.offidx, 0, 0, ele_count, 0);
1856 }
1857 }
1858
1859 if (! order_index_is_null(&mpk.ordidx)) {
1860 if (order_index_is_filled(&map.ordidx)) {
1861 order_index_copy(&mpk.ordidx, &map.ordidx, 0, 0, ele_count, NULL);
1862 }
1863 else {
1864 map_packer_fill_ordidx(&mpk, mpk.contents, mpk.content_sz);
1865 }
1866 }
1867
1868#ifdef MAP_DEBUG_VERIFY
1869 if (! map_verify(&com->ctx)) {
1870 cdt_bin_print(com->ctx.b, "packed_map_set_flags");
1871 map_print(&map, "original");
1872 cf_crash(AS_PARTICLE, "map_set_flags: ele_count %u", map.ele_count);
1873 }
1874#endif
1875
1876 return AS_OK;
1877}
1878
1879static int
1880map_increment(cdt_op_mem *com, const cdt_payload *key,
1881 const cdt_payload *delta_value, bool is_decrement)
1882{
1883 packed_map map;
1884
1885 if (! packed_map_init_from_com(&map, com, true)) {
1886 cf_warning(AS_PARTICLE, "map_increment() invalid packed map, ele_count=%u", map.ele_count);
1887 return -AS_ERR_PARAMETER;
1888 }
1889
1890 setup_map_must_have_offidx(u, &map, com->alloc_idx);
1891
1892 if (! packed_map_check_and_fill_offidx(&map)) {
1893 cf_warning(AS_PARTICLE, "map_increment() invalid packed map, ele_count=%u", map.ele_count);
1894 return -AS_ERR_PARAMETER;
1895 }
1896
1897 map_ele_find find_key;
1898 cdt_calc_delta calc_delta;
1899
1900 map_ele_find_init(&find_key, &map);
1901
1902 if (! packed_map_find_key(&map, &find_key, key)) {
1903 cf_warning(AS_PARTICLE, "map_increment() invalid packed map, ele_count=%u", map.ele_count);
1904 return -AS_ERR_PARAMETER;
1905 }
1906
1907 if (! cdt_calc_delta_init(&calc_delta, delta_value, is_decrement)) {
1908 return -AS_ERR_PARAMETER;
1909 }
1910
1911 if (find_key.found_key) {
1912 define_map_unpacker(pk_map_value, &map);
1913
1914 pk_map_value.offset = find_key.value_offset;
1915
1916 if (! cdt_calc_delta_add(&calc_delta, &pk_map_value)) {
1917 return -AS_ERR_PARAMETER;
1918 }
1919 }
1920 else {
1921 if (! cdt_calc_delta_add(&calc_delta, NULL)) {
1922 return -AS_ERR_PARAMETER;
1923 }
1924 }
1925
1926 uint8_t value_buf[CDT_MAX_PACKED_INT_SZ];
1927
1928 cdt_payload value = {
1929 .ptr = value_buf,
1930 .sz = 0
1931 };
1932
1933 cdt_calc_delta_pack_and_result(&calc_delta, &value, com->result.result);
1934
1935 map_add_control control = {
1936 .allow_overwrite = true,
1937 .allow_create = true,
1938 };
1939
1940 // TODO - possible improvement: offidx isn't saved for data-NOT-in-memory so
1941 // it will be recalculated again in map_add.
1942 return map_add(com, key, &value, &control, false);
1943}
1944
1945static int
1946map_add(cdt_op_mem *com, const cdt_payload *key, const cdt_payload *value,
1947 const map_add_control *control, bool set_result)
1948{
1949 if (! cdt_check_storage_list_contents(key->ptr, key->sz, 1) ||
1950 ! cdt_check_storage_list_contents(value->ptr, value->sz, 1)) {
1951 cf_warning(AS_PARTICLE, "map_add() invalid params");
1952 return -AS_ERR_PARAMETER;
1953 }
1954
1955 packed_map map;
1956
1957 if (! packed_map_init_from_com(&map, com, true)) {
1958 cf_warning(AS_PARTICLE, "map_add() invalid packed map, ele_count=%u", map.ele_count);
1959 return -AS_ERR_PARAMETER;
1960 }
1961
1962 setup_map_must_have_offidx(u, &map, com->alloc_idx);
1963
1964 if (! packed_map_check_and_fill_offidx(&map)) {
1965 cf_warning(AS_PARTICLE, "map_add() invalid packed map, ele_count=%u", map.ele_count);
1966 return -AS_ERR_PARAMETER;
1967 }
1968
1969 map_ele_find find_key_to_remove;
1970 map_ele_find_init(&find_key_to_remove, &map);
1971
1972 if (! packed_map_find_key(&map, &find_key_to_remove, key)) {
1973 cf_warning(AS_PARTICLE, "map_add() invalid packed map, ele_count=%u", map.ele_count);
1974 return -AS_ERR_PARAMETER;
1975 }
1976
1977 if (find_key_to_remove.found_key) {
1978 // ADD for [unique] & [key exist].
1979 if (! control->allow_overwrite) {
1980 if (control->no_fail) {
1981 if (set_result) {
1982 as_bin_set_int(com->result.result, map.ele_count);
1983 }
1984
1985 return AS_OK;
1986 }
1987
1988 return -AS_ERR_ELEMENT_EXISTS;
1989 }
1990 }
1991 else {
1992 // REPLACE for ![key exist].
1993 if (! control->allow_create) {
1994 if (control->no_fail) {
1995 if (set_result) {
1996 as_bin_set_int(com->result.result, map.ele_count);
1997 }
1998
1999 return AS_OK;
2000 }
2001
2002 return -AS_ERR_ELEMENT_NOT_FOUND;
2003 }
2004
2005 // Normal cases handled by packed_map_op_add():
2006 // ADD for (![unique] & [key exist]) or ![key exist]
2007 // PUT for all cases
2008 // REPLACE for ([unique] & [key exist])
2009 // UPDATE for ([unique] & [key exist]) or ![key exist]
2010 }
2011
2012 define_packed_map_op(op, &map);
2013 uint32_t new_sz = packed_map_op_add(&op, &find_key_to_remove);
2014 uint32_t content_sz = new_sz + key->sz + value->sz;
2015 define_map_packer(mpk, op.new_ele_count, map.flags, content_sz);
2016
2017 map_packer_setup_bin(&mpk, com);
2018
2019 map_packer_write_seg1(&mpk, &op);
2020 map_packer_write_msgpack_seg(&mpk, key);
2021 map_packer_write_msgpack_seg(&mpk, value);
2022 map_packer_write_seg2(&mpk, &op);
2023
2024 map_packer_add_op_copy_index(&mpk, &op, &find_key_to_remove,
2025 key->sz + value->sz, value);
2026
2027 if (set_result) {
2028 as_bin_set_int(com->result.result, op.new_ele_count);
2029 }
2030
2031#ifdef MAP_DEBUG_VERIFY
2032 if (! map_verify(&com->ctx)) {
2033 cdt_bin_print(com->ctx.b, "map_add");
2034 map_print(&map, "original");
2035 offset_index_print(&map.offidx, "map.offidx");
2036 order_index_print(&map.ordidx, "map.ordidx");
2037 offset_index_print(&mpk.offidx, "mpk.offidx");
2038 order_index_print(&mpk.ordidx, "mpk.ordidx");
2039 cf_crash(AS_PARTICLE, "map_add: ele_count %u no_fail %d do_partial %d allow_create %d allow_overwrite %d", map.ele_count, control->no_fail, control->do_partial, control->allow_create, control->allow_overwrite);
2040 }
2041#endif
2042
2043 return AS_OK;
2044}
2045
2046static int
2047map_add_items_unordered(const packed_map *map, cdt_op_mem *com,
2048 const offset_index *val_off, order_index *val_ord,
2049 const map_add_control *control)
2050{
2051 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
2052 define_cdt_idx_mask(found_mask, val_ord->max_idx, com->alloc_idx);
2053 uint32_t rm_count = 0;
2054 uint32_t rm_sz = 0;
2055
2056 for (uint32_t i = 0; i < map->ele_count; i++) {
2057 uint32_t offset = offset_index_get_const(&map->offidx, i);
2058
2059 cdt_payload value = {
2060 .ptr = map->contents + offset,
2061 .sz = map->content_sz - offset
2062 };
2063
2064 order_index_find find = {
2065 .count = val_ord->max_idx,
2066 .target = 0 // find first occurrence of value
2067 };
2068
2069 order_index_find_rank_by_value(val_ord, &value, val_off, &find, false);
2070
2071 if (find.found) {
2072 cdt_idx_mask_set(found_mask, find.result);
2073
2074 // ADD for [key exist].
2075 if (! control->allow_overwrite) {
2076 if (control->no_fail) {
2077 if (control->do_partial) {
2078 continue;
2079 }
2080
2081 result_data_set_int(&com->result, map->ele_count);
2082 return AS_OK;
2083 }
2084
2085 return -AS_ERR_ELEMENT_EXISTS;
2086 }
2087
2088 cdt_idx_mask_set(rm_mask, i);
2089 rm_count++;
2090 rm_sz += offset_index_get_delta_const(&map->offidx, i);
2091 }
2092 }
2093
2094 uint32_t dup_count;
2095 uint32_t dup_sz;
2096
2097 order_index_sorted_mark_dup_eles(val_ord, val_off, &dup_count, &dup_sz);
2098
2099 if (! control->allow_overwrite && control->no_fail && control->do_partial) {
2100 for (uint32_t i = 0; i < val_ord->max_idx; i++) {
2101 uint32_t idx = order_index_get(val_ord, i);
2102
2103 if (idx == val_ord->max_idx) {
2104 continue;
2105 }
2106
2107 if (cdt_idx_mask_is_set(found_mask, i)) {
2108 order_index_set(val_ord, i, val_ord->max_idx);
2109 dup_count++;
2110 dup_sz += offset_index_get_delta_const(val_off, idx);
2111 }
2112 }
2113 }
2114
2115 if (! control->allow_create) {
2116 // REPLACE for ![key exist].
2117 if (cdt_idx_mask_bit_count(found_mask, val_ord->max_idx) !=
2118 val_ord->max_idx - dup_count) {
2119 if (control->no_fail) {
2120 if (control->do_partial) {
2121 for (uint32_t i = 0; i < val_ord->max_idx; i++) {
2122 uint32_t idx = order_index_get(val_ord, i);
2123
2124 if (idx == val_ord->max_idx) {
2125 continue;
2126 }
2127
2128 if (! cdt_idx_mask_is_set(found_mask, i)) {
2129 order_index_set(val_ord, i, val_ord->max_idx);
2130 dup_count++;
2131 dup_sz += offset_index_get_delta_const(val_off,
2132 idx);
2133 }
2134 }
2135 }
2136 else {
2137 result_data_set_int(&com->result, map->ele_count);
2138 return AS_OK;
2139 }
2140 }
2141 else {
2142 return -AS_ERR_ELEMENT_NOT_FOUND;
2143 }
2144 }
2145 }
2146
2147 uint32_t new_ele_count = map->ele_count - rm_count +
2148 val_ord->max_idx - dup_count;
2149 uint32_t new_content_sz = map->content_sz - rm_sz +
2150 val_off->content_sz - dup_sz;
2151 define_map_packer(mpk, new_ele_count, map->flags, new_content_sz);
2152
2153 map_packer_setup_bin(&mpk, com);
2154 mpk.write_ptr = cdt_idx_mask_write_eles(rm_mask, rm_count, &map->offidx,
2155 mpk.write_ptr, true);
2156 mpk.write_ptr = order_index_write_eles(val_ord, val_ord->max_idx, val_off,
2157 mpk.write_ptr, false);
2158 result_data_set_int(&com->result, new_ele_count);
2159
2160#ifdef MAP_DEBUG_VERIFY
2161 if (! map_verify(&com->ctx)) {
2162 cdt_bin_print(com->ctx.b, "map_add_items_unordered");
2163 map_print(map, "original");
2164 offset_index_print(val_off, "val_off");
2165 order_index_print(val_ord, "val_ord");
2166 cf_crash(AS_PARTICLE, "ele_count %u dup_count %u dup_sz %u new_ele_count %u new_content_sz %u", map->ele_count, dup_count, dup_sz, new_ele_count, new_content_sz);
2167 }
2168#endif
2169
2170 return AS_OK;
2171}
2172
2173static int
2174map_add_items_ordered(const packed_map *map, cdt_op_mem *com,
2175 const offset_index *val_off, order_index *val_ord,
2176 const map_add_control *control)
2177{
2178 uint32_t dup_count;
2179 uint32_t dup_sz;
2180
2181 order_index_sorted_mark_dup_eles(val_ord, val_off, &dup_count, &dup_sz);
2182
2183 if (map->ele_count == 0) {
2184 uint32_t new_content_sz = order_index_get_ele_size(val_ord,
2185 val_ord->max_idx, val_off);
2186 uint32_t new_ele_count = val_ord->max_idx - dup_count;
2187 define_map_packer(mpk, new_ele_count, map->flags, new_content_sz);
2188
2189 map_packer_setup_bin(&mpk, com);
2190 order_index_write_eles(val_ord, val_ord->max_idx, val_off,
2191 mpk.write_ptr, false);
2192
2193 if (! offset_index_is_null(&mpk.offidx)) {
2194 offset_index_set_filled(&mpk.offidx, 1);
2195
2196 for (uint32_t i = 0; i < val_ord->max_idx; i++) {
2197 uint32_t val_idx = order_index_get(val_ord, i);
2198
2199 if (val_idx == val_ord->max_idx) {
2200 continue;
2201 }
2202
2203 uint32_t sz = offset_index_get_delta_const(val_off, val_idx);
2204
2205 offset_index_append_size(&mpk.offidx, sz);
2206 }
2207 }
2208
2209 if (! order_index_is_null(&mpk.ordidx)) {
2210 order_index_set(&mpk.ordidx, 0, new_ele_count);
2211 }
2212
2213 result_data_set_int(&com->result, new_ele_count);
2214
2215#ifdef MAP_DEBUG_VERIFY
2216 if (! map_verify(&com->ctx)) {
2217 cdt_bin_print(com->ctx.b, "map_add_items_ordered");
2218 map_print(map, "original");
2219 offset_index_print(val_off, "val_off");
2220 order_index_print(val_ord, "val_ord");
2221 cf_crash(AS_PARTICLE, "ele_count 0 dup_count %u dup_sz %u new_ele_count %u new_content_sz %u", dup_count, dup_sz, new_ele_count, new_content_sz);
2222 }
2223#endif
2224
2225 return AS_OK;
2226 }
2227
2228 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
2229 uint32_t rm_count = 0;
2230 uint32_t rm_sz = 0;
2231 define_order_index2(insert_idx, map->ele_count, val_ord->max_idx,
2232 com->alloc_idx);
2233
2234 for (uint32_t i = 0; i < val_ord->max_idx; i++) {
2235 uint32_t val_idx = order_index_get(val_ord, i);
2236
2237 if (val_idx == val_ord->max_idx) {
2238 continue;
2239 }
2240
2241 uint32_t off = offset_index_get_const(val_off, val_idx);
2242 uint32_t sz = offset_index_get_delta_const(val_off, val_idx);
2243
2244 const cdt_payload value = {
2245 .ptr = val_off->contents + off,
2246 .sz = sz
2247 };
2248
2249 map_ele_find find;
2250 map_ele_find_init(&find, map);
2251
2252 packed_map_find_key_indexed(map, &find, &value);
2253
2254 if (find.found_key) {
2255 // ADD for [key exist].
2256 if (! control->allow_overwrite) {
2257 if (control->no_fail) {
2258 if (control->do_partial) {
2259 order_index_set(val_ord, i, val_ord->max_idx); // skip this value
2260 dup_count++;
2261 dup_sz += sz;
2262 continue;
2263 }
2264
2265 result_data_set_int(&com->result, map->ele_count);
2266 return AS_OK;
2267 }
2268
2269 return -AS_ERR_ELEMENT_EXISTS;
2270 }
2271
2272 if (! cdt_idx_mask_is_set(rm_mask, find.idx)) {
2273 cdt_idx_mask_set(rm_mask, find.idx);
2274 rm_count++;
2275 rm_sz += offset_index_get_delta_const(&map->offidx, find.idx);
2276 }
2277 }
2278 else {
2279 // REPLACE for ![key exist].
2280 if (! control->allow_create) {
2281 if (control->no_fail) {
2282 if (control->do_partial) {
2283 order_index_set(val_ord, i, val_ord->max_idx); // skip this value
2284 dup_count++;
2285 dup_sz += sz;
2286 continue;
2287 }
2288
2289 result_data_set_int(&com->result, map->ele_count);
2290 return AS_OK;
2291 }
2292
2293 return -AS_ERR_ELEMENT_NOT_FOUND;
2294 }
2295 }
2296
2297 cf_assert(find.idx <= map->ele_count, AS_PARTICLE, "Invalid find.idx %u > ele_count %u", find.idx, map->ele_count);
2298 order_index_set(&insert_idx, i, find.idx);
2299 }
2300
2301 uint32_t new_ele_count = map->ele_count - rm_count + val_ord->max_idx -
2302 dup_count;
2303 uint32_t new_content_sz = map->content_sz - rm_sz + val_off->content_sz -
2304 dup_sz;
2305 define_map_packer(mpk, new_ele_count, map->flags, new_content_sz);
2306 uint32_t start_off = 0;
2307
2308 map_packer_setup_bin(&mpk, com);
2309
2310 for (uint32_t i = 0; i < val_ord->max_idx; i++) {
2311 uint32_t val_idx = order_index_get(val_ord, i);
2312
2313 if (val_idx == val_ord->max_idx) {
2314 continue;
2315 }
2316
2317 uint32_t index = order_index_get(&insert_idx, i);
2318 uint32_t off = offset_index_get_const(&map->offidx, index);
2319
2320 if (start_off < off) {
2321 uint32_t sz = off - start_off;
2322
2323 memcpy(mpk.write_ptr, map->contents + start_off, sz);
2324 mpk.write_ptr += sz;
2325
2326 if (index == map->ele_count) {
2327 start_off = map->content_sz;
2328 }
2329 else if (cdt_idx_mask_is_set(rm_mask, index)) {
2330 start_off = offset_index_get_const(&map->offidx, index + 1);
2331 }
2332 else {
2333 start_off = off;
2334 }
2335 }
2336 else if (index == map->ele_count) {
2337 start_off = map->content_sz;
2338 }
2339 else if (start_off == off && cdt_idx_mask_is_set(rm_mask, index)) {
2340 start_off = offset_index_get_const(&map->offidx, index + 1);
2341 }
2342
2343 uint32_t val_offset = offset_index_get_const(val_off, val_idx);
2344 uint32_t val_sz = offset_index_get_delta_const(val_off, val_idx);
2345
2346 memcpy(mpk.write_ptr, val_off->contents + val_offset, val_sz);
2347 mpk.write_ptr += val_sz;
2348 }
2349
2350 uint32_t sz = map->content_sz - start_off;
2351
2352 if (sz != 0) {
2353 memcpy(mpk.write_ptr, map->contents + start_off, sz);
2354 }
2355
2356 if (! offset_index_is_null(&mpk.offidx)) {
2357 uint32_t read_index = 0;
2358 uint32_t write_index = 1;
2359 int delta = 0;
2360
2361 offset_index_set_filled(&mpk.offidx, 1);
2362
2363 for (uint32_t i = 0; i < val_ord->max_idx; i++) {
2364 uint32_t val_idx = order_index_get(val_ord, i);
2365
2366 if (val_idx == val_ord->max_idx) {
2367 continue;
2368 }
2369
2370 uint32_t index = order_index_get(&insert_idx, i);
2371
2372 if (index > read_index) {
2373 uint32_t count = index - read_index;
2374
2375 if (read_index + count == map->ele_count) {
2376 count--;
2377 }
2378
2379 offset_index_copy(&mpk.offidx, &map->offidx, write_index,
2380 read_index + 1, count, delta);
2381 write_index += count;
2382 read_index += count;
2383 offset_index_set_filled(&mpk.offidx, write_index);
2384
2385 if (index != map->ele_count &&
2386 cdt_idx_mask_is_set(rm_mask, index)) {
2387 read_index++;
2388 delta -= offset_index_get_delta_const(&map->offidx, index);
2389 }
2390 }
2391 else if (index != map->ele_count && index == read_index &&
2392 cdt_idx_mask_is_set(rm_mask, index)) {
2393 read_index++;
2394 delta -= offset_index_get_delta_const(&map->offidx, index);
2395 }
2396
2397 uint32_t sz = offset_index_get_delta_const(val_off, val_idx);
2398
2399 offset_index_append_size(&mpk.offidx, sz);
2400 write_index++;
2401 delta += sz;
2402 }
2403
2404 if (read_index + 1 < map->ele_count && write_index < new_ele_count) {
2405 offset_index_copy(&mpk.offidx, &map->offidx, write_index,
2406 read_index + 1, map->ele_count - read_index - 1, delta);
2407 }
2408
2409 offset_index_set_filled(&mpk.offidx, map->ele_count);
2410 }
2411
2412 if (! order_index_is_null(&mpk.ordidx)) {
2413 order_index_set(&mpk.ordidx, 0, new_ele_count);
2414 }
2415
2416 result_data_set_int(&com->result, new_ele_count);
2417
2418#ifdef MAP_DEBUG_VERIFY
2419 if (! map_verify(&com->ctx)) {
2420 cdt_bin_print(com->ctx.b, "map_add_items_ordered");
2421 map_print(map, "original");
2422 offset_index_print(val_off, "val_off");
2423 order_index_print(val_ord, "val_ord");
2424 cf_crash(AS_PARTICLE, "ele_count %u dup_count %u dup_sz %u new_ele_count %u new_content_sz %u", map->ele_count, dup_count, dup_sz, new_ele_count, new_content_sz);
2425 }
2426#endif
2427
2428 return AS_OK;
2429}
2430
2431static int
2432map_add_items(cdt_op_mem *com, const cdt_payload *items,
2433 const map_add_control *control)
2434{
2435 as_unpacker pk = {
2436 .buffer = items->ptr,
2437 .length = items->sz
2438 };
2439
2440 int64_t items_count = as_unpack_map_header_element_count(&pk);
2441
2442 if (items_count < 0) {
2443 cf_warning(AS_PARTICLE, "map_add_items() invalid parameter, expected packed map");
2444 return -AS_ERR_PARAMETER;
2445 }
2446
2447 if (items_count > 0 && as_unpack_peek_is_ext(&pk)) {
2448 if (as_unpack_size(&pk) <= 0 || as_unpack_size(&pk) <= 0) {
2449 cf_warning(AS_PARTICLE, "map_add_items() invalid parameter");
2450 return -AS_ERR_PARAMETER;
2451 }
2452
2453 items_count--;
2454 }
2455
2456 const uint8_t *val_contents = pk.buffer + pk.offset;
2457 uint32_t val_content_sz = pk.length - pk.offset;
2458 uint32_t val_count = (uint32_t)items_count;
2459 define_order_index(val_ord, val_count, com->alloc_idx);
2460 define_offset_index(val_off, val_contents, val_content_sz, val_count,
2461 com->alloc_idx);
2462
2463 if (! map_offset_index_check_and_fill(&val_off, val_count)) {
2464 cf_warning(AS_PARTICLE, "map_add_items() invalid parameter");
2465 return -AS_ERR_PARAMETER;
2466 }
2467
2468 packed_map map;
2469
2470 if (! packed_map_init_from_com(&map, com, true)) {
2471 cf_warning(AS_PARTICLE, "map_add_items() invalid packed map, ele_count=%u", map.ele_count);
2472 return -AS_ERR_PARAMETER;
2473 }
2474
2475 if (val_count == 0) {
2476 result_data_set_int(&com->result, map.ele_count);
2477 return AS_OK; // no-op
2478 }
2479
2480 setup_map_must_have_offidx(u, &map, com->alloc_idx);
2481
2482 if (! packed_map_check_and_fill_offidx(&map)) {
2483 cf_warning(AS_PARTICLE, "map_add_items() invalid packed map");
2484 return -AS_ERR_PARAMETER;
2485 }
2486
2487 order_index_set_sorted(&val_ord, &val_off, val_contents, val_content_sz,
2488 SORT_BY_KEY);
2489
2490 if (map_is_k_ordered(&map)) {
2491 return map_add_items_ordered(&map, com, &val_off, &val_ord, control);
2492 }
2493
2494 return map_add_items_unordered(&map, com, &val_off, &val_ord, control);
2495}
2496
2497static int
2498map_remove_by_key_interval(cdt_op_mem *com, const cdt_payload *key_start,
2499 const cdt_payload *key_end)
2500{
2501 packed_map map;
2502
2503 if (! packed_map_init_from_com(&map, com, true)) {
2504 cf_warning(AS_PARTICLE, "packed_map_remove_by_key_interval() invalid packed map, ele_count=%u", map.ele_count);
2505 return -AS_ERR_PARAMETER;
2506 }
2507
2508 return packed_map_get_remove_by_key_interval(&map, com, key_start, key_end);
2509}
2510
2511static int
2512map_remove_by_index_range(cdt_op_mem *com, int64_t index, uint64_t count)
2513{
2514 packed_map map;
2515
2516 if (! packed_map_init_from_com(&map, com, true)) {
2517 cf_warning(AS_PARTICLE, "packed_map_remove_by_index_range() invalid packed map index, ele_count=%u", map.ele_count);
2518 return -AS_ERR_PARAMETER;
2519 }
2520
2521 return packed_map_get_remove_by_index_range(&map, com, index, count);
2522}
2523
2524// value_end == NULL means looking for: [value_start, largest possible value].
2525// value_start == value_end means looking for a single value: [value_start, value_start].
2526static int
2527map_remove_by_value_interval(cdt_op_mem *com, const cdt_payload *value_start,
2528 const cdt_payload *value_end)
2529{
2530 packed_map map;
2531
2532 if (! packed_map_init_from_com(&map, com, true)) {
2533 cf_warning(AS_PARTICLE, "packed_map_remove_by_value_interval() invalid packed map, ele_count=%u", map.ele_count);
2534 return -AS_ERR_PARAMETER;
2535 }
2536
2537 return packed_map_get_remove_by_value_interval(&map, com, value_start,
2538 value_end);
2539}
2540
2541static int
2542map_remove_by_rank_range(cdt_op_mem *com, int64_t rank, uint64_t count)
2543{
2544 packed_map map;
2545
2546 if (! packed_map_init_from_com(&map, com, true)) {
2547 cf_warning(AS_PARTICLE, "packed_map_remove_by_index_range() invalid packed map index, ele_count=%u", map.ele_count);
2548 return -AS_ERR_PARAMETER;
2549 }
2550
2551 return packed_map_get_remove_by_rank_range(&map, com, rank, count);
2552}
2553
2554static int
2555map_remove_by_rel_index_range(cdt_op_mem *com, const cdt_payload *key,
2556 int64_t index, uint64_t count)
2557{
2558 packed_map map;
2559
2560 if (! packed_map_init_from_com(&map, com, true)) {
2561 cf_warning(AS_PARTICLE, "map_remove_by_rel_index_range() invalid packed map index, ele_count=%u", map.ele_count);
2562 return -AS_ERR_PARAMETER;
2563 }
2564
2565 return packed_map_get_remove_by_rel_index_range(&map, com, key, index,
2566 count);
2567}
2568
2569static int
2570map_remove_by_rel_rank_range(cdt_op_mem *com, const cdt_payload *value,
2571 int64_t rank, uint64_t count)
2572{
2573 packed_map map;
2574
2575 if (! packed_map_init_from_com(&map, com, true)) {
2576 cf_warning(AS_PARTICLE, "map_remove_by_rel_rank_range() invalid packed map index, ele_count=%u", map.ele_count);
2577 return -AS_ERR_PARAMETER;
2578 }
2579
2580 return packed_map_get_remove_by_rel_rank_range(&map, com, value, rank,
2581 count);
2582}
2583
2584static int
2585map_remove_all_by_key_list(cdt_op_mem *com, const cdt_payload *key_list)
2586{
2587 packed_map map;
2588
2589 if (! packed_map_init_from_com(&map, com, true)) {
2590 cf_warning(AS_PARTICLE, "map_remove_all_by_key_list() invalid packed map, ele_count=%u", map.ele_count);
2591 return -AS_ERR_PARAMETER;
2592 }
2593
2594 return packed_map_get_remove_all_by_key_list(&map, com, key_list);
2595}
2596
2597static int
2598map_remove_all_by_value_list(cdt_op_mem *com, const cdt_payload *value_list)
2599{
2600 packed_map map;
2601
2602 if (! packed_map_init_from_com(&map, com, true)) {
2603 cf_warning(AS_PARTICLE, "map_get_remove_all_value_items() invalid packed map, ele_count=%u", map.ele_count);
2604 return -AS_ERR_PARAMETER;
2605 }
2606
2607 return packed_map_get_remove_all_by_value_list(&map, com, value_list);
2608}
2609
2610static int
2611map_clear(cdt_op_mem *com)
2612{
2613 packed_map map;
2614
2615 if (! packed_map_init_from_com(&map, com, false)) {
2616 cf_warning(AS_PARTICLE, "packed_map_clear() invalid packed map, ele_count=%u", map.ele_count);
2617 return -AS_ERR_PARAMETER;
2618 }
2619
2620 define_map_packer(mpk, 0, map.flags, 0);
2621
2622 map_packer_setup_bin(&mpk, com);
2623
2624 return AS_OK;
2625}
2626
2627//------------------------------------------------
2628// packed_map
2629
2630static bool
2631packed_map_init(packed_map *map, const uint8_t *buf, uint32_t sz,
2632 bool fill_idxs)
2633{
2634 map->packed = buf;
2635 map->packed_sz = sz;
2636
2637 map->ele_count = 0;
2638
2639 return packed_map_unpack_hdridx(map, fill_idxs);
2640}
2641
2642static inline bool
2643packed_map_init_from_particle(packed_map *map, const as_particle *p,
2644 bool fill_idxs)
2645{
2646 const map_mem *p_map_mem = (const map_mem *)p;
2647 return packed_map_init(map, p_map_mem->data, p_map_mem->sz, fill_idxs);
2648}
2649
2650static bool
2651packed_map_init_from_bin(packed_map *map, const as_bin *b, bool fill_idxs)
2652{
2653 uint8_t type = as_bin_get_particle_type(b);
2654
2655 cf_assert(is_map_type(type), AS_PARTICLE, "packed_map_init_from_bin() invalid type %d", type);
2656
2657 return packed_map_init_from_particle(map, b->particle, fill_idxs);
2658}
2659
2660static bool
2661packed_map_init_from_ctx(packed_map *map, const cdt_context *ctx,
2662 bool fill_idxs)
2663{
2664 if (ctx->data_sz == 0) {
2665 return packed_map_init_from_bin(map, ctx->b, fill_idxs);
2666 }
2667
2668 const cdt_mem *p_cdt_mem = (const cdt_mem *)ctx->b->particle;
2669
2670 map->packed = p_cdt_mem->data + ctx->data_offset + ctx->delta_off;
2671 map->packed_sz = ctx->data_sz + ctx->delta_sz;
2672 map->ele_count = 0;
2673
2674 return packed_map_unpack_hdridx(map, fill_idxs);
2675}
2676
2677static inline bool
2678packed_map_init_from_com(packed_map *map, cdt_op_mem *com, bool fill_idxs)
2679{
2680 return packed_map_init_from_ctx(map, &com->ctx, fill_idxs);
2681}
2682
2683static bool
2684packed_map_unpack_hdridx(packed_map *map, bool fill_idxs)
2685{
2686 as_unpacker pk = {
2687 .buffer = map->packed,
2688 .length = map->packed_sz
2689 };
2690
2691 if (map->packed_sz == 0) {
2692 map->flags = 0;
2693 return false;
2694 }
2695
2696 int64_t ele_count = as_unpack_map_header_element_count(&pk);
2697
2698 if (ele_count < 0) {
2699 return false;
2700 }
2701
2702 map->ele_count = (uint32_t)ele_count;
2703
2704 if (ele_count != 0 && as_unpack_peek_is_ext(&pk)) {
2705 as_msgpack_ext ext;
2706
2707 if (as_unpack_ext(&pk, &ext) != 0) {
2708 return false;
2709 }
2710
2711 if (as_unpack_size(&pk) <= 0) { // skip the packed nil
2712 return false;
2713 }
2714
2715 map->flags = ext.type;
2716 map->ele_count--;
2717
2718 map->contents = map->packed + pk.offset;
2719 map->content_sz = map->packed_sz - pk.offset;
2720 offset_index_init(&map->offidx, NULL, map->ele_count, map->contents,
2721 map->content_sz);
2722 order_index_init(&map->ordidx, NULL, map->ele_count);
2723
2724 uint32_t index_sz_left = ext.size;
2725 uint8_t *ptr = (uint8_t *)ext.data;
2726 uint32_t sz = offset_index_size(&map->offidx);
2727
2728 if ((map->flags & AS_PACKED_MAP_FLAG_OFF_IDX) && index_sz_left >= sz &&
2729 sz != 0) {
2730 offset_index_set_ptr(&map->offidx, ptr, map->packed + pk.offset);
2731 ptr += sz;
2732 index_sz_left -= sz;
2733
2734 if (fill_idxs && ! packed_map_check_and_fill_offidx(map)) {
2735 return false;
2736 }
2737 }
2738
2739 sz = order_index_size(&map->ordidx);
2740
2741 if ((map->flags & AS_PACKED_MAP_FLAG_ORD_IDX) && index_sz_left >= sz &&
2742 map->ele_count > 1) {
2743 order_index_set_ptr(&map->ordidx, ptr);
2744 }
2745 }
2746 else {
2747 map->contents = map->packed + pk.offset;
2748 map->content_sz = map->packed_sz - pk.offset;
2749
2750 offset_index_init(&map->offidx, NULL, ele_count, map->contents,
2751 map->content_sz);
2752 order_index_init(&map->ordidx, NULL, ele_count);
2753 map->flags = AS_PACKED_MAP_FLAG_NONE;
2754 }
2755
2756 return true;
2757}
2758
2759static void
2760packed_map_init_indexes(const packed_map *map, as_packer *pk,
2761 offset_index *offidx, order_index *ordidx)
2762{
2763 cf_assert(map_is_k_ordered(map), AS_PARTICLE, "not at least k ordered");
2764
2765 uint8_t *ptr = pk->buffer + pk->offset;
2766
2767 offset_index_init(offidx, ptr, map->ele_count, map->contents,
2768 map->content_sz);
2769
2770 uint32_t offidx_sz = offset_index_size(offidx);
2771
2772 ptr += offidx_sz;
2773 offset_index_set_filled(offidx, 1);
2774 pk->offset += offidx_sz;
2775
2776 if (map_is_kv_ordered(map) && map->ele_count > 1) {
2777 order_index_init(ordidx, ptr, map->ele_count);
2778 pk->offset += order_index_size(ordidx);
2779
2780 if (ordidx->max_idx != 0) {
2781 order_index_set(ordidx, 0, map->ele_count);
2782 }
2783 }
2784}
2785
2786static void
2787packed_map_ensure_ordidx_filled(const packed_map *map)
2788{
2789 cf_assert(offset_index_is_full(&map->offidx), AS_PARTICLE, "offidx not full");
2790 order_index *ordidx = (order_index *)&map->ordidx;
2791
2792 if (! order_index_is_filled(ordidx)) {
2793 order_index_set_sorted(ordidx, &map->offidx, map->contents,
2794 map->content_sz, SORT_BY_VALUE);
2795 }
2796}
2797
2798static bool
2799packed_map_check_and_fill_offidx(const packed_map *map)
2800{
2801 return map_offset_index_check_and_fill((offset_index *)&map->offidx,
2802 map->ele_count);
2803}
2804
2805static uint32_t
2806packed_map_find_index_by_idx_unordered(const packed_map *map, uint32_t idx)
2807{
2808 uint32_t pk_offset = offset_index_get_const(&map->offidx, idx);
2809
2810 cdt_payload key = {
2811 .ptr = map->contents + pk_offset,
2812 .sz = map->content_sz - pk_offset
2813 };
2814
2815 return packed_map_find_index_by_key_unordered(map, &key);
2816}
2817
2818static uint32_t
2819packed_map_find_index_by_key_unordered(const packed_map *map,
2820 const cdt_payload *key)
2821{
2822 msgpack_in pk_key = {
2823 .buf = key->ptr,
2824 .buf_sz = key->sz
2825 };
2826
2827 uint32_t index = 0;
2828 define_map_msgpack_in(pk, map);
2829
2830 for (uint32_t i = 0; i < map->ele_count; i++) {
2831 pk_key.offset = 0;
2832 msgpack_compare_t cmp = msgpack_cmp(&pk, &pk_key);
2833
2834 if (cmp == MSGPACK_COMPARE_ERROR) {
2835 return map->ele_count;
2836 }
2837
2838 if (cmp == MSGPACK_COMPARE_LESS) {
2839 index++;
2840 }
2841
2842 if (msgpack_sz(&pk) == 0) {
2843 return map->ele_count;
2844 }
2845 }
2846
2847 return index;
2848}
2849
2850static void
2851packed_map_find_rank_indexed_linear(const packed_map *map, map_ele_find *find,
2852 uint32_t start, uint32_t len)
2853{
2854 uint32_t rank = order_index_find_idx(&map->ordidx, find->idx, start,
2855 len);
2856
2857 if (rank < start + len) {
2858 find->found_value = true;
2859 find->rank = rank;
2860 }
2861}
2862
2863// Find rank given index (find->idx).
2864static void
2865packed_map_find_rank_indexed(const packed_map *map, map_ele_find *find)
2866{
2867 uint32_t ele_count = map->ele_count;
2868
2869 if (ele_count == 0) {
2870 return;
2871 }
2872
2873 if (find->idx >= ele_count) {
2874 find->found_value = false;
2875 return;
2876 }
2877
2878 const offset_index *offset_idx = &map->offidx;
2879 const order_index *value_idx = &map->ordidx;
2880
2881 uint32_t rank = ele_count / 2;
2882 uint32_t upper = ele_count;
2883 uint32_t lower = 0;
2884
2885 msgpack_in pk_value = {
2886 .buf = map->contents + find->value_offset,
2887 .buf_sz = find->key_offset + find->sz - find->value_offset
2888 };
2889
2890 find->found_value = false;
2891
2892 while (true) {
2893 if (upper - lower < LINEAR_FIND_RANK_MAX_COUNT) {
2894 packed_map_find_rank_indexed_linear(map, find, lower,
2895 upper - lower);
2896 return;
2897 }
2898
2899 uint32_t idx = order_index_get(value_idx, rank);
2900
2901 if (find->idx == idx) {
2902 find->found_value = true;
2903 find->rank = rank;
2904 break;
2905 }
2906
2907 msgpack_in pk_buf = {
2908 .buf = map->contents,
2909 .buf_sz = map->content_sz,
2910 .offset = offset_index_get_const(offset_idx, idx)
2911 };
2912
2913 if (msgpack_sz(&pk_buf) == 0) { // skip key
2914 cf_crash(AS_PARTICLE, "packed_map_find_rank_indexed() unpack key failed at rank=%u", rank);
2915 }
2916
2917 msgpack_compare_t cmp = msgpack_cmp_peek(&pk_value, &pk_buf);
2918
2919 if (cmp == MSGPACK_COMPARE_EQUAL) {
2920 if (find->idx < idx) {
2921 cmp = MSGPACK_COMPARE_LESS;
2922 }
2923 else if (find->idx > idx) {
2924 cmp = MSGPACK_COMPARE_GREATER;
2925 }
2926
2927 find->found_value = true;
2928 }
2929
2930 if (cmp == MSGPACK_COMPARE_EQUAL) {
2931 find->rank = rank;
2932 break;
2933 }
2934
2935 if (cmp == MSGPACK_COMPARE_GREATER) {
2936 if (rank >= upper - 1) {
2937 find->rank = rank + 1;
2938 break;
2939 }
2940
2941 lower = rank + 1;
2942 rank += upper;
2943 rank /= 2;
2944 }
2945 else if (cmp == MSGPACK_COMPARE_LESS) {
2946 if (rank == lower) {
2947 find->rank = rank;
2948 break;
2949 }
2950
2951 upper = rank;
2952 rank += lower;
2953 rank /= 2;
2954 }
2955 else {
2956 cf_crash(AS_PARTICLE, "packed_map_find_rank_indexed() error=%d lower=%u rank=%u upper=%u", (int)cmp, lower, rank, upper);
2957 }
2958 }
2959}
2960
2961static void
2962packed_map_find_rank_by_value_indexed(const packed_map *map,
2963 map_ele_find *map_find, const cdt_payload *value)
2964{
2965 order_index_find find = {
2966 .target = map_find->idx,
2967 .count = map->ele_count
2968 };
2969
2970 order_index_find_rank_by_value(&map->ordidx, value, &map->offidx, &find,
2971 true);
2972
2973 map_find->found_value = find.found;
2974 map_find->rank = find.result;
2975}
2976
2977// value_end == NULL means looking for: [value_start, largest possible value].
2978// value_start == value_end means looking for a single value: [value_start, value_start].
2979static void
2980packed_map_find_rank_range_by_value_interval_indexed(const packed_map *map,
2981 const cdt_payload *value_start, const cdt_payload *value_end,
2982 uint32_t *rank, uint32_t *count, bool is_multi)
2983{
2984 cf_assert(map_has_offidx(map), AS_PARTICLE, "packed_map_find_rank_range_by_value_interval_indexed() offset_index needs to be valid");
2985
2986 map_ele_find find_start;
2987
2988 map_ele_find_init(&find_start, map);
2989 find_start.idx = 0; // find least ranked entry with value == value_start
2990 packed_map_find_rank_by_value_indexed(map, &find_start, value_start);
2991
2992 *rank = find_start.rank;
2993 *count = 1;
2994
2995 if (! value_end || ! value_end->ptr) {
2996 *count = map->ele_count - *rank;
2997 }
2998 else {
2999 map_ele_find find_end;
3000
3001 map_ele_find_init(&find_end, map);
3002
3003 if (value_end != value_start) {
3004 find_end.idx = 0;
3005 packed_map_find_rank_by_value_indexed(map, &find_end, value_end);
3006 *count = (find_end.rank > find_start.rank) ?
3007 find_end.rank - find_start.rank : 0;
3008 }
3009 else {
3010 if (! find_start.found_value) {
3011 *count = 0;
3012 }
3013 else if (is_multi) {
3014 find_end.idx = map->ele_count; // find highest ranked entry with value == value_start
3015 packed_map_find_rank_by_value_indexed(map, &find_end,
3016 value_start);
3017 *count = find_end.rank - find_start.rank;
3018 }
3019 }
3020 }
3021}
3022
3023// value_end == NULL means looking for: [value_start, largest possible value].
3024// value_start == value_end means looking for a single value: [value_start, value_start].
3025static void
3026packed_map_find_rank_range_by_value_interval_unordered(const packed_map *map,
3027 const cdt_payload *value_start, const cdt_payload *value_end,
3028 uint32_t *rank, uint32_t *count, uint64_t *mask, bool is_multi)
3029{
3030 cf_assert(value_end, AS_PARTICLE, "value_end == NULL");
3031
3032 msgpack_in pk_start = {
3033 .buf = value_start->ptr,
3034 .buf_sz = value_start->sz
3035 };
3036
3037 msgpack_in pk_end = {
3038 .buf = value_end->ptr,
3039 .buf_sz = value_end->sz
3040 };
3041
3042 bool can_early_exit = false;
3043 uint32_t temp_rank;
3044
3045 if (rank == NULL) {
3046 rank = &temp_rank;
3047 can_early_exit = true;
3048 }
3049
3050 *rank = 0;
3051 *count = 0;
3052
3053 define_map_msgpack_in(pk, map);
3054
3055 cf_assert(offset_index_is_full(&map->offidx), AS_PARTICLE, "packed_map_find_rank_range_by_value_interval_unordered() offset_index needs to be full");
3056
3057 for (uint32_t i = 0; i < map->ele_count; i++) {
3058 if (msgpack_sz(&pk) == 0) { // skip key
3059 cf_crash(AS_PARTICLE, "packed_map_find_rank_range_by_value_interval_unordered() invalid packed map at index %u", i);
3060 }
3061
3062 uint32_t value_offset = pk.offset; // save for pk_end
3063
3064 pk_start.offset = 0; // reset
3065
3066 msgpack_compare_t cmp_start = msgpack_cmp(&pk, &pk_start);
3067
3068 cf_assert(cmp_start != MSGPACK_COMPARE_ERROR, AS_PARTICLE, "packed_map_find_rank_range_by_value_interval_unordered() invalid packed map at index %u", i);
3069
3070 if (cmp_start == MSGPACK_COMPARE_LESS) {
3071 (*rank)++;
3072 }
3073 else if (value_start != value_end) {
3074 msgpack_compare_t cmp_end = MSGPACK_COMPARE_LESS;
3075
3076 // NULL value_end means largest possible value.
3077 if (value_end->ptr) {
3078 pk.offset = value_offset;
3079 pk_end.offset = 0;
3080 cmp_end = msgpack_cmp(&pk, &pk_end);
3081 }
3082
3083 if (cmp_end == MSGPACK_COMPARE_LESS) {
3084 if (mask != NULL) {
3085 cdt_idx_mask_set(mask, i);
3086 }
3087
3088 (*count)++;
3089 }
3090 }
3091 // Single value case.
3092 else if (cmp_start == MSGPACK_COMPARE_EQUAL) {
3093 if (! is_multi) {
3094 if (*count == 0) {
3095 if (mask != NULL) {
3096 *mask = i;
3097 }
3098
3099 *count = 1;
3100
3101 if (can_early_exit) {
3102 break;
3103 }
3104 }
3105
3106 continue;
3107 }
3108
3109 if (mask != NULL) {
3110 cdt_idx_mask_set(mask, i);
3111 }
3112
3113 (*count)++;
3114 }
3115 }
3116}
3117
3118// Find key given list index.
3119static void
3120packed_map_find_key_indexed(const packed_map *map, map_ele_find *find,
3121 const cdt_payload *key)
3122{
3123 const offset_index *offidx = &map->offidx;
3124 uint32_t ele_count = map->ele_count;
3125
3126 find->lower = 0;
3127 find->upper = ele_count;
3128
3129 uint32_t idx = (find->lower + find->upper) / 2;
3130
3131 msgpack_in pk_key = {
3132 .buf = key->ptr,
3133 .buf_sz = key->sz
3134 };
3135
3136 find->found_key = false;
3137
3138 if (ele_count == 0) {
3139 find->idx = 0;
3140 return;
3141 }
3142
3143 while (true) {
3144 uint32_t offset = offset_index_get_const(offidx, idx);
3145 uint32_t content_sz = map->content_sz;
3146 uint32_t sz = content_sz - offset;
3147
3148 msgpack_in pk_buf = {
3149 .buf = map->contents + offset,
3150 .buf_sz = sz
3151 };
3152
3153 pk_key.offset = 0; // reset
3154
3155 msgpack_compare_t cmp = msgpack_cmp(&pk_key, &pk_buf);
3156 uint32_t key_sz = pk_buf.offset;
3157
3158 if (cmp == MSGPACK_COMPARE_EQUAL) {
3159 if (! find->found_key) {
3160 find->found_key = true;
3161 find->key_offset = offset;
3162 find->value_offset = offset + key_sz;
3163 find->idx = idx++;
3164 find->sz = (idx >= ele_count) ?
3165 sz : offset_index_get_const(offidx, idx) - offset;
3166 }
3167
3168 break;
3169 }
3170
3171 if (cmp == MSGPACK_COMPARE_GREATER) {
3172 if (idx >= find->upper - 1) {
3173 if (++idx >= ele_count) {
3174 find->key_offset = content_sz;
3175 find->value_offset = content_sz;
3176 find->idx = idx;
3177 find->sz = 0;
3178 break;
3179 }
3180
3181 if (! find->found_key) {
3182 uint32_t offset = offset_index_get_const(offidx, idx);
3183 uint32_t tail = content_sz - offset;
3184
3185 msgpack_in pk = {
3186 .buf = map->contents + offset,
3187 .buf_sz = tail
3188 };
3189
3190 if (msgpack_sz(&pk) == 0) {
3191 cf_crash(AS_PARTICLE, "packed_map_find_key_indexed() invalid packed map");
3192 }
3193
3194 find->key_offset = offset;
3195 find->value_offset = offset + pk.offset;
3196 find->idx = idx++;
3197 find->sz = (idx >= ele_count) ?
3198 tail : offset_index_get_const(offidx, idx) - offset;
3199 }
3200
3201 break;
3202 }
3203
3204 find->lower = idx + 1;
3205 idx += find->upper;
3206 idx /= 2;
3207 }
3208 else if (cmp == MSGPACK_COMPARE_LESS) {
3209 if (idx == find->lower) {
3210 find->key_offset = offset;
3211 find->value_offset = offset + key_sz;
3212 find->idx = idx++;
3213 find->sz = (idx >= ele_count) ?
3214 sz : offset_index_get_const(offidx, idx) - offset;
3215 break;
3216 }
3217
3218 find->upper = idx;
3219 idx += find->lower;
3220 idx /= 2;
3221 }
3222 else {
3223 cf_crash(AS_PARTICLE, "packed_map_find_key_indexed() compare error=%d", (int)cmp);
3224 }
3225 }
3226}
3227
3228static bool
3229packed_map_find_key(const packed_map *map, map_ele_find *find,
3230 const cdt_payload *key)
3231{
3232 uint32_t ele_count = map->ele_count;
3233 const offset_index *offidx = (const offset_index *)&map->offidx;
3234
3235 if (ele_count == 0) {
3236 return true;
3237 }
3238
3239 cf_assert(offset_index_is_full(offidx), AS_PARTICLE, "offidx not full");
3240
3241 if (map_is_k_ordered(map)) {
3242 packed_map_find_key_indexed(map, find, key);
3243 return true;
3244 }
3245
3246 msgpack_in pk_key = {
3247 .buf = key->ptr,
3248 .buf_sz = key->sz
3249 };
3250
3251 find->found_key = false;
3252
3253 define_map_msgpack_in(pk, map);
3254 uint32_t content_sz = pk.buf_sz;
3255
3256 // Unordered compare.
3257 // Assumes same keys are clustered (for future multi-map support).
3258 for (uint32_t i = 0; i < ele_count; i++) {
3259 pk.offset = offset_index_get_const(offidx, i);
3260
3261 uint32_t key_offset = pk.offset;
3262 msgpack_compare_t cmp = msgpack_cmp_peek(&pk_key, &pk);
3263
3264 cf_assert(cmp != MSGPACK_COMPARE_ERROR, AS_PARTICLE, "compare error");
3265
3266 if (cmp == MSGPACK_COMPARE_EQUAL) {
3267 // Get value offset.
3268 if (msgpack_sz(&pk) == 0) {
3269 cf_warning(AS_PARTICLE, "msgpack error at offset %u", pk.offset);
3270 return false;
3271 }
3272
3273 if (! find->found_key) {
3274 find->found_key = true;
3275 find->idx = i;
3276 find->key_offset = key_offset;
3277 find->value_offset = pk.offset;
3278 find->sz = offset_index_get_const(offidx, i + 1) - key_offset;
3279 }
3280
3281 return true;
3282 }
3283 else if (find->found_key) {
3284 return true;
3285 }
3286 }
3287
3288 find->key_offset = content_sz;
3289 find->value_offset = content_sz;
3290 find->sz = 0;
3291 find->idx = ele_count;
3292 return true;
3293}
3294
3295static int
3296packed_map_get_remove_by_key_interval(const packed_map *map, cdt_op_mem *com,
3297 const cdt_payload *key_start, const cdt_payload *key_end)
3298{
3299 cdt_result_data *result = &com->result;
3300
3301 if (result_data_is_return_rank_range(result)) {
3302 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_key_interval() result_type %d not supported", result->type);
3303 return -AS_ERR_OP_NOT_APPLICABLE;
3304 }
3305
3306 setup_map_must_have_offidx(u, map, com->alloc_idx);
3307 uint32_t index = 0;
3308 uint32_t count = 0;
3309
3310 if (! packed_map_check_and_fill_offidx(map)) {
3311 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_key_interval() invalid packed map");
3312 return -AS_ERR_PARAMETER;
3313 }
3314
3315 cf_assert(key_start->ptr != NULL, AS_PARTICLE, "packed_map_get_remove_by_key_interval() invalid start key");
3316
3317 if (map_is_k_ordered(map)) {
3318 packed_map_get_range_by_key_interval_ordered(map, key_start, key_end,
3319 &index, &count);
3320
3321 if (count == 0 && ! result->is_multi) {
3322 if (! result_data_set_key_not_found(result, -1)) {
3323 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_key_interval() invalid result_type %d", result->type);
3324 return -AS_ERR_OP_NOT_APPLICABLE;
3325 }
3326
3327 return AS_OK;
3328 }
3329
3330 return packed_map_get_remove_by_index_range(map, com, index, count);
3331 }
3332
3333 bool inverted = result_data_is_inverted(result);
3334
3335 if (inverted && ! result->is_multi) {
3336 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_key_interval() INVERTED flag not supported for single result ops");
3337 return -AS_ERR_OP_NOT_APPLICABLE;
3338 }
3339
3340 if (key_start == key_end) {
3341 map_ele_find find_key;
3342
3343 map_ele_find_init(&find_key, map);
3344 packed_map_find_key(map, &find_key, key_start);
3345
3346 if (! find_key.found_key) {
3347 if (! result_data_set_key_not_found(result, -1)) {
3348 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_key_interval() invalid result_type %d", result->type);
3349 return -AS_ERR_OP_NOT_APPLICABLE;
3350 }
3351
3352 return AS_OK;
3353 }
3354
3355 if (cdt_op_is_modify(com)) {
3356 define_packed_map_op(op, map);
3357 uint32_t new_sz = packed_map_op_remove(&op, &find_key, 1,
3358 find_key.sz);
3359 define_map_packer(mpk, op.new_ele_count, map->flags, new_sz);
3360
3361 map_packer_setup_bin(&mpk, com);
3362 map_packer_write_seg1(&mpk, &op);
3363 map_packer_write_seg2(&mpk, &op);
3364 }
3365
3366#ifdef MAP_DEBUG_VERIFY
3367 if (! map_verify(&com->ctx)) {
3368 cdt_bin_print(com->ctx.b, "packed_map_get_remove_by_key_interval");
3369 map_print(map, "original");
3370 cf_crash(AS_PARTICLE, "ele_count %u index %u count 1 is_multi %d inverted %d", map->ele_count, index, result->is_multi, inverted);
3371 }
3372#endif
3373
3374 return packed_map_build_result_by_key(map, key_start, find_key.idx,
3375 1, result);
3376 }
3377
3378 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
3379
3380 packed_map_get_range_by_key_interval_unordered(map, key_start, key_end,
3381 &index, &count, rm_mask);
3382
3383 uint32_t rm_count = count;
3384
3385 if (inverted) {
3386 rm_count = map->ele_count - count;
3387 cdt_idx_mask_invert(rm_mask, map->ele_count);
3388 }
3389
3390 uint32_t rm_sz = 0;
3391 int ret = AS_OK;
3392
3393 if (cdt_op_is_modify(com)) {
3394 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
3395 }
3396
3397 if (result_data_is_return_elements(result)) {
3398 if (! packed_map_build_ele_result_by_mask(map, rm_mask, rm_count, rm_sz,
3399 result)) {
3400 return -AS_ERR_UNKNOWN;
3401 }
3402 }
3403 else if (result_data_is_return_rank(result)) {
3404 packed_map_build_rank_result_by_mask(map, rm_mask, rm_count,
3405 result);
3406 }
3407 else {
3408 ret = result_data_set_range(result, index, count, map->ele_count);
3409 }
3410
3411 if (ret != AS_OK) {
3412 return ret;
3413 }
3414
3415#ifdef MAP_DEBUG_VERIFY
3416 if (! map_verify(&com->ctx)) {
3417 cdt_bin_print(com->ctx.b, "packed_map_get_remove_by_key_interval");
3418 map_print(map, "original");
3419 cf_crash(AS_PARTICLE, "ele_count %u index %u count %u rm_count %u inverted %d", map->ele_count, index, count, rm_count, inverted);
3420 }
3421#endif
3422
3423 return AS_OK;
3424}
3425
3426static int
3427packed_map_trim_ordered(const packed_map *map, cdt_op_mem *com, uint32_t index,
3428 uint32_t count)
3429{
3430 cdt_result_data *result = &com->result;
3431
3432 cf_assert(result->is_multi, AS_PARTICLE, "packed_map_trim_ordered() required to be a multi op");
3433 cf_assert(! result_data_is_inverted(result), AS_PARTICLE, "packed_map_trim_ordered() INVERTED flag not supported");
3434
3435 setup_map_must_have_offidx(u, map, com->alloc_idx);
3436 uint32_t rm_count = map->ele_count - count;
3437 uint32_t index1 = index + count;
3438
3439 if (! packed_map_check_and_fill_offidx(map)) {
3440 cf_warning(AS_PARTICLE, "packed_map_trim_ordered() invalid packed map");
3441 return -AS_ERR_PARAMETER;
3442 }
3443
3444 uint32_t offset0 = offset_index_get_const(u->offidx, index);
3445 uint32_t offset1 = offset_index_get_const(u->offidx, index1);
3446 uint32_t content_sz = offset1 - offset0;
3447
3448 if (cdt_op_is_modify(com)) {
3449 define_map_packer(mpk, count, map->flags, content_sz);
3450
3451 map_packer_setup_bin(&mpk, com);
3452 memcpy(mpk.write_ptr, map->contents + offset0, content_sz);
3453 }
3454
3455 switch (result->type) {
3456 case RESULT_TYPE_NONE:
3457 break;
3458 case RESULT_TYPE_COUNT:
3459 as_bin_set_int(result->result, rm_count);
3460 break;
3461 case RESULT_TYPE_REVINDEX:
3462 case RESULT_TYPE_INDEX: {
3463 bool is_rev = (result->type == RESULT_TYPE_REVINDEX);
3464 define_int_list_builder(builder, result->alloc, rm_count);
3465
3466 cdt_container_builder_add_int_range(&builder, 0, index, map->ele_count,
3467 is_rev);
3468 cdt_container_builder_add_int_range(&builder, index1,
3469 map->ele_count - index1, map->ele_count, is_rev);
3470 cdt_container_builder_set_result(&builder, result);
3471 break;
3472 }
3473 case RESULT_TYPE_RANK:
3474 case RESULT_TYPE_REVRANK:
3475 result->flags = AS_CDT_OP_FLAG_INVERTED;
3476 packed_map_build_rank_result_by_index_range(map, index, count, result);
3477 break;
3478 case RESULT_TYPE_KEY:
3479 case RESULT_TYPE_VALUE:
3480 case RESULT_TYPE_MAP:
3481 result->flags = AS_CDT_OP_FLAG_INVERTED;
3482
3483 if (! packed_map_build_ele_result_by_idx_range(map, index, count,
3484 result)) {
3485 return -AS_ERR_UNKNOWN;
3486 }
3487
3488 break;
3489 default:
3490 cf_warning(AS_PARTICLE, "packed_map_trim_ordered() result_type %d not supported", result->type);
3491 return -AS_ERR_OP_NOT_APPLICABLE;
3492 }
3493
3494 return AS_OK;
3495}
3496
3497// Set b = NULL for get_by_index_range operation.
3498static int
3499packed_map_get_remove_by_index_range(const packed_map *map, cdt_op_mem *com,
3500 int64_t index, uint64_t count)
3501{
3502 cdt_result_data *result = &com->result;
3503 uint32_t uindex;
3504 uint32_t count32;
3505
3506 if (! calc_index_count(index, count, map->ele_count, &uindex, &count32,
3507 result->is_multi)) {
3508 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_index_range() index %ld out of bounds for ele_count %u", index, map->ele_count);
3509 return -AS_ERR_OP_NOT_APPLICABLE;
3510 }
3511
3512 if (result_data_is_return_rank_range(result)) {
3513 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_index_range() result_type %d not supported", result->type);
3514 return -AS_ERR_OP_NOT_APPLICABLE;
3515 }
3516
3517 if (result_data_is_inverted(result)) {
3518 if (! result->is_multi) {
3519 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_index_range() INVERTED flag not supported for single result ops");
3520 return -AS_ERR_OP_NOT_APPLICABLE;
3521 }
3522
3523 result->flags &= ~AS_CDT_OP_FLAG_INVERTED;
3524
3525 if (count32 == 0) {
3526 // Reduce to remove all.
3527 uindex = 0;
3528 count32 = map->ele_count;
3529 }
3530 else if (uindex == 0) {
3531 // Reduce to remove tail section.
3532 uindex = count32;
3533 count32 = map->ele_count - count32;
3534 }
3535 else if (uindex + count32 >= map->ele_count) {
3536 // Reduce to remove head section.
3537 count32 = uindex;
3538 uindex = 0;
3539 }
3540 else if (map_is_k_ordered(map)) {
3541 return packed_map_trim_ordered(map, com, uindex, count32);
3542 }
3543 else {
3544 result->flags |= AS_CDT_OP_FLAG_INVERTED;
3545 }
3546 }
3547
3548 if (count32 == 0) {
3549 if (! result_data_set_key_not_found(result, uindex)) {
3550 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_index_range() invalid result type %d", result->type);
3551 return -AS_ERR_OP_NOT_APPLICABLE;
3552 }
3553
3554 return AS_OK;
3555 }
3556
3557 setup_map_must_have_offidx(u, map, com->alloc_idx);
3558
3559 if (count32 == map->ele_count) {
3560 return packed_map_get_remove_all(map, com);
3561 }
3562
3563 if (! packed_map_check_and_fill_offidx(map)) {
3564 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_index_range() invalid packed map");
3565 return -AS_ERR_PARAMETER;
3566 }
3567
3568 int ret = AS_OK;
3569
3570 if (map_is_k_ordered(map)) {
3571 if (cdt_op_is_modify(com)) {
3572 packed_map_remove_idx_range(map, com, uindex, count32);
3573 }
3574
3575 if (result_data_is_return_elements(result)) {
3576 if (! packed_map_build_ele_result_by_idx_range(map, uindex, count32,
3577 result)) {
3578 return -AS_ERR_UNKNOWN;
3579 }
3580 }
3581 else if (result_data_is_return_rank(result)) {
3582 packed_map_build_rank_result_by_index_range(map, uindex, count32,
3583 result);
3584 }
3585 else {
3586 ret = result_data_set_range(result, uindex, count32,
3587 map->ele_count);
3588 }
3589 }
3590 else {
3591 define_build_order_heap_by_range(heap, uindex, count32, map->ele_count,
3592 map, packed_map_compare_key_by_idx, success, com->alloc_idx);
3593
3594 if (! success) {
3595 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_index_range() invalid packed map");
3596 return -AS_ERR_PARAMETER;
3597 }
3598
3599 uint32_t rm_sz = 0;
3600 bool inverted = result_data_is_inverted(result);
3601 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
3602 uint32_t rm_count = (inverted ? map->ele_count - count32 : count32);
3603
3604 cdt_idx_mask_set_by_ordidx(rm_mask, &heap._, heap.filled, count32,
3605 inverted);
3606
3607 if (cdt_op_is_modify(com)) {
3608 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
3609 }
3610
3611 switch (result->type) {
3612 case RESULT_TYPE_RANK:
3613 case RESULT_TYPE_REVRANK:
3614 if (inverted) {
3615 packed_map_build_rank_result_by_mask(map, rm_mask, rm_count,
3616 result);
3617 }
3618 else {
3619 if (heap.cmp == MSGPACK_COMPARE_LESS) {
3620 order_heap_reverse_end(&heap, count32);
3621 }
3622
3623 packed_map_build_rank_result_by_ele_idx(map, &heap._,
3624 heap.filled, count32, result);
3625 }
3626 break;
3627 case RESULT_TYPE_KEY:
3628 case RESULT_TYPE_VALUE:
3629 case RESULT_TYPE_MAP: {
3630 bool success;
3631
3632 if (inverted) {
3633 success = packed_map_build_ele_result_by_mask(map, rm_mask,
3634 rm_count, rm_sz, result);
3635 }
3636 else {
3637 if (heap.cmp == MSGPACK_COMPARE_LESS) {
3638 order_heap_reverse_end(&heap, count32);
3639 }
3640
3641 success = packed_map_build_ele_result_by_ele_idx(map, &heap._,
3642 heap.filled, count32, rm_sz, result);
3643 }
3644
3645 if (! success) {
3646 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_index_range() invalid packed map");
3647 return -AS_ERR_PARAMETER;
3648 }
3649
3650 break;
3651 }
3652 default:
3653 ret = result_data_set_range(result, uindex, count32,
3654 map->ele_count);
3655 break;
3656 }
3657 }
3658
3659 if (ret != AS_OK) {
3660 return ret;
3661 }
3662
3663#ifdef MAP_DEBUG_VERIFY
3664 if (! map_verify(&com->ctx)) {
3665 cdt_bin_print(com->ctx.b, "packed_map_get_remove_by_index_range");
3666 map_print(map, "original");
3667 cf_crash(AS_PARTICLE, "ele_count %u uindex %u count32 %u", map->ele_count, uindex, count32);
3668 }
3669#endif
3670
3671 return AS_OK;
3672}
3673
3674// value_end == NULL means looking for: [value_start, largest possible value].
3675// value_start == value_end means looking for a single value: [value_start, value_start].
3676static int
3677packed_map_get_remove_by_value_interval(const packed_map *map, cdt_op_mem *com,
3678 const cdt_payload *value_start, const cdt_payload *value_end)
3679{
3680 cdt_result_data *result = &com->result;
3681
3682 if (result_data_is_return_index_range(result)) {
3683 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_value_interval() result_type %d not supported", result->type);
3684 return -AS_ERR_OP_NOT_APPLICABLE;
3685 }
3686
3687 bool inverted = result_data_is_inverted(result);
3688
3689 if (inverted && ! result->is_multi) {
3690 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_value_interval() INVERTED flag not supported for single result ops");
3691 return -AS_ERR_OP_NOT_APPLICABLE;
3692 }
3693
3694 if (map->ele_count == 0) {
3695 if (! result_data_set_value_not_found(result, -1)) {
3696 return -AS_ERR_OP_NOT_APPLICABLE;
3697 }
3698
3699 return AS_OK;
3700 }
3701
3702 setup_map_must_have_offidx(u, map, com->alloc_idx);
3703
3704 if (! packed_map_check_and_fill_offidx(map)) {
3705 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_value_interval() invalid packed map");
3706 return -AS_ERR_PARAMETER;
3707 }
3708
3709 uint32_t rank = 0;
3710 uint32_t count = 0;
3711 int ret = AS_OK;
3712
3713 if (! order_index_is_null(&map->ordidx)) {
3714 packed_map_ensure_ordidx_filled(map);
3715 packed_map_find_rank_range_by_value_interval_indexed(map, value_start,
3716 value_end, &rank, &count, result->is_multi);
3717
3718 uint32_t rm_count = (inverted ? map->ele_count - count : count);
3719 bool need_mask = cdt_op_is_modify(com) ||
3720 (inverted && (result_data_is_return_elements(result) ||
3721 result_data_is_return_index(result)));
3722 define_cond_cdt_idx_mask(rm_mask, map->ele_count, need_mask,
3723 com->alloc_idx);
3724 uint32_t rm_sz = 0;
3725
3726 if (need_mask) {
3727 cdt_idx_mask_set_by_ordidx(rm_mask, &map->ordidx, rank, count,
3728 inverted);
3729 }
3730
3731 if (cdt_op_is_modify(com)) {
3732 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
3733 }
3734
3735 if (result_data_is_return_elements(result)) {
3736 if (inverted) {
3737 if (! packed_map_build_ele_result_by_mask(map, rm_mask,
3738 rm_count, rm_sz, result)) {
3739 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_value_interval() invalid packed map");
3740 return -AS_ERR_PARAMETER;
3741 }
3742 }
3743 else if (! packed_map_build_ele_result_by_ele_idx(map, &map->ordidx,
3744 rank, count, rm_sz, result)) {
3745 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_value_interval() invalid packed map");
3746 return -AS_ERR_PARAMETER;
3747 }
3748 }
3749 else if (result_data_is_return_index(result)) {
3750 if (inverted) {
3751 packed_map_build_index_result_by_mask(map, rm_mask, rm_count,
3752 result);
3753 }
3754 else {
3755 packed_map_build_index_result_by_ele_idx(map, &map->ordidx,
3756 rank, count, result);
3757 }
3758 }
3759 else {
3760 ret = result_data_set_range(result, rank, count, map->ele_count);
3761 }
3762 }
3763 else {
3764 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
3765 bool is_ret_rank = result_data_is_return_rank(result) ||
3766 result_data_is_return_rank_range(result);
3767
3768 packed_map_find_rank_range_by_value_interval_unordered(map, value_start,
3769 value_end, is_ret_rank ? &rank : NULL, &count, rm_mask,
3770 result->is_multi);
3771
3772 if (count == 0) {
3773 if (inverted) {
3774 result->flags &= ~AS_CDT_OP_FLAG_INVERTED;
3775
3776 return packed_map_get_remove_all(map, com);
3777 }
3778 else if (! result_data_set_value_not_found(result, rank)) {
3779 return -AS_ERR_OP_NOT_APPLICABLE;
3780 }
3781 }
3782 else {
3783 if (! result->is_multi) {
3784 if (value_start == value_end) {
3785 uint64_t idx = rm_mask[0];
3786
3787 rm_mask[0] = 0;
3788 cdt_idx_mask_set(rm_mask, idx);
3789 }
3790
3791 count = 1;
3792 }
3793
3794 uint32_t rm_sz = 0;
3795 uint32_t rm_count = count;
3796
3797 if (inverted) {
3798 cdt_idx_mask_invert(rm_mask, map->ele_count);
3799 rm_count = map->ele_count - count;
3800 }
3801
3802 if (cdt_op_is_modify(com)) {
3803 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
3804 }
3805
3806 if (result_data_is_return_elements(result)) {
3807 if (! packed_map_build_ele_result_by_mask(map, rm_mask,
3808 rm_count, rm_sz, result)) {
3809 return -AS_ERR_UNKNOWN;
3810 }
3811 }
3812 else if (result_data_is_return_index(result)) {
3813 packed_map_build_index_result_by_mask(map, rm_mask, rm_count,
3814 result);
3815 }
3816 else {
3817 ret = result_data_set_range(result, rank, count,
3818 map->ele_count);
3819 }
3820 }
3821 }
3822
3823 if (ret != AS_OK) {
3824 return ret;
3825 }
3826
3827#ifdef MAP_DEBUG_VERIFY
3828 if (! map_verify(&com->ctx)) {
3829 cdt_bin_print(com->ctx.b, "packed_map_get_remove_by_value_interval");
3830 map_print(map, "original");
3831 cf_crash(AS_PARTICLE, "ele_count %u rank %u count %u inverted %d", map->ele_count, rank, count, inverted);
3832 }
3833#endif
3834
3835 return AS_OK;
3836}
3837
3838static int
3839packed_map_get_remove_by_rank_range(const packed_map *map, cdt_op_mem *com,
3840 int64_t rank, uint64_t count)
3841{
3842 cdt_result_data *result = &com->result;
3843 uint32_t urank;
3844 uint32_t count32;
3845
3846 if (! calc_index_count(rank, count, map->ele_count, &urank, &count32,
3847 result->is_multi)) {
3848 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() rank %ld out of bounds for ele_count %u", rank, map->ele_count);
3849 return -AS_ERR_OP_NOT_APPLICABLE;
3850 }
3851
3852 if (result_data_is_return_index_range(result)) {
3853 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() result_type %d not supported", result->type);
3854 return -AS_ERR_OP_NOT_APPLICABLE;
3855 }
3856
3857 if (result_data_is_inverted(result)) {
3858 if (! result->is_multi) {
3859 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() INVERTED flag not supported for single result ops");
3860 return -AS_ERR_OP_NOT_APPLICABLE;
3861 }
3862
3863 result->flags &= ~AS_CDT_OP_FLAG_INVERTED;
3864
3865 if (count32 == 0) {
3866 // Reduce to remove all.
3867 urank = 0;
3868 count32 = map->ele_count;
3869 }
3870 else if (urank == 0) {
3871 // Reduce to remove tail section.
3872 urank = count32;
3873 count32 = map->ele_count - count32;
3874 }
3875 else if (urank + count32 >= map->ele_count) {
3876 // Reduce to remove head section.
3877 count32 = urank;
3878 urank = 0;
3879 }
3880 else {
3881 result->flags |= AS_CDT_OP_FLAG_INVERTED;
3882 }
3883 }
3884
3885 if (count32 == 0) {
3886 if (! result_data_set_value_not_found(result, urank)) {
3887 return -AS_ERR_OP_NOT_APPLICABLE;
3888 }
3889
3890 return AS_OK;
3891 }
3892
3893 setup_map_must_have_offidx(u, map, com->alloc_idx);
3894
3895 if (! packed_map_check_and_fill_offidx(map)) {
3896 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() invalid packed map");
3897 return -AS_ERR_PARAMETER;
3898 }
3899
3900 bool inverted = result_data_is_inverted(result);
3901 uint32_t rm_count = inverted ? map->ele_count - count32 : count32;
3902 const order_index *ordidx = &map->ordidx;
3903 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
3904 order_index ret_idxs;
3905
3906 if (! order_index_is_null(ordidx)) {
3907 packed_map_ensure_ordidx_filled(map);
3908 cdt_idx_mask_set_by_ordidx(rm_mask, ordidx, urank, count32, inverted);
3909 order_index_init_ref(&ret_idxs, ordidx, urank, count32);
3910 }
3911 else {
3912 define_build_order_heap_by_range(heap, urank, count32, map->ele_count,
3913 map, packed_map_compare_value_by_idx, success, com->alloc_idx);
3914
3915 if (! success) {
3916 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() invalid packed map");
3917 return -AS_ERR_PARAMETER;
3918 }
3919
3920 cdt_idx_mask_set_by_ordidx(rm_mask, &heap._, heap.filled, count32,
3921 inverted);
3922
3923 if (! inverted) {
3924 if (heap.cmp == MSGPACK_COMPARE_LESS) {
3925 // Reorder results from lowest to highest order.
3926 order_heap_reverse_end(&heap, count32);
3927 }
3928
3929 if (result_data_is_return_index(result)) {
3930 packed_map_build_index_result_by_ele_idx(map, &heap._,
3931 heap.filled, count32, result);
3932 }
3933 else if (result_data_is_return_elements(result)) {
3934 if (! packed_map_build_ele_result_by_ele_idx(map, &heap._,
3935 heap.filled, count32, 0, result)) {
3936 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() invalid packed map");
3937 return -AS_ERR_PARAMETER;
3938 }
3939 }
3940 }
3941 }
3942
3943 uint32_t rm_sz = 0;
3944 int ret = AS_OK;
3945
3946 if (cdt_op_is_modify(com)) {
3947 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
3948 }
3949
3950 switch (result->type) {
3951 case RESULT_TYPE_NONE:
3952 case RESULT_TYPE_COUNT:
3953 case RESULT_TYPE_RANK:
3954 case RESULT_TYPE_REVRANK:
3955 ret = result_data_set_index_rank_count(result, urank, count32,
3956 map->ele_count);
3957 break;
3958 case RESULT_TYPE_INDEX:
3959 case RESULT_TYPE_REVINDEX:
3960 if (inverted) {
3961 packed_map_build_index_result_by_mask(map, rm_mask, rm_count,
3962 result);
3963 }
3964 else if (! order_index_is_null(ordidx)) {
3965 packed_map_build_index_result_by_ele_idx(map, &ret_idxs, 0,
3966 rm_count, result);
3967 }
3968 break;
3969 case RESULT_TYPE_KEY:
3970 case RESULT_TYPE_VALUE:
3971 case RESULT_TYPE_MAP:
3972 if (inverted) {
3973 if (! packed_map_build_ele_result_by_mask(map, rm_mask,
3974 rm_count, rm_sz, result)) {
3975 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() invalid packed map");
3976 return -AS_ERR_PARAMETER;
3977 }
3978 }
3979 else if (! order_index_is_null(ordidx) &&
3980 ! packed_map_build_ele_result_by_ele_idx(map, &ret_idxs, 0,
3981 rm_count, rm_sz, result)) {
3982 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() invalid packed map");
3983 return -AS_ERR_PARAMETER;
3984 }
3985 break;
3986 case RESULT_TYPE_REVRANK_RANGE:
3987 case RESULT_TYPE_RANK_RANGE:
3988 ret = result_data_set_range(result, urank, rm_count, map->ele_count);
3989 break;
3990 case RESULT_TYPE_INDEX_RANGE:
3991 case RESULT_TYPE_REVINDEX_RANGE:
3992 default:
3993 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rank_range() result_type %d not supported", result->type);
3994 return -AS_ERR_OP_NOT_APPLICABLE;
3995 }
3996
3997 if (ret != AS_OK) {
3998 return ret;
3999 }
4000
4001#ifdef MAP_DEBUG_VERIFY
4002 if (! map_verify(&com->ctx)) {
4003 cdt_bin_print(com->ctx.b, "packed_map_get_remove_by_rank_range");
4004 map_print(map, "original");
4005 cf_crash(AS_PARTICLE, "packed_map_get_remove_all_by_value_list");
4006 }
4007#endif
4008
4009 return AS_OK;
4010}
4011
4012static int
4013packed_map_get_remove_all_by_key_list(const packed_map *map, cdt_op_mem *com,
4014 const cdt_payload *key_list)
4015{
4016 cdt_result_data *result = &com->result;
4017 as_unpacker items_pk;
4018 uint32_t items_count;
4019
4020 if (! list_param_parse(key_list, &items_pk, &items_count)) {
4021 return -AS_ERR_PARAMETER;
4022 }
4023
4024 bool inverted = result_data_is_inverted(result);
4025
4026 if (items_count == 0) {
4027 switch (result->type) {
4028 case RESULT_TYPE_RANK:
4029 case RESULT_TYPE_REVRANK:
4030 case RESULT_TYPE_INDEX_RANGE:
4031 case RESULT_TYPE_REVINDEX_RANGE:
4032 case RESULT_TYPE_RANK_RANGE:
4033 case RESULT_TYPE_REVRANK_RANGE:
4034 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_key_list() invalid result type %d", result->type);
4035 return -AS_ERR_OP_NOT_APPLICABLE;
4036 default:
4037 break;
4038 }
4039
4040 if (! inverted) {
4041 result_data_set_key_not_found(result, 0);
4042
4043 return AS_OK;
4044 }
4045
4046 result->flags &= ~AS_CDT_OP_FLAG_INVERTED;
4047
4048 return packed_map_get_remove_all(map, com);
4049 }
4050
4051 setup_map_must_have_offidx(u, map, com->alloc_idx);
4052
4053 if (! packed_map_check_and_fill_offidx(map)) {
4054 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_key_list() invalid packed map");
4055 return -AS_ERR_PARAMETER;
4056 }
4057
4058 if (map_is_k_ordered(map)) {
4059 return packed_map_get_remove_all_by_key_list_ordered(map, com,
4060 &items_pk, items_count);
4061 }
4062
4063 return packed_map_get_remove_all_by_key_list_unordered(map, com, &items_pk,
4064 items_count);
4065}
4066
4067static int
4068packed_map_get_remove_all_by_key_list_ordered(const packed_map *map,
4069 cdt_op_mem *com, as_unpacker *items_pk, uint32_t items_count)
4070{
4071 cdt_result_data *result = &com->result;
4072 define_order_index2(rm_ic, map->ele_count, 2 * items_count, com->alloc_idx);
4073 uint32_t rc_count = 0;
4074
4075 for (uint32_t i = 0; i < items_count; i++) {
4076 cdt_payload key = {
4077 .ptr = items_pk->buffer + items_pk->offset,
4078 .sz = items_pk->offset
4079 };
4080
4081 if (as_unpack_size(items_pk) <= 0) {
4082 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_key_list_ordered() invalid parameter");
4083 return -AS_ERR_PARAMETER;
4084 }
4085
4086 key.sz = items_pk->offset - key.sz;
4087
4088 map_ele_find find_key;
4089
4090 map_ele_find_init(&find_key, map);
4091 packed_map_find_key(map, &find_key, &key);
4092
4093 uint32_t count = find_key.found_key ? 1 : 0;
4094
4095 order_index_set(&rm_ic, 2 * i, find_key.idx);
4096 order_index_set(&rm_ic, (2 * i) + 1, count);
4097 rc_count += count;
4098 }
4099
4100 bool inverted = result_data_is_inverted(result);
4101 bool need_mask = cdt_op_is_modify(com) ||
4102 result_data_is_return_elements(result) ||
4103 result->type == RESULT_TYPE_COUNT ||
4104 (inverted && result->type != RESULT_TYPE_NONE);
4105 define_cond_cdt_idx_mask(rm_mask, map->ele_count, need_mask,
4106 com->alloc_idx);
4107 uint32_t rm_sz = 0;
4108 uint32_t rm_count = 0;
4109
4110 if (need_mask) {
4111 cdt_idx_mask_set_by_irc(rm_mask, &rm_ic, NULL, inverted);
4112 rm_count = cdt_idx_mask_bit_count(rm_mask, map->ele_count);
4113 }
4114
4115 if (cdt_op_is_modify(com)) {
4116 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
4117 }
4118
4119 switch (result->type) {
4120 case RESULT_TYPE_NONE:
4121 break;
4122 case RESULT_TYPE_REVINDEX:
4123 case RESULT_TYPE_INDEX:
4124 if (inverted) {
4125 result_data_set_int_list_by_mask(result, rm_mask, rm_count,
4126 map->ele_count);
4127 }
4128 else {
4129 result_data_set_by_irc(result, &rm_ic, NULL, rc_count);
4130 }
4131 break;
4132 case RESULT_TYPE_COUNT:
4133 as_bin_set_int(com->result.result, rm_count);
4134 break;
4135 case RESULT_TYPE_KEY:
4136 case RESULT_TYPE_VALUE:
4137 case RESULT_TYPE_MAP:
4138 if (! packed_map_build_ele_result_by_mask(map, rm_mask, rm_count,
4139 rm_sz, result)) {
4140 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_key_list_ordered() invalid packed map");
4141 return -AS_ERR_PARAMETER;
4142 }
4143 break;
4144 case RESULT_TYPE_REVRANK:
4145 case RESULT_TYPE_RANK:
4146 default:
4147 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_key_list_ordered() invalid return type %d", result->type);
4148 return -AS_ERR_OP_NOT_APPLICABLE;
4149 }
4150
4151#ifdef MAP_DEBUG_VERIFY
4152 if (! map_verify(&com->ctx)) {
4153 cdt_bin_print(com->ctx.b, "packed_map_get_remove_all_by_key_list_ordered");
4154 map_print(map, "original");
4155 cf_crash(AS_PARTICLE, "packed_map_get_remove_all_by_key_list_ordered");
4156 }
4157#endif
4158
4159 return AS_OK;
4160}
4161
4162static int
4163packed_map_get_remove_all_by_key_list_unordered(const packed_map *map,
4164 cdt_op_mem *com, as_unpacker *items_pk, uint32_t items_count)
4165{
4166 cdt_result_data *result = &com->result;
4167 bool inverted = result_data_is_inverted(result);
4168 bool is_ret_index = result_data_is_return_index(result);
4169 uint32_t rm_count;
4170 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
4171 define_order_index(key_list_ordidx, items_count, com->alloc_idx);
4172 definep_cond_order_index2(ic, map->ele_count, items_count * 2,
4173 is_ret_index, com->alloc_idx);
4174
4175 if (! offset_index_find_items((offset_index *)&map->offidx,
4176 CDT_FIND_ITEMS_IDXS_FOR_MAP_KEY, items_pk, &key_list_ordidx,
4177 inverted, rm_mask, &rm_count, ic, com->alloc_idx)) {
4178 return -AS_ERR_PARAMETER;
4179 }
4180
4181 uint32_t rm_sz = 0;
4182
4183 if (cdt_op_is_modify(com)) {
4184 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
4185 }
4186
4187 switch (result->type) {
4188 case RESULT_TYPE_NONE:
4189 break;
4190 case RESULT_TYPE_REVINDEX:
4191 case RESULT_TYPE_INDEX: {
4192 result_data_set_by_itemlist_irc(result, &key_list_ordidx, ic, rm_count);
4193 break;
4194 }
4195 case RESULT_TYPE_COUNT:
4196 as_bin_set_int(com->result.result, rm_count);
4197 break;
4198 case RESULT_TYPE_KEY:
4199 case RESULT_TYPE_VALUE:
4200 case RESULT_TYPE_MAP: {
4201 if (! packed_map_build_ele_result_by_mask(map, rm_mask, rm_count, rm_sz,
4202 result)) {
4203 return -AS_ERR_UNKNOWN;
4204 }
4205 break;
4206 }
4207 default:
4208 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_key_list_unordered() invalid return type %d", result->type);
4209 return -AS_ERR_OP_NOT_APPLICABLE;
4210 }
4211
4212#ifdef MAP_DEBUG_VERIFY
4213 if (! map_verify(&com->ctx)) {
4214 cdt_bin_print(com->ctx.b, "packed_map_get_remove_all_by_key_list_unordered");
4215 map_print(map, "original");
4216 cdt_idx_mask_print(rm_mask, map->ele_count, "rm_mask");
4217 print_packed(items_pk->buffer, items_pk->length, "items_pk");
4218 cf_crash(AS_PARTICLE, "packed_map_get_remove_all_by_key_list_unordered: items_count %u ele_count %u", items_count, map->ele_count);
4219 }
4220#endif
4221
4222 return AS_OK;
4223}
4224
4225static int
4226packed_map_get_remove_all_by_value_list(const packed_map *map, cdt_op_mem *com,
4227 const cdt_payload *value_list)
4228{
4229 cdt_result_data *result = &com->result;
4230 as_unpacker items_pk;
4231 uint32_t items_count;
4232
4233 if (! list_param_parse(value_list, &items_pk, &items_count)) {
4234 return -AS_ERR_PARAMETER;
4235 }
4236
4237 bool inverted = result_data_is_inverted(result);
4238
4239 if (items_count == 0) {
4240 switch (result->type) {
4241 case RESULT_TYPE_INDEX_RANGE:
4242 case RESULT_TYPE_REVINDEX_RANGE:
4243 case RESULT_TYPE_RANK_RANGE:
4244 case RESULT_TYPE_REVRANK_RANGE:
4245 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_value_list() invalid result type %d", result->type);
4246 return -AS_ERR_OP_NOT_APPLICABLE;
4247 default:
4248 break;
4249 }
4250
4251 if (! inverted) {
4252 result_data_set_not_found(result, 0);
4253 return AS_OK;
4254 }
4255
4256 result->flags &= ~AS_CDT_OP_FLAG_INVERTED;
4257
4258 return packed_map_get_remove_all(map, com);
4259 }
4260
4261 setup_map_must_have_offidx(u, map, com->alloc_idx);
4262
4263 if (! packed_map_check_and_fill_offidx(map)) {
4264 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_value_list() invalid packed map");
4265 return -AS_ERR_PARAMETER;
4266 }
4267
4268 if (order_index_is_valid(&map->ordidx)) {
4269 return packed_map_get_remove_all_by_value_list_ordered(map, com,
4270 &items_pk, items_count);
4271 }
4272
4273 bool is_ret_rank = result_data_is_return_rank(result);
4274 define_cdt_idx_mask(rm_mask, map->ele_count, com->alloc_idx);
4275 uint32_t rm_count = 0;
4276 define_order_index(value_list_ordidx, items_count, com->alloc_idx);
4277 definep_cond_order_index2(rc, map->ele_count, items_count * 2, is_ret_rank,
4278 com->alloc_idx);
4279
4280 if (! offset_index_find_items(u->offidx,
4281 CDT_FIND_ITEMS_IDXS_FOR_MAP_VALUE, &items_pk, &value_list_ordidx,
4282 inverted, rm_mask, &rm_count, rc, com->alloc_idx)) {
4283 return -AS_ERR_PARAMETER;
4284 }
4285
4286 uint32_t rm_sz = 0;
4287
4288 if (cdt_op_is_modify(com)) {
4289 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
4290 }
4291
4292 switch (result->type) {
4293 case RESULT_TYPE_NONE:
4294 break;
4295 case RESULT_TYPE_REVINDEX:
4296 case RESULT_TYPE_INDEX: {
4297 packed_map_build_index_result_by_mask(map, rm_mask, rm_count, result);
4298 break;
4299 }
4300 case RESULT_TYPE_REVRANK:
4301 case RESULT_TYPE_RANK: {
4302 result_data_set_by_itemlist_irc(result, &value_list_ordidx, rc,
4303 rm_count);
4304 break;
4305 }
4306 case RESULT_TYPE_COUNT:
4307 as_bin_set_int(result->result, rm_count);
4308 break;
4309 case RESULT_TYPE_KEY:
4310 case RESULT_TYPE_VALUE:
4311 case RESULT_TYPE_MAP: {
4312 if (! packed_map_build_ele_result_by_mask(map, rm_mask, rm_count, rm_sz,
4313 result)) {
4314 return -AS_ERR_UNKNOWN;
4315 }
4316 break;
4317 }
4318 default:
4319 cf_warning(AS_PARTICLE, "packed_map_get_remove_all_by_value_list() invalid return type %d", result->type);
4320 return -AS_ERR_OP_NOT_APPLICABLE;
4321 }
4322
4323#ifdef MAP_DEBUG_VERIFY
4324 if (! map_verify(&com->ctx)) {
4325 cdt_bin_print(com->ctx.b, "packed_map_get_remove_all_by_value_list");
4326 map_print(map, "original");
4327 cf_crash(AS_PARTICLE, "packed_map_get_remove_all_by_value_list");
4328 }
4329#endif
4330
4331 return AS_OK;
4332}
4333
4334static int
4335packed_map_get_remove_all_by_value_list_ordered(const packed_map *map,
4336 cdt_op_mem *com, as_unpacker *items_pk, uint32_t items_count)
4337{
4338 cdt_result_data *result = &com->result;
4339 define_order_index2(rm_rc, map->ele_count, 2 * items_count, com->alloc_idx);
4340 uint32_t rc_count = 0;
4341
4342 packed_map_ensure_ordidx_filled(map);
4343
4344 for (uint32_t i = 0; i < items_count; i++) {
4345 cdt_payload value = {
4346 .ptr = items_pk->buffer + items_pk->offset,
4347 .sz = items_pk->offset
4348 };
4349
4350 if (as_unpack_size(items_pk) <= 0) {
4351 cf_warning(AS_PARTICLE, "packed_map_remove_all_value_items_ordered() invalid parameter");
4352 return -AS_ERR_PARAMETER;
4353 }
4354
4355 value.sz = items_pk->offset - value.sz;
4356
4357 uint32_t rank = 0;
4358 uint32_t count = 0;
4359
4360 packed_map_find_rank_range_by_value_interval_indexed(map, &value,
4361 &value, &rank, &count, result->is_multi);
4362
4363 order_index_set(&rm_rc, 2 * i, rank);
4364 order_index_set(&rm_rc, (2 * i) + 1, count);
4365 rc_count += count;
4366 }
4367
4368 bool inverted = result_data_is_inverted(result);
4369 bool need_mask = cdt_op_is_modify(com) ||
4370 result_data_is_return_elements(result) ||
4371 result->type == RESULT_TYPE_COUNT ||
4372 (inverted && result->type != RESULT_TYPE_NONE);
4373 define_cond_cdt_idx_mask(rm_mask, map->ele_count, need_mask,
4374 com->alloc_idx);
4375 uint32_t rm_sz = 0;
4376 uint32_t rm_count = 0;
4377
4378 if (need_mask) {
4379 cdt_idx_mask_set_by_irc(rm_mask, &rm_rc, &map->ordidx, inverted);
4380 rm_count = cdt_idx_mask_bit_count(rm_mask, map->ele_count);
4381 }
4382
4383 if (cdt_op_is_modify(com)) {
4384 packed_map_remove_by_mask(map, com, rm_mask, rm_count, &rm_sz);
4385 }
4386
4387 switch (result->type) {
4388 case RESULT_TYPE_NONE:
4389 break;
4390 case RESULT_TYPE_REVINDEX:
4391 case RESULT_TYPE_INDEX: {
4392 if (inverted) {
4393 packed_map_build_index_result_by_mask(map, rm_mask, rm_count,
4394 result);
4395 }
4396 else {
4397 result_data_set_by_irc(result, &rm_rc, &map->ordidx, rc_count);
4398 }
4399 break;
4400 }
4401 case RESULT_TYPE_REVRANK:
4402 case RESULT_TYPE_RANK:
4403 if (inverted) {
4404 packed_map_build_rank_result_by_mask(map, rm_mask, rm_count,
4405 result);
4406 }
4407 else {
4408 result_data_set_by_irc(result, &rm_rc, NULL, rc_count);
4409 }
4410 break;
4411 case RESULT_TYPE_COUNT:
4412 as_bin_set_int(result->result, rm_count);
4413 break;
4414 case RESULT_TYPE_KEY:
4415 case RESULT_TYPE_VALUE:
4416 case RESULT_TYPE_MAP: {
4417 if (! packed_map_build_ele_result_by_mask(map, rm_mask, rm_count, rm_sz,
4418 result)) {
4419 cf_warning(AS_PARTICLE, "packed_map_remove_all_value_items_ordered() invalid packed map");
4420 return -AS_ERR_PARAMETER;
4421 }
4422 break;
4423 }
4424 default:
4425 cf_warning(AS_PARTICLE, "packed_map_remove_all_value_items_ordered() invalid return type %d", result->type);
4426 return -AS_ERR_OP_NOT_APPLICABLE;
4427 }
4428
4429#ifdef MAP_DEBUG_VERIFY
4430 if (! map_verify(&com->ctx)) {
4431 cdt_bin_print(com->ctx.b, "packed_map_remove_all_value_items_ordered");
4432 map_print(map, "original");
4433 cf_crash(AS_PARTICLE, "packed_map_remove_all_value_items_ordered");
4434 }
4435#endif
4436
4437 return AS_OK;
4438}
4439
4440static int
4441packed_map_get_remove_by_rel_index_range(const packed_map *map, cdt_op_mem *com,
4442 const cdt_payload *key, int64_t index, uint64_t count)
4443{
4444 uint32_t rel_index;
4445 setup_map_must_have_offidx(u, map, com->alloc_idx);
4446
4447 if (! packed_map_check_and_fill_offidx(map)) {
4448 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rel_index_range() invalid packed map");
4449 return -AS_ERR_PARAMETER;
4450 }
4451
4452 if (map_is_k_ordered(map)) {
4453 uint32_t temp;
4454
4455 packed_map_get_range_by_key_interval_ordered(map, key, key, &rel_index,
4456 &temp);
4457 }
4458 else {
4459 uint32_t temp;
4460
4461 packed_map_get_range_by_key_interval_unordered(map, key, key,
4462 &rel_index, &temp, NULL);
4463 }
4464
4465 calc_rel_index_count(index, count, rel_index, &index, &count);
4466
4467 return packed_map_get_remove_by_index_range(map, com, index, count);
4468}
4469
4470static int
4471packed_map_get_remove_by_rel_rank_range(const packed_map *map, cdt_op_mem *com,
4472 const cdt_payload *value, int64_t rank, uint64_t count)
4473{
4474 cdt_result_data *result = &com->result;
4475 uint32_t rel_rank;
4476
4477 setup_map_must_have_offidx(u, map, com->alloc_idx);
4478
4479 if (! packed_map_check_and_fill_offidx(map)) {
4480 cf_warning(AS_PARTICLE, "packed_map_get_remove_by_rel_rank_range() invalid packed map");
4481 return -AS_ERR_PARAMETER;
4482 }
4483
4484 if (! order_index_is_null(&map->ordidx)) {
4485 uint32_t temp;
4486
4487 packed_map_ensure_ordidx_filled(map);
4488 packed_map_find_rank_range_by_value_interval_indexed(map, value, value,
4489 &rel_rank, &temp, result->is_multi);
4490 }
4491 else {
4492 uint32_t temp;
4493
4494 packed_map_find_rank_range_by_value_interval_unordered(map, value,
4495 value, &rel_rank, &temp, NULL, true);
4496 }
4497
4498 calc_rel_index_count(rank, count, rel_rank, &rank, &count);
4499
4500 return packed_map_get_remove_by_rank_range(map, com, rank, count);
4501}
4502
4503static int
4504packed_map_get_remove_all(const packed_map *map, cdt_op_mem *com)
4505{
4506 cdt_result_data *result = &com->result;
4507
4508 cf_assert(! result_data_is_inverted(result), AS_PARTICLE, "packed_map_get_remove_all() INVERTED flag is invalid here");
4509
4510 if (cdt_op_is_modify(com)) {
4511 cdt_context_set_empty_packed_map(&com->ctx, map->flags);
4512 }
4513
4514 bool is_rev = false;
4515
4516 switch (result->type) {
4517 case RESULT_TYPE_NONE:
4518 break;
4519 case RESULT_TYPE_REVINDEX:
4520 case RESULT_TYPE_REVRANK:
4521 is_rev = true;
4522 // no break
4523 case RESULT_TYPE_INDEX:
4524 case RESULT_TYPE_RANK: {
4525 if (! result->is_multi) {
4526 cf_assert(map->ele_count == 1, AS_PARTICLE, "single result op with multiple results %u", map->ele_count);
4527 as_bin_set_int(result->result, 0);
4528 break;
4529 }
4530
4531 define_int_list_builder(builder, result->alloc, map->ele_count);
4532
4533 cdt_container_builder_add_int_range(&builder, 0, map->ele_count,
4534 map->ele_count, is_rev);
4535 cdt_container_builder_set_result(&builder, result);
4536 break;
4537 }
4538 case RESULT_TYPE_COUNT:
4539 as_bin_set_int(result->result, map->ele_count);
4540 break;
4541 case RESULT_TYPE_KEY:
4542 case RESULT_TYPE_VALUE:
4543 case RESULT_TYPE_MAP: {
4544 if (! packed_map_build_ele_result_by_idx_range(map, 0, map->ele_count,
4545 result)) {
4546 return -AS_ERR_UNKNOWN;
4547 }
4548 break;
4549 }
4550 case RESULT_TYPE_INDEX_RANGE:
4551 case RESULT_TYPE_REVINDEX_RANGE:
4552 case RESULT_TYPE_RANK_RANGE:
4553 case RESULT_TYPE_REVRANK_RANGE:
4554 result_data_set_list_int2x(result, 0, map->ele_count);
4555 break;
4556 default:
4557 cf_warning(AS_PARTICLE, "packed_map_get_remove_all() invalid return type %d", result->type);
4558 return -AS_ERR_OP_NOT_APPLICABLE;
4559 }
4560
4561#ifdef MAP_DEBUG_VERIFY
4562 if (! map_verify(&com->ctx)) {
4563 cdt_bin_print(com->ctx.b, "packed_map_get_remove_all");
4564 map_print(map, "original");
4565 cf_crash(AS_PARTICLE, "packed_map_get_remove_all_by_value_list");
4566 }
4567#endif
4568
4569 return AS_OK;
4570}
4571
4572static void
4573packed_map_remove_by_mask(const packed_map *map, cdt_op_mem *com,
4574 const uint64_t *rm_mask, uint32_t count, uint32_t *rm_sz_r)
4575{
4576 if (count == 0) {
4577 return;
4578 }
4579
4580 const offset_index *offidx = &map->offidx;
4581 uint32_t rm_sz = cdt_idx_mask_get_content_sz(rm_mask, count, offidx);
4582
4583 if (rm_sz_r) {
4584 *rm_sz_r = rm_sz;
4585 }
4586
4587 uint32_t new_ele_count = map->ele_count - count;
4588 uint32_t content_sz = map->content_sz - rm_sz;
4589 define_map_packer(mpk, new_ele_count, map->flags, content_sz);
4590
4591 map_packer_setup_bin(&mpk, com);
4592 mpk.write_ptr = cdt_idx_mask_write_eles(rm_mask, count, offidx,
4593 mpk.write_ptr, true);
4594
4595 if (! offset_index_is_null(&mpk.offidx)) {
4596 cf_assert(offset_index_is_full(offidx), AS_PARTICLE, "offidx not full");
4597 map_offset_index_copy_rm_mask(&mpk.offidx, offidx, rm_mask, count);
4598 }
4599
4600 if (! order_index_is_null(&mpk.ordidx)) {
4601 if (order_index_is_filled(&map->ordidx)) {
4602 order_index_op_remove_idx_mask(&mpk.ordidx, &map->ordidx, rm_mask,
4603 count);
4604 }
4605 else {
4606 order_index_set_sorted(&mpk.ordidx, &mpk.offidx, mpk.contents,
4607 mpk.content_sz, SORT_BY_VALUE);
4608 }
4609 }
4610}
4611
4612static void
4613packed_map_remove_idx_range(const packed_map *map, cdt_op_mem *com,
4614 uint32_t idx, uint32_t count)
4615{
4616 offset_index *offidx = (offset_index *)&map->offidx;
4617 uint32_t offset0 = offset_index_get_const(offidx, idx);
4618 uint32_t idx_end = idx + count;
4619 uint32_t offset1 = offset_index_get_const(offidx, idx_end);
4620 uint32_t content_sz = map->content_sz - offset1 + offset0;
4621 uint32_t new_ele_count = map->ele_count - count;
4622 define_map_packer(mpk, new_ele_count, map->flags, content_sz);
4623
4624 map_packer_setup_bin(&mpk, com);
4625
4626 uint32_t tail_sz = map->content_sz - offset1;
4627
4628 memcpy(mpk.write_ptr, map->contents, offset0);
4629 mpk.write_ptr += offset0;
4630 memcpy(mpk.write_ptr, map->contents + offset1, tail_sz);
4631
4632 if (! offset_index_is_null(&mpk.offidx)) {
4633 cf_assert(offset_index_is_full(offidx), AS_PARTICLE, "offidx not full");
4634 map_offset_index_copy_rm_range(&mpk.offidx, offidx, idx, count);
4635 }
4636
4637 if (! order_index_is_null(&mpk.ordidx)) {
4638 if (order_index_is_filled(&map->ordidx)) {
4639 uint32_t count0 = 0;
4640
4641 for (uint32_t i = 0; i < map->ele_count; i++) {
4642 uint32_t idx0 = order_index_get(&map->ordidx, i);
4643
4644 if (idx0 >= idx && idx0 < idx_end) {
4645 continue;
4646 }
4647
4648 if (idx0 >= idx_end) {
4649 idx0 -= count;
4650 }
4651
4652 order_index_set(&mpk.ordidx, count0++, idx0);
4653 }
4654 }
4655 else {
4656 order_index_set_sorted(&mpk.ordidx, &mpk.offidx, mpk.contents,
4657 mpk.content_sz, SORT_BY_VALUE);
4658 }
4659 }
4660
4661 return;
4662}
4663
4664static void
4665packed_map_get_range_by_key_interval_unordered(const packed_map *map,
4666 const cdt_payload *key_start, const cdt_payload *key_end,
4667 uint32_t *index, uint32_t *count, uint64_t *mask)
4668{
4669 cf_assert(key_end, AS_PARTICLE, "key_end == NULL");
4670
4671 msgpack_in pk_start = {
4672 .buf = key_start->ptr,
4673 .buf_sz = key_start->sz
4674 };
4675
4676 msgpack_in pk_end = {
4677 .buf = key_end->ptr,
4678 .buf_sz = key_end->sz
4679 };
4680
4681 *index = 0;
4682 *count = 0;
4683
4684 offset_index *offidx = (offset_index *)&map->offidx;
4685 define_map_msgpack_in(pk, map);
4686
4687 for (uint32_t i = 0; i < map->ele_count; i++) {
4688 uint32_t key_offset = pk.offset; // start of key
4689
4690 offset_index_set(offidx, i, key_offset);
4691
4692 pk_start.offset = 0;
4693
4694 msgpack_compare_t cmp_start = msgpack_cmp(&pk, &pk_start);
4695
4696 cf_assert(cmp_start != MSGPACK_COMPARE_ERROR, AS_PARTICLE, "packed_map_get_range_by_key_interval_unordered() invalid packed map at index %u", i);
4697
4698 if (cmp_start == MSGPACK_COMPARE_LESS) {
4699 (*index)++;
4700 }
4701 else {
4702 msgpack_compare_t cmp_end = MSGPACK_COMPARE_LESS;
4703
4704 // NULL key_end->ptr means largest possible value.
4705 if (key_end->ptr) {
4706 pk.offset = key_offset;
4707 pk_end.offset = 0;
4708 cmp_end = msgpack_cmp(&pk, &pk_end);
4709 }
4710
4711 if (cmp_end == MSGPACK_COMPARE_LESS) {
4712 cdt_idx_mask_set(mask, i);
4713 (*count)++;
4714 }
4715 }
4716
4717 // Skip value.
4718 if (msgpack_sz(&pk) == 0) {
4719 cf_crash(AS_PARTICLE, "packed_map_get_range_by_key_interval_unordered() invalid packed map at index %u", i);
4720 }
4721 }
4722
4723 offset_index_set_filled(offidx, map->ele_count);
4724}
4725
4726static void
4727packed_map_get_range_by_key_interval_ordered(const packed_map *map,
4728 const cdt_payload *key_start, const cdt_payload *key_end,
4729 uint32_t *index, uint32_t *count)
4730{
4731 map_ele_find find_key_start;
4732
4733 map_ele_find_init(&find_key_start, map);
4734 packed_map_find_key(map, &find_key_start, key_start);
4735
4736 *index = find_key_start.idx;
4737
4738 if (key_start == key_end) {
4739 if (find_key_start.found_key) {
4740 *count = 1;
4741 }
4742 else {
4743 *count = 0;
4744 }
4745 }
4746 else if (key_end && key_end->ptr) {
4747 map_ele_find find_key_end;
4748
4749 map_ele_find_continue_from_lower(&find_key_end, &find_key_start,
4750 map->ele_count);
4751 packed_map_find_key(map, &find_key_end, key_end);
4752
4753 if (find_key_end.idx <= find_key_start.idx) {
4754 *count = 0;
4755 }
4756 else {
4757 *count = find_key_end.idx - find_key_start.idx;
4758 }
4759 }
4760 else {
4761 *count = map->ele_count - find_key_start.idx;
4762 }
4763}
4764
4765// Does not respect invert flag.
4766static void
4767packed_map_build_rank_result_by_ele_idx(const packed_map *map,
4768 const order_index *ele_idx, uint32_t start, uint32_t count,
4769 cdt_result_data *result)
4770{
4771 if (! result->is_multi) {
4772 uint32_t idx = order_index_get(ele_idx, start);
4773
4774 packed_map_build_rank_result_by_idx(map, idx, result);
4775
4776 return;
4777 }
4778
4779 define_int_list_builder(builder, result->alloc, count);
4780 bool is_rev = result->type == RESULT_TYPE_REVRANK;
4781
4782 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp indexes
4783 setup_map_must_have_all_idx(uv, map, alloc_idx);
4784 packed_map_ensure_ordidx_filled(map);
4785
4786 for (uint32_t i = 0; i < count; i++) {
4787 uint32_t idx = order_index_get(ele_idx, start + i);
4788 map_ele_find find;
4789
4790 map_ele_find_init_from_idx(&find, map, idx);
4791 packed_map_find_rank_indexed(map, &find);
4792
4793 cf_assert(find.found_value, AS_PARTICLE, "packed_map_build_rank_result_by_ele_idx() idx %u not found find.rank %u", idx, find.rank);
4794
4795 cdt_container_builder_add_int_range(&builder, find.rank, 1,
4796 map->ele_count, is_rev);
4797 }
4798
4799 cdt_container_builder_set_result(&builder, result);
4800 rollback_alloc_rollback(alloc_idx);
4801}
4802
4803// Does not respect invert flag.
4804static void
4805packed_map_build_rank_result_by_mask(const packed_map *map,
4806 const uint64_t *mask, uint32_t count, cdt_result_data *result)
4807{
4808 uint32_t idx = 0;
4809
4810 if (! result->is_multi) {
4811 idx = cdt_idx_mask_find(mask, idx, map->ele_count, false);
4812 packed_map_build_rank_result_by_idx(map, idx, result);
4813 return;
4814 }
4815
4816 define_int_list_builder(builder, result->alloc, count);
4817 bool is_rev = result->type == RESULT_TYPE_REVRANK;
4818
4819 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp indexes
4820 setup_map_must_have_all_idx(uv, map, alloc_idx);
4821 packed_map_ensure_ordidx_filled(map);
4822
4823 for (uint32_t i = 0; i < count; i++) {
4824 idx = cdt_idx_mask_find(mask, idx, map->ele_count, false);
4825
4826 map_ele_find find;
4827
4828 map_ele_find_init_from_idx(&find, map, idx);
4829 packed_map_find_rank_indexed(map, &find);
4830
4831 cf_assert(find.found_value, AS_PARTICLE, "packed_map_build_rank_result_by_mask() idx %u not found find.rank %u", idx, find.rank);
4832
4833 cdt_container_builder_add_int_range(&builder, find.rank, 1,
4834 map->ele_count, is_rev);
4835 idx++;
4836 }
4837
4838 cdt_container_builder_set_result(&builder, result);
4839 rollback_alloc_rollback(alloc_idx);
4840}
4841
4842static void
4843packed_map_build_rank_result_by_index_range(const packed_map *map,
4844 uint32_t index, uint32_t count, cdt_result_data *result)
4845{
4846 if (! result->is_multi) {
4847 packed_map_build_rank_result_by_idx(map, index, result);
4848 return;
4849 }
4850
4851 cf_assert(map_is_k_ordered(map), AS_PARTICLE, "map must be K_ORDERED");
4852
4853 bool inverted = result_data_is_inverted(result);
4854 uint32_t ret_count = (inverted ? map->ele_count - count : count);
4855 define_int_list_builder(builder, result->alloc, ret_count);
4856
4857 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp indexes
4858 setup_map_must_have_all_idx(uv, map, alloc_idx);
4859 packed_map_ensure_ordidx_filled(map);
4860
4861 bool is_rev = result->type == RESULT_TYPE_REVRANK;
4862
4863 if (inverted) {
4864 for (uint32_t i = 0; i < index; i++) {
4865 map_ele_find find;
4866
4867 map_ele_find_init_from_idx(&find, map, i);
4868 packed_map_find_rank_indexed(map, &find);
4869
4870 cf_assert(find.found_value, AS_PARTICLE, "packed_map_build_rank_result_by_index_range() idx %u count %u not found find.rank %u", index, count, find.rank);
4871
4872 uint32_t rank = find.rank;
4873
4874 if (is_rev) {
4875 rank = map->ele_count - rank - 1;
4876 }
4877
4878 cdt_container_builder_add_int64(&builder, rank);
4879 }
4880
4881 for (uint32_t i = index + count; i < map->ele_count; i++) {
4882 map_ele_find find;
4883
4884 map_ele_find_init_from_idx(&find, map, i);
4885 packed_map_find_rank_indexed(map, &find);
4886
4887 cf_assert(find.found_value, AS_PARTICLE, "packed_map_build_rank_result_by_index_range() idx %u count %u not found find.rank %u", index, count, find.rank);
4888
4889 uint32_t rank = find.rank;
4890
4891 if (is_rev) {
4892 rank = map->ele_count - rank - 1;
4893 }
4894
4895 cdt_container_builder_add_int64(&builder, rank);
4896 }
4897 }
4898 else {
4899 for (uint32_t i = 0; i < count; i++) {
4900 map_ele_find find;
4901
4902 map_ele_find_init_from_idx(&find, map, index + i);
4903 packed_map_find_rank_indexed(map, &find);
4904
4905 cf_assert(find.found_value, AS_PARTICLE, "packed_map_build_rank_result_by_index_range() idx %u count %u not found find.rank %u", index, count, find.rank);
4906
4907 uint32_t rank = find.rank;
4908
4909 if (result->type == RESULT_TYPE_REVRANK) {
4910 rank = map->ele_count - rank - 1;
4911 }
4912
4913 cdt_container_builder_add_int64(&builder, rank);
4914 }
4915 }
4916
4917 cdt_container_builder_set_result(&builder, result);
4918 rollback_alloc_rollback(alloc_idx);
4919}
4920
4921static void
4922packed_map_get_key_by_idx(const packed_map *map, cdt_payload *key,
4923 uint32_t index)
4924{
4925 uint32_t pk_offset = offset_index_get_const(&map->offidx, index);
4926
4927 msgpack_in pk = {
4928 .buf = map->contents + pk_offset,
4929 .buf_sz = map->content_sz - pk_offset
4930 };
4931
4932 key->ptr = pk.buf;
4933 key->sz = msgpack_sz(&pk); // key
4934
4935 cf_assert(key->sz != 0, AS_PARTICLE, "packed_map_get_key_by_idx() read key failed offset %u", pk.offset);
4936}
4937
4938static void
4939packed_map_get_value_by_idx(const packed_map *map, cdt_payload *value,
4940 uint32_t idx)
4941{
4942 uint32_t pk_offset = offset_index_get_const(&map->offidx, idx);
4943 uint32_t sz = offset_index_get_delta_const(&map->offidx, idx);
4944
4945 msgpack_in pk = {
4946 .buf = map->contents + pk_offset,
4947 .buf_sz = map->content_sz - pk_offset
4948 };
4949
4950 uint32_t key_sz = msgpack_sz(&pk); // key
4951
4952 cf_assert(key_sz != 0, AS_PARTICLE, "packed_map_get_value_by_idx() read key failed offset %u", pk.offset);
4953
4954 value->ptr = pk.buf + key_sz;
4955 value->sz = sz - key_sz;
4956}
4957
4958static void
4959packed_map_get_pair_by_idx(const packed_map *map, cdt_payload *value,
4960 uint32_t index)
4961{
4962 uint32_t pk_offset = offset_index_get_const(&map->offidx, index);
4963 uint32_t sz = offset_index_get_delta_const(&map->offidx, index);
4964
4965 value->ptr = map->contents + pk_offset;
4966 value->sz = sz;
4967}
4968
4969// Does not respect invert flag.
4970static void
4971packed_map_build_index_result_by_ele_idx(const packed_map *map,
4972 const order_index *ele_idx, uint32_t start, uint32_t count,
4973 cdt_result_data *result)
4974{
4975 if (count == 0) {
4976 if (! result_data_set_not_found(result, start)) {
4977 cf_crash(AS_PARTICLE, "packed_map_build_index_result_by_ele_idx() invalid result type %d", result->type);
4978 }
4979
4980 return;
4981 }
4982
4983 if (! result->is_multi) {
4984 uint32_t index = order_index_get(ele_idx, start);
4985
4986 if (! map_is_k_ordered(map)) {
4987 index = packed_map_find_index_by_idx_unordered(map, index);
4988 }
4989
4990 if (result->type == RESULT_TYPE_REVINDEX) {
4991 index = map->ele_count - index - 1;
4992 }
4993
4994 as_bin_set_int(result->result, index);
4995
4996 return;
4997 }
4998
4999 define_int_list_builder(builder, result->alloc, count);
5000
5001 if (map_is_k_ordered(map)) {
5002 for (uint32_t i = 0; i < count; i++) {
5003 uint32_t index = order_index_get(ele_idx, start + i);
5004
5005 if (result->type == RESULT_TYPE_REVINDEX) {
5006 index = map->ele_count - index - 1;
5007 }
5008
5009 cdt_container_builder_add_int64(&builder, index);
5010 }
5011 }
5012 else {
5013 define_rollback_alloc(alloc_idx, NULL, 2, false);
5014 define_order_index(keyordidx, map->ele_count, alloc_idx);
5015
5016 cf_assert(offset_index_is_full(&map->offidx), AS_PARTICLE, "offidx not full");
5017 order_index_set_sorted(&keyordidx, &map->offidx, map->contents,
5018 map->content_sz, SORT_BY_KEY);
5019
5020 for (uint32_t i = 0; i < count; i++) {
5021 uint32_t idx = order_index_get(ele_idx, start + i);
5022 uint32_t index = order_index_find_idx(&keyordidx, idx, 0,
5023 map->ele_count);
5024
5025 cf_assert(index < map->ele_count, AS_PARTICLE, "idx %u index %u >= ele_count %u", idx, index, map->ele_count);
5026
5027 if (result->type == RESULT_TYPE_REVINDEX) {
5028 index = map->ele_count - index - 1;
5029 }
5030
5031 cdt_container_builder_add_int64(&builder, index);
5032 }
5033
5034 rollback_alloc_rollback(alloc_idx);
5035 }
5036
5037 cdt_container_builder_set_result(&builder, result);
5038}
5039
5040// Does not respect invert flag.
5041static void
5042packed_map_build_index_result_by_mask(const packed_map *map,
5043 const uint64_t *mask, uint32_t count, cdt_result_data *result)
5044{
5045 if (count == 0) {
5046 result_data_set_not_found(result, -1);
5047 return;
5048 }
5049
5050 if (! result->is_multi) {
5051 uint32_t index = cdt_idx_mask_find(mask, 0, map->ele_count, false);
5052
5053 if (! map_is_k_ordered(map)) {
5054 index = packed_map_find_index_by_idx_unordered(map, index);
5055 }
5056
5057 if (result->type == RESULT_TYPE_REVINDEX) {
5058 index = map->ele_count - index - 1;
5059 }
5060
5061 as_bin_set_int(result->result, index);
5062
5063 return;
5064 }
5065
5066 define_int_list_builder(builder, result->alloc, count);
5067
5068 if (map_is_k_ordered(map)) {
5069 uint32_t index = 0;
5070
5071 for (uint32_t i = 0; i < count; i++) {
5072 index = cdt_idx_mask_find(mask, index, map->ele_count, false);
5073 cdt_container_builder_add_int64(&builder,
5074 result->type == RESULT_TYPE_REVINDEX ?
5075 map->ele_count - index - 1 : index);
5076 index++;
5077 }
5078 }
5079 else {
5080 define_rollback_alloc(alloc_idx, NULL, 2, false);
5081 define_order_index(keyordidx, map->ele_count, alloc_idx);
5082 uint32_t idx = 0;
5083
5084 cf_assert(offset_index_is_full(&map->offidx), AS_PARTICLE, "offidx not full");
5085 order_index_set_sorted(&keyordidx, &map->offidx, map->contents,
5086 map->content_sz, SORT_BY_KEY);
5087
5088 for (uint32_t i = 0; i < count; i++) {
5089 idx = cdt_idx_mask_find(mask, idx, map->ele_count, false);
5090
5091 uint32_t index = order_index_find_idx(&keyordidx, idx, 0,
5092 map->ele_count);
5093
5094 cf_assert(index < map->ele_count, AS_PARTICLE, "idx %u index %u >= ele_count %u", idx, index, map->ele_count);
5095
5096 if (result->type == RESULT_TYPE_REVINDEX) {
5097 index = map->ele_count - index - 1;
5098 }
5099
5100 cdt_container_builder_add_int64(&builder, index);
5101 idx++;
5102 }
5103
5104 rollback_alloc_rollback(alloc_idx);
5105 }
5106
5107 cdt_container_builder_set_result(&builder, result);
5108}
5109
5110// Build by map ele_idx range.
5111static bool
5112packed_map_build_ele_result_by_idx_range(const packed_map *map,
5113 uint32_t start_idx, uint32_t count, cdt_result_data *result)
5114{
5115 if (! packed_map_check_and_fill_offidx(map)) {
5116 return false;
5117 }
5118
5119 bool inverted = result_data_is_inverted(result);
5120 uint32_t offset0 = offset_index_get_const(&map->offidx, start_idx);
5121 uint32_t offset1 = offset_index_get_const(&map->offidx, start_idx + count);
5122 uint32_t max_sz = offset1 - offset0;
5123 uint32_t ret_count = count;
5124 cdt_container_builder builder;
5125
5126 if (inverted) {
5127 ret_count = map->ele_count - count;
5128 max_sz = map->content_sz - max_sz;
5129 }
5130
5131 if (result->type == RESULT_TYPE_MAP) {
5132 cdt_map_builder_start(&builder, result->alloc, ret_count, max_sz,
5133 AS_PACKED_MAP_FLAG_PRESERVE_ORDER);
5134
5135 if (inverted) {
5136 uint32_t tail_sz = map->content_sz - offset1;
5137
5138 memcpy(builder.write_ptr, map->contents, offset0);
5139 builder.write_ptr += offset0;
5140 memcpy(builder.write_ptr, map->contents + offset1, tail_sz);
5141 }
5142 else {
5143 memcpy(builder.write_ptr, map->contents + offset0, max_sz);
5144 }
5145
5146 *builder.sz += max_sz;
5147 cdt_container_builder_set_result(&builder, result);
5148
5149 return true;
5150 }
5151
5152 packed_map_get_by_idx_func get_by_idx_func;
5153
5154 if (result->type == RESULT_TYPE_KEY) {
5155 get_by_idx_func = packed_map_get_key_by_idx;
5156 }
5157 else {
5158 get_by_idx_func = packed_map_get_value_by_idx;
5159 }
5160
5161 if (result->is_multi) {
5162 cdt_list_builder_start(&builder, result->alloc, ret_count, max_sz);
5163 }
5164 else {
5165 cdt_payload packed;
5166
5167 get_by_idx_func(map, &packed, start_idx);
5168
5169 return rollback_alloc_from_msgpack(result->alloc, result->result,
5170 &packed);
5171 }
5172
5173 if (inverted) {
5174 for (uint32_t i = 0; i < start_idx; i++) {
5175 cdt_payload packed;
5176
5177 get_by_idx_func(map, &packed, i);
5178 cdt_container_builder_add(&builder, packed.ptr, packed.sz);
5179 }
5180
5181 for (uint32_t i = start_idx + count; i < map->ele_count; i++) {
5182 cdt_payload packed;
5183
5184 get_by_idx_func(map, &packed, i);
5185 cdt_container_builder_add(&builder, packed.ptr, packed.sz);
5186 }
5187 }
5188 else {
5189 for (uint32_t i = 0; i < count; i++) {
5190 cdt_payload packed;
5191
5192 get_by_idx_func(map, &packed, start_idx + i);
5193 cdt_container_builder_add(&builder, packed.ptr, packed.sz);
5194 }
5195 }
5196
5197 cdt_container_builder_set_result(&builder, result);
5198
5199 return true;
5200}
5201
5202// Does not respect invert flag.
5203static bool
5204packed_map_build_ele_result_by_ele_idx(const packed_map *map,
5205 const order_index *ele_idx, uint32_t start, uint32_t count,
5206 uint32_t rm_sz, cdt_result_data *result)
5207{
5208 if (rm_sz == 0) {
5209 if (start != 0) {
5210 order_index ref;
5211
5212 order_index_init_ref(&ref, ele_idx, start, count);
5213 rm_sz = order_index_get_ele_size(&ref, count, &map->offidx);
5214 }
5215 else {
5216 rm_sz = order_index_get_ele_size(ele_idx, count, &map->offidx);
5217 }
5218 }
5219
5220 packed_map_get_by_idx_func get_by_index_func;
5221 cdt_container_builder builder;
5222 uint32_t max_sz = (count != 0 ? rm_sz : 0);
5223
5224 if (result->type == RESULT_TYPE_MAP) {
5225 get_by_index_func = packed_map_get_pair_by_idx;
5226
5227 cdt_map_builder_start(&builder, result->alloc, count, max_sz,
5228 AS_PACKED_MAP_FLAG_PRESERVE_ORDER);
5229 }
5230 else {
5231 if (result->type == RESULT_TYPE_KEY) {
5232 get_by_index_func = packed_map_get_key_by_idx;
5233 }
5234 else {
5235 get_by_index_func = packed_map_get_value_by_idx;
5236 }
5237
5238 if (result->is_multi) {
5239 cdt_list_builder_start(&builder, result->alloc, count,
5240 max_sz - count);
5241 }
5242 else if (count == 0) {
5243 return true;
5244 }
5245 else {
5246 uint32_t index = order_index_get(ele_idx, start);
5247 cdt_payload packed;
5248
5249 get_by_index_func(map, &packed, index);
5250
5251 return rollback_alloc_from_msgpack(result->alloc, result->result,
5252 &packed);
5253 }
5254 }
5255
5256 for (uint32_t i = 0; i < count; i++) {
5257 uint32_t index = order_index_get(ele_idx, i + start);
5258 cdt_payload packed;
5259
5260 get_by_index_func(map, &packed, index);
5261 cdt_container_builder_add(&builder, packed.ptr, packed.sz);
5262 }
5263
5264 cdt_container_builder_set_result(&builder, result);
5265
5266 return true;
5267}
5268
5269// Does not respect invert flag.
5270static bool
5271packed_map_build_ele_result_by_mask(const packed_map *map, const uint64_t *mask,
5272 uint32_t count, uint32_t rm_sz, cdt_result_data *result)
5273{
5274 if (! result->is_multi) {
5275 uint32_t idx = cdt_idx_mask_find(mask, 0, map->ele_count, false);
5276 define_order_index2(ele_idx, map->ele_count, 1, NULL);
5277
5278 order_index_set(&ele_idx, 0, idx);
5279
5280 return packed_map_build_ele_result_by_ele_idx(map, &ele_idx, 0, 1,
5281 rm_sz, result);
5282 }
5283
5284 if (rm_sz == 0) {
5285 rm_sz = cdt_idx_mask_get_content_sz(mask, count, &map->offidx);
5286 }
5287
5288 packed_map_get_by_idx_func get_by_index_func;
5289 cdt_container_builder builder;
5290 uint32_t max_sz = (count != 0 ? rm_sz : 0);
5291
5292 if (result->type == RESULT_TYPE_MAP) {
5293 get_by_index_func = packed_map_get_pair_by_idx;
5294
5295 cdt_map_builder_start(&builder, result->alloc, count, max_sz,
5296 AS_PACKED_MAP_FLAG_PRESERVE_ORDER);
5297 }
5298 else {
5299 if (result->type == RESULT_TYPE_KEY) {
5300 get_by_index_func = packed_map_get_key_by_idx;
5301 }
5302 else {
5303 get_by_index_func = packed_map_get_value_by_idx;
5304 }
5305
5306 cdt_list_builder_start(&builder, result->alloc, count, max_sz - count);
5307 }
5308
5309 uint32_t index = 0;
5310
5311 for (uint32_t i = 0; i < count; i++) {
5312 cdt_payload packed;
5313
5314 index = cdt_idx_mask_find(mask, index, map->ele_count, false);
5315
5316 get_by_index_func(map, &packed, index);
5317 cdt_container_builder_add(&builder, packed.ptr, packed.sz);
5318 index++;
5319 }
5320
5321 cdt_container_builder_set_result(&builder, result);
5322
5323 return true;
5324}
5325
5326static int
5327packed_map_build_result_by_key(const packed_map *map, const cdt_payload *key,
5328 uint32_t idx, uint32_t count, cdt_result_data *result)
5329{
5330 switch (result->type) {
5331 case RESULT_TYPE_NONE:
5332 break;
5333 case RESULT_TYPE_INDEX_RANGE:
5334 case RESULT_TYPE_REVINDEX_RANGE:
5335 case RESULT_TYPE_INDEX:
5336 case RESULT_TYPE_REVINDEX: {
5337 uint32_t index = idx;
5338
5339 if (! map_is_k_ordered(map)) {
5340 index = packed_map_find_index_by_key_unordered(map, key);
5341 }
5342
5343 if (result_data_is_return_index_range(result)) {
5344 if (result->type == RESULT_TYPE_REVINDEX_RANGE) {
5345 index = map->ele_count - index - count;
5346 }
5347
5348 result_data_set_list_int2x(result, index, count);
5349 }
5350 else {
5351 if (result->type == RESULT_TYPE_REVINDEX) {
5352 index = map->ele_count - index - count;
5353 }
5354
5355 as_bin_set_int(result->result, index);
5356 }
5357
5358 break;
5359 }
5360 case RESULT_TYPE_RANK:
5361 case RESULT_TYPE_REVRANK:
5362 if (result->is_multi) {
5363 packed_map_build_rank_result_by_idx_range(map, idx, count, result);
5364 break;
5365 }
5366
5367 packed_map_build_rank_result_by_idx(map, idx, result);
5368 break;
5369 case RESULT_TYPE_COUNT:
5370 as_bin_set_int(result->result, count);
5371 break;
5372 case RESULT_TYPE_KEY:
5373 case RESULT_TYPE_VALUE:
5374 case RESULT_TYPE_MAP:
5375 if (! packed_map_build_ele_result_by_idx_range(map, idx, count,
5376 result)) {
5377 return -AS_ERR_UNKNOWN;
5378 }
5379
5380 break;
5381 case RESULT_TYPE_RANK_RANGE:
5382 case RESULT_TYPE_REVRANK_RANGE:
5383 default:
5384 cf_warning(AS_PARTICLE, "packed_map_build_result_by_key() invalid result_type %d", result->type);
5385 return -AS_ERR_OP_NOT_APPLICABLE;
5386 }
5387
5388 return AS_OK;
5389}
5390
5391// Return negative codes on error.
5392static uint32_t
5393packed_map_get_rank_by_idx(const packed_map *map, uint32_t idx)
5394{
5395 cf_assert(map_has_offidx(map), AS_PARTICLE, "packed_map_get_rank_by_idx() offset_index needs to be valid");
5396
5397 uint32_t rank;
5398
5399 if (! order_index_is_null(&map->ordidx)) {
5400 packed_map_ensure_ordidx_filled(map);
5401
5402 map_ele_find find_key;
5403 map_ele_find_init_from_idx(&find_key, map, idx);
5404
5405 packed_map_find_rank_indexed(map, &find_key);
5406 cf_assert(find_key.found_value, AS_PARTICLE, "rank not found, idx=%u rank=%u", find_key.idx, find_key.rank);
5407 rank = find_key.rank;
5408 }
5409 else {
5410 const offset_index *offidx = &map->offidx;
5411 uint32_t pk_offset = offset_index_get_const(offidx, idx);
5412 define_map_msgpack_in(pk, map);
5413
5414 msgpack_in pk_entry = {
5415 .buf = map->contents + pk_offset,
5416 .buf_sz = map->content_sz - pk_offset
5417 };
5418
5419 rank = 0;
5420
5421 for (uint32_t i = 0; i < map->ele_count; i++) {
5422 pk_entry.offset = 0;
5423
5424 msgpack_compare_t cmp = packed_map_compare_values(&pk, &pk_entry);
5425
5426 cf_assert(cmp != MSGPACK_COMPARE_ERROR, AS_PARTICLE, "offset %u/%u", pk.offset, pk.buf_sz);
5427
5428 if (cmp == MSGPACK_COMPARE_LESS) {
5429 rank++;
5430 }
5431 }
5432 }
5433
5434 return rank;
5435}
5436
5437static void
5438packed_map_build_rank_result_by_idx(const packed_map *map, uint32_t idx,
5439 cdt_result_data *result)
5440{
5441 uint32_t rank = packed_map_get_rank_by_idx(map, idx);
5442
5443 if (result->type == RESULT_TYPE_REVRANK) {
5444 as_bin_set_int(result->result, (int64_t)map->ele_count - rank - 1);
5445 }
5446 else {
5447 as_bin_set_int(result->result, rank);
5448 }
5449}
5450
5451static void
5452packed_map_build_rank_result_by_idx_range(const packed_map *map, uint32_t idx,
5453 uint32_t count, cdt_result_data *result)
5454{
5455 define_int_list_builder(builder, result->alloc, count);
5456
5457 for (uint32_t i = 0; i < count; i++) {
5458 uint32_t rank = packed_map_get_rank_by_idx(map, idx);
5459
5460 if (result->type == RESULT_TYPE_REVRANK) {
5461 rank = map->ele_count - rank - 1;
5462 }
5463
5464 cdt_container_builder_add_int64(&builder, rank);
5465 }
5466
5467 cdt_container_builder_set_result(&builder, result);
5468}
5469
5470static msgpack_compare_t
5471packed_map_compare_key_by_idx(const void *ptr, uint32_t idx1, uint32_t idx2)
5472{
5473 const packed_map *map = ptr;
5474 const offset_index *offidx = &map->offidx;
5475
5476 msgpack_in pk1 = {
5477 .buf = map->contents,
5478 .buf_sz = map->content_sz,
5479 .offset = offset_index_get_const(offidx, idx1)
5480 };
5481
5482 msgpack_in pk2 = {
5483 .buf = map->contents,
5484 .buf_sz = map->content_sz,
5485 .offset = offset_index_get_const(offidx, idx2)
5486 };
5487
5488 msgpack_compare_t ret = msgpack_cmp(&pk1, &pk2);
5489
5490 if (ret == MSGPACK_COMPARE_EQUAL) {
5491 ret = msgpack_cmp_peek(&pk1, &pk2);
5492 }
5493
5494 return ret;
5495}
5496
5497static msgpack_compare_t
5498packed_map_compare_values(msgpack_in *pk1, msgpack_in *pk2)
5499{
5500 msgpack_compare_t keycmp = msgpack_cmp(pk1, pk2);
5501
5502 if (keycmp == MSGPACK_COMPARE_ERROR) {
5503 return MSGPACK_COMPARE_ERROR;
5504 }
5505
5506 msgpack_compare_t ret = msgpack_cmp(pk1, pk2);
5507
5508 if (ret == MSGPACK_COMPARE_EQUAL) {
5509 return keycmp;
5510 }
5511
5512 return ret;
5513}
5514
5515static msgpack_compare_t
5516packed_map_compare_value_by_idx(const void *ptr, uint32_t idx1, uint32_t idx2)
5517{
5518 const packed_map *map = ptr;
5519 const offset_index *offidx = &map->offidx;
5520
5521 msgpack_in pk1 = {
5522 .buf = map->contents,
5523 .buf_sz = map->content_sz,
5524 .offset = offset_index_get_const(offidx, idx1)
5525 };
5526
5527 msgpack_in pk2 = {
5528 .buf = map->contents,
5529 .buf_sz = map->content_sz,
5530 .offset = offset_index_get_const(offidx, idx2)
5531 };
5532
5533 return packed_map_compare_values(&pk1, &pk2);
5534}
5535
5536static void
5537packed_map_write_k_ordered(const packed_map *map, uint8_t *write_ptr,
5538 offset_index *offsets_new)
5539{
5540 uint32_t ele_count = map->ele_count;
5541 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp indexes
5542 define_order_index(key_ordidx, ele_count, alloc_idx);
5543
5544 order_index_set_sorted_with_offsets(&key_ordidx, &map->offidx, SORT_BY_KEY);
5545
5546 const uint8_t *ptr = map->offidx.contents;
5547 bool has_new_offsets = ! offset_index_is_null(offsets_new);
5548
5549 if (has_new_offsets) {
5550 offset_index_set_filled(offsets_new, 1);
5551 }
5552
5553 for (uint32_t i = 0; i < ele_count; i++) {
5554 uint32_t index = order_index_get(&key_ordidx, i);
5555 uint32_t offset = offset_index_get_const(&map->offidx, index);
5556 uint32_t sz = offset_index_get_delta_const(&map->offidx, index);
5557
5558 memcpy(write_ptr, ptr + offset, sz);
5559 write_ptr += sz;
5560
5561 if (has_new_offsets) {
5562 offset_index_append_size(offsets_new, sz);
5563 }
5564 }
5565
5566 rollback_alloc_rollback(alloc_idx);
5567}
5568
5569//------------------------------------------------
5570// packed_map_op
5571
5572static void
5573packed_map_op_init(packed_map_op *op, const packed_map *map)
5574{
5575 op->map = map;
5576
5577 op->new_ele_count = 0;
5578 op->ele_removed = 0;
5579
5580 op->seg1_sz = 0;
5581 op->seg2_offset = 0;
5582 op->seg2_sz = 0;
5583
5584 op->key1_offset = 0;
5585 op->key1_sz = 0;
5586 op->key2_offset = 0;
5587 op->key2_sz = 0;
5588}
5589
5590// Return new size of map elements.
5591static uint32_t
5592packed_map_op_add(packed_map_op *op, const map_ele_find *found)
5593{
5594 // Replace at offset.
5595 if (found->found_key) {
5596 op->new_ele_count = op->map->ele_count;
5597 op->seg2_offset = found->key_offset + found->sz;
5598 }
5599 // Insert at offset.
5600 else {
5601 op->new_ele_count = op->map->ele_count + 1;
5602 op->seg2_offset = found->key_offset;
5603 }
5604
5605 op->seg1_sz = found->key_offset;
5606 op->seg2_sz = op->map->content_sz - op->seg2_offset;
5607
5608 return op->seg1_sz + op->seg2_sz;
5609}
5610
5611static uint32_t
5612packed_map_op_remove(packed_map_op *op, const map_ele_find *found,
5613 uint32_t count, uint32_t remove_sz)
5614{
5615 op->new_ele_count = op->map->ele_count - count;
5616 op->seg1_sz = found->key_offset;
5617 op->seg2_offset = found->key_offset + remove_sz;
5618 op->seg2_sz = op->map->content_sz - op->seg2_offset;
5619
5620 op->ele_removed = count;
5621
5622 return op->seg1_sz + op->seg2_sz;
5623}
5624
5625static uint8_t *
5626packed_map_op_write_seg1(const packed_map_op *op, uint8_t *buf)
5627{
5628 const uint8_t *src = op->map->contents;
5629
5630 memcpy(buf, src, op->seg1_sz);
5631 memcpy(buf + op->seg1_sz, src + op->key1_offset, op->key1_sz);
5632
5633 return buf + op->seg1_sz + op->key1_sz;
5634}
5635
5636static uint8_t *
5637packed_map_op_write_seg2(const packed_map_op *op, uint8_t *buf)
5638{
5639 const uint8_t *src = op->map->contents;
5640
5641 memcpy(buf, src + op->key2_offset, op->key2_sz);
5642 memcpy(buf + op->key2_sz, src + op->seg2_offset, op->seg2_sz);
5643
5644 return buf + op->key2_sz + op->seg2_sz;
5645}
5646
5647static void
5648packed_map_op_write_new_offidx(const packed_map_op *op,
5649 const map_ele_find *remove_info, const map_ele_find *add_info,
5650 offset_index *new_offidx, uint32_t kv_sz)
5651{
5652 const offset_index *offidx = &op->map->offidx;
5653
5654 cf_assert(offset_index_is_full(offidx), AS_PARTICLE, "offidx not full");
5655 cf_assert(op->new_ele_count >= op->map->ele_count, AS_PARTICLE, "op->new_ele_count %u < op->map->ele_count %u", op->new_ele_count, op->map->ele_count);
5656
5657 uint32_t ele_count = op->map->ele_count;
5658
5659 if (op->new_ele_count - op->map->ele_count != 0) { // add 1
5660 // Insert at end.
5661 if (remove_info->idx == ele_count) {
5662 offset_index_copy(new_offidx, offidx, 0, 0, ele_count, 0);
5663 offset_index_set(new_offidx, ele_count, op->seg1_sz + op->seg2_sz);
5664 }
5665 // Insert at offset.
5666 else {
5667 offset_index_copy(new_offidx, offidx, 0, 0,
5668 remove_info->idx + 1, 0);
5669 offset_index_copy(new_offidx, offidx, remove_info->idx + 1,
5670 remove_info->idx, (ele_count - remove_info->idx), kv_sz);
5671 }
5672 }
5673 else { // replace 1
5674 cf_assert(remove_info->idx == add_info->idx, AS_PARTICLE, "remove_info->idx %u != add_info->idx %u", remove_info->idx, add_info->idx);
5675
5676 offset_index_copy(new_offidx, offidx, 0, 0, remove_info->idx, 0);
5677 offset_index_set(new_offidx, remove_info->idx, remove_info->key_offset);
5678
5679 int delta = (int)kv_sz - (int)remove_info->sz;
5680
5681 offset_index_copy(new_offidx, offidx, remove_info->idx + 1,
5682 remove_info->idx + 1, ele_count - remove_info->idx - 1, delta);
5683 }
5684
5685 offset_index_set_filled(new_offidx, op->new_ele_count);
5686}
5687
5688static void
5689packed_map_op_write_new_ordidx(const packed_map_op *op,
5690 const map_ele_find *remove_info, const map_ele_find *add_info,
5691 order_index *new_ordidx)
5692{
5693 const order_index *ordidx = &op->map->ordidx;
5694
5695 cf_assert(order_index_is_valid(ordidx), AS_PARTICLE, "ordidx invalid");
5696 cf_assert(op->new_ele_count >= op->map->ele_count, AS_PARTICLE, "op->new_ele_count %u < op->map->ele_count %u", op->new_ele_count, op->map->ele_count);
5697
5698 if (op->new_ele_count - op->map->ele_count != 0) { // add 1
5699 order_index_op_add(new_ordidx, ordidx, add_info->idx, add_info->rank);
5700 }
5701 else { // replace 1
5702 cf_assert(remove_info->idx == add_info->idx, AS_PARTICLE, "remove_info->idx %u != add_info->idx %u", remove_info->idx, add_info->idx);
5703
5704 order_index_op_replace1(new_ordidx, ordidx, add_info->rank,
5705 remove_info->rank);
5706 }
5707}
5708
5709//------------------------------------------------
5710// map_particle
5711
5712static as_particle *
5713map_particle_create(rollback_alloc *alloc_buf, uint32_t ele_count,
5714 const uint8_t *buf, uint32_t content_sz, uint8_t flags)
5715{
5716 define_map_packer(mpk, ele_count, flags, content_sz);
5717 map_mem *p_map_mem = (map_mem *)map_packer_create_particle(&mpk, alloc_buf);
5718
5719 map_packer_write_hdridx(&mpk);
5720
5721 if (buf) {
5722 memcpy(mpk.write_ptr, buf, content_sz);
5723 }
5724
5725 return (as_particle *)p_map_mem;
5726}
5727
5728// Return new size on success, negative values on failure.
5729static uint32_t
5730map_particle_strip_indexes(const as_particle *p, uint8_t *dest)
5731{
5732 const map_mem *p_map_mem = (const map_mem *)p;
5733
5734 if (p_map_mem->sz == 0) {
5735 return 0;
5736 }
5737
5738 as_unpacker upk = {
5739 .buffer = p_map_mem->data,
5740 .length = p_map_mem->sz
5741 };
5742
5743 int64_t ele_count = as_unpack_map_header_element_count(&upk);
5744
5745 cf_assert(ele_count >= 0, AS_PARTICLE, "map_particle_strip_indexes() hdr fail ele_count %ld", ele_count);
5746
5747 as_packer pk = {
5748 .buffer = dest,
5749 .capacity = INT_MAX
5750 };
5751
5752 if (ele_count > 0 && as_unpack_peek_is_ext(&upk)) {
5753 as_msgpack_ext ext;
5754
5755 if (as_unpack_ext(&upk, &ext) != 0) {
5756 cf_crash(AS_PARTICLE, "map_particle_strip_indexes() invalid ext");
5757 }
5758
5759 // Skip nil val.
5760 if (as_unpack_size(&upk) <= 0) {
5761 cf_crash(AS_PARTICLE, "map_particle_strip_indexes() expected nil");
5762 }
5763
5764 uint8_t flags = ext.type;
5765
5766 if (flags != AS_PACKED_MAP_FLAG_NONE) {
5767 ele_count--;
5768 }
5769
5770 flags &= ~(AS_PACKED_MAP_FLAG_OFF_IDX | AS_PACKED_MAP_FLAG_ORD_IDX);
5771
5772 if (flags != AS_PACKED_MAP_FLAG_NONE) {
5773 as_pack_map_header(&pk, (uint32_t)ele_count + 1);
5774 as_pack_ext_header(&pk, 0, flags);
5775 pk.buffer[pk.offset++] = msgpack_nil[0];
5776 }
5777 else {
5778 as_pack_map_header(&pk, (uint32_t)ele_count);
5779 }
5780 }
5781 else {
5782 // Copy header.
5783 as_pack_map_header(&pk, (uint32_t)ele_count);
5784 }
5785
5786 // Copy elements.
5787 uint32_t ele_sz = upk.length - upk.offset;
5788
5789 memcpy(pk.buffer + pk.offset, upk.buffer + upk.offset, ele_sz);
5790
5791 return pk.offset + ele_sz;
5792}
5793
5794//------------------------------------------------
5795// map_ele_find
5796
5797static void
5798map_ele_find_init(map_ele_find *find, const packed_map *map)
5799{
5800 find->found_key = false;
5801 find->found_value = false;
5802 find->idx = map->ele_count;
5803 find->rank = map->ele_count;
5804
5805 find->key_offset = 0;
5806 find->value_offset = 0;
5807 find->sz = 0;
5808
5809 find->lower = 0;
5810 find->upper = map->ele_count;
5811}
5812
5813static void
5814map_ele_find_continue_from_lower(map_ele_find *find, const map_ele_find *found,
5815 uint32_t ele_count)
5816{
5817 find->found_key = false;
5818 find->found_value = false;
5819
5820 find->idx = ele_count + found->idx;
5821 find->idx /= 2;
5822 find->rank = find->idx;
5823
5824 find->key_offset = found->key_offset;
5825 find->value_offset = found->value_offset;
5826 find->sz = found->sz;
5827
5828 find->lower = found->idx;
5829 find->upper = ele_count;
5830}
5831
5832static void
5833map_ele_find_init_from_idx(map_ele_find *find, const packed_map *map,
5834 uint32_t idx)
5835{
5836 map_ele_find_init(find, map);
5837 find->found_key = true;
5838 find->idx = idx;
5839 find->key_offset = offset_index_get_const(&map->offidx, idx);
5840
5841 msgpack_in pk = {
5842 .buf = map->contents,
5843 .buf_sz = map->content_sz,
5844 .offset = find->key_offset
5845 };
5846
5847 msgpack_sz(&pk);
5848 find->value_offset = pk.offset;
5849 find->sz = offset_index_get_const(&map->offidx, idx + 1) - find->key_offset;
5850}
5851
5852//------------------------------------------------
5853// map_offset_index
5854
5855static bool
5856map_offset_index_check_and_fill(offset_index *offidx, uint32_t index)
5857{
5858 uint32_t ele_filled = offset_index_get_filled(offidx);
5859
5860 if (offidx->_.ele_count <= 1 || index < ele_filled ||
5861 offidx->_.ele_count == ele_filled) {
5862 return true;
5863 }
5864
5865 msgpack_in pk = {
5866 .buf = offidx->contents,
5867 .buf_sz = offidx->content_sz
5868 };
5869
5870 pk.offset = offset_index_get_const(offidx, ele_filled - 1);
5871
5872 for (uint32_t i = ele_filled; i < index; i++) {
5873 if (msgpack_sz_rep(&pk, 2) == 0) {
5874 return false;
5875 }
5876
5877 offset_index_set(offidx, i, pk.offset);
5878 }
5879
5880 if (msgpack_sz_rep(&pk, 2) == 0) {
5881 return false;
5882 }
5883
5884 // Make sure last iteration is in range for set.
5885 if (index < offidx->_.ele_count) {
5886 offset_index_set(offidx, index, pk.offset);
5887 offset_index_set_filled(offidx, index + 1);
5888 }
5889 else if (pk.offset != offidx->content_sz) { // size doesn't match
5890 cf_warning(AS_PARTICLE, "map_offset_index_fill() offset mismatch %u, expected %u", pk.offset, offidx->content_sz);
5891 return false;
5892 }
5893 else {
5894 offset_index_set_filled(offidx, offidx->_.ele_count);
5895 }
5896
5897 return ! pk.has_nonstorage;
5898}
5899
5900static void
5901map_offset_index_copy_rm_mask(offset_index *dest, const offset_index *src,
5902 const uint64_t *rm_mask, uint32_t rm_count)
5903{
5904 uint32_t ele_count = src->_.ele_count;
5905 uint32_t rm_idx = 0;
5906 uint32_t d_i = 0;
5907 uint32_t s_i = 0;
5908 int delta_sz = 0;
5909
5910 for (uint32_t i = 0; i < rm_count; i++) {
5911 rm_idx = cdt_idx_mask_find(rm_mask, rm_idx, ele_count, false);
5912
5913 uint32_t cpy_count = rm_idx - s_i;
5914 uint32_t rm_sz = offset_index_get_delta_const(src, rm_idx);
5915
5916 offset_index_copy(dest, src, d_i, s_i, cpy_count, delta_sz);
5917 delta_sz -= rm_sz;
5918 d_i += cpy_count;
5919 s_i += cpy_count + 1;
5920
5921 rm_idx++;
5922 }
5923
5924 uint32_t tail_count = ele_count - s_i;
5925
5926 offset_index_copy(dest, src, d_i, s_i, tail_count, delta_sz);
5927 d_i += tail_count;
5928 offset_index_set_filled(dest, d_i);
5929}
5930
5931static void
5932map_offset_index_copy_rm_range(offset_index *dest, const offset_index *src,
5933 uint32_t rm_idx, uint32_t rm_count)
5934{
5935 offset_index_copy(dest, src, 0, 0, rm_idx, 0); // copy head
5936
5937 uint32_t rm_end = rm_idx + rm_count;
5938 uint32_t tail_count = src->_.ele_count - rm_end;
5939 uint32_t mem_sz = offset_index_get_const(src, rm_end) -
5940 offset_index_get_const(src, rm_idx);
5941
5942 offset_index_copy(dest, src, rm_idx, rm_end, tail_count, -(int)mem_sz); // copy tail
5943 offset_index_set_filled(dest, rm_idx + tail_count);
5944}
5945
5946//------------------------------------------------
5947// order_index
5948
5949static void
5950order_index_sort(order_index *ordidx, const offset_index *offsets,
5951 const uint8_t *contents, uint32_t content_sz, sort_by_t sort_by)
5952{
5953 uint32_t ele_count = ordidx->_.ele_count;
5954
5955 index_sort_userdata udata = {
5956 .order = ordidx,
5957 .offsets = offsets,
5958 .contents = contents,
5959 .content_sz = content_sz,
5960 .sort_by = sort_by
5961 };
5962
5963 if (ele_count <= 1) {
5964 return;
5965 }
5966
5967 qsort_r(order_index_get_mem(ordidx, 0), ele_count, ordidx->_.ele_sz,
5968 map_packer_fill_index_sort_compare, (void *)&udata);
5969}
5970
5971static inline void
5972order_index_set_sorted(order_index *ordidx, const offset_index *offsets,
5973 const uint8_t *ele_start, uint32_t tot_ele_sz, sort_by_t sort_by)
5974{
5975 uint32_t ele_count = ordidx->_.ele_count;
5976
5977 if (ele_count <= 1) {
5978 if (order_index_is_null(ordidx)) {
5979 return;
5980 }
5981
5982 if (ele_count == 1) {
5983 order_index_set(ordidx, 0, 0);
5984 }
5985
5986 return;
5987 }
5988
5989 cf_assert(! order_index_is_null(ordidx), AS_PARTICLE, "ordidx NULL");
5990
5991 for (uint32_t i = 0; i < ele_count; i++) {
5992 order_index_set(ordidx, i, i);
5993 }
5994
5995 order_index_sort(ordidx, offsets, ele_start, tot_ele_sz, sort_by);
5996}
5997
5998static void
5999order_index_set_sorted_with_offsets(order_index *ordidx,
6000 const offset_index *offsets, sort_by_t sort_by)
6001{
6002 order_index_set_sorted(ordidx, offsets, offsets->contents,
6003 offsets->content_sz, sort_by);
6004}
6005
6006static uint32_t
6007order_index_find_idx(const order_index *ordidx, uint32_t idx, uint32_t start,
6008 uint32_t len)
6009{
6010 for (uint32_t i = start; i < start + len; i++) {
6011 if (order_index_get(ordidx, i) == idx) {
6012 return i;
6013 }
6014 }
6015
6016 return start + len;
6017}
6018
6019//------------------------------------------------
6020// order_index_adjust
6021
6022static uint32_t
6023order_index_adjust_lower(const order_index_adjust *via, uint32_t src)
6024{
6025 if (src >= via->lower) {
6026 return src + via->delta;
6027 }
6028
6029 return src;
6030}
6031
6032//------------------------------------------------
6033// order_index_op
6034
6035static inline void
6036order_index_op_add(order_index *dest, const order_index *src, uint32_t add_idx,
6037 uint32_t add_rank)
6038{
6039 uint32_t ele_count = src->_.ele_count;
6040
6041 order_index_adjust adjust = {
6042 .f = order_index_adjust_lower,
6043 .lower = add_idx,
6044 .upper = 0,
6045 .delta = 1
6046 };
6047
6048 cf_assert(add_rank <= ele_count, AS_PARTICLE, "order_index_op_add() add_rank(%u) > ele_count(%u)", add_rank, ele_count);
6049 order_index_copy(dest, src, 0, 0, add_rank, &adjust);
6050 order_index_set(dest, add_rank, add_idx);
6051 order_index_copy(dest, src, add_rank + 1, add_rank, ele_count - add_rank,
6052 &adjust);
6053}
6054
6055static inline void
6056order_index_op_replace1_internal(order_index *dest, const order_index *src,
6057 uint32_t add_idx, uint32_t add_rank, uint32_t remove_rank,
6058 const order_index_adjust *adjust)
6059{
6060 uint32_t ele_count = src->_.ele_count;
6061
6062 if (add_rank == remove_rank) {
6063 order_index_copy(dest, src, 0, 0, ele_count, NULL);
6064 }
6065 else if (add_rank > remove_rank) {
6066 order_index_copy(dest, src, 0, 0, remove_rank, adjust);
6067 order_index_copy(dest, src, remove_rank, remove_rank + 1,
6068 add_rank - remove_rank - 1, adjust);
6069 order_index_set(dest, add_rank - 1, add_idx);
6070 order_index_copy(dest, src, add_rank, add_rank, ele_count - add_rank,
6071 adjust);
6072 }
6073 else {
6074 order_index_copy(dest, src, 0, 0, add_rank, adjust);
6075 order_index_set(dest, add_rank, add_idx);
6076 order_index_copy(dest, src, add_rank + 1, add_rank,
6077 remove_rank - add_rank, adjust);
6078 order_index_copy(dest, src, remove_rank + 1, remove_rank + 1,
6079 ele_count - remove_rank - 1, adjust);
6080 }
6081}
6082
6083// Replace remove_rank with add_rank in dest.
6084static inline void
6085order_index_op_replace1(order_index *dest, const order_index *src,
6086 uint32_t add_rank, uint32_t remove_rank)
6087{
6088 uint32_t add_idx = order_index_get(src, remove_rank);
6089
6090 order_index_op_replace1_internal(dest, src, add_idx, add_rank, remove_rank,
6091 NULL);
6092}
6093
6094static void
6095order_index_op_remove_idx_mask(order_index *dest, const order_index *src,
6096 const uint64_t *mask, uint32_t count)
6097{
6098 if (count == 0) {
6099 return;
6100 }
6101
6102 uint32_t ele_count = src->max_idx;
6103 uint32_t mask_count = cdt_idx_mask_count(ele_count);
6104 define_rollback_alloc(alloc_idx, NULL, 2, false); // for temp indexes
6105 define_order_index2(cntidx, ele_count, mask_count, alloc_idx);
6106
6107 order_index_set(&cntidx, 0, cf_bit_count64(mask[0]));
6108
6109 for (uint32_t i = 1; i < mask_count; i++) {
6110 uint32_t prev = order_index_get(&cntidx, i - 1);
6111
6112 order_index_set(&cntidx, i, prev + cf_bit_count64(mask[i]));
6113 }
6114
6115 uint32_t di = 0;
6116
6117 for (uint32_t i = 0; i < ele_count; i++) {
6118 uint32_t idx = order_index_get(src, i);
6119
6120 if (idx >= ele_count || cdt_idx_mask_is_set(mask, idx)) {
6121 continue;
6122 }
6123
6124 uint32_t mask_i = idx / 64;
6125 uint32_t offset = idx % 64;
6126 uint64_t bits = cdt_idx_mask_get(mask, idx) & ((1ULL << offset) - 1);
6127
6128 if (mask_i == 0) {
6129 idx -= cf_bit_count64(bits);
6130 }
6131 else {
6132 idx -= cf_bit_count64(bits) + order_index_get(&cntidx, mask_i - 1);
6133 }
6134
6135 order_index_set(dest, di++, idx);
6136 }
6137
6138 rollback_alloc_rollback(alloc_idx);
6139 cf_assert(dest->_.ele_count == di, AS_PARTICLE, "count mismatch ele_count %u != di %u", dest->_.ele_count, di);
6140}
6141
6142
6143//==========================================================
6144// result_data
6145
6146static bool
6147result_data_set_key_not_found(cdt_result_data *rd, int64_t index)
6148{
6149 switch (rd->type) {
6150 case RESULT_TYPE_RANK_RANGE:
6151 case RESULT_TYPE_REVRANK_RANGE:
6152 break;
6153 default:
6154 return result_data_set_not_found(rd, index);
6155 }
6156
6157 return false;
6158}
6159
6160static bool
6161result_data_set_value_not_found(cdt_result_data *rd, int64_t rank)
6162{
6163 switch (rd->type) {
6164 case RESULT_TYPE_REVINDEX_RANGE:
6165 case RESULT_TYPE_INDEX_RANGE:
6166 return false;
6167 default:
6168 return result_data_set_not_found(rd, rank);
6169 }
6170
6171 return true;
6172}
6173
6174
6175//==========================================================
6176// cdt_map_builder
6177//
6178
6179void
6180cdt_map_builder_start(cdt_container_builder *builder, rollback_alloc *alloc_buf,
6181 uint32_t ele_count, uint32_t max_sz, uint8_t flags)
6182{
6183 uint32_t sz = sizeof(map_mem) + sizeof(uint64_t) + 1 + 3 + max_sz;
6184 map_mem *p_map_mem = (map_mem *)rollback_alloc_reserve(alloc_buf, sz);
6185
6186 as_packer pk = {
6187 .buffer = p_map_mem->data,
6188 .capacity = INT_MAX
6189 };
6190
6191 if (flags != AS_PACKED_MAP_FLAG_NONE) {
6192 as_pack_map_header(&pk, ele_count + 1);
6193 as_pack_ext_header(&pk, 0, flags);
6194 pk.buffer[pk.offset++] = msgpack_nil[0];
6195 }
6196 else {
6197 as_pack_map_header(&pk, ele_count);
6198 }
6199
6200 p_map_mem->type = AS_PARTICLE_TYPE_MAP;
6201 p_map_mem->sz = pk.offset;
6202
6203 builder->particle = (as_particle *)p_map_mem;
6204 builder->write_ptr = p_map_mem->data + p_map_mem->sz;
6205 builder->ele_count = 0;
6206 builder->sz = &p_map_mem->sz;
6207}
6208
6209
6210//==========================================================
6211// cdt_process_state_packed_map
6212//
6213
6214bool
6215cdt_process_state_packed_map_modify_optype(cdt_process_state *state,
6216 cdt_op_mem *com)
6217{
6218 cdt_context *ctx = &com->ctx;
6219 as_cdt_optype optype = state->type;
6220
6221 if (ctx->data_sz == 0 && as_bin_inuse(ctx->b) &&
6222 ! is_map_type(as_bin_get_particle_type(ctx->b))) {
6223 cf_warning(AS_PARTICLE, "cdt_process_state_packed_map_modify_optype() invalid type %d", as_bin_get_particle_type(ctx->b));
6224 com->ret_code = -AS_ERR_INCOMPATIBLE_TYPE;
6225 return false;
6226 }
6227
6228 int ret = AS_OK;
6229
6230 switch (optype) {
6231 case AS_CDT_OP_MAP_SET_TYPE: {
6232 uint64_t flags;
6233
6234 if (! CDT_OP_TABLE_GET_PARAMS(state, &flags)) {
6235 com->ret_code = -AS_ERR_PARAMETER;
6236 return false;
6237 }
6238
6239 cdt_context_use_static_map_if_notinuse(ctx, 0);
6240 ret = map_set_flags(com, (uint8_t)flags);
6241 break;
6242 }
6243 case AS_CDT_OP_MAP_ADD: {
6244 cdt_payload key;
6245 cdt_payload value;
6246 uint64_t flags = 0;
6247
6248 if (! CDT_OP_TABLE_GET_PARAMS(state, &key, &value, &flags)) {
6249 com->ret_code = -AS_ERR_PARAMETER;
6250 return false;
6251 }
6252
6253 map_add_control control = {
6254 .allow_overwrite = false,
6255 .allow_create = true,
6256 };
6257
6258 cdt_context_use_static_map_if_notinuse(ctx, flags);
6259 ret = map_add(com, &key, &value, &control, true);
6260 break;
6261 }
6262 case AS_CDT_OP_MAP_ADD_ITEMS: {
6263 cdt_payload items;
6264 uint64_t flags = 0;
6265
6266 if (! CDT_OP_TABLE_GET_PARAMS(state, &items, &flags)) {
6267 com->ret_code = -AS_ERR_PARAMETER;
6268 return false;
6269 }
6270
6271 map_add_control control = {
6272 .allow_overwrite = false,
6273 .allow_create = true,
6274 };
6275
6276 cdt_context_use_static_map_if_notinuse(ctx, flags);
6277 ret = map_add_items(com, &items, &control);
6278 break;
6279 }
6280 case AS_CDT_OP_MAP_PUT: {
6281 cdt_payload key;
6282 cdt_payload value;
6283 uint64_t flags = 0;
6284 uint64_t modify = 0;
6285
6286 if (! CDT_OP_TABLE_GET_PARAMS(state, &key, &value, &flags, &modify)) {
6287 com->ret_code = -AS_ERR_PARAMETER;
6288 return false;
6289 }
6290
6291 map_add_control control = {
6292 .allow_overwrite = ! (modify & AS_CDT_MAP_NO_OVERWRITE),
6293 .allow_create = ! (modify & AS_CDT_MAP_NO_CREATE),
6294 .no_fail = modify & AS_CDT_MAP_NO_FAIL,
6295 .do_partial = modify & AS_CDT_MAP_DO_PARTIAL
6296 };
6297
6298 cdt_context_use_static_map_if_notinuse(ctx, flags);
6299 ret = map_add(com, &key, &value, &control, true);
6300 break;
6301 }
6302 case AS_CDT_OP_MAP_PUT_ITEMS: {
6303 cdt_payload items;
6304 uint64_t flags = 0;
6305 uint64_t modify = 0;
6306
6307 if (! CDT_OP_TABLE_GET_PARAMS(state, &items, &flags, &modify)) {
6308 com->ret_code = -AS_ERR_PARAMETER;
6309 return false;
6310 }
6311
6312 map_add_control control = {
6313 .allow_overwrite = ! (modify & AS_CDT_MAP_NO_OVERWRITE),
6314 .allow_create = ! (modify & AS_CDT_MAP_NO_CREATE),
6315 .no_fail = modify & AS_CDT_MAP_NO_FAIL,
6316 .do_partial = modify & AS_CDT_MAP_DO_PARTIAL
6317 };
6318
6319 cdt_context_use_static_map_if_notinuse(ctx, flags);
6320 ret = map_add_items(com, &items, &control);
6321 break;
6322 }
6323 case AS_CDT_OP_MAP_REPLACE: {
6324 cdt_payload key;
6325 cdt_payload value;
6326
6327 if (! CDT_OP_TABLE_GET_PARAMS(state, &key, &value)) {
6328 com->ret_code = -AS_ERR_PARAMETER;
6329 return false;
6330 }
6331
6332 map_add_control control = {
6333 .allow_overwrite = true,
6334 .allow_create = false,
6335 };
6336
6337 cdt_context_use_static_map_if_notinuse(ctx, 0);
6338 ret = map_add(com, &key, &value, &control, true);
6339 break;
6340 }
6341 case AS_CDT_OP_MAP_REPLACE_ITEMS: {
6342 if (! as_bin_inuse(ctx->b)) {
6343 com->ret_code = -AS_ERR_ELEMENT_NOT_FOUND;
6344 return false;
6345 }
6346
6347 cdt_payload items;
6348
6349 if (! CDT_OP_TABLE_GET_PARAMS(state, &items)) {
6350 com->ret_code = -AS_ERR_PARAMETER;
6351 return false;
6352 }
6353
6354 map_add_control control = {
6355 .allow_overwrite = true,
6356 .allow_create = false,
6357 };
6358
6359 ret = map_add_items(com, &items, &control);
6360 break;
6361 }
6362 case AS_CDT_OP_MAP_INCREMENT:
6363 case AS_CDT_OP_MAP_DECREMENT: {
6364 cdt_payload key;
6365 cdt_payload delta_value = { NULL };
6366 uint64_t flags = 0;
6367
6368 if (! CDT_OP_TABLE_GET_PARAMS(state, &key, &delta_value, &flags)) {
6369 com->ret_code = -AS_ERR_PARAMETER;
6370 return false;
6371 }
6372
6373 cdt_context_use_static_map_if_notinuse(ctx, flags);
6374 ret = map_increment(com, &key, &delta_value,
6375 optype == AS_CDT_OP_MAP_DECREMENT);
6376 break;
6377 }
6378 case AS_CDT_OP_MAP_REMOVE_BY_KEY: {
6379 if (! as_bin_inuse(ctx->b)) {
6380 return true; // no-op
6381 }
6382
6383 uint64_t op_flags;
6384 cdt_payload key;
6385
6386 if (! CDT_OP_TABLE_GET_PARAMS(state, &op_flags, &key)) {
6387 com->ret_code = -AS_ERR_PARAMETER;
6388 return false;
6389 }
6390
6391 result_data_set(&com->result, op_flags, false);
6392 ret = map_remove_by_key_interval(com, &key, &key);
6393 break;
6394 }
6395 case AS_CDT_OP_MAP_REMOVE_BY_INDEX: {
6396 if (! as_bin_inuse(ctx->b)) {
6397 return true; // no-op
6398 }
6399
6400 uint64_t result_type;
6401 int64_t index;
6402
6403 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index)) {
6404 com->ret_code = -AS_ERR_PARAMETER;
6405 return false;
6406 }
6407
6408 result_data_set(&com->result, result_type, false);
6409 ret = map_remove_by_index_range(com, index, 1);
6410 break;
6411 }
6412 case AS_CDT_OP_MAP_REMOVE_BY_VALUE: {
6413 if (! as_bin_inuse(ctx->b)) {
6414 return true; // no-op
6415 }
6416
6417 uint64_t result_type;
6418 cdt_payload value;
6419
6420 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value)) {
6421 com->ret_code = -AS_ERR_PARAMETER;
6422 return false;
6423 }
6424
6425 result_data_set(&com->result, result_type, false);
6426 ret = map_remove_by_value_interval(com, &value, &value);
6427 break;
6428 }
6429 case AS_CDT_OP_MAP_REMOVE_BY_RANK: {
6430 if (! as_bin_inuse(ctx->b)) {
6431 return true; // no-op
6432 }
6433
6434 uint64_t result_type;
6435 int64_t index;
6436
6437 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index)) {
6438 com->ret_code = -AS_ERR_PARAMETER;
6439 return false;
6440 }
6441
6442 result_data_set(&com->result, result_type, false);
6443 ret = map_remove_by_rank_range(com, index, 1);
6444 break;
6445 }
6446 case AS_CDT_OP_MAP_REMOVE_BY_KEY_LIST: {
6447 if (! as_bin_inuse(ctx->b)) {
6448 return true; // no-op
6449 }
6450
6451 uint64_t result_type;
6452 cdt_payload items;
6453
6454 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &items)) {
6455 com->ret_code = -AS_ERR_PARAMETER;
6456 return false;
6457 }
6458
6459 result_data_set(&com->result, result_type, true);
6460 ret = map_remove_all_by_key_list(com, &items);
6461 break;
6462 }
6463 case AS_CDT_OP_MAP_REMOVE_ALL_BY_VALUE: {
6464 if (! as_bin_inuse(ctx->b)) {
6465 return true; // no-op
6466 }
6467
6468 uint64_t result_type;
6469 cdt_payload value;
6470
6471 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value)) {
6472 com->ret_code = -AS_ERR_PARAMETER;
6473 return false;
6474 }
6475
6476 result_data_set(&com->result, result_type, true);
6477 ret = map_remove_by_value_interval(com, &value, &value);
6478 break;
6479 }
6480 case AS_CDT_OP_MAP_REMOVE_BY_VALUE_LIST: {
6481 if (! as_bin_inuse(ctx->b)) {
6482 return true; // no-op
6483 }
6484
6485 uint64_t result_type;
6486 cdt_payload items;
6487
6488 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &items)) {
6489 com->ret_code = -AS_ERR_PARAMETER;
6490 return false;
6491 }
6492
6493 result_data_set(&com->result, result_type, true);
6494 ret = map_remove_all_by_value_list(com, &items);
6495 break;
6496 }
6497 case AS_CDT_OP_MAP_REMOVE_BY_KEY_INTERVAL: {
6498 if (! as_bin_inuse(ctx->b)) {
6499 return true; // no-op
6500 }
6501
6502 uint64_t result_type;
6503 cdt_payload key_start;
6504 cdt_payload key_end = { NULL };
6505
6506 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &key_start,
6507 &key_end)) {
6508 com->ret_code = -AS_ERR_PARAMETER;
6509 return false;
6510 }
6511
6512 result_data_set(&com->result, result_type, true);
6513 ret = map_remove_by_key_interval(com, &key_start, &key_end);
6514 break;
6515 }
6516 case AS_CDT_OP_MAP_REMOVE_BY_INDEX_RANGE: {
6517 if (! as_bin_inuse(ctx->b)) {
6518 return true; // no-op
6519 }
6520
6521 uint64_t result_type;
6522 int64_t index;
6523 uint64_t count = UINT32_MAX;
6524
6525 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index, &count)) {
6526 com->ret_code = -AS_ERR_PARAMETER;
6527 return false;
6528 }
6529
6530 result_data_set(&com->result, result_type, true);
6531 ret = map_remove_by_index_range(com, index, count);
6532 break;
6533 }
6534 case AS_CDT_OP_MAP_REMOVE_BY_VALUE_INTERVAL: {
6535 if (! as_bin_inuse(ctx->b)) {
6536 return true; // no-op
6537 }
6538
6539 uint64_t result_type;
6540 cdt_payload value_start;
6541 cdt_payload value_end = { NULL };
6542
6543 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value_start,
6544 &value_end)) {
6545 com->ret_code = -AS_ERR_PARAMETER;
6546 return false;
6547 }
6548
6549 result_data_set(&com->result, result_type, true);
6550 ret = map_remove_by_value_interval(com, &value_start, &value_end);
6551 break;
6552 }
6553 case AS_CDT_OP_MAP_REMOVE_BY_RANK_RANGE: {
6554 if (! as_bin_inuse(ctx->b)) {
6555 return true; // no-op
6556 }
6557
6558 uint64_t result_type;
6559 int64_t rank;
6560 uint64_t count = UINT32_MAX;
6561
6562 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &rank, &count)) {
6563 com->ret_code = -AS_ERR_PARAMETER;
6564 return false;
6565 }
6566
6567 result_data_set(&com->result, result_type, true);
6568 ret = map_remove_by_rank_range(com, rank, count);
6569 break;
6570 }
6571 case AS_CDT_OP_MAP_REMOVE_BY_KEY_REL_INDEX_RANGE: {
6572 if (! as_bin_inuse(ctx->b)) {
6573 return true; // no-op
6574 }
6575
6576 uint64_t result_type;
6577 cdt_payload value;
6578 int64_t index;
6579 uint64_t count = UINT32_MAX;
6580
6581 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value, &index,
6582 &count)) {
6583 com->ret_code = -AS_ERR_PARAMETER;
6584 return false;
6585 }
6586
6587 result_data_set(&com->result, result_type, true);
6588 ret = map_remove_by_rel_index_range(com, &value, index, count);
6589 break;
6590 }
6591 case AS_CDT_OP_MAP_REMOVE_BY_VALUE_REL_RANK_RANGE: {
6592 if (! as_bin_inuse(ctx->b)) {
6593 return true; // no-op
6594 }
6595
6596 uint64_t result_type;
6597 cdt_payload value;
6598 int64_t rank;
6599 uint64_t count = UINT32_MAX;
6600
6601 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value, &rank,
6602 &count)) {
6603 com->ret_code = -AS_ERR_PARAMETER;
6604 return false;
6605 }
6606
6607 result_data_set(&com->result, result_type, true);
6608 ret = map_remove_by_rel_rank_range(com, &value, rank, count);
6609 break;
6610 }
6611 case AS_CDT_OP_MAP_CLEAR: {
6612 if (! as_bin_inuse(ctx->b)) {
6613 return true; // no-op
6614 }
6615
6616 ret = map_clear(com);
6617 break;
6618 }
6619 default:
6620 cf_warning(AS_PARTICLE, "cdt_process_state_packed_map_modify_optype() invalid cdt op: %d", optype);
6621 com->ret_code = -AS_ERR_PARAMETER;
6622 return false;
6623 }
6624
6625 if (ret != AS_OK) {
6626 cf_warning(AS_PARTICLE, "%s: failed", cdt_process_state_get_op_name(state));
6627 com->ret_code = ret;
6628 return false;
6629 }
6630
6631 if (ctx->b->particle == (const as_particle *)&map_mem_empty) {
6632 cdt_context_set_empty_packed_map(ctx, 0);
6633 }
6634 else if (ctx->b->particle == (const as_particle *)&map_mem_empty_k) {
6635 cdt_context_set_empty_packed_map(ctx,
6636 map_mem_empty_k.data[MAP_EMPTY_EXT_FLAGS]);
6637 }
6638 else if (ctx->b->particle == (const as_particle *)&map_mem_empty_kv) {
6639 cdt_context_set_empty_packed_map(ctx,
6640 map_mem_empty_kv.data[MAP_EMPTY_EXT_FLAGS]);
6641 }
6642
6643 return true;
6644}
6645
6646bool
6647cdt_process_state_packed_map_read_optype(cdt_process_state *state,
6648 cdt_op_mem *com)
6649{
6650 const cdt_context *ctx = &com->ctx;
6651 as_cdt_optype optype = state->type;
6652
6653 if (ctx->data_sz == 0 && ! is_map_type(as_bin_get_particle_type(ctx->b))) {
6654 com->ret_code = -AS_ERR_INCOMPATIBLE_TYPE;
6655 return false;
6656 }
6657
6658 packed_map map;
6659
6660 if (! packed_map_init_from_ctx(&map, ctx, false)) {
6661 cf_warning(AS_PARTICLE, "%s: invalid map", cdt_process_state_get_op_name(state));
6662 com->ret_code = -AS_ERR_PARAMETER;
6663 return false;
6664 }
6665
6666 int ret = AS_OK;
6667 cdt_result_data *result = &com->result;
6668
6669 switch (optype) {
6670 case AS_CDT_OP_MAP_SIZE: {
6671 as_bin_set_int(result->result, map.ele_count);
6672 break;
6673 }
6674 case AS_CDT_OP_MAP_GET_BY_KEY: {
6675 uint64_t op_flags;
6676 cdt_payload key;
6677
6678 if (! CDT_OP_TABLE_GET_PARAMS(state, &op_flags, &key)) {
6679 com->ret_code = -AS_ERR_PARAMETER;
6680 return false;
6681 }
6682
6683 result_data_set(&com->result, op_flags, false);
6684 ret = packed_map_get_remove_by_key_interval(&map, com, &key, &key);
6685 break;
6686 }
6687 case AS_CDT_OP_MAP_GET_BY_VALUE: {
6688 uint64_t result_type;
6689 cdt_payload value;
6690
6691 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value)) {
6692 com->ret_code = -AS_ERR_PARAMETER;
6693 return false;
6694 }
6695
6696 result_data_set(&com->result, result_type, false);
6697 ret = packed_map_get_remove_by_value_interval(&map, com, &value,
6698 &value);
6699 break;
6700 }
6701 case AS_CDT_OP_MAP_GET_BY_INDEX: {
6702 uint64_t result_type;
6703 int64_t index;
6704
6705 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index)) {
6706 com->ret_code = -AS_ERR_PARAMETER;
6707 return false;
6708 }
6709
6710 result_data_set(&com->result, result_type, false);
6711 ret = packed_map_get_remove_by_index_range(&map, com, index, 1);
6712 break;
6713 }
6714 case AS_CDT_OP_MAP_GET_BY_RANK: {
6715 uint64_t result_type;
6716 int64_t rank;
6717
6718 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &rank)) {
6719 com->ret_code = -AS_ERR_PARAMETER;
6720 return false;
6721 }
6722
6723 result_data_set(&com->result, result_type, false);
6724 ret = packed_map_get_remove_by_rank_range(&map, com, rank, 1);
6725 break;
6726 }
6727 case AS_CDT_OP_MAP_GET_ALL_BY_VALUE: {
6728 uint64_t result_type;
6729 cdt_payload value;
6730
6731 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value)) {
6732 com->ret_code = -AS_ERR_PARAMETER;
6733 return false;
6734 }
6735
6736 result_data_set(&com->result, result_type, true);
6737 ret = packed_map_get_remove_by_value_interval(&map, com, &value,
6738 &value);
6739 break;
6740 }
6741 case AS_CDT_OP_MAP_GET_BY_KEY_INTERVAL: {
6742 uint64_t result_type;
6743 cdt_payload key_start;
6744 cdt_payload key_end = { NULL };
6745
6746 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &key_start,
6747 &key_end)) {
6748 com->ret_code = -AS_ERR_PARAMETER;
6749 return false;
6750 }
6751
6752 result_data_set(&com->result, result_type, true);
6753 ret = packed_map_get_remove_by_key_interval(&map, com, &key_start,
6754 &key_end);
6755 break;
6756 }
6757 case AS_CDT_OP_MAP_GET_BY_VALUE_INTERVAL: {
6758 uint64_t result_type;
6759 cdt_payload value_start;
6760 cdt_payload value_end = { NULL };
6761
6762 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value_start,
6763 &value_end)) {
6764 com->ret_code = -AS_ERR_PARAMETER;
6765 return false;
6766 }
6767
6768 result_data_set(&com->result, result_type, true);
6769 ret = packed_map_get_remove_by_value_interval(&map, com, &value_start,
6770 &value_end);
6771 break;
6772 }
6773 case AS_CDT_OP_MAP_GET_BY_INDEX_RANGE: {
6774 uint64_t result_type;
6775 int64_t index;
6776 uint64_t count = UINT32_MAX;
6777
6778 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index, &count)) {
6779 com->ret_code = -AS_ERR_PARAMETER;
6780 return false;
6781 }
6782
6783 result_data_set(&com->result, result_type, true);
6784 ret = packed_map_get_remove_by_index_range(&map, com, index, count);
6785 break;
6786 }
6787 case AS_CDT_OP_MAP_GET_BY_RANK_RANGE: {
6788 uint64_t result_type;
6789 int64_t rank;
6790 uint64_t count = UINT32_MAX;
6791
6792 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &rank, &count)) {
6793 com->ret_code = -AS_ERR_PARAMETER;
6794 return false;
6795 }
6796
6797 result_data_set(&com->result, result_type, true);
6798 ret = packed_map_get_remove_by_rank_range(&map, com, rank, count);
6799 break;
6800 }
6801 case AS_CDT_OP_MAP_GET_BY_KEY_LIST: {
6802 uint64_t result_type;
6803 cdt_payload items;
6804
6805 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &items)) {
6806 com->ret_code = -AS_ERR_PARAMETER;
6807 return false;
6808 }
6809
6810 result_data_set(&com->result, result_type, true);
6811 ret = packed_map_get_remove_all_by_key_list(&map, com, &items);
6812 break;
6813 }
6814 case AS_CDT_OP_MAP_GET_BY_VALUE_LIST: {
6815 uint64_t result_type;
6816 cdt_payload items;
6817
6818 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &items)) {
6819 com->ret_code = -AS_ERR_PARAMETER;
6820 return false;
6821 }
6822
6823 result_data_set(&com->result, result_type, true);
6824 ret = packed_map_get_remove_all_by_value_list(&map, com, &items);
6825 break;
6826 }
6827 case AS_CDT_OP_MAP_GET_BY_KEY_REL_INDEX_RANGE: {
6828 uint64_t result_type;
6829 cdt_payload value;
6830 int64_t index;
6831 uint64_t count = UINT32_MAX;
6832
6833 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value, &index,
6834 &count)) {
6835 com->ret_code = -AS_ERR_PARAMETER;
6836 return false;
6837 }
6838
6839 result_data_set(&com->result, result_type, true);
6840 ret = packed_map_get_remove_by_rel_index_range(&map, com, &value, index,
6841 count);
6842 break;
6843 }
6844 case AS_CDT_OP_MAP_GET_BY_VALUE_REL_RANK_RANGE: {
6845 uint64_t result_type;
6846 cdt_payload value;
6847 int64_t rank;
6848 uint64_t count = UINT32_MAX;
6849
6850 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value, &rank,
6851 &count)) {
6852 com->ret_code = -AS_ERR_PARAMETER;
6853 return false;
6854 }
6855
6856 result_data_set(&com->result, result_type, true);
6857 ret = packed_map_get_remove_by_rel_rank_range(&map, com, &value, rank,
6858 count);
6859 break;
6860 }
6861 default:
6862 cf_warning(AS_PARTICLE, "cdt_process_state_packed_map_read_optype() invalid cdt op: %d", optype);
6863 com->ret_code = -AS_ERR_PARAMETER;
6864 return false;
6865 }
6866
6867 if (ret != AS_OK) {
6868 cf_warning(AS_PARTICLE, "%s: failed", cdt_process_state_get_op_name(state));
6869 com->ret_code = ret;
6870 return false;
6871 }
6872
6873 return true;
6874}
6875
6876
6877//==========================================================
6878// Debugging support.
6879//
6880
6881void
6882map_print(const packed_map *map, const char *name)
6883{
6884 print_packed(map->packed, map->packed_sz, name);
6885}
6886
6887static bool
6888map_verify_fn(const cdt_context *ctx, rollback_alloc *alloc_idx)
6889{
6890 if (! ctx->b) {
6891 return true;
6892 }
6893
6894 packed_map map;
6895 uint8_t type = as_bin_get_particle_type(ctx->b);
6896
6897 if (type != AS_PARTICLE_TYPE_LIST && type != AS_PARTICLE_TYPE_MAP) {
6898 cf_warning(AS_PARTICLE, "map_verify() non-map type: %u", type);
6899 return false;
6900 }
6901
6902 // Check header.
6903 if (! packed_map_init_from_ctx(&map, ctx, false)) {
6904 cf_warning(AS_PARTICLE, "map_verify() invalid packed map");
6905 return false;
6906 }
6907
6908 if (map.flags != 0) {
6909 const uint8_t *byte = map.contents - 1;
6910
6911 if (*byte != 0xC0) {
6912 cf_warning(AS_PARTICLE, "map_verify() invalid ext header, expected C0 for pair.2");
6913 }
6914 }
6915
6916 const order_index *ordidx = &map.ordidx;
6917 bool check_offidx = map_has_offidx(&map);
6918 define_map_msgpack_in(pk, &map);
6919 setup_map_must_have_offidx(u, &map, alloc_idx);
6920
6921 uint32_t filled = offset_index_get_filled(u->offidx);
6922 define_offset_index(temp_offidx, u->offidx->contents, u->offidx->content_sz,
6923 u->offidx->_.ele_count, alloc_idx);
6924
6925 if (map.ele_count > 1) {
6926 offset_index_copy(&temp_offidx, u->offidx, 0, 0, filled, 0);
6927 }
6928
6929 // Check offsets.
6930 for (uint32_t i = 0; i < map.ele_count; i++) {
6931 uint32_t offset;
6932
6933 if (check_offidx) {
6934 if (i < filled) {
6935 offset = offset_index_get_const(u->offidx, i);
6936
6937 if (pk.offset != offset) {
6938 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u expected=%d", i, offset, pk.offset);
6939 return false;
6940 }
6941 }
6942 else {
6943 offset_index_set(&temp_offidx, i, pk.offset);
6944 }
6945 }
6946 else {
6947 offset_index_set(u->offidx, i, pk.offset);
6948 }
6949
6950 offset = pk.offset;
6951
6952 if (msgpack_sz(&pk) == 0) {
6953 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u pk.offset=%u invalid key", i, offset, pk.offset);
6954 return false;
6955 }
6956
6957 offset = pk.offset;
6958
6959 if (msgpack_sz(&pk) == 0) {
6960 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u pk.offset=%u invalid value", i, offset, pk.offset);
6961 return false;
6962 }
6963 }
6964
6965 if (check_offidx && filled < map.ele_count) {
6966 u->offidx->_.ptr = temp_offidx._.ptr;
6967 }
6968
6969 // Check packed size.
6970 if (map.content_sz != pk.offset) {
6971 cf_warning(AS_PARTICLE, "map_verify() content_sz=%u expected=%u", map.content_sz, pk.offset);
6972 return false;
6973 }
6974
6975 // Check key orders.
6976 if (map_is_k_ordered(&map) && map.ele_count > 0) {
6977 pk.offset = 0;
6978
6979 define_map_msgpack_in(pk_key, &map);
6980
6981 for (uint32_t i = 1; i < map.ele_count; i++) {
6982 uint32_t offset = pk.offset;
6983 msgpack_compare_t cmp = msgpack_cmp(&pk_key, &pk);
6984
6985 if (cmp == MSGPACK_COMPARE_ERROR) {
6986 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u pk.offset=%u invalid key", i, offset, pk.offset);
6987 return false;
6988 }
6989
6990 if (cmp == MSGPACK_COMPARE_GREATER) {
6991 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u pk.offset=%u keys not in order", i, offset, pk.offset);
6992 return false;
6993 }
6994
6995 pk_key.offset = offset;
6996
6997 if (msgpack_sz(&pk) == 0) {
6998 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u pk.offset=%u invalid value", i, offset, pk.offset);
6999 return false;
7000 }
7001 }
7002 }
7003
7004 // Check value orders.
7005 if (order_index_is_filled(ordidx) && map.ele_count > 1) {
7006 // Compare with freshly sorted.
7007 define_order_index(cmp_order, map.ele_count, alloc_idx);
7008
7009 order_index_set_sorted(&cmp_order, u->offidx, map.contents,
7010 map.content_sz, SORT_BY_VALUE);
7011
7012 for (uint32_t i = 0; i < map.ele_count; i++) {
7013 uint32_t expected = order_index_get(&cmp_order, i);
7014 uint32_t index = order_index_get(ordidx, i);
7015
7016 if (index != expected) {
7017 cf_warning(AS_PARTICLE, "map_verify() i=%u index=%u expected=%u invalid order index", i, index, expected);
7018 return false;
7019 }
7020 }
7021
7022 // Walk index and check value order.
7023 pk.offset = 0;
7024
7025 define_map_msgpack_in(prev_value, &map);
7026 uint32_t index = order_index_get(ordidx, 0);
7027
7028 prev_value.offset = offset_index_get_const(u->offidx, index);
7029
7030 if (msgpack_sz(&prev_value) == 0) {
7031 cf_warning(AS_PARTICLE, "map_verify() index=%u pk.offset=%u invalid key", index, pk.offset);
7032 return false;
7033 }
7034
7035 for (uint32_t i = 1; i < map.ele_count; i++) {
7036 index = order_index_get(ordidx, i);
7037 pk.offset = offset_index_get_const(u->offidx, index);
7038
7039 if (msgpack_sz(&pk) == 0) {
7040 cf_warning(AS_PARTICLE, "map_verify() i=%u index=%u pk.offset=%u invalid key", i, index, pk.offset);
7041 return false;
7042 }
7043
7044 uint32_t offset = pk.offset;
7045 msgpack_compare_t cmp = msgpack_cmp(&prev_value, &pk);
7046
7047 if (cmp == MSGPACK_COMPARE_ERROR) {
7048 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u pk.offset=%u invalid value", i, offset, pk.offset);
7049 return false;
7050 }
7051
7052 if (cmp == MSGPACK_COMPARE_GREATER) {
7053 cf_warning(AS_PARTICLE, "map_verify() i=%u offset=%u pk.offset=%u value index not in order", i, offset, pk.offset);
7054 return false;
7055 }
7056
7057 prev_value.offset = offset;
7058 }
7059 }
7060
7061 return true;
7062}
7063
7064bool
7065map_verify(const cdt_context *ctx)
7066{
7067 define_rollback_alloc(alloc_idx, NULL, 8, false); // for temp indexes
7068 bool ret = map_verify_fn(ctx, alloc_idx);
7069
7070 rollback_alloc_rollback(alloc_idx);
7071 return ret;
7072}
7073