1/*
2 * particle_list.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 <stdarg.h>
24#include <stddef.h>
25#include <stdint.h>
26#include <string.h>
27#include <sys/param.h>
28
29#include "aerospike/as_buffer.h"
30#include "aerospike/as_msgpack.h"
31#include "aerospike/as_serializer.h"
32#include "aerospike/as_val.h"
33#include "citrusleaf/alloc.h"
34#include "citrusleaf/cf_byte_order.h"
35
36#include "fault.h"
37
38#include "base/cdt.h"
39#include "base/cfg.h"
40#include "base/datamodel.h"
41#include "base/msgpack_in.h"
42#include "base/particle.h"
43#include "base/particle_blob.h"
44#include "base/proto.h"
45
46
47//==========================================================
48// LIST particle interface - function declarations.
49//
50
51// Destructor, etc.
52void list_destruct(as_particle *p);
53uint32_t list_size(const as_particle *p);
54
55// Handle "wire" format.
56int32_t list_concat_size_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
57int list_append_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
58int list_prepend_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
59int list_incr_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
60int32_t list_size_from_wire(const uint8_t *wire_value, uint32_t value_size);
61int list_from_wire(as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size, as_particle **pp);
62int list_compare_from_wire(const as_particle *p, as_particle_type wire_type, const uint8_t *wire_value, uint32_t value_size);
63uint32_t list_wire_size(const as_particle *p);
64uint32_t list_to_wire(const as_particle *p, uint8_t *wire);
65
66// Handle as_val translation.
67uint32_t list_size_from_asval(const as_val *val);
68void list_from_asval(const as_val *val, as_particle **pp);
69as_val *list_to_asval(const as_particle *p);
70uint32_t list_asval_wire_size(const as_val *val);
71uint32_t list_asval_to_wire(const as_val *val, uint8_t *wire);
72
73// Handle msgpack translation.
74uint32_t list_size_from_msgpack(const uint8_t *packed, uint32_t packed_size);
75void list_from_msgpack(const uint8_t *packed, uint32_t packed_size, as_particle **pp);
76
77// Handle on-device "flat" format.
78const uint8_t *list_from_flat(const uint8_t *flat, const uint8_t *end, as_particle **pp);
79uint32_t list_flat_size(const as_particle *p);
80uint32_t list_to_flat(const as_particle *p, uint8_t *flat);
81
82
83//==========================================================
84// LIST particle interface - vtable.
85//
86
87const as_particle_vtable list_vtable = {
88 list_destruct,
89 list_size,
90
91 list_concat_size_from_wire,
92 list_append_from_wire,
93 list_prepend_from_wire,
94 list_incr_from_wire,
95 list_size_from_wire,
96 list_from_wire,
97 list_compare_from_wire,
98 list_wire_size,
99 list_to_wire,
100
101 list_size_from_asval,
102 list_from_asval,
103 list_to_asval,
104 list_asval_wire_size,
105 list_asval_to_wire,
106
107 list_size_from_msgpack,
108 list_from_msgpack,
109
110 blob_skip_flat,
111 blob_cast_from_flat,
112 list_from_flat,
113 list_flat_size,
114 list_to_flat
115};
116
117
118//==========================================================
119// Typedefs & constants.
120//
121
122#if defined(CDT_DEBUG_VERIFY)
123#define LIST_DEBUG_VERIFY
124#endif
125
126#define PACKED_LIST_INDEX_STEP 128
127
128#define AS_PACKED_LIST_FLAG_NONE 0x00
129#define AS_PACKED_LIST_FLAG_ORDERED 0x01
130
131#define PACKED_LIST_FLAG_OFF_IDX 0x10
132#define PACKED_LIST_FLAG_FULLOFF_IDX 0x20
133
134typedef struct packed_list_s {
135 const uint8_t *packed;
136 uint32_t packed_sz;
137
138 uint32_t ele_count; // excludes ext ele
139 // Mutable state member (is considered mutable in const objects).
140 offset_index offidx; // offset start at contents (excluding ext metadata ele)
141 // Mutable state member (is considered mutable in const objects).
142 offset_index full_offidx; // index at every element
143 uint8_t ext_flags;
144
145 const uint8_t *contents; // where elements start (excludes ext)
146 uint32_t content_sz;
147} packed_list;
148
149typedef struct packed_list_op_s {
150 const packed_list *list;
151
152 uint32_t new_ele_count;
153 uint32_t new_content_sz;
154
155 uint32_t seg1_sz;
156 uint32_t seg2_offset;
157 uint32_t seg2_sz;
158 uint32_t nil_ele_sz; // number of nils we need to insert
159} packed_list_op;
160
161typedef struct list_mem_s {
162 uint8_t type;
163 uint32_t sz;
164 uint8_t data[];
165} __attribute__ ((__packed__)) list_mem;
166
167typedef struct list_flat_s {
168 uint8_t type;
169 uint32_t sz; // host order on device and in memory
170 uint8_t data[];
171} __attribute__ ((__packed__)) list_flat;
172
173typedef enum {
174 LIST_EMPTY_LIST_HDR = 0,
175 LIST_EMPTY_EXT_HDR,
176 LIST_EMPTY_EXT_SZ,
177 LIST_EMPTY_EXT_FLAGS,
178 LIST_EMPTY_FLAGED_SIZE
179} list_empty_bytes;
180
181static const list_mem list_ordered_empty = {
182 .type = AS_PARTICLE_TYPE_LIST,
183 .sz = LIST_EMPTY_FLAGED_SIZE,
184 .data = {
185 [LIST_EMPTY_LIST_HDR] = 0x91,
186 [LIST_EMPTY_EXT_HDR] = 0xC7,
187 [LIST_EMPTY_EXT_SZ] = 0,
188 [LIST_EMPTY_EXT_FLAGS] = AS_PACKED_LIST_FLAG_ORDERED
189 }
190};
191
192static const list_mem list_mem_empty = {
193 .type = AS_PARTICLE_TYPE_LIST,
194 .sz = 1,
195 .data = {0x90}
196};
197
198typedef struct {
199 const offset_index *offsets;
200 const order_index *order;
201 as_cdt_sort_flags flags;
202 bool error;
203} list_order_index_sort_userdata;
204
205typedef struct {
206 offset_index *offidx;
207 uint8_t mem_temp[];
208} __attribute__ ((__packed__)) list_vla_offidx_cast;
209
210#define define_packed_list_op(__name, __list_p) \
211 packed_list_op __name; \
212 packed_list_op_init(&__name, __list_p)
213
214#define list_full_offidx_p(__list_p) \
215 ((offset_index *)(list_is_ordered(__list_p) ? &(__list_p)->offidx : &(__list_p)->full_offidx))
216
217#define setup_list_must_have_full_offidx(__name, __list_p, __alloc) \
218 uint8_t __name ## __vlatemp[sizeof(offset_index *) + offset_index_vla_sz(list_full_offidx_p(__list_p))]; \
219 list_vla_offidx_cast *__name = (list_vla_offidx_cast *)__name ## __vlatemp; \
220 __name->offidx = list_full_offidx_p(__list_p); \
221 offset_index_alloc_temp(list_full_offidx_p(__list_p), __name->mem_temp, __alloc)
222
223#define setup_list_context_full_offidx(__name, __list_p, __alloc, __need_idx_mem) \
224 uint8_t __name ## __vlatemp[sizeof(offset_index *) + (need_idx_mem ? 0 : offset_index_vla_sz(list_full_offidx_p(__list_p)))]; \
225 list_vla_offidx_cast *__name = (list_vla_offidx_cast *)__name ## __vlatemp; \
226 __name->offidx = list_full_offidx_p(__list_p); \
227 if (__need_idx_mem) { \
228 __name->offidx->_.ptr = rollback_alloc_reserve(__alloc, offset_index_size(__name->offidx)); \
229 offset_index_set_filled(__name->offidx, 1); \
230 } \
231 else { \
232 offset_index_alloc_temp(list_full_offidx_p(__list_p), __name->mem_temp, __alloc); \
233 }
234
235#define define_packed_list_particle(__name, __particle, __ret) \
236 packed_list __name; \
237 bool __ret = packed_list_init_from_particle(&__name, __particle)
238
239
240//==========================================================
241// Forward declarations.
242//
243
244static inline bool is_list_type(uint8_t type);
245static inline bool flags_is_ordered(uint8_t flags);
246static inline bool list_is_ordered(const packed_list *list);
247static inline uint8_t get_ext_flags(bool ordered);
248static uint32_t list_calc_ext_content_sz(uint32_t ele_count, uint32_t content_sz, bool ordered);
249
250static uint32_t list_pack_header(uint8_t *buf, uint32_t ele_count);
251static void list_pack_empty_index(as_packer *pk, uint32_t ele_count, const uint8_t *contents, uint32_t content_sz, bool is_ordered);
252
253// as_bin
254static void as_bin_set_ordered_empty_list(as_bin *b, rollback_alloc *alloc_buf);
255
256// cdt_context
257static inline void cdt_context_set_empty_list(cdt_context *ctx, bool is_ordered);
258static inline void cdt_context_use_static_list_if_notinuse(cdt_context *ctx, uint64_t create_flags);
259
260static inline bool cdt_context_list_need_idx_mem(const cdt_context *ctx, const packed_list *list, bool is_dim);
261static inline void cdt_context_list_push(cdt_context *ctx, const packed_list *list, uint32_t idx, rollback_alloc *alloc_idx, bool is_dim, bool need_idx_mem);
262
263// packed_list
264static bool packed_list_init(packed_list *list, const uint8_t *buf, uint32_t sz);
265static inline bool packed_list_init_from_particle(packed_list *list, const as_particle *p);
266static bool packed_list_init_from_bin(packed_list *list, const as_bin *b);
267static bool packed_list_init_from_ctx(packed_list *list, const cdt_context *ctx);
268static bool packed_list_init_from_ctx_orig(packed_list *list, const cdt_context *ctx);
269static bool packed_list_unpack_hdridx(packed_list *list);
270static void packed_list_partial_offidx_update(const packed_list *list);
271
272static void packed_list_find_by_value_ordered(const packed_list *list, const cdt_payload *value, order_index_find *find);
273static uint32_t packed_list_find_idx_offset(const packed_list *list, uint32_t index);
274static uint32_t packed_list_find_idx_offset_continue(const packed_list *list, uint32_t index, uint32_t index0, uint32_t offset0);
275static void packed_list_find_rank_range_by_value_interval_ordered(const packed_list *list, const cdt_payload *value_start, const cdt_payload *value_end, uint32_t *rank_r, uint32_t *count_r, bool is_multi);
276static bool packed_list_find_rank_range_by_value_interval_unordered(const packed_list *list, const cdt_payload *value_start, const cdt_payload *value_end, uint32_t *rank, uint32_t *count, uint64_t *mask_val, bool inverted, bool is_multi);
277
278static uint32_t packed_list_mem_sz(const packed_list *list, bool has_ext, uint32_t *ext_content_sz_r);
279static uint32_t packed_list_pack_buf(const packed_list *list, uint8_t *buf, uint32_t sz, uint32_t ext_content_sz, bool strip_flags);
280static list_mem *packed_list_pack_mem(const packed_list *list, list_mem *p_list_mem);
281static void packed_list_content_pack(const packed_list *list, as_packer *pk);
282static int packed_list_remove_by_idx(const packed_list *list, cdt_op_mem *com, const uint64_t rm_idx, uint32_t *rm_sz);
283static int packed_list_remove_by_mask(const packed_list *list, cdt_op_mem *com, const uint64_t *rm_mask, uint32_t rm_count, uint32_t *rm_sz);
284
285static int packed_list_trim(const packed_list *list, cdt_op_mem *com, uint32_t index, uint32_t count);
286static int packed_list_get_remove_by_index_range(const packed_list *list, cdt_op_mem *com, int64_t index, uint64_t count);
287static int packed_list_get_remove_by_value_interval(const packed_list *list, cdt_op_mem *com, const cdt_payload *value_start, const cdt_payload *value_end);
288static int packed_list_get_remove_by_rank_range(const packed_list *list, cdt_op_mem *com, int64_t rank, uint64_t count);
289static int packed_list_get_remove_all_by_value_list(const packed_list *list, cdt_op_mem *com, const cdt_payload *value_list);
290static int packed_list_get_remove_by_rel_rank_range(const packed_list *list, cdt_op_mem *com, const cdt_payload *value, int64_t rank, uint64_t count);
291
292static int packed_list_insert(const packed_list *list, cdt_op_mem *com, int64_t index, const cdt_payload *payload, bool payload_is_list, uint64_t mod_flags, bool set_result);
293static int packed_list_add_ordered(const packed_list *list, cdt_op_mem *com, const cdt_payload *payload, uint64_t mod_flags);
294static int packed_list_add_items_ordered(const packed_list *list, cdt_op_mem *com, const cdt_payload *items, uint64_t mod_flags);
295static int packed_list_replace_ordered(const packed_list *list, cdt_op_mem *com, uint32_t index, const cdt_payload *value, uint64_t mod_flags);
296
297static bool packed_list_check_order_and_fill_offidx(const packed_list *list);
298
299// packed_list_op
300static void packed_list_op_init(packed_list_op *op, const packed_list *list);
301static bool packed_list_op_insert(packed_list_op *op, uint32_t index, uint32_t count, uint32_t insert_sz);
302static bool packed_list_op_remove(packed_list_op *op, uint32_t index, uint32_t count);
303
304static uint32_t packed_list_op_write_seg1(const packed_list_op *op, uint8_t *buf);
305static uint32_t packed_list_op_write_seg2(const packed_list_op *op, uint8_t *buf);
306
307static bool packed_list_builder_add_ranks_by_range(const packed_list *list, cdt_container_builder *builder, msgpack_in *start, uint32_t count, bool reverse);
308
309// list
310static list_mem *list_create(rollback_alloc *alloc_buf, uint32_t ele_count, uint32_t content_sz);
311static as_particle *list_simple_create_from_buf(rollback_alloc *alloc_buf, uint32_t ele_count, const uint8_t *contents, uint32_t content_sz);
312static as_particle *list_simple_create(rollback_alloc *alloc_buf, uint32_t ele_count, uint32_t content_sz, uint8_t **contents_r);
313
314static int list_set_flags(cdt_op_mem *com, uint8_t flags);
315static int list_append(cdt_op_mem *com, const cdt_payload *payload, bool payload_is_list, uint64_t mod_flags);
316static int list_insert(cdt_op_mem *com, int64_t index, const cdt_payload *payload, bool payload_is_list, uint64_t mod_flags);
317static int list_set(cdt_op_mem *com, int64_t index, const cdt_payload *value, uint64_t mod_flags);
318static int list_increment(cdt_op_mem *com, int64_t index, cdt_payload *delta_value, uint64_t mod_flags);
319static int list_sort(cdt_op_mem *com, as_cdt_sort_flags sort_flags);
320
321static int list_remove_by_index_range(cdt_op_mem *com, int64_t index, uint64_t count);
322static int list_remove_by_value_interval(cdt_op_mem *com, const cdt_payload *value_start, const cdt_payload *value_end);
323static int list_remove_by_rank_range(cdt_op_mem *com, int64_t rank, uint64_t count);
324static int list_remove_all_by_value_list(cdt_op_mem *com, const cdt_payload *value_list);
325static int list_remove_by_rel_rank_range(cdt_op_mem *com, const cdt_payload *value, int64_t rank, uint64_t count);
326
327static uint8_t *list_setup_bin(as_bin *b, rollback_alloc *alloc_buf, uint8_t flags, uint32_t content_sz, uint32_t ele_count, uint32_t idx_trunc, const offset_index *old_offidx, offset_index *new_offidx);
328static uint8_t *list_setup_bin_ctx(cdt_context *ctx, uint8_t flags, uint32_t content_sz, uint32_t ele_count, uint32_t idx_trunc, const offset_index *old_offidx, offset_index *new_offidx);
329
330// list_offset_index
331static inline uint32_t list_offset_partial_index_count(uint32_t ele_count);
332static inline void list_offset_index_init(offset_index *offidx, uint8_t *idx_mem_ptr, uint32_t ele_count, const uint8_t *contents, uint32_t content_sz);
333static void list_offset_index_rm_mask_cpy(offset_index *dst, const offset_index *full_src, const uint64_t *rm_mask, uint32_t rm_count);
334
335// list_full_offset_index
336static inline void list_full_offset_index_init(offset_index *offidx, uint8_t *idx_mem_ptr, uint32_t ele_count, const uint8_t *contents, uint32_t content_sz);
337static bool list_full_offset_index_fill_to(offset_index *offidx, uint32_t index, bool check_storage);
338
339// list_order_index
340static int list_order_index_sort_cmp_fn(const void *x, const void *y, void *p);
341static uint8_t *list_order_index_pack(const order_index *ordidx, const offset_index *full_offidx, uint8_t *buf, offset_index *new_offidx);
342
343// list_order_heap
344static msgpack_compare_t list_order_heap_cmp_fn(const void *udata, uint32_t idx1, uint32_t idx2);
345
346// list_result_data
347static bool list_result_data_set_not_found(cdt_result_data *rd, int64_t index);
348static void list_result_data_set_values_by_mask(cdt_result_data *rd, const uint64_t *mask, const offset_index *full_offidx, uint32_t count, uint32_t sz);
349static void list_result_data_set_values_by_idxcount(cdt_result_data *rd, const order_index *idxcnt, const offset_index *full_offidx);
350static bool list_result_data_set_values_by_ordidx(cdt_result_data *rd, const order_index *ordidx, const offset_index *full_offidx, uint32_t count, uint32_t sz);
351
352// Debugging support
353void list_print(const packed_list *list, const char *name);
354
355
356//==========================================================
357// LIST particle interface - function definitions.
358//
359
360//------------------------------------------------
361// Destructor, etc.
362//
363
364void
365list_destruct(as_particle *p)
366{
367 cf_free(p);
368}
369
370uint32_t
371list_size(const as_particle *p)
372{
373 const list_mem *p_list_mem = (const list_mem *)p;
374 return (uint32_t)sizeof(list_mem) + p_list_mem->sz;
375}
376
377//------------------------------------------------
378// Handle "wire" format.
379//
380
381int32_t
382list_concat_size_from_wire(as_particle_type wire_type,
383 const uint8_t *wire_value, uint32_t value_size, as_particle **pp)
384{
385 cf_warning(AS_PARTICLE, "concat size for list");
386 return -AS_ERR_INCOMPATIBLE_TYPE;
387}
388
389int
390list_append_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
391 uint32_t value_size, as_particle **pp)
392{
393 cf_warning(AS_PARTICLE, "append to list");
394 return -AS_ERR_INCOMPATIBLE_TYPE;
395}
396
397int
398list_prepend_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
399 uint32_t value_size, as_particle **pp)
400{
401 cf_warning(AS_PARTICLE, "prepend to list");
402 return -AS_ERR_INCOMPATIBLE_TYPE;
403}
404
405int
406list_incr_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
407 uint32_t value_size, as_particle **pp)
408{
409 cf_warning(AS_PARTICLE, "increment of list");
410 return -AS_ERR_INCOMPATIBLE_TYPE;
411}
412
413int32_t
414list_size_from_wire(const uint8_t *wire_value, uint32_t value_size)
415{
416 // TODO - CDT can't determine in memory or not.
417 packed_list list;
418
419 if (! packed_list_init(&list, wire_value, value_size)) {
420 cf_warning(AS_PARTICLE, "list_size_from_wire() invalid packed list");
421 return -AS_ERR_UNKNOWN;
422 }
423
424 return (int32_t)(sizeof(list_mem) + packed_list_mem_sz(&list, true, NULL));
425}
426
427int
428list_from_wire(as_particle_type wire_type, const uint8_t *wire_value,
429 uint32_t value_size, as_particle **pp)
430{
431 // TODO - CDT can't determine in memory or not.
432 // It works for data-not-in-memory but we'll incur a memcpy that could be
433 // eliminated.
434 packed_list list;
435 bool is_valid = packed_list_init(&list, wire_value, value_size);
436
437 cf_assert(is_valid, AS_PARTICLE, "list_from_wire() invalid packed list");
438
439 list_mem *p_list_mem = packed_list_pack_mem(&list, (list_mem *)*pp);
440
441 p_list_mem->type = wire_type;
442
443 packed_list new_list;
444 bool check = packed_list_init_from_particle(&new_list, *pp);
445
446 cf_assert(check, AS_PARTICLE, "list_from_wire() invalid list");
447
448 if (! packed_list_check_order_and_fill_offidx(&new_list)) {
449 cf_warning(AS_PARTICLE, "list_from_wire() invalid packed list");
450 return -AS_ERR_UNKNOWN;
451 }
452
453 return AS_OK;
454}
455
456int
457list_compare_from_wire(const as_particle *p, as_particle_type wire_type,
458 const uint8_t *wire_value, uint32_t value_size)
459{
460 cf_warning(AS_PARTICLE, "list_compare_from_wire() not implemented");
461 return -AS_ERR_INCOMPATIBLE_TYPE;
462}
463
464uint32_t
465list_wire_size(const as_particle *p)
466{
467 define_packed_list_particle(list, p, success);
468 cf_assert(success, AS_PARTICLE, "list_wire_size() invalid packed list");
469
470 return packed_list_mem_sz(&list, false, NULL);
471}
472
473uint32_t
474list_to_wire(const as_particle *p, uint8_t *wire)
475{
476 define_packed_list_particle(list, p, success);
477 cf_assert(success, AS_PARTICLE, "list_to_wire() invalid packed list");
478
479 return packed_list_pack_buf(&list, wire, INT_MAX, 0, true);
480}
481
482//------------------------------------------------
483// Handle as_val translation.
484//
485
486uint32_t
487list_size_from_asval(const as_val *val)
488{
489 as_serializer s;
490 as_msgpack_init(&s);
491
492 uint32_t sz = as_serializer_serialize_getsize(&s, (as_val *)val);
493
494 as_serializer_destroy(&s);
495
496 const as_list *list = (const as_list *)val;
497
498 uint32_t ele_count = as_list_size(list);
499 uint32_t base_hdr_sz = as_pack_list_header_get_size(ele_count);
500 uint32_t content_sz = sz - base_hdr_sz;
501 bool is_ordered = flags_is_ordered((uint8_t)list->flags);
502 uint32_t ext_content_sz = list_calc_ext_content_sz(ele_count, content_sz,
503 is_ordered);
504 uint32_t hdr_sz = (is_ordered || ext_content_sz != 0) ?
505 as_pack_list_header_get_size(ele_count + 1) : base_hdr_sz;
506
507 return (uint32_t)sizeof(list_mem) + hdr_sz +
508 as_pack_ext_header_get_size(ext_content_sz) + ext_content_sz +
509 content_sz;
510}
511
512void
513list_from_asval(const as_val *val, as_particle **pp)
514{
515 as_serializer s;
516 as_msgpack_init(&s);
517
518 list_mem *p_list_mem = (list_mem *)*pp;
519 int32_t sz = as_serializer_serialize_presized(&s, val, p_list_mem->data);
520
521 cf_assert(sz >= 0, AS_PARTICLE, "list_from_asval() failed to presize");
522 as_serializer_destroy(&s);
523
524 const as_list *list = (const as_list *)val;
525
526 uint32_t ele_count = as_list_size(list);
527 uint32_t base_hdr_sz = as_pack_list_header_get_size(ele_count);
528 uint32_t content_sz = (uint32_t)sz - base_hdr_sz;
529 bool is_ordered = flags_is_ordered((uint8_t)list->flags);
530 uint32_t ext_content_sz = list_calc_ext_content_sz(ele_count, content_sz,
531 is_ordered);
532
533 if (is_ordered || ext_content_sz != 0) {
534 uint32_t hdr_sz = as_pack_list_header_get_size(ele_count + 1);
535 uint32_t ele_start = hdr_sz +
536 as_pack_ext_header_get_size(ext_content_sz) + ext_content_sz;
537
538 // Prefer memmove over 2x serialize.
539 memmove(p_list_mem->data + ele_start, p_list_mem->data + base_hdr_sz,
540 content_sz);
541
542 as_packer pk = {
543 .buffer = p_list_mem->data,
544 .capacity = ele_start
545 };
546
547 as_pack_list_header(&pk, ele_count + 1);
548 as_pack_ext_header(&pk, ext_content_sz, get_ext_flags(is_ordered));
549
550 if (ext_content_sz != 0) {
551 list_pack_empty_index(&pk, ele_count, NULL, content_sz, is_ordered);
552 }
553
554 cf_assert(pk.offset == ele_start, AS_PARTICLE, "size mismatch pk.offset(%d) != ele_start(%u)", pk.offset, ele_start);
555 p_list_mem->sz = ele_start + content_sz;
556 }
557 else {
558 p_list_mem->sz = (uint32_t)sz;
559 }
560
561 p_list_mem->type = AS_PARTICLE_TYPE_LIST;
562}
563
564as_val *
565list_to_asval(const as_particle *p)
566{
567 list_mem *p_list_mem = (list_mem *)p;
568
569 as_buffer buf = {
570 .capacity = p_list_mem->sz,
571 .size = p_list_mem->sz,
572 .data = p_list_mem->data
573 };
574
575 as_serializer s;
576 as_msgpack_init(&s);
577
578 as_val *val = NULL;
579
580 as_serializer_deserialize(&s, &buf, &val);
581 as_serializer_destroy(&s);
582
583 if (! val) {
584 return (as_val *)as_arraylist_new(0, 1);
585 }
586
587 return val;
588}
589
590uint32_t
591list_asval_wire_size(const as_val *val)
592{
593 as_serializer s;
594 as_msgpack_init(&s);
595
596 uint32_t sz = as_serializer_serialize_getsize(&s, (as_val *)val);
597
598 as_serializer_destroy(&s);
599
600 return sz;
601}
602
603uint32_t
604list_asval_to_wire(const as_val *val, uint8_t *wire)
605{
606 as_serializer s;
607 as_msgpack_init(&s);
608
609 int32_t sz = as_serializer_serialize_presized(&s, val, wire);
610
611 as_serializer_destroy(&s);
612 cf_assert(sz > 0, AS_PARTICLE, "list_asval_to_wire() sz %d failed to serialize", sz);
613
614 return (uint32_t)sz;
615}
616
617//------------------------------------------------
618// Handle msgpack translation.
619//
620
621uint32_t
622list_size_from_msgpack(const uint8_t *packed, uint32_t packed_size)
623{
624 return (uint32_t)sizeof(list_mem) + packed_size;
625}
626
627void
628list_from_msgpack(const uint8_t *packed, uint32_t packed_size, as_particle **pp)
629{
630 list_mem *p_list_mem = (list_mem *)*pp;
631
632 p_list_mem->type = AS_PARTICLE_TYPE_LIST;
633 p_list_mem->sz = packed_size;
634 memcpy(p_list_mem->data, packed, p_list_mem->sz);
635}
636
637//------------------------------------------------
638// Handle on-device "flat" format.
639//
640
641const uint8_t *
642list_from_flat(const uint8_t *flat, const uint8_t *end, as_particle **pp)
643{
644 if (flat + sizeof(list_flat) > end) {
645 cf_warning(AS_PARTICLE, "incomplete flat list");
646 return NULL;
647 }
648
649 // Convert temp buffer from disk to data-in-memory.
650 const list_flat *p_list_flat = (const list_flat *)flat;
651
652 flat += sizeof(list_flat) + p_list_flat->sz;
653
654 if (flat > end) {
655 cf_warning(AS_PARTICLE, "incomplete flat list");
656 return NULL;
657 }
658
659 packed_list list;
660
661 if (! packed_list_init(&list, p_list_flat->data, p_list_flat->sz)) {
662 cf_warning(AS_PARTICLE, "list_from_flat() invalid packed list");
663 return NULL;
664 }
665
666 list_mem *p_list_mem = packed_list_pack_mem(&list, NULL);
667
668 p_list_mem->type = p_list_flat->type;
669 *pp = (as_particle *)p_list_mem;
670
671 packed_list new_list;
672 bool check = packed_list_init_from_particle(&new_list, *pp);
673
674 cf_assert(check, AS_PARTICLE, "list_from_flat() invalid list");
675
676 if (! packed_list_check_order_and_fill_offidx(&new_list)) {
677 cf_warning(AS_PARTICLE, "list_from_flat() invalid packed list");
678 return NULL;
679 }
680
681 return flat;
682}
683
684uint32_t
685list_flat_size(const as_particle *p)
686{
687 define_packed_list_particle(list, p, success);
688 cf_assert(success, AS_PARTICLE, "list_to_flat() invalid packed list");
689
690 return sizeof(list_flat) + packed_list_mem_sz(&list, false, NULL);
691}
692
693uint32_t
694list_to_flat(const as_particle *p, uint8_t *flat)
695{
696 define_packed_list_particle(list, p, success);
697 list_flat *p_list_flat = (list_flat *)flat;
698
699 cf_assert(success, AS_PARTICLE, "list_to_flat() invalid packed list");
700 p_list_flat->sz = packed_list_mem_sz(&list, false, NULL);
701
702 uint32_t check = packed_list_pack_buf(&list, p_list_flat->data,
703 p_list_flat->sz, 0, true);
704
705 cf_assert(check == p_list_flat->sz, AS_PARTICLE, "size mismatch check(%u) != sz(%u), ele_count %u content_sz %u flags 0x%x", check, p_list_flat->sz, list.ele_count, list.content_sz, list.ext_flags);
706
707 // Already wrote the type.
708
709 return sizeof(list_flat) + p_list_flat->sz;
710}
711
712
713//==========================================================
714// as_bin particle functions specific to LIST.
715//
716
717void
718as_bin_particle_list_get_packed_val(const as_bin *b, cdt_payload *packed)
719{
720 const list_mem *p_list_mem = (const list_mem *)b->particle;
721
722 packed->ptr = (uint8_t *)p_list_mem->data;
723 packed->sz = p_list_mem->sz;
724}
725
726bool
727list_subcontext_by_index(cdt_context *ctx, as_unpacker *val)
728{
729 int64_t index;
730 packed_list list;
731 uint32_t uindex;
732 uint32_t count32;
733
734 if (as_unpack_int64(val, &index) != 0) {
735 cf_warning(AS_PARTICLE, "list_subcontext_by_index() invalid subcontext");
736 return false;
737 }
738
739 if (! packed_list_init_from_ctx(&list, ctx)) {
740 cf_warning(AS_PARTICLE, "list_subcontext_by_index() invalid list");
741 return false;
742 }
743
744 if (! calc_index_count(index, 1, list.ele_count, &uindex, &count32,
745 false)) {
746 cf_warning(AS_PARTICLE, "list_subcontext_by_index() index %ld out of bounds for ele_count %u", index, list.ele_count);
747 return false;
748 }
749
750 bool is_dim = ! offset_index_is_null(&list.offidx);
751 bool need_idx_mem = cdt_context_list_need_idx_mem(ctx, &list, is_dim);
752 define_rollback_alloc(alloc_idx, NULL, 1, false); // for temp indexes
753 setup_list_context_full_offidx(full, &list, alloc_idx, need_idx_mem);
754
755 if (! list_full_offset_index_fill_to(full->offidx,
756 list_is_ordered(&list) ? list.ele_count : uindex + 1, true)) {
757 cf_warning(AS_PARTICLE, "list_subcontext_by_index() invalid packed list");
758 rollback_alloc_rollback(alloc_idx);
759 return false;
760 }
761
762 uint32_t offset0 = packed_list_find_idx_offset(&list, uindex);
763
764 if (uindex != 0 && offset0 == 0) {
765 rollback_alloc_rollback(alloc_idx);
766 return false;
767 }
768
769 uint32_t offset1 = packed_list_find_idx_offset_continue(&list, uindex + 1,
770 uindex, offset0);
771
772 if (offset1 == 0) {
773 rollback_alloc_rollback(alloc_idx);
774 return false;
775 }
776
777 cdt_context_list_push(ctx, &list, uindex, alloc_idx, is_dim, need_idx_mem);
778
779 ctx->data_offset += list.packed_sz - list.content_sz + offset0;
780 ctx->data_sz = offset1 - offset0;
781
782 return true;
783}
784
785bool
786list_subcontext_by_rank(cdt_context *ctx, as_unpacker *val)
787{
788 packed_list list;
789
790 if (! packed_list_init_from_ctx(&list, ctx)) {
791 cf_warning(AS_PARTICLE, "list_subcontext_by_rank() invalid list");
792 return false;
793 }
794
795 if (list_is_ordered(&list)) {
796 // idx == rank for ordered lists.
797 return list_subcontext_by_index(ctx, val);
798 }
799
800 int64_t rank;
801 uint32_t urank;
802 uint32_t count32;
803
804 if (as_unpack_int64(val, &rank) != 0) {
805 cf_warning(AS_PARTICLE, "list_subcontext_by_rank() invalid subcontext");
806 return false;
807 }
808
809 if (! calc_index_count(rank, 1, list.ele_count, &urank, &count32,
810 false)) {
811 cf_warning(AS_PARTICLE, "list_subcontext_by_rank() rank %ld out of bounds for ele_count %u", rank, list.ele_count);
812 return false;
813 }
814
815 bool is_dim = ! offset_index_is_null(&list.offidx);
816 bool need_idx_mem = cdt_context_list_need_idx_mem(ctx, &list, is_dim);
817 define_rollback_alloc(alloc_idx, NULL, 8, false); // for temp indexes
818 setup_list_context_full_offidx(full, &list, alloc_idx, need_idx_mem);
819
820 if (! list_full_offset_index_fill_all(full->offidx)) {
821 cf_warning(AS_PARTICLE, "list_subcontext_by_rank() invalid packed list");
822 rollback_alloc_rollback(alloc_idx);
823 return false;
824 }
825
826 define_build_order_heap_by_range(heap, urank, count32, list.ele_count,
827 &list, list_order_heap_cmp_fn, success, alloc_idx);
828
829 if (! success) {
830 cf_warning(AS_PARTICLE, "list_subcontext_by_rank() invalid packed list");
831 rollback_alloc_rollback(alloc_idx);
832 return false;
833 }
834
835 uint32_t idx = order_index_get(&heap._, heap.filled);
836 uint32_t offset0 = offset_index_get_const(full->offidx, idx);
837 uint32_t offset1 = offset_index_get_const(full->offidx, idx + 1);
838
839 cdt_context_list_push(ctx, &list, idx, alloc_idx, is_dim, need_idx_mem);
840
841 ctx->data_offset += list.packed_sz - list.content_sz + offset0;
842 ctx->data_sz = offset1 - offset0;
843
844 return true;
845}
846
847bool
848list_subcontext_by_key(cdt_context *ctx, as_unpacker *val)
849{
850 cf_warning(AS_PARTICLE, "list_subcontext_by_key() Not supported");
851 return false;
852}
853
854bool
855list_subcontext_by_value(cdt_context *ctx, as_unpacker *val)
856{
857 cdt_payload value;
858 packed_list list;
859
860 value.ptr = val->buffer + val->offset;
861
862 int64_t value_sz = as_unpack_size(val);
863
864 if (value_sz <= 0) {
865 cf_warning(AS_PARTICLE, "list_subcontext_by_value() invalid subcontext");
866 return false;
867 }
868
869 value.sz = (uint32_t)value_sz;
870
871 if (! packed_list_init_from_ctx(&list, ctx)) {
872 cf_warning(AS_PARTICLE, "list_subcontext_by_value() invalid packed list");
873 return false;
874 }
875
876 if (list.ele_count == 0) {
877 cf_warning(AS_PARTICLE, "list_subcontext_by_value() list is empty");
878 return false;
879 }
880
881 bool is_dim = ! offset_index_is_null(&list.offidx);
882 bool need_idx_mem = cdt_context_list_need_idx_mem(ctx, &list, is_dim);
883 define_rollback_alloc(alloc_idx, NULL, 8, false); // for temp indexes
884 setup_list_context_full_offidx(full, &list, alloc_idx, need_idx_mem);
885
886 if (! list_full_offset_index_fill_all(full->offidx)) {
887 cf_warning(AS_PARTICLE, "list_subcontext_by_value() invalid packed list");
888 rollback_alloc_rollback(alloc_idx);
889 return false;
890 }
891
892 uint32_t rank;
893 uint32_t count;
894 uint32_t idx;
895
896 if (list_is_ordered(&list)) {
897 packed_list_find_rank_range_by_value_interval_ordered(&list, &value,
898 &value, &rank, &count, false);
899 idx = rank;
900 }
901 else {
902 uint64_t idx64;
903
904 if (! packed_list_find_rank_range_by_value_interval_unordered(&list,
905 &value, &value, &rank, &count, &idx64, false, false)) {
906 rollback_alloc_rollback(alloc_idx);
907 return false;
908 }
909
910 idx = (uint32_t)idx64;
911 }
912
913 if (count == 0) {
914 cf_warning(AS_PARTICLE, "list_subcontext_by_value() value not found");
915 rollback_alloc_rollback(alloc_idx);
916 return false;
917 }
918
919 cdt_context_list_push(ctx, &list, idx, alloc_idx, is_dim, need_idx_mem);
920
921 uint32_t offset0 = offset_index_get_const(full->offidx, idx);
922 uint32_t offset1 = offset_index_get_const(full->offidx, idx + 1);
923
924 ctx->data_offset += list.packed_sz - list.content_sz + offset0;
925 ctx->data_sz = offset1 - offset0;
926
927 return true;
928}
929
930void
931cdt_context_unwind_list(cdt_context *ctx, cdt_ctx_list_stack_entry *p)
932{
933 packed_list list;
934
935 packed_list_init_from_ctx(&list, ctx);
936
937 if (! list_is_ordered(&list)) { // unordered, top level, dim case
938 if (! offset_index_is_null(&list.offidx)) {
939 offset_index_set_filled(&list.offidx,
940 p->idx / PACKED_LIST_INDEX_STEP);
941 }
942
943 return;
944 }
945
946 packed_list orig;
947
948 packed_list_init_from_ctx_orig(&orig, ctx);
949
950 if (! offset_index_is_valid(&orig.offidx)) {
951 offset_index_set_ptr(&orig.offidx, p->idx_mem, orig.contents);
952 }
953
954 uint32_t orig_off = offset_index_get_const(&orig.offidx, p->idx);
955 uint32_t rank;
956 uint32_t count;
957 int32_t delta_sz = ctx->delta_sz;
958 bool is_toplvl = cdt_context_is_toplvl(ctx);
959
960 cdt_payload value = {
961 .ptr = list.contents + orig_off,
962 .sz = offset_index_get_delta_const(&orig.offidx, p->idx) + delta_sz
963 };
964
965 packed_list_find_rank_range_by_value_interval_ordered(&orig, &value, &value,
966 &rank, &count, false);
967
968 if (rank == p->idx || rank == p->idx + 1) { // no change
969 if (is_toplvl && ! offset_index_is_null(&list.offidx)) {
970 offset_index_move_ele(&list.offidx, &orig.offidx, p->idx, p->idx);
971 }
972
973 return;
974 }
975
976 uint32_t orig_sz = offset_index_get_delta_const(&orig.offidx, p->idx);
977 uint32_t new_sz = orig_sz + delta_sz;
978 uint8_t *dest_contents = (uint8_t *)list.contents;
979
980 if (rank < p->idx) {
981 uint32_t begin_off = offset_index_get_const(&orig.offidx, rank);
982
983 memmove(dest_contents + begin_off, list.contents + orig_off, new_sz);
984 memcpy(dest_contents + begin_off + new_sz, orig.contents + begin_off,
985 orig_off - begin_off);
986 }
987 else {
988 uint32_t end_off = offset_index_get_const(&orig.offidx, rank);
989 uint32_t dest_off = end_off - orig_sz;
990
991 memmove(dest_contents + dest_off, list.contents + orig_off, new_sz);
992 memcpy(dest_contents + orig_off, orig.contents + orig_off + orig_sz,
993 end_off - orig_off - orig_sz);
994 }
995
996 if (is_toplvl && ! offset_index_is_null(&list.offidx)) {
997 offset_index_move_ele(&list.offidx, &orig.offidx, p->idx, rank);
998 }
999}
1000
1001//==========================================================
1002// Local helpers.
1003//
1004
1005static inline bool
1006is_list_type(uint8_t type)
1007{
1008 return type == AS_PARTICLE_TYPE_LIST;
1009}
1010
1011static inline bool
1012flags_is_ordered(uint8_t flags)
1013{
1014 return (flags & AS_PACKED_LIST_FLAG_ORDERED) != 0;
1015}
1016
1017static inline bool
1018list_is_ordered(const packed_list *list)
1019{
1020 return flags_is_ordered(list->ext_flags);
1021}
1022
1023static inline bool
1024mod_flags_is_unique(uint64_t flags)
1025{
1026 return (flags & AS_CDT_LIST_ADD_UNIQUE) != 0;
1027}
1028
1029static inline bool
1030mod_flags_is_bounded(uint64_t flags)
1031{
1032 return (flags & AS_CDT_LIST_INSERT_BOUNDED) != 0;
1033}
1034
1035static inline bool
1036mod_flags_is_do_partial(uint64_t flags)
1037{
1038 return (flags & (AS_CDT_LIST_NO_FAIL | AS_CDT_LIST_DO_PARTIAL)) ==
1039 (AS_CDT_LIST_NO_FAIL | AS_CDT_LIST_DO_PARTIAL);
1040}
1041
1042static inline bool
1043mod_flags_is_no_fail(uint64_t flags)
1044{
1045 return (flags & AS_CDT_LIST_NO_FAIL) != 0;
1046}
1047
1048static inline int
1049mod_flags_return_exists(uint64_t flags)
1050{
1051 if (mod_flags_is_no_fail(flags)) {
1052 return AS_OK;
1053 }
1054
1055 return -AS_ERR_ELEMENT_EXISTS;
1056}
1057
1058static inline uint8_t
1059strip_ext_flags(uint8_t flags)
1060{
1061 return flags & AS_PACKED_LIST_FLAG_ORDERED;
1062}
1063
1064static inline uint8_t
1065get_ext_flags(bool ordered)
1066{
1067 return ordered ?
1068 (AS_PACKED_LIST_FLAG_ORDERED | PACKED_LIST_FLAG_FULLOFF_IDX) :
1069 PACKED_LIST_FLAG_OFF_IDX;
1070}
1071
1072static uint32_t
1073list_calc_ext_content_sz(uint32_t ele_count, uint32_t content_sz, bool ordered)
1074{
1075 offset_index offidx;
1076
1077 if (! ordered) {
1078 list_offset_index_init(&offidx, NULL, ele_count, NULL, content_sz);
1079 }
1080 else {
1081 list_full_offset_index_init(&offidx, NULL, ele_count, NULL, content_sz);
1082 }
1083
1084 if (ele_count <= 1) {
1085 return 0;
1086 }
1087
1088 return offset_index_size(&offidx);
1089}
1090
1091static uint32_t
1092list_pack_header(uint8_t *buf, uint32_t ele_count)
1093{
1094 as_packer pk = {
1095 .buffer = buf,
1096 .capacity = INT_MAX,
1097 };
1098
1099 if (as_pack_list_header(&pk, ele_count) != 0) {
1100 cf_crash(AS_PARTICLE, "as_pack_list_header() unexpected failure");
1101 }
1102
1103 return pk.offset;
1104}
1105
1106static void
1107list_pack_empty_index(as_packer *pk, uint32_t ele_count,
1108 const uint8_t *contents, uint32_t content_sz, bool is_ordered)
1109{
1110 offset_index offidx;
1111
1112 if (is_ordered) {
1113 list_full_offset_index_init(&offidx, pk->buffer + pk->offset, ele_count,
1114 contents, content_sz);
1115 }
1116 else {
1117 list_offset_index_init(&offidx, pk->buffer + pk->offset, ele_count,
1118 contents, content_sz);
1119 }
1120
1121 offset_index_set_filled(&offidx, 1);
1122 pk->offset += offset_index_size(&offidx);
1123}
1124
1125//------------------------------------------------
1126// as_bin
1127//
1128
1129void
1130as_bin_set_unordered_empty_list(as_bin *b, rollback_alloc *alloc_buf)
1131{
1132 b->particle = list_simple_create_from_buf(alloc_buf, 0, NULL, 0);
1133 as_bin_state_set_from_type(b, AS_PARTICLE_TYPE_LIST);
1134}
1135
1136static void
1137as_bin_set_ordered_empty_list(as_bin *b, rollback_alloc *alloc_buf)
1138{
1139 b->particle = list_simple_create_from_buf(alloc_buf, 1,
1140 list_ordered_empty.data + 1, LIST_EMPTY_FLAGED_SIZE - 1);
1141 as_bin_state_set_from_type(b, AS_PARTICLE_TYPE_LIST);
1142}
1143
1144//------------------------------------------------
1145// cdt_context
1146//
1147
1148static inline void
1149cdt_context_set_empty_list(cdt_context *ctx, bool is_ordered)
1150{
1151 if (ctx->data_sz == 0) {
1152 if (is_ordered) {
1153 as_bin_set_ordered_empty_list(ctx->b, ctx->alloc_buf);
1154 }
1155 else {
1156 as_bin_set_unordered_empty_list(ctx->b, ctx->alloc_buf);
1157 }
1158 }
1159 else {
1160 list_setup_bin_ctx(ctx, is_ordered ?
1161 AS_PACKED_LIST_FLAG_ORDERED : AS_PACKED_LIST_FLAG_NONE,
1162 0, 0, 0, NULL, NULL);
1163 }
1164}
1165
1166static inline void
1167cdt_context_use_static_list_if_notinuse(cdt_context *ctx, uint64_t create_flags)
1168{
1169 if (! as_bin_inuse(ctx->b)) {
1170 cf_assert(ctx->data_sz == 0, AS_PARTICLE, "invalid state");
1171 ctx->b->particle = (create_flags & AS_PACKED_LIST_FLAG_ORDERED) != 0 ?
1172 (as_particle *)&list_ordered_empty :
1173 (as_particle *)&list_mem_empty;
1174 as_bin_state_set_from_type(ctx->b, AS_PARTICLE_TYPE_LIST);
1175 }
1176}
1177
1178static inline bool
1179cdt_context_list_need_idx_mem(const cdt_context *ctx, const packed_list *list,
1180 bool is_dim)
1181{
1182 return ! (cdt_context_is_toplvl(ctx) && is_dim) && list_is_ordered(list) &&
1183 list->ele_count > 1;
1184}
1185
1186static inline void
1187cdt_context_list_push(cdt_context *ctx, const packed_list *list, uint32_t idx,
1188 rollback_alloc *alloc_idx, bool is_dim, bool need_idx_mem)
1189{
1190 if (cdt_context_is_modify(ctx) &&
1191 ((cdt_context_is_toplvl(ctx) && is_dim) || list_is_ordered(list)) &&
1192 list->ele_count > 1) {
1193 if (need_idx_mem) {
1194 cdt_context_push(ctx, idx, list_full_offidx_p(list)->_.ptr)->type =
1195 AS_LIST;
1196 }
1197 else {
1198 cdt_context_push(ctx, idx, NULL)->type = AS_LIST;
1199 rollback_alloc_rollback(alloc_idx);
1200
1201 if (cdt_context_is_toplvl(ctx)) {
1202 ctx->top_content_sz = list->content_sz;
1203 ctx->top_content_off = list->contents - list->packed;
1204 ctx->top_ele_count = list->ele_count;
1205 }
1206 }
1207 }
1208 else {
1209 rollback_alloc_rollback(alloc_idx);
1210 }
1211}
1212
1213//----------------------------------------------------------
1214// packed_list
1215//
1216
1217static bool
1218packed_list_init(packed_list *list, const uint8_t *buf, uint32_t sz)
1219{
1220 list->packed = buf;
1221 list->packed_sz = sz;
1222
1223 list->ele_count = 0;
1224 list->ext_flags = 0;
1225 list->contents = NULL;
1226
1227 return packed_list_unpack_hdridx(list);
1228}
1229
1230static inline bool
1231packed_list_init_from_particle(packed_list *list, const as_particle *p)
1232{
1233 const list_mem *p_list_mem = (const list_mem *)p;
1234 return packed_list_init(list, p_list_mem->data, p_list_mem->sz);
1235}
1236
1237static bool
1238packed_list_init_from_bin(packed_list *list, const as_bin *b)
1239{
1240 uint8_t type = as_bin_get_particle_type(b);
1241 cf_assert(is_list_type(type), AS_PARTICLE, "packed_list_init_from_bin() invalid type %d", type);
1242 return packed_list_init_from_particle(list, b->particle);
1243}
1244
1245static bool
1246packed_list_init_from_ctx(packed_list *list, const cdt_context *ctx)
1247{
1248 if (ctx->data_sz == 0) {
1249 return packed_list_init_from_bin(list, ctx->b);
1250 }
1251
1252 const cdt_mem *p_cdt_mem = (const cdt_mem *)ctx->b->particle;
1253
1254 return packed_list_init(list,
1255 p_cdt_mem->data + ctx->data_offset + ctx->delta_off,
1256 ctx->data_sz + ctx->delta_sz);
1257}
1258
1259static bool
1260packed_list_init_from_ctx_orig(packed_list *list, const cdt_context *ctx)
1261{
1262 if (ctx->data_sz == 0) {
1263 return packed_list_init_from_particle(list, ctx->orig);
1264 }
1265
1266 const cdt_mem *p_cdt_mem = (const cdt_mem *)ctx->orig;
1267
1268 return packed_list_init(list, p_cdt_mem->data + ctx->data_offset,
1269 ctx->data_sz);
1270}
1271
1272static bool
1273packed_list_unpack_hdridx(packed_list *list)
1274{
1275 if (list->packed_sz == 0) {
1276 list->ext_flags = 0;
1277 return false;
1278 }
1279
1280 as_unpacker pk = {
1281 .buffer = list->packed,
1282 .length = list->packed_sz
1283 };
1284
1285 int64_t ele_count = as_unpack_list_header_element_count(&pk);
1286
1287 if (ele_count < 0) {
1288 return false;
1289 }
1290
1291 list->ele_count = (uint32_t)ele_count;
1292
1293 if (ele_count != 0 && as_unpack_peek_is_ext(&pk)) {
1294 as_msgpack_ext ext;
1295
1296 if (as_unpack_ext(&pk, &ext) != 0) {
1297 return false;
1298 }
1299
1300 list->ext_flags = ext.type;
1301 list->ele_count--;
1302 list->contents = list->packed + pk.offset;
1303 list->content_sz = list->packed_sz - pk.offset;
1304
1305 if (list_is_ordered(list)) {
1306 list_full_offset_index_init(&list->offidx, NULL, list->ele_count,
1307 list->contents, list->content_sz);
1308 }
1309 else {
1310 list_offset_index_init(&list->offidx, NULL, list->ele_count,
1311 list->contents, list->content_sz);
1312 }
1313
1314 list_full_offset_index_init(&list->full_offidx, NULL, list->ele_count,
1315 list->contents, list->content_sz);
1316
1317 if (ext.size >= offset_index_size(&list->offidx)) {
1318 offset_index_set_ptr(&list->offidx, (uint8_t *)ext.data,
1319 list->packed + pk.offset);
1320 }
1321 }
1322 else {
1323 list->contents = list->packed + pk.offset;
1324 list->content_sz = list->packed_sz - pk.offset;
1325 list->ext_flags = 0;
1326
1327 list_offset_index_init(&list->offidx, NULL, list->ele_count,
1328 list->contents, list->content_sz);
1329 list_full_offset_index_init(&list->full_offidx, NULL, list->ele_count,
1330 list->contents, list->content_sz);
1331 }
1332
1333 return true;
1334}
1335
1336static void
1337packed_list_partial_offidx_update(const packed_list *list)
1338{
1339 if (list_is_ordered(list) || ! offset_index_is_valid(&list->full_offidx) ||
1340 offset_index_is_null(&list->offidx)) {
1341 return;
1342 }
1343
1344 offset_index *full = (offset_index *)&list->full_offidx;
1345 offset_index *part = (offset_index *)&list->offidx;
1346 uint32_t filled = offset_index_get_filled(part);
1347 uint32_t max =
1348 list_offset_partial_index_count(offset_index_get_filled(full));
1349
1350 if (filled >= max) {
1351 return;
1352 }
1353
1354 for (uint32_t j = filled; j < max; j++) {
1355 uint32_t off = offset_index_get_const(full, j * PACKED_LIST_INDEX_STEP);
1356 offset_index_set(part, j, off);
1357 }
1358
1359 offset_index_set_filled(part, max);
1360}
1361
1362static void
1363packed_list_find_by_value_ordered(const packed_list *list,
1364 const cdt_payload *value, order_index_find *find)
1365{
1366 if (list->ele_count == 0) {
1367 find->found = false;
1368 find->result = 0;
1369 return;
1370 }
1371
1372 offset_index *offidx = list_full_offidx_p(list);
1373
1374 cf_assert(offset_index_is_full(offidx), AS_PARTICLE, "invalid offidx");
1375 find->count = list->ele_count - find->start;
1376
1377 order_index_find_rank_by_value(NULL, value, offidx, find, false);
1378}
1379
1380static uint32_t
1381packed_list_find_idx_offset(const packed_list *list, uint32_t index)
1382{
1383 if (index == 0) {
1384 return 0;
1385 }
1386
1387 if (list_is_ordered(list)) {
1388 cf_assert(offset_index_is_valid(&list->offidx), AS_PARTICLE, "invalid offidx");
1389
1390 offset_index *offidx = (offset_index *)&list->offidx;
1391
1392 if (! list_full_offset_index_fill_to(offidx, index, false)) {
1393 return 0;
1394 }
1395
1396 return offset_index_get_const(offidx, index);
1397 }
1398 else if (offset_index_is_valid(&list->full_offidx) &&
1399 index < offset_index_get_filled(&list->full_offidx)) {
1400 return offset_index_get_const(&list->full_offidx, index);
1401 }
1402
1403 msgpack_in pk = {
1404 .buf = list->contents,
1405 .buf_sz = list->content_sz
1406 };
1407
1408 uint32_t steps = index;
1409
1410 if (offset_index_is_valid(&list->offidx)) {
1411 uint32_t pt_idx = index / PACKED_LIST_INDEX_STEP;
1412 uint32_t pt_filled = offset_index_get_filled(&list->offidx);
1413
1414 if (pt_idx >= pt_filled) {
1415 cf_assert(pt_filled != 0, AS_PARTICLE, "packed_list_op_find_idx_offset() filled is zero");
1416 pt_idx = pt_filled - 1;
1417 }
1418
1419 pk.offset = offset_index_get_const(&list->offidx, pt_idx);
1420 steps -= pt_idx * PACKED_LIST_INDEX_STEP;
1421
1422 offset_index *offidx = (offset_index *)&list->offidx; // mutable struct variable
1423 uint32_t blocks = steps / PACKED_LIST_INDEX_STEP;
1424
1425 steps %= PACKED_LIST_INDEX_STEP;
1426
1427 for (uint32_t i = 0; i < blocks; i++) {
1428 if (msgpack_sz_rep(&pk, PACKED_LIST_INDEX_STEP) == 0) {
1429 return 0;
1430 }
1431
1432 pt_idx++;
1433 offset_index_set_next(offidx, pt_idx, pk.offset);
1434 }
1435 }
1436
1437 if (steps != 0 && msgpack_sz_rep(&pk, steps) == 0) {
1438 return 0;
1439 }
1440
1441 return pk.offset;
1442}
1443
1444static uint32_t
1445packed_list_find_idx_offset_continue(const packed_list *list, uint32_t index,
1446 uint32_t index0, uint32_t offset0)
1447{
1448 if (list_is_ordered(list)) {
1449 return packed_list_find_idx_offset(list, index);
1450 }
1451 else if (offset_index_is_valid(&list->full_offidx) &&
1452 index < offset_index_get_filled(&list->full_offidx)) {
1453 return offset_index_get_const(&list->full_offidx, index);
1454 }
1455
1456 msgpack_in pk = {
1457 .buf = list->contents,
1458 .buf_sz = list->content_sz,
1459 .offset = offset0
1460 };
1461
1462 uint32_t steps = index - index0;
1463
1464 if (offset_index_is_valid(&list->offidx)) {
1465 uint32_t pt_idx0 = index0 / PACKED_LIST_INDEX_STEP;
1466 uint32_t pt_idx = index / PACKED_LIST_INDEX_STEP;
1467 uint32_t pt_filled = offset_index_get_filled(&list->offidx);
1468
1469 if (pt_idx0 != pt_idx) {
1470 if (pt_idx0 < pt_filled - 1) {
1471 return packed_list_find_idx_offset(list, index);
1472 }
1473
1474 uint32_t mod0 = index0 % PACKED_LIST_INDEX_STEP;
1475 offset_index *offidx = (offset_index *)&list->offidx;
1476
1477 if (mod0 != 0) {
1478 uint32_t rep = PACKED_LIST_INDEX_STEP - mod0;
1479
1480 if (msgpack_sz_rep(&pk, rep) == 0) {
1481 return 0;
1482 }
1483
1484 steps -= rep;
1485 pt_idx0++;
1486 offset_index_set_next(offidx, pt_idx0, pk.offset);
1487 }
1488
1489 uint32_t blocks = pt_idx - pt_idx0;
1490
1491 for (uint32_t i = 0; i < blocks; i++) {
1492 if (msgpack_sz_rep(&pk, PACKED_LIST_INDEX_STEP) == 0) {
1493 return 0;
1494 }
1495
1496 pt_idx0++;
1497 offset_index_set_next(offidx, pt_idx0, pk.offset);
1498 }
1499
1500 steps -= blocks * PACKED_LIST_INDEX_STEP;
1501 }
1502 }
1503
1504 for (uint32_t i = 0; i < steps; i++) {
1505 if (msgpack_sz(&pk) == 0) {
1506 return 0;
1507 }
1508 }
1509
1510 return pk.offset;
1511}
1512
1513// value_end == NULL means looking for: [value_start, largest possible value].
1514// value_start == value_end means looking for a single value:
1515// [value_start, value_start].
1516static void
1517packed_list_find_rank_range_by_value_interval_ordered(const packed_list *list,
1518 const cdt_payload *value_start, const cdt_payload *value_end,
1519 uint32_t *rank_r, uint32_t *count_r, bool is_multi)
1520{
1521 cf_assert(offset_index_is_valid(list_full_offidx_p(list)), AS_PARTICLE, "packed_list_find_rank_range_by_value_interval_ordered() invalid full offset_index");
1522 cf_assert(value_end, AS_PARTICLE, "value_end == NULL");
1523
1524 order_index_find find = {
1525 .target = 0
1526 };
1527
1528 packed_list_find_by_value_ordered(list, value_start, &find);
1529 *rank_r = find.result;
1530
1531 if (value_end == value_start) {
1532 if (! find.found) {
1533 *count_r = 0;
1534 }
1535 else if (is_multi) {
1536 find.start = find.result + 1;
1537 find.target = list->ele_count;
1538 packed_list_find_by_value_ordered(list, value_start, &find);
1539
1540 if (find.found) {
1541 *count_r = find.result - *rank_r;
1542 }
1543 else {
1544 *count_r = 1;
1545 }
1546 }
1547 else {
1548 *count_r = 1;
1549 }
1550
1551 return;
1552 }
1553
1554 if (! value_end->ptr) {
1555 *count_r = list->ele_count - *rank_r;
1556 return;
1557 }
1558
1559 msgpack_in pk_start = {
1560 .buf = value_start->ptr,
1561 .buf_sz = value_start->sz
1562 };
1563
1564 msgpack_in pk_end = {
1565 .buf = value_end->ptr,
1566 .buf_sz = value_end->sz
1567 };
1568
1569 msgpack_compare_t cmp = msgpack_cmp_peek(&pk_start, &pk_end);
1570
1571 if (cmp == MSGPACK_COMPARE_GREATER || cmp == MSGPACK_COMPARE_EQUAL) {
1572 *count_r = 0;
1573 return;
1574 }
1575
1576 find.start = find.result;
1577 packed_list_find_by_value_ordered(list, value_end, &find);
1578 *count_r = find.result - *rank_r;
1579}
1580
1581// value_end == NULL means looking for: [value_start, largest possible value].
1582// value_start == value_end means looking for a single value:
1583// [value_start, value_start].
1584// mask_val is a mask for is_multi case and a uint64_t[1] value for ! is_multi.
1585static bool
1586packed_list_find_rank_range_by_value_interval_unordered(const packed_list *list,
1587 const cdt_payload *value_start, const cdt_payload *value_end,
1588 uint32_t *rank, uint32_t *count, uint64_t *mask_val, bool inverted,
1589 bool is_multi)
1590{
1591 cf_assert(value_end, AS_PARTICLE, "value_end == NULL");
1592
1593 msgpack_in pk_start = {
1594 .buf = value_start->ptr,
1595 .buf_sz = value_start->sz
1596 };
1597
1598 msgpack_in pk_end = {
1599 .buf = value_end->ptr,
1600 .buf_sz = value_end->sz
1601 };
1602
1603 offset_index *full_offidx = list_full_offidx_p(list);
1604
1605 if (offset_index_is_null(full_offidx)) {
1606 full_offidx = NULL;
1607 }
1608
1609 *rank = 0;
1610 *count = 0;
1611
1612 msgpack_in pk = {
1613 .buf = list->contents,
1614 .buf_sz = list->content_sz
1615 };
1616
1617 for (uint32_t i = 0; i < list->ele_count; i++) {
1618 uint32_t value_offset = pk.offset; // save for pk_end
1619
1620 pk_start.offset = 0; // reset
1621
1622 msgpack_compare_t cmp_start = msgpack_cmp(&pk, &pk_start);
1623
1624 if (full_offidx) {
1625 offset_index_set(full_offidx, i + 1, pk.offset);
1626 }
1627
1628 if (cmp_start == MSGPACK_COMPARE_ERROR) {
1629 cf_warning(AS_PARTICLE, "packed_list_op_find_rank_range_by_value_interval_unordered() invalid packed list at index %u", i);
1630 return false;
1631 }
1632
1633 if (cmp_start == MSGPACK_COMPARE_LESS) {
1634 (*rank)++;
1635
1636 if (inverted) {
1637 if (mask_val) {
1638 cdt_idx_mask_set(mask_val, i);
1639 }
1640
1641 (*count)++;
1642 }
1643 }
1644 else if (value_start != value_end) {
1645 msgpack_compare_t cmp_end = MSGPACK_COMPARE_LESS;
1646
1647 // NULL value_end means largest possible value.
1648 if (value_end->ptr) {
1649 pk.offset = value_offset;
1650 pk_end.offset = 0;
1651 cmp_end = msgpack_cmp(&pk, &pk_end);
1652 }
1653
1654 if ((cmp_end == MSGPACK_COMPARE_LESS && ! inverted) ||
1655 ((cmp_end == MSGPACK_COMPARE_GREATER ||
1656 cmp_end == MSGPACK_COMPARE_EQUAL) && inverted)) {
1657 if (mask_val) {
1658 cdt_idx_mask_set(mask_val, i);
1659 }
1660
1661 (*count)++;
1662 }
1663 }
1664 // Single value case.
1665 else if (cmp_start == MSGPACK_COMPARE_EQUAL) {
1666 if (is_multi) {
1667 if (! inverted) {
1668 if (mask_val) {
1669 cdt_idx_mask_set(mask_val, i);
1670 }
1671
1672 (*count)++;
1673 }
1674 }
1675 else if (*count == 0) {
1676 if (mask_val) {
1677 *mask_val = i;
1678 }
1679
1680 (*count)++;
1681 }
1682 }
1683 else if (inverted && is_multi) {
1684 if (mask_val) {
1685 cdt_idx_mask_set(mask_val, i);
1686 }
1687
1688 (*count)++;
1689 }
1690 }
1691
1692 if (full_offidx) {
1693 offset_index_set_filled(full_offidx, list->ele_count);
1694 }
1695
1696 return true;
1697}
1698
1699static uint32_t
1700packed_list_mem_sz(const packed_list *list, bool has_ext,
1701 uint32_t *ext_content_sz_r)
1702{
1703 bool ordered = list_is_ordered(list);
1704 uint32_t ext_cont_sz = 0;
1705
1706 if (has_ext) {
1707 ext_cont_sz = list_calc_ext_content_sz(list->ele_count,
1708 list->content_sz, ordered);
1709
1710 if (ext_content_sz_r) {
1711 *ext_content_sz_r = ext_cont_sz;
1712 }
1713 }
1714 else if (! ordered) {
1715 return as_pack_list_header_get_size(list->ele_count) + list->content_sz;
1716 }
1717
1718 if (! ordered && ext_cont_sz == 0) {
1719 return as_pack_list_header_get_size(list->ele_count) + list->content_sz;
1720 }
1721
1722 return as_pack_list_header_get_size(list->ele_count + 1) +
1723 as_pack_ext_header_get_size(ext_cont_sz) + ext_cont_sz +
1724 list->content_sz;
1725}
1726
1727static uint32_t
1728packed_list_pack_buf(const packed_list *list, uint8_t *buf, uint32_t sz,
1729 uint32_t ext_content_sz, bool strip_flags)
1730{
1731 as_packer pk = {
1732 .buffer = buf,
1733 .capacity = sz
1734 };
1735
1736 bool ordered = list_is_ordered(list);
1737
1738 if (ordered || ext_content_sz != 0) {
1739 as_pack_list_header(&pk, list->ele_count + 1);
1740 as_pack_ext_header(&pk, ext_content_sz, strip_flags ?
1741 strip_ext_flags(list->ext_flags) : get_ext_flags(ordered));
1742
1743 if (ext_content_sz != 0) {
1744 list_pack_empty_index(&pk, list->ele_count, NULL, list->content_sz,
1745 ordered);
1746 }
1747 }
1748 else {
1749 as_pack_list_header(&pk, list->ele_count);
1750 }
1751
1752 packed_list_content_pack(list, &pk);
1753
1754 return pk.offset;
1755}
1756
1757static list_mem *
1758packed_list_pack_mem(const packed_list *list, list_mem *p_list_mem)
1759{
1760 uint32_t ext_content_sz = 0;
1761 uint32_t sz = packed_list_mem_sz(list, true, &ext_content_sz);
1762
1763 if (! p_list_mem) {
1764 p_list_mem = cf_malloc_ns(sizeof(list_mem) + sz);
1765 }
1766
1767 p_list_mem->sz = sz;
1768 packed_list_pack_buf(list, p_list_mem->data, sz, ext_content_sz, false);
1769
1770 return p_list_mem;
1771}
1772
1773static void
1774packed_list_content_pack(const packed_list *list, as_packer *pk)
1775{
1776 uint8_t *ptr = pk->buffer + pk->offset;
1777
1778 memcpy(ptr, list->contents, list->content_sz);
1779 pk->offset += list->content_sz;
1780}
1781
1782static int
1783packed_list_remove_by_idx(const packed_list *list, cdt_op_mem *com,
1784 const uint64_t rm_idx, uint32_t *rm_sz)
1785{
1786 define_packed_list_op(op, list);
1787
1788 if (! packed_list_op_remove(&op, rm_idx, 1)) {
1789 cf_warning(AS_PARTICLE, "packed_list_remove_by_idx() as_packed_list_remove failed");
1790 return -AS_ERR_PARAMETER;
1791 }
1792
1793 if (op.new_ele_count == 0) {
1794 cdt_context_set_empty_list(&com->ctx, list_is_ordered(list));
1795 }
1796 else {
1797 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list->ext_flags,
1798 op.new_content_sz, op.new_ele_count, rm_idx, &list->offidx,
1799 NULL);
1800
1801 ptr += packed_list_op_write_seg1(&op, ptr);
1802 packed_list_op_write_seg2(&op, ptr);
1803 }
1804
1805 *rm_sz = list->content_sz - op.new_content_sz;
1806
1807 return AS_OK;
1808}
1809
1810static int
1811packed_list_remove_by_mask(const packed_list *list, cdt_op_mem *com,
1812 const uint64_t *rm_mask, uint32_t rm_count, uint32_t *rm_sz)
1813{
1814 offset_index *full_offidx = list_full_offidx_p(list);
1815
1816 *rm_sz = cdt_idx_mask_get_content_sz(rm_mask, rm_count, full_offidx);
1817
1818 offset_index new_offidx;
1819 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list->ext_flags,
1820 list->content_sz - *rm_sz, list->ele_count - rm_count, 0, NULL,
1821 &new_offidx);
1822
1823 ptr = cdt_idx_mask_write_eles(rm_mask, rm_count, full_offidx, ptr, true);
1824
1825 if (! offset_index_is_null(&new_offidx)) {
1826 list_offset_index_rm_mask_cpy(&new_offidx, full_offidx, rm_mask,
1827 rm_count);
1828 }
1829
1830 return AS_OK;
1831}
1832
1833// Assumes index/count(non-zero) is surrounded by other elements.
1834static int
1835packed_list_trim(const packed_list *list, cdt_op_mem *com, uint32_t index,
1836 uint32_t count)
1837{
1838 cdt_result_data *result = &com->result;
1839 cf_assert(result->is_multi, AS_PARTICLE, "packed_list_trim() required to be a multi op");
1840
1841 uint32_t rm_count = list->ele_count - count;
1842 uint32_t index1 = index + count;
1843 uint32_t offset0 = packed_list_find_idx_offset(list, index);
1844 uint32_t offset1 = packed_list_find_idx_offset_continue(list, index1,
1845 index, offset0);
1846 uint32_t content_sz = offset1 - offset0;
1847
1848 if ((offset0 == 0 && index != 0) || offset1 == 0) {
1849 cf_warning(AS_PARTICLE, "packed_list_trim() invalid list");
1850 return -AS_ERR_PARAMETER;
1851 }
1852
1853 if (cdt_op_is_modify(com)) {
1854 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list->ext_flags,
1855 content_sz, count, 0, &list->offidx, NULL);
1856
1857 memcpy(ptr, list->contents + offset0, content_sz);
1858 }
1859
1860 switch (result->type) {
1861 case RESULT_TYPE_NONE:
1862 break;
1863 case RESULT_TYPE_COUNT:
1864 as_bin_set_int(result->result, rm_count);
1865 break;
1866 case RESULT_TYPE_REVINDEX:
1867 case RESULT_TYPE_INDEX: {
1868 bool is_rev = (result->type == RESULT_TYPE_REVINDEX);
1869 define_int_list_builder(builder, result->alloc, rm_count);
1870
1871 cdt_container_builder_add_int_range(&builder, 0, index,
1872 list->ele_count, is_rev);
1873 cdt_container_builder_add_int_range(&builder, index1,
1874 list->ele_count - index1, list->ele_count, is_rev);
1875 cdt_container_builder_set_result(&builder, result);
1876 break;
1877 }
1878 case RESULT_TYPE_RANK:
1879 case RESULT_TYPE_REVRANK: {
1880 define_int_list_builder(builder, result->alloc, rm_count);
1881
1882 if (list_is_ordered(list)) {
1883 cdt_container_builder_add_int_range(&builder, 0, index,
1884 list->ele_count, result->type == RESULT_TYPE_REVRANK);
1885 cdt_container_builder_add_int_range(&builder, index + count,
1886 rm_count - index, list->ele_count,
1887 result->type == RESULT_TYPE_REVRANK);
1888 cdt_container_builder_set_result(&builder, result);
1889 break;
1890 }
1891
1892 msgpack_in pk = {
1893 .buf = list->contents,
1894 .buf_sz = list->content_sz
1895 };
1896
1897 if (! packed_list_builder_add_ranks_by_range(list, &builder, &pk, index,
1898 result->type == RESULT_TYPE_REVRANK)) {
1899 cf_warning(AS_PARTICLE, "packed_list_trim() invalid list");
1900 return -AS_ERR_PARAMETER;
1901 }
1902
1903 pk.offset = offset1;
1904
1905 if (! packed_list_builder_add_ranks_by_range(list, &builder, &pk,
1906 rm_count - index, result->type == RESULT_TYPE_REVRANK)) {
1907 cf_warning(AS_PARTICLE, "packed_list_trim() invalid list");
1908 return -AS_ERR_PARAMETER;
1909 }
1910
1911 cdt_container_builder_set_result(&builder, result);
1912 break;
1913 }
1914 case RESULT_TYPE_VALUE: {
1915 uint32_t tail_sz = list->content_sz - offset1;
1916 list_mem *p_list_mem = list_create(result->alloc, rm_count,
1917 offset0 + tail_sz);
1918
1919 cf_assert(p_list_mem, AS_PARTICLE, "NULL list");
1920 result->result->particle = (as_particle *)p_list_mem;
1921
1922 uint8_t *ptr = p_list_mem->data;
1923 uint32_t hdr_sz = list_pack_header(ptr, rm_count);
1924
1925 ptr += hdr_sz;
1926 memcpy(ptr, list->contents, offset0);
1927 ptr += offset0;
1928 memcpy(ptr, list->contents + offset1, tail_sz);
1929
1930 as_bin_state_set_from_type(result->result, AS_PARTICLE_TYPE_LIST);
1931
1932 break;
1933 }
1934 default:
1935 cf_warning(AS_PARTICLE, "packed_list_trim() result_type %d not supported", result->type);
1936 return -AS_ERR_OP_NOT_APPLICABLE;
1937 }
1938
1939 return AS_OK;
1940}
1941
1942static int
1943packed_list_get_remove_by_index_range(const packed_list *list, cdt_op_mem *com,
1944 int64_t index, uint64_t count)
1945{
1946 cdt_result_data *result = &com->result;
1947 uint32_t uindex;
1948 uint32_t count32;
1949
1950 if (! calc_index_count(index, count, list->ele_count, &uindex, &count32,
1951 result->is_multi)) {
1952 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_index_range() index %ld out of bounds for ele_count %u", index, list->ele_count);
1953 return -AS_ERR_OP_NOT_APPLICABLE;
1954 }
1955
1956 if (result_data_is_inverted(result)) {
1957 if (! result->is_multi) {
1958 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_index_range() INVERTED flag not supported for single result ops");
1959 return -AS_ERR_OP_NOT_APPLICABLE;
1960 }
1961
1962 if (result_data_is_return_index_range(result) ||
1963 result_data_is_return_rank_range(result)) {
1964 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_index_range() result_type %d not supported with INVERTED flag", result->type);
1965 return -AS_ERR_OP_NOT_APPLICABLE;
1966 }
1967
1968 result->flags &= ~AS_CDT_OP_FLAG_INVERTED;
1969
1970 if (count32 == 0) {
1971 // Reduce to remove all.
1972 uindex = 0;
1973 count32 = list->ele_count;
1974 }
1975 else if (uindex == 0) {
1976 // Reduce to remove tail section.
1977 uindex = count32;
1978 count32 = list->ele_count - count32;
1979 }
1980 else if (uindex + count32 >= list->ele_count) {
1981 // Reduce to remove head section.
1982 count32 = uindex;
1983 uindex = 0;
1984 }
1985 else {
1986 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
1987
1988 return packed_list_trim(list, com, uindex, count32);
1989 }
1990 }
1991
1992 if (count32 == 0) {
1993 if (! list_result_data_set_not_found(result, uindex)) {
1994 return -AS_ERR_OP_NOT_APPLICABLE;
1995 }
1996
1997 return AS_OK;
1998 }
1999
2000 define_packed_list_op(op, list);
2001 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2002
2003 if (! packed_list_op_remove(&op, uindex, count32)) {
2004 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_index_range() as_packed_list_remove failed");
2005 return -AS_ERR_PARAMETER;
2006 }
2007
2008 if (cdt_op_is_modify(com)) {
2009 if (op.new_ele_count == 0) {
2010 cdt_context_set_empty_list(&com->ctx, list_is_ordered(list));
2011 }
2012 else {
2013 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list->ext_flags,
2014 op.new_content_sz, op.new_ele_count, uindex, &list->offidx,
2015 NULL);
2016
2017 ptr += packed_list_op_write_seg1(&op, ptr);
2018 packed_list_op_write_seg2(&op, ptr);
2019 }
2020 }
2021
2022 switch (result->type) {
2023 case RESULT_TYPE_NONE:
2024 break;
2025 case RESULT_TYPE_INDEX:
2026 case RESULT_TYPE_REVINDEX:
2027 return result_data_set_index_rank_count(result, uindex, count32,
2028 list->ele_count);
2029 case RESULT_TYPE_RANK:
2030 case RESULT_TYPE_REVRANK: {
2031 if (op.new_ele_count == 0) {
2032 return result_data_set_index_rank_count(result, 0, count32,
2033 list->ele_count);
2034 }
2035
2036 if (! result->is_multi) {
2037 uint32_t rank;
2038
2039 if (list_is_ordered(list)) {
2040 rank = uindex;
2041 }
2042 else {
2043 uint32_t rcount;
2044
2045 cdt_payload value = {
2046 .ptr = list->contents + op.seg1_sz,
2047 .sz = list->content_sz - op.new_content_sz
2048 };
2049
2050 if (! packed_list_find_rank_range_by_value_interval_unordered(
2051 list, &value, &value, &rank, &rcount, NULL, false,
2052 false)) {
2053 return -AS_ERR_PARAMETER;
2054 }
2055 }
2056
2057 if (result->type == RESULT_TYPE_REVRANK) {
2058 rank = list->ele_count - rank - 1;
2059 }
2060
2061 as_bin_set_int(result->result, (int64_t)rank);
2062 break;
2063 }
2064
2065 msgpack_in pk = {
2066 .buf = list->contents + op.seg1_sz,
2067 .buf_sz = list->content_sz - op.new_content_sz
2068 };
2069
2070 uint32_t rm_count = list->ele_count - op.new_ele_count;
2071 define_int_list_builder(builder, result->alloc, rm_count);
2072
2073 if (list_is_ordered(list)) {
2074 cdt_container_builder_add_int_range(&builder, uindex, count32,
2075 list->ele_count, result->type == RESULT_TYPE_REVRANK);
2076 }
2077 else if (! packed_list_builder_add_ranks_by_range(list, &builder, &pk,
2078 rm_count, result->type == RESULT_TYPE_REVRANK)) {
2079 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_index_range() invalid list");
2080 return -AS_ERR_PARAMETER;
2081 }
2082
2083 cdt_container_builder_set_result(&builder, result);
2084 break;
2085 }
2086 case RESULT_TYPE_COUNT:
2087 as_bin_set_int(result->result, list->ele_count - op.new_ele_count);
2088 break;
2089 case RESULT_TYPE_VALUE: {
2090 const uint8_t *result_ptr = list->contents + op.seg1_sz;
2091 uint32_t end = (op.seg2_sz != 0) ? op.seg2_offset : list->content_sz;
2092 uint32_t result_sz = end - op.seg1_sz;
2093 uint32_t result_count = list->ele_count - op.new_ele_count;
2094
2095 if (result->is_multi) {
2096 result->result->particle =
2097 list_simple_create_from_buf(result->alloc,
2098 result_count, result_ptr, result_sz);
2099
2100 if (! result->result->particle) {
2101 return -AS_ERR_UNKNOWN;
2102 }
2103
2104 as_bin_state_set_from_type(result->result, AS_PARTICLE_TYPE_LIST);
2105 }
2106 else if (result_sz != 0) {
2107 cf_assert(count32 <= 1, AS_PARTICLE, "packed_list_get_remove_by_index_range() result must be list for count > 1");
2108 as_bin_particle_alloc_from_msgpack(result->result, result_ptr,
2109 result_sz);
2110 }
2111 // else - leave result bin empty because result_size is 0.
2112 break;
2113 }
2114 case RESULT_TYPE_REVINDEX_RANGE:
2115 if (result->type == RESULT_TYPE_REVINDEX_RANGE) {
2116 uindex = list->ele_count - uindex - count32;
2117 }
2118 // no break
2119 case RESULT_TYPE_INDEX_RANGE:
2120 result_data_set_list_int2x(result, uindex, count32);
2121 break;
2122 case RESULT_TYPE_RANK_RANGE:
2123 case RESULT_TYPE_REVRANK_RANGE:
2124 if (list_is_ordered(list)) {
2125 return result_data_set_range(result, uindex, count32,
2126 list->ele_count);
2127 }
2128 // no break
2129 default:
2130 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_index_range() result_type %d not supported", result->type);
2131 return -AS_ERR_OP_NOT_APPLICABLE;
2132 }
2133
2134#ifdef LIST_DEBUG_VERIFY
2135 if (! list_verify(&com->ctx)) {
2136 cdt_bin_print(com->ctx.b, "packed_list_get_remove_by_index_range");
2137 cf_crash(AS_PARTICLE, "packed_list_get_remove_by_index_range: index %ld count %lu", index, count);
2138 }
2139#endif
2140
2141 return AS_OK;
2142}
2143
2144// value_end == NULL means looking for: [value_start, largest possible value].
2145// value_start == value_end means looking for a single value: [value_start, value_start].
2146static int
2147packed_list_get_remove_by_value_interval(const packed_list *list,
2148 cdt_op_mem *com, const cdt_payload *value_start,
2149 const cdt_payload *value_end)
2150{
2151 cdt_result_data *result = &com->result;
2152 bool inverted = result_data_is_inverted(result);
2153
2154 if (inverted && ! result->is_multi) {
2155 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_value_interval() INVERTED flag not supported for single result ops");
2156 return -AS_ERR_OP_NOT_APPLICABLE;
2157 }
2158
2159 uint32_t rank;
2160 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2161
2162 if (list_is_ordered(list)) {
2163 uint32_t count;
2164
2165 if (! list_full_offset_index_fill_all(full->offidx)) {
2166 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_value_interval() invalid list");
2167 return -AS_ERR_PARAMETER;
2168 }
2169
2170 packed_list_find_rank_range_by_value_interval_ordered(list, value_start,
2171 value_end, &rank, &count, result->is_multi);
2172
2173 if (count == 0 && ! result->is_multi) {
2174 if (! list_result_data_set_not_found(result, 0)) {
2175 return -AS_ERR_OP_NOT_APPLICABLE;
2176 }
2177
2178 return AS_OK;
2179 }
2180
2181 return packed_list_get_remove_by_index_range(list, com, (int64_t)rank,
2182 (uint64_t)count);
2183 }
2184
2185 uint32_t rm_count;
2186 define_cdt_idx_mask(rm_mask, result->is_multi ? list->ele_count : 1,
2187 com->alloc_idx);
2188
2189 if (! packed_list_find_rank_range_by_value_interval_unordered(list,
2190 value_start, value_end, &rank, &rm_count, rm_mask, inverted,
2191 result->is_multi)) {
2192 return -AS_ERR_PARAMETER;
2193 }
2194
2195 uint32_t rm_sz = 0;
2196
2197 if (cdt_op_is_modify(com)) {
2198 if (rm_count == list->ele_count) {
2199 cdt_context_set_empty_list(&com->ctx, false);
2200 }
2201 else if (rm_count != 0) {
2202 int ret;
2203
2204 if (result->is_multi) {
2205 ret = packed_list_remove_by_mask(list, com, rm_mask, rm_count,
2206 &rm_sz);
2207 }
2208 else {
2209 // rm_mask[0] is an idx for single value finds.
2210 ret = packed_list_remove_by_idx(list, com, rm_mask[0], &rm_sz);
2211 }
2212
2213 if (ret != AS_OK) {
2214 return ret;
2215 }
2216 }
2217 else {
2218 packed_list_partial_offidx_update(list);
2219 }
2220 }
2221 else {
2222 packed_list_partial_offidx_update(list);
2223 }
2224
2225 switch (result->type) {
2226 case RESULT_TYPE_NONE:
2227 case RESULT_TYPE_COUNT:
2228 case RESULT_TYPE_REVRANK:
2229 case RESULT_TYPE_RANK:
2230 case RESULT_TYPE_REVRANK_RANGE:
2231 case RESULT_TYPE_RANK_RANGE:
2232 return result_data_set_range(result, rank, inverted ?
2233 list->ele_count - rm_count : rm_count, list->ele_count);
2234 case RESULT_TYPE_INDEX:
2235 case RESULT_TYPE_REVINDEX:
2236 if (result->is_multi) {
2237 result_data_set_int_list_by_mask(result, rm_mask, rm_count,
2238 list->ele_count);
2239 }
2240 else {
2241 result_data_set_index_rank_count(result, rm_mask[0], rm_count,
2242 list->ele_count);
2243 }
2244 break;
2245 case RESULT_TYPE_VALUE:
2246 if (result->is_multi) {
2247 list_result_data_set_values_by_mask(result, rm_mask,
2248 list_full_offidx_p(list), rm_count, rm_sz);
2249 }
2250 else {
2251 define_order_index2(rm_idx, list->ele_count, 1, com->alloc_idx);
2252
2253 order_index_set(&rm_idx, 0, rm_mask[0]);
2254 list_result_data_set_values_by_ordidx(result, &rm_idx, full->offidx,
2255 rm_count, rm_sz);
2256 }
2257 break;
2258 case RESULT_TYPE_INDEX_RANGE:
2259 case RESULT_TYPE_REVINDEX_RANGE:
2260 default:
2261 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_value_interval() result_type %d not supported", result->type);
2262 return -AS_ERR_OP_NOT_APPLICABLE;
2263 }
2264
2265 return AS_OK;
2266}
2267
2268static int
2269packed_list_get_remove_by_rank_range(const packed_list *list, cdt_op_mem *com,
2270 int64_t rank, uint64_t count)
2271{
2272 cdt_result_data *result = &com->result;
2273 bool inverted = result_data_is_inverted(result);
2274
2275 if (inverted && ! result->is_multi) {
2276 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() INVERTED flag not supported for single result ops");
2277 return -AS_ERR_OP_NOT_APPLICABLE;
2278 }
2279
2280 if (list_is_ordered(list)) {
2281 // idx == rank for ordered lists.
2282 return packed_list_get_remove_by_index_range(list, com, rank, count);
2283 }
2284
2285 uint32_t urank;
2286 uint32_t count32;
2287
2288 if (! calc_index_count(rank, count, list->ele_count, &urank, &count32,
2289 result->is_multi)) {
2290 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() rank %u out of bounds for ele_count %u", urank, list->ele_count);
2291 return -AS_ERR_OP_NOT_APPLICABLE;
2292 }
2293
2294 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2295
2296 if (! list_full_offset_index_fill_all(full->offidx)) {
2297 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() invalid packed list");
2298 return -AS_ERR_PARAMETER;
2299 }
2300
2301 define_build_order_heap_by_range(heap, urank, count32, list->ele_count,
2302 list, list_order_heap_cmp_fn, success, com->alloc_idx);
2303
2304 if (! success) {
2305 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() invalid packed list");
2306 return -AS_ERR_PARAMETER;
2307 }
2308
2309 uint32_t rm_count = inverted ? list->ele_count - count32 : count32;
2310
2311 if (rm_count == 0) {
2312 if (! list_result_data_set_not_found(result, urank)) {
2313 return -AS_ERR_OP_NOT_APPLICABLE;
2314 }
2315
2316 packed_list_partial_offidx_update(list);
2317
2318 return AS_OK;
2319 }
2320
2321 define_cdt_idx_mask(rm_mask, list->ele_count, com->alloc_idx);
2322 order_index ret_idx;
2323
2324 cdt_idx_mask_set_by_ordidx(rm_mask, &heap._, heap.filled, count32,
2325 inverted);
2326
2327 if (inverted) {
2328 if (result_data_is_return_rank_range(result)) {
2329 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() result_type %d not supported with INVERTED flag", result->type);
2330 return -AS_ERR_OP_NOT_APPLICABLE;
2331 }
2332
2333 if (! result->is_multi) {
2334 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() singe result type %d not supported with INVERTED flag", result->type);
2335 return -AS_ERR_OP_NOT_APPLICABLE;
2336 }
2337 }
2338 else {
2339 order_index_init_ref(&ret_idx, &heap._, heap.filled, rm_count);
2340 }
2341
2342 uint32_t rm_sz = 0;
2343
2344 if (cdt_op_is_modify(com)) {
2345 int ret = packed_list_remove_by_mask(list, com, rm_mask, rm_count,
2346 &rm_sz);
2347
2348 if (ret != AS_OK) {
2349 return ret;
2350 }
2351 }
2352 else {
2353 packed_list_partial_offidx_update(list);
2354 }
2355
2356 switch (result->type) {
2357 case RESULT_TYPE_NONE:
2358 case RESULT_TYPE_COUNT:
2359 case RESULT_TYPE_RANK:
2360 case RESULT_TYPE_REVRANK:
2361 case RESULT_TYPE_RANK_RANGE:
2362 case RESULT_TYPE_REVRANK_RANGE:
2363 return result_data_set_range(result, urank, count32, list->ele_count);
2364 case RESULT_TYPE_INDEX:
2365 case RESULT_TYPE_REVINDEX:
2366 result_data_set_int_list_by_mask(result, rm_mask, rm_count,
2367 list->ele_count);
2368 break;
2369 case RESULT_TYPE_VALUE:
2370 if (inverted) {
2371 list_result_data_set_values_by_mask(result, rm_mask,
2372 &list->full_offidx, rm_count, rm_sz);
2373 }
2374 else if (! list_result_data_set_values_by_ordidx(result, &ret_idx,
2375 &list->full_offidx, rm_count, rm_sz)) {
2376 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() invalid packed list");
2377 return -AS_ERR_PARAMETER;
2378 }
2379 break;
2380 case RESULT_TYPE_INDEX_RANGE:
2381 case RESULT_TYPE_REVINDEX_RANGE:
2382 default:
2383 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rank_range() result_type %d not supported", result->type);
2384 return -AS_ERR_OP_NOT_APPLICABLE;
2385 }
2386
2387 return AS_OK;
2388}
2389
2390static int
2391packed_list_get_remove_all_by_value_list_ordered(const packed_list *list,
2392 cdt_op_mem *com, as_unpacker *items_pk, uint32_t items_count)
2393{
2394 cdt_result_data *result = &com->result;
2395 cf_assert(result->is_multi, AS_PARTICLE, "not supported");
2396
2397 define_order_index2(rm_rc, list->ele_count, 2 * items_count,
2398 com->alloc_idx);
2399 uint32_t rc_count = 0;
2400
2401 for (uint32_t i = 0; i < items_count; i++) {
2402 cdt_payload value = { items_pk->buffer + items_pk->offset };
2403 int64_t sz = as_unpack_size(items_pk);
2404
2405 if (sz <= 0) {
2406 cf_warning(AS_PARTICLE, "packed_list_get_remove_all_by_value_list_ordered() invalid list");
2407 return -AS_ERR_PARAMETER;
2408 }
2409
2410 value.sz = (uint32_t)sz;
2411
2412 uint32_t rank;
2413 uint32_t count;
2414
2415 packed_list_find_rank_range_by_value_interval_ordered(list, &value,
2416 &value, &rank, &count, true);
2417
2418 order_index_set(&rm_rc, 2 * i, rank);
2419 order_index_set(&rm_rc, (2 * i) + 1, count);
2420 rc_count += count;
2421 }
2422
2423 uint32_t rm_sz = 0;
2424 uint32_t rm_count = 0;
2425 bool inverted = result_data_is_inverted(result);
2426 bool need_mask = (cdt_op_is_modify(com) ||
2427 result->type == RESULT_TYPE_COUNT ||
2428 (inverted && result->type != RESULT_TYPE_NONE));
2429 define_cond_cdt_idx_mask(rm_mask, list->ele_count, need_mask,
2430 com->alloc_idx);
2431
2432 if (need_mask) {
2433 cdt_idx_mask_set_by_irc(rm_mask, &rm_rc, NULL, inverted);
2434 rm_count = cdt_idx_mask_bit_count(rm_mask, list->ele_count);
2435 }
2436
2437 if (cdt_op_is_modify(com)) {
2438 if (rm_count == list->ele_count) {
2439 cdt_context_set_empty_list(&com->ctx, true);
2440 }
2441 else if (rm_count != 0) {
2442 int ret = packed_list_remove_by_mask(list, com, rm_mask, rm_count,
2443 &rm_sz);
2444
2445 if (ret != AS_OK) {
2446 return ret;
2447 }
2448 }
2449 else {
2450 packed_list_partial_offidx_update(list);
2451 }
2452 }
2453 else {
2454 packed_list_partial_offidx_update(list);
2455 }
2456
2457 switch (result->type) {
2458 case RESULT_TYPE_NONE:
2459 break;
2460 case RESULT_TYPE_COUNT:
2461 as_bin_set_int(result->result, rm_count);
2462 break;
2463 case RESULT_TYPE_INDEX:
2464 case RESULT_TYPE_REVINDEX:
2465 case RESULT_TYPE_RANK:
2466 case RESULT_TYPE_REVRANK:
2467 if (inverted) {
2468 result_data_set_int_list_by_mask(result, rm_mask, rm_count,
2469 list->ele_count);
2470 }
2471 else {
2472 result_data_set_by_irc(result, &rm_rc, NULL, rc_count);
2473 }
2474 break;
2475 case RESULT_TYPE_VALUE: {
2476 if (inverted) {
2477 list_result_data_set_values_by_mask(result, rm_mask, &list->offidx,
2478 rm_count, rm_sz);
2479 }
2480 else {
2481 list_result_data_set_values_by_idxcount(result, &rm_rc,
2482 &list->offidx);
2483 }
2484 break;
2485 }
2486 default:
2487 cf_warning(AS_PARTICLE, "packed_list_get_remove_all_by_value_list_ordered() result_type %d not supported", result->type);
2488 return -AS_ERR_OP_NOT_APPLICABLE;
2489 }
2490
2491#ifdef LIST_DEBUG_VERIFY
2492 if (! list_verify(&com->ctx)) {
2493 cdt_bin_print(com->ctx.b, "packed_list_get_remove_all_by_value_list_ordered");
2494 list_print(list, "original");
2495 cf_crash(AS_PARTICLE, "all_by_value_list_ordered: ele_count %u items_count %u rm_count %u", list->ele_count, items_count, rm_count);
2496 }
2497#endif
2498
2499 return AS_OK;
2500}
2501
2502static int
2503packed_list_get_remove_all_by_value_list(const packed_list *list,
2504 cdt_op_mem *com, const cdt_payload *value_list)
2505{
2506 cdt_result_data *result = &com->result;
2507
2508 if (result_data_is_return_rank_range(result) ||
2509 result_data_is_return_index_range(result)) {
2510 cf_warning(AS_PARTICLE, "packed_list_op_get_remove_all_by_value_list() result_type %d not supported", result->type);
2511 return -AS_ERR_OP_NOT_APPLICABLE;
2512 }
2513
2514 as_unpacker items_pk;
2515 uint32_t items_count;
2516
2517 if (! list_param_parse(value_list, &items_pk, &items_count)) {
2518 return -AS_ERR_PARAMETER;
2519 }
2520
2521 bool inverted = result_data_is_inverted(result);
2522
2523 if (items_count == 0) {
2524 if (! inverted) {
2525 if (! list_result_data_set_not_found(result, 0)) {
2526 cf_warning(AS_PARTICLE, "packed_list_get_remove_all_by_value_list() invalid result type %d", result->type);
2527 return -AS_ERR_OP_NOT_APPLICABLE;
2528 }
2529
2530 return AS_OK;
2531 }
2532
2533 result->flags &= ~AS_CDT_OP_FLAG_INVERTED;
2534
2535 return packed_list_get_remove_by_index_range(list, com, 0,
2536 list->ele_count);
2537 }
2538
2539 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2540
2541 if (list_is_ordered(list)) {
2542 if (! list_full_offset_index_fill_all(full->offidx)) {
2543 cf_warning(AS_PARTICLE, "packed_list_get_remove_all_by_value_list_ordered() invalid list");
2544 return -AS_ERR_PARAMETER;
2545 }
2546
2547 return packed_list_get_remove_all_by_value_list_ordered(list, com,
2548 &items_pk, items_count);
2549 }
2550
2551 bool is_ret_rank = result_data_is_return_rank(result);
2552 uint32_t rm_count = 0;
2553 define_order_index(value_list_ordidx, items_count, com->alloc_idx);
2554 define_cdt_idx_mask(rm_mask, list->ele_count, com->alloc_idx);
2555 definep_cond_order_index2(rc, list->ele_count, items_count * 2,
2556 is_ret_rank, com->alloc_idx);
2557
2558 if (! offset_index_find_items(full->offidx,
2559 CDT_FIND_ITEMS_IDXS_FOR_LIST_VALUE, &items_pk, &value_list_ordidx,
2560 inverted, rm_mask, &rm_count, rc, com->alloc_idx)) {
2561 return -AS_ERR_PARAMETER;
2562 }
2563
2564 uint32_t rm_sz = 0;
2565
2566 if (cdt_op_is_modify(com)) {
2567 if (rm_count == list->ele_count) {
2568 cdt_context_set_empty_list(&com->ctx, false);
2569 }
2570 else if (rm_count != 0) {
2571 int ret = packed_list_remove_by_mask(list, com, rm_mask, rm_count,
2572 &rm_sz);
2573
2574 if (ret != AS_OK) {
2575 return ret;
2576 }
2577 }
2578 else {
2579 packed_list_partial_offidx_update(list);
2580 }
2581 }
2582 else {
2583 packed_list_partial_offidx_update(list);
2584 }
2585
2586 switch (result->type) {
2587 case RESULT_TYPE_NONE:
2588 break;
2589 case RESULT_TYPE_INDEX:
2590 case RESULT_TYPE_REVINDEX:
2591 result_data_set_int_list_by_mask(result, rm_mask, rm_count,
2592 list->ele_count);
2593 break;
2594 case RESULT_TYPE_RANK:
2595 case RESULT_TYPE_REVRANK:
2596 result_data_set_by_itemlist_irc(result, &value_list_ordidx, rc,
2597 rm_count);
2598 break;
2599 case RESULT_TYPE_COUNT:
2600 as_bin_set_int(result->result, rm_count);
2601 break;
2602 case RESULT_TYPE_VALUE: {
2603 list_result_data_set_values_by_mask(result, rm_mask, full->offidx,
2604 rm_count, rm_sz);
2605 break;
2606 }
2607 default:
2608 cf_warning(AS_PARTICLE, "packed_list_op_get_remove_all_by_value_list() result_type %d not supported", result->type);
2609 return -AS_ERR_OP_NOT_APPLICABLE;
2610 }
2611
2612 return AS_OK;
2613}
2614
2615static int
2616packed_list_get_remove_by_rel_rank_range(const packed_list *list,
2617 cdt_op_mem *com, const cdt_payload *value, int64_t rank, uint64_t count)
2618{
2619 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2620 cdt_result_data *result = &com->result;
2621
2622 if (! list_full_offset_index_fill_all(full->offidx)) {
2623 cf_warning(AS_PARTICLE, "packed_list_get_remove_by_rel_rank_range() invalid list");
2624 return -AS_ERR_PARAMETER;
2625 }
2626
2627 if (list_is_ordered(list)) {
2628 uint32_t rel_rank;
2629 uint32_t temp;
2630
2631 packed_list_find_rank_range_by_value_interval_ordered(list, value,
2632 value, &rel_rank, &temp, result->is_multi);
2633
2634 calc_rel_index_count(rank, count, rel_rank, &rank, &count);
2635
2636 return packed_list_get_remove_by_index_range(list, com, rank, count);
2637 }
2638
2639 uint32_t rel_rank;
2640 uint32_t temp;
2641
2642 if (! packed_list_find_rank_range_by_value_interval_unordered(list,
2643 value, value, &rel_rank, &temp, NULL,
2644 result_data_is_inverted(result), result->is_multi)) {
2645 return -AS_ERR_PARAMETER;
2646 }
2647
2648 calc_rel_index_count(rank, count, rel_rank, &rank, &count);
2649
2650 return packed_list_get_remove_by_rank_range(list, com, rank, count);
2651}
2652
2653static int
2654packed_list_insert(const packed_list *list, cdt_op_mem *com, int64_t index,
2655 const cdt_payload *payload, bool payload_is_list, uint64_t mod_flags,
2656 bool set_result)
2657{
2658 cdt_result_data *result = set_result ? &com->result : NULL;
2659 uint32_t param_count = 1;
2660 uint32_t payload_hdr_sz = 0;
2661
2662 if (payload_is_list) {
2663 int64_t payload_count =
2664 as_unpack_buf_list_element_count(payload->ptr, payload->sz);
2665
2666 if (payload_count < 0) {
2667 cf_warning(AS_PARTICLE, "packed_list_insert() invalid payload, expected a list");
2668 return -AS_ERR_PARAMETER;
2669 }
2670
2671 if (payload_count == 0) {
2672 result_data_set_int(result, list->ele_count);
2673 return AS_OK;
2674 }
2675
2676 param_count = (uint32_t)payload_count;
2677 payload_hdr_sz = as_pack_list_header_get_size(param_count);
2678
2679 if (payload_hdr_sz > payload->sz) {
2680 cf_warning(AS_PARTICLE, "packed_list_insert() invalid list header: payload->size=%d", payload->sz);
2681 return -AS_ERR_PARAMETER;
2682 }
2683 }
2684
2685 if (index > INT32_MAX || (index = calc_index(index, list->ele_count)) < 0) {
2686 cf_warning(AS_PARTICLE, "packed_list_insert() index %ld out of bounds for ele_count %d", index > 0 ? index : index - list->ele_count, list->ele_count);
2687 return -AS_ERR_OP_NOT_APPLICABLE;
2688 }
2689
2690 if (mod_flags_is_bounded(mod_flags) && (uint32_t)index > list->ele_count) {
2691 if (mod_flags_is_no_fail(mod_flags)) {
2692 result_data_set_int(result, list->ele_count);
2693 return AS_OK; // no-op
2694 }
2695
2696 return -AS_ERR_OP_NOT_APPLICABLE;
2697 }
2698
2699 uint32_t rm_sz = 0;
2700 uint32_t rm_count = 0;
2701 bool is_unique = mod_flags_is_unique(mod_flags);
2702 define_cond_cdt_idx_mask(pfound, param_count, is_unique, com->alloc_idx);
2703
2704 if (is_unique) {
2705 // Assume only here for the unordered case.
2706 if (payload_is_list) {
2707 msgpack_in pk = {
2708 .buf = payload->ptr + payload_hdr_sz,
2709 .buf_sz = payload->sz - payload_hdr_sz
2710 };
2711
2712 for (uint32_t i = 0; i < param_count; i++) {
2713 cdt_payload val;
2714 uint32_t rank;
2715 uint32_t count;
2716
2717 val.ptr = pk.buf + pk.offset;
2718 val.sz = msgpack_sz(&pk);
2719
2720 if (val.sz == 0) {
2721 cf_warning(AS_PARTICLE, "packed_list_insert() invalid parameters");
2722 return -AS_ERR_PARAMETER;
2723 }
2724
2725 if (! packed_list_find_rank_range_by_value_interval_unordered(
2726 list, &val, &val, &rank, &count, NULL, false, false)) {
2727 return -AS_ERR_PARAMETER;
2728 }
2729
2730 if (count == 0) {
2731 msgpack_in cmp0 = {
2732 .buf = val.ptr,
2733 .buf_sz = val.sz
2734 };
2735
2736 msgpack_in cmp1 = pk;
2737 bool found = false;
2738
2739 cmp1.offset = 0;
2740
2741 for (uint32_t j = 0; j < i; j++) {
2742 cmp0.offset = 0;
2743
2744 msgpack_compare_t cmp = msgpack_cmp(&cmp0, &cmp1);
2745
2746 if (cmp == MSGPACK_COMPARE_EQUAL) {
2747 if (! mod_flags_is_no_fail(mod_flags)) {
2748 return -AS_ERR_OP_NOT_APPLICABLE;
2749 }
2750
2751 if (! mod_flags_is_do_partial(mod_flags)) {
2752 result_data_set_int(result, list->ele_count);
2753 return AS_OK;
2754 }
2755
2756 rm_sz += val.sz;
2757 rm_count++;
2758 found = true;
2759 break;
2760 }
2761 }
2762
2763 if (! found) {
2764 cdt_idx_mask_set(pfound, i);
2765 }
2766 }
2767 else {
2768 if (mod_flags_is_do_partial(mod_flags)) {
2769 rm_sz += val.sz;
2770 rm_count++;
2771 }
2772 else {
2773 result_data_set_int(result, list->ele_count);
2774 return mod_flags_return_exists(mod_flags);
2775 }
2776 }
2777 }
2778
2779 if (param_count == rm_count) {
2780 result_data_set_int(result, list->ele_count);
2781 return mod_flags_return_exists(mod_flags);
2782 }
2783 }
2784 else {
2785 uint32_t rank;
2786 uint32_t count;
2787
2788 if (! packed_list_find_rank_range_by_value_interval_unordered(list,
2789 payload, payload, &rank, &count, NULL, false, false)) {
2790 return -AS_ERR_PARAMETER;
2791 }
2792
2793 if (count != 0) {
2794 result_data_set_int(result, list->ele_count);
2795 return mod_flags_return_exists(mod_flags);
2796 }
2797 }
2798 }
2799
2800 uint32_t uindex = (uint32_t)index;
2801 define_packed_list_op(op, list);
2802 uint32_t insert_sz = payload->sz - payload_hdr_sz - rm_sz;
2803 uint32_t add_count = param_count - rm_count;
2804
2805 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2806
2807 if (! packed_list_op_insert(&op, uindex, add_count, insert_sz)) {
2808 cf_warning(AS_PARTICLE, "packed_list_insert() packed_list_op_insert failed");
2809 return -AS_ERR_PARAMETER;
2810 }
2811
2812 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list->ext_flags,
2813 op.new_content_sz, op.new_ele_count, uindex, &list->offidx, NULL);
2814
2815 ptr += packed_list_op_write_seg1(&op, ptr);
2816
2817 const uint8_t *p = payload->ptr + payload_hdr_sz;
2818
2819 if (rm_sz == 0) {
2820 uint32_t sz = payload->sz - payload_hdr_sz;
2821
2822 memcpy(ptr, p, sz);
2823 ptr += sz;
2824 }
2825 else {
2826 msgpack_in pk = {
2827 .buf = payload->ptr + payload_hdr_sz,
2828 .buf_sz = payload->sz - payload_hdr_sz
2829 };
2830
2831 uint32_t idx = 0;
2832
2833 for (uint32_t i = 0; i < add_count; i++) {
2834 uint32_t next = cdt_idx_mask_find(pfound, idx, param_count, false);
2835 uint32_t skip = next - idx;
2836
2837 for (uint32_t j = 0; j < skip; j++) {
2838 msgpack_sz(&pk);
2839 }
2840
2841 const uint8_t *begin = pk.buf + pk.offset;
2842 size_t sz = (size_t)msgpack_sz(&pk);
2843
2844 memcpy(ptr, begin, sz);
2845 ptr += sz;
2846 idx = next + 1;
2847 }
2848 }
2849
2850 packed_list_op_write_seg2(&op, ptr);
2851 result_data_set_int(result, op.new_ele_count);
2852
2853#ifdef LIST_DEBUG_VERIFY
2854 if (! list_verify(&com->ctx)) {
2855 cdt_bin_print(com->ctx.b, "packed_list_insert");
2856 cdt_context_print(&com->ctx, "ctx");
2857 cf_crash(AS_PARTICLE, "packed_list_insert: index %ld payload_is_list %d mod_flags 0x%lX", index, payload_is_list, mod_flags);
2858 }
2859#endif
2860
2861 return AS_OK;
2862}
2863
2864static int
2865packed_list_add_ordered(const packed_list *list, cdt_op_mem *com,
2866 const cdt_payload *payload, uint64_t mod_flags)
2867{
2868 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2869
2870 if (! list_full_offset_index_fill_all(full->offidx)) {
2871 cf_warning(AS_PARTICLE, "packed_list_add_ordered() invalid list");
2872 return -AS_ERR_PARAMETER;
2873 }
2874
2875 order_index_find find = {
2876 .target = list->ele_count + 1
2877 };
2878
2879 packed_list_find_by_value_ordered(list, payload, &find);
2880
2881 if (find.found && mod_flags_is_unique(mod_flags)) {
2882 result_data_set_int(&com->result, list->ele_count);
2883 return mod_flags_return_exists(mod_flags);
2884 }
2885
2886 return packed_list_insert(list, com, (int64_t)find.result, payload,
2887 false, AS_CDT_LIST_MODIFY_DEFAULT, true);
2888}
2889
2890static int
2891packed_list_add_items_ordered(const packed_list *list, cdt_op_mem *com,
2892 const cdt_payload *items, uint64_t mod_flags)
2893{
2894 cdt_result_data *result = &com->result;
2895 int64_t add_count = as_unpack_buf_list_element_count(items->ptr, items->sz);
2896
2897 if (add_count < 0) {
2898 cf_warning(AS_PARTICLE, "packed_list_add_items_ordered() invalid payload, expected a list");
2899 return -AS_ERR_PARAMETER;
2900 }
2901
2902 if (add_count == 0) {
2903 result_data_set_int(result, list->ele_count);
2904 return AS_OK; // no-op
2905 }
2906
2907 uint32_t val_count = (uint32_t)add_count;
2908 uint32_t hdr_sz = as_pack_list_header_get_size(val_count);
2909
2910 if (hdr_sz > items->sz) {
2911 cf_warning(AS_PARTICLE, "packed_list_add_items_ordered() invalid list header: payload->size=%d", items->sz);
2912 return -AS_ERR_PARAMETER;
2913 }
2914
2915 // Sort items to add.
2916 define_order_index(val_ord, val_count, com->alloc_idx);
2917 define_offset_index(val_off, items->ptr + hdr_sz, items->sz - hdr_sz,
2918 val_count, com->alloc_idx);
2919
2920 if (! list_full_offset_index_fill_all(&val_off) ||
2921 ! list_order_index_sort(&val_ord, &val_off,
2922 AS_CDT_SORT_ASCENDING)) {
2923 cf_warning(AS_PARTICLE, "packed_list_add_items_ordered() invalid list");
2924 return -AS_ERR_PARAMETER;
2925 }
2926
2927 bool unique = mod_flags_is_unique(mod_flags);
2928
2929 if (unique) {
2930 uint32_t rm_count;
2931 uint32_t rm_sz;
2932 bool success = order_index_sorted_mark_dup_eles(&val_ord, &val_off,
2933 &rm_count, &rm_sz);
2934 cf_assert(success, AS_PARTICLE, "remove dup failed");
2935
2936 if (rm_count != 0) {
2937 if (! mod_flags_is_no_fail(mod_flags)) {
2938 return -AS_ERR_OP_NOT_APPLICABLE;
2939 }
2940
2941 if (! mod_flags_is_do_partial(mod_flags)) {
2942 as_bin_set_int(result->result, list->ele_count);
2943 return AS_OK;
2944 }
2945 }
2946 }
2947
2948 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
2949 define_order_index2(insert_idx, list->ele_count, val_count, com->alloc_idx);
2950 uint32_t new_content_sz = list->content_sz;
2951 uint32_t new_ele_count = list->ele_count;
2952
2953 if (! list_full_offset_index_fill_all(full->offidx)) {
2954 cf_warning(AS_PARTICLE, "packed_list_add_items_ordered() invalid list");
2955 return -AS_ERR_PARAMETER;
2956 }
2957
2958 for (uint32_t i = 0; i < val_count; i++) {
2959 uint32_t val_idx = order_index_get(&val_ord, i);
2960
2961 if (val_idx == val_count) {
2962 continue;
2963 }
2964
2965 uint32_t off = offset_index_get_const(&val_off, val_idx);
2966 uint32_t sz = offset_index_get_delta_const(&val_off, val_idx);
2967
2968 const cdt_payload value = {
2969 .ptr = items->ptr + hdr_sz + off,
2970 .sz = sz
2971 };
2972
2973 order_index_find find = {
2974 .target = list->ele_count + 1
2975 };
2976
2977 packed_list_find_by_value_ordered(list, &value, &find);
2978
2979 if (unique && find.found) {
2980 if (mod_flags_is_do_partial(mod_flags)) {
2981 order_index_set(&val_ord, i, val_count);
2982 }
2983 else {
2984 as_bin_set_int(result->result, list->ele_count);
2985 return mod_flags_return_exists(mod_flags);
2986 }
2987 }
2988 else {
2989 order_index_set(&insert_idx, i, find.result);
2990 new_content_sz += sz;
2991 new_ele_count++;
2992 }
2993 }
2994
2995 // Construct new list.
2996 offset_index new_offidx;
2997 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list->ext_flags,
2998 new_content_sz, new_ele_count, 0, &list->offidx, &new_offidx);
2999 uint32_t list_start = 0;
3000
3001 bool has_new_offidx = ! offset_index_is_null(&new_offidx);
3002 uint32_t new_idx = 0;
3003 uint32_t cpy_delta = 0;
3004 uint32_t cur_offset = 0;
3005
3006 for (uint32_t i = 0; i < val_count; i++) {
3007 uint32_t val_idx = order_index_get(&val_ord, i);
3008
3009 if (val_idx == val_count) {
3010 continue;
3011 }
3012
3013 uint32_t list_idx = order_index_get(&insert_idx, i);
3014
3015 if (list_idx > list_start) {
3016 uint32_t off0 = offset_index_get_const(&list->offidx, list_start);
3017 uint32_t off1 = offset_index_get_const(&list->offidx, list_idx);
3018 uint32_t seg_count = list_idx - list_start;
3019 uint32_t seg_sz = off1 - off0;
3020
3021 memcpy(ptr, list->contents + off0, seg_sz);
3022 ptr += seg_sz;
3023
3024 if (has_new_offidx) {
3025 offset_index_copy(&new_offidx, &list->offidx, new_idx,
3026 list_start, seg_count, cpy_delta);
3027 new_idx += seg_count;
3028 cur_offset = off1 + cpy_delta;
3029 }
3030
3031 list_start = list_idx;
3032 }
3033
3034 uint32_t off = offset_index_get_const(&val_off, val_idx);
3035 uint32_t val_sz = offset_index_get_delta_const(&val_off, val_idx);
3036
3037 memcpy(ptr, items->ptr + hdr_sz + off, val_sz);
3038 ptr += val_sz;
3039
3040 if (has_new_offidx) {
3041 offset_index_set(&new_offidx, new_idx++, cur_offset);
3042 cpy_delta += val_sz;
3043 cur_offset += val_sz;
3044 }
3045 }
3046
3047 if (list_start < list->ele_count && list->ele_count != 0) {
3048 uint32_t off = offset_index_get_const(&list->offidx, list_start);
3049 uint32_t seg_count = list->ele_count - list_start;
3050
3051 memcpy(ptr, list->contents + off, list->content_sz - off);
3052
3053 if (has_new_offidx) {
3054 offset_index_copy(&new_offidx, &list->offidx, new_idx, list_start,
3055 seg_count, cpy_delta);
3056 }
3057 }
3058
3059 if (has_new_offidx) {
3060 offset_index_set_filled(&new_offidx, new_ele_count);
3061 }
3062
3063 result_data_set_int(result, new_ele_count);
3064
3065#ifdef LIST_DEBUG_VERIFY
3066 if (! list_verify(&com->ctx)) {
3067 cdt_bin_print(com->ctx.b, "packed_list_add_items_ordered");
3068 list_print(list, "original");
3069 cf_crash(AS_PARTICLE, "add_items_ordered: val_count %u", val_count);
3070 }
3071#endif
3072
3073 return AS_OK;
3074}
3075
3076static int
3077packed_list_replace_ordered(const packed_list *list, cdt_op_mem *com,
3078 uint32_t index, const cdt_payload *value, uint64_t mod_flags)
3079{
3080 uint32_t rank;
3081 uint32_t count;
3082
3083 setup_list_must_have_full_offidx(full, list, com->alloc_idx);
3084
3085 if (! list_full_offset_index_fill_all(full->offidx)) {
3086 cf_warning(AS_PARTICLE, "packed_list_replace_ordered() invalid list");
3087 return -AS_ERR_PARAMETER;
3088 }
3089
3090 packed_list_find_rank_range_by_value_interval_ordered(list, value, value,
3091 &rank, &count, false);
3092
3093 define_packed_list_op(op, list);
3094
3095 if (index > list->ele_count) {
3096 cf_warning(AS_PARTICLE, "packed_list_replace_ordered() index %u > ele_count %u out of bounds not allowed for ORDERED lists", index, list->ele_count);
3097 return -AS_ERR_OP_NOT_APPLICABLE;
3098 }
3099
3100 if (! packed_list_op_remove(&op, index, 1)) {
3101 cf_warning(AS_PARTICLE, "packed_list_replace_ordered() as_packed_list_remove failed");
3102 return -AS_ERR_PARAMETER;
3103 }
3104
3105 if (mod_flags_is_unique(mod_flags) && count != 0) {
3106 if (rank == index) { // uniquely replacing element with same value
3107 return AS_OK; // no-op
3108 }
3109
3110 return mod_flags_return_exists(mod_flags);
3111 }
3112
3113 uint32_t new_ele_count = list->ele_count;
3114
3115 op.new_content_sz += value->sz;
3116
3117 if (index == list->ele_count) {
3118 new_ele_count++;
3119 }
3120
3121 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list->ext_flags,
3122 op.new_content_sz, new_ele_count, (rank < index) ? rank : index,
3123 &list->offidx, NULL);
3124 uint32_t offset = offset_index_get_const(full->offidx, rank);
3125
3126 if (rank <= index) {
3127 uint32_t tail_sz = op.seg1_sz - offset;
3128
3129 memcpy(ptr, list->contents, offset);
3130 ptr += offset;
3131 memcpy(ptr, value->ptr, value->sz);
3132 ptr += value->sz;
3133 memcpy(ptr, list->contents + offset, tail_sz);
3134 ptr += tail_sz;
3135 packed_list_op_write_seg2(&op, ptr);
3136 }
3137 else if (op.seg2_sz == 0) {
3138 ptr += packed_list_op_write_seg1(&op, ptr);
3139 memcpy(ptr, value->ptr, value->sz);
3140 }
3141 else {
3142 uint32_t head_sz = offset - op.seg2_offset;
3143 uint32_t tail_sz = op.seg2_sz - head_sz;
3144
3145 ptr += packed_list_op_write_seg1(&op, ptr);
3146 memcpy(ptr, list->contents + op.seg2_offset, head_sz);
3147 ptr += head_sz;
3148 memcpy(ptr, value->ptr, value->sz);
3149 ptr += value->sz;
3150 memcpy(ptr, list->contents + offset, tail_sz);
3151 }
3152
3153 return AS_OK;
3154}
3155
3156static bool
3157packed_list_check_order_and_fill_offidx(const packed_list *list)
3158{
3159 if (list->ele_count == 0) {
3160 return true;
3161 }
3162
3163 offset_index *offidx = (offset_index *)&list->offidx;
3164
3165 if (list_is_ordered(list)) {
3166 if (! offset_index_check_order_and_fill(offidx, false)) {
3167 return false;
3168 }
3169 }
3170 else if (! offset_index_is_null(offidx)) {
3171 msgpack_in pk = {
3172 .buf = list->contents,
3173 .buf_sz = list->content_sz
3174 };
3175
3176 uint32_t blocks = list_offset_partial_index_count(list->ele_count);
3177
3178 for (uint32_t j = 1; j < blocks; j++) {
3179 if (msgpack_sz_rep(&pk, PACKED_LIST_INDEX_STEP) == 0 ||
3180 pk.has_nonstorage) {
3181 return false;
3182 }
3183
3184 offset_index_set(offidx, j, pk.offset);
3185 }
3186
3187 offset_index_set_filled(offidx, blocks);
3188
3189 uint32_t mod_count = list->ele_count % PACKED_LIST_INDEX_STEP;
3190
3191 if (mod_count != 0 &&
3192 (msgpack_sz_rep(&pk, mod_count) == 0 || pk.has_nonstorage)) {
3193 return false;
3194 }
3195 }
3196 else {
3197 msgpack_in pk = {
3198 .buf = list->contents,
3199 .buf_sz = list->content_sz
3200 };
3201
3202 if (msgpack_sz_rep(&pk, list->ele_count) == 0 || pk.has_nonstorage) {
3203 return false;
3204 }
3205 }
3206
3207 return true;
3208}
3209
3210//----------------------------------------------------------
3211// packed_list_op
3212//
3213
3214static void
3215packed_list_op_init(packed_list_op *op, const packed_list *list)
3216{
3217 memset(op, 0, sizeof(packed_list_op));
3218 op->list = list;
3219}
3220
3221// Calculate a packed list split via insert op.
3222// Return true on success.
3223static bool
3224packed_list_op_insert(packed_list_op *op, uint32_t index, uint32_t count,
3225 uint32_t insert_sz)
3226{
3227 uint32_t ele_count = op->list->ele_count;
3228
3229 if (index >= ele_count) { // insert off the end
3230 if (index + count >= INT32_MAX) {
3231 cf_warning(AS_PARTICLE, "as_packed_list_insert() index %u + count %u overflow", index, count);
3232 return false;
3233 }
3234
3235 op->new_ele_count = index + count;
3236 op->nil_ele_sz = index - ele_count;
3237
3238 op->seg1_sz = op->list->content_sz;
3239 op->seg2_sz = 0;
3240 }
3241 else { // insert front or middle
3242 op->new_ele_count = ele_count + count;
3243 op->nil_ele_sz = 0;
3244 uint32_t offset = packed_list_find_idx_offset(op->list, index);
3245
3246 if (index != 0 && offset == 0) {
3247 return false;
3248 }
3249
3250 op->seg1_sz = offset;
3251 op->seg2_offset = offset;
3252 op->seg2_sz = op->list->content_sz - offset;
3253 }
3254
3255 op->new_content_sz = op->seg1_sz + op->nil_ele_sz + insert_sz + op->seg2_sz;
3256
3257 return true;
3258}
3259
3260// Calculate a packed list split via remove op.
3261// Assume count != 0.
3262// Return true on success.
3263static bool
3264packed_list_op_remove(packed_list_op *op, uint32_t index, uint32_t count)
3265{
3266 uint32_t ele_count = op->list->ele_count;
3267
3268 if (index >= ele_count) { // nothing to remove
3269 op->seg1_sz = op->list->content_sz;
3270 op->seg2_sz = 0;
3271 op->new_ele_count = ele_count;
3272 op->new_content_sz = op->list->content_sz;
3273
3274 return true;
3275 }
3276
3277 uint32_t offset = packed_list_find_idx_offset(op->list, index);
3278
3279 if (index != 0 && offset == 0) {
3280 return false;
3281 }
3282
3283 if (count >= ele_count - index) { // remove tail elements
3284 op->new_ele_count = index;
3285
3286 op->seg1_sz = offset;
3287 op->seg2_offset = 0;
3288 op->seg2_sz = 0;
3289 }
3290 else { // remove front or middle
3291 op->new_ele_count = ele_count - count;
3292 op->seg1_sz = offset;
3293
3294 uint32_t end_off = packed_list_find_idx_offset_continue(op->list,
3295 index + count, index, offset);
3296
3297 if (end_off == 0) {
3298 return false;
3299 }
3300
3301 op->seg2_offset = end_off;
3302 op->seg2_sz = op->list->content_sz - end_off;
3303 }
3304
3305 op->new_content_sz = op->seg1_sz + op->seg2_sz;
3306
3307 return true;
3308}
3309
3310// Write segment 1 and trailing nils if any.
3311// Return number of bytes written.
3312static uint32_t
3313packed_list_op_write_seg1(const packed_list_op *op, uint8_t *buf)
3314{
3315 memcpy(buf, op->list->contents, op->seg1_sz);
3316
3317 if (op->nil_ele_sz == 0) {
3318 return op->seg1_sz;
3319 }
3320
3321 buf += op->seg1_sz;
3322 memset(buf, msgpack_nil[0], op->nil_ele_sz);
3323
3324 return op->seg1_sz + op->nil_ele_sz;
3325}
3326
3327// Write segment 2 if any.
3328// Return number of bytes written.
3329static uint32_t
3330packed_list_op_write_seg2(const packed_list_op *op, uint8_t *buf)
3331{
3332 if (op->seg2_sz == 0) {
3333 return 0;
3334 }
3335
3336 memcpy(buf, op->list->contents + op->seg2_offset, op->seg2_sz);
3337
3338 return op->seg2_sz;
3339}
3340
3341static bool
3342packed_list_builder_add_ranks_by_range(const packed_list *list,
3343 cdt_container_builder *builder, msgpack_in *start, uint32_t count,
3344 bool reverse)
3345{
3346 for (uint32_t i = 0; i < count; i++) {
3347 cdt_payload value = {
3348 .ptr = start->buf + start->offset
3349 };
3350
3351 value.sz = msgpack_sz(start);
3352
3353 if (value.sz == 0) {
3354 return false;
3355 }
3356
3357 uint32_t rank;
3358 uint32_t rcount;
3359
3360 if (! packed_list_find_rank_range_by_value_interval_unordered(list,
3361 &value, &value, &rank, &rcount, NULL, false, false)) {
3362 return false;
3363 }
3364
3365 cdt_container_builder_add_int64(builder,
3366 reverse ? list->ele_count - rank - 1 : rank);
3367 }
3368
3369 return true;
3370}
3371
3372//----------------------------------------------------------
3373// list
3374//
3375
3376// Create a non-indexed list.
3377// If alloc_buf is NULL, memory is reserved using cf_malloc.
3378static list_mem *
3379list_create(rollback_alloc *alloc_buf, uint32_t ele_count, uint32_t content_sz)
3380{
3381 uint32_t hdr_sz = as_pack_list_header_get_size(ele_count);
3382 uint32_t sz = hdr_sz + content_sz;
3383 list_mem *p_list_mem = (list_mem *)rollback_alloc_reserve(alloc_buf,
3384 sizeof(list_mem) + sz);
3385
3386 p_list_mem->type = AS_PARTICLE_TYPE_LIST;
3387 p_list_mem->sz = sz;
3388
3389 return p_list_mem;
3390}
3391
3392static as_particle *
3393list_simple_create_from_buf(rollback_alloc *alloc_buf, uint32_t ele_count,
3394 const uint8_t *contents, uint32_t content_sz)
3395{
3396 list_mem *p_list_mem = list_create(alloc_buf, ele_count, content_sz);
3397
3398 if (p_list_mem) {
3399 uint32_t hdr_sz = list_pack_header(p_list_mem->data, ele_count);
3400
3401 if (content_sz > 0 && contents) {
3402 memcpy(p_list_mem->data + hdr_sz, contents, content_sz);
3403 }
3404 }
3405
3406 return (as_particle *)p_list_mem;
3407}
3408
3409static as_particle *
3410list_simple_create(rollback_alloc *alloc_buf, uint32_t ele_count,
3411 uint32_t content_sz, uint8_t **contents_r)
3412{
3413 list_mem *p_list_mem = list_create(alloc_buf, ele_count, content_sz);
3414 uint32_t hdr_sz = list_pack_header(p_list_mem->data, ele_count);
3415
3416 *contents_r = p_list_mem->data + hdr_sz;
3417
3418 return (as_particle *)p_list_mem;
3419}
3420
3421static int
3422list_set_flags(cdt_op_mem *com, uint8_t set_flags)
3423{
3424 packed_list list;
3425
3426 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3427 cf_warning(AS_PARTICLE, "list_set_flags() invalid packed list");
3428 return -AS_ERR_PARAMETER;
3429 }
3430
3431 bool reorder = false;
3432 bool was_ordered = list_is_ordered(&list);
3433
3434 if (flags_is_ordered(set_flags)) {
3435 if (was_ordered) {
3436 return AS_OK; // no-op
3437 }
3438
3439 if (list.ele_count > 1) {
3440 reorder = true;
3441 }
3442 }
3443 else {
3444 if (! was_ordered) {
3445 return AS_OK; // no-op
3446 }
3447 }
3448
3449 offset_index new_offidx;
3450 uint8_t * const ptr = list_setup_bin_ctx(&com->ctx, set_flags,
3451 list.content_sz, list.ele_count, reorder ? 0 : list.ele_count,
3452 &list.offidx, &new_offidx);
3453
3454 if (! reorder) {
3455 memcpy(ptr, list.contents, list.content_sz);
3456 }
3457 else {
3458 setup_list_must_have_full_offidx(full, &list, com->alloc_idx);
3459
3460 if (! list_full_offset_index_fill_all(full->offidx)) {
3461 cf_warning(AS_PARTICLE, "list_set_flags() invalid list");
3462 return -AS_ERR_PARAMETER;
3463 }
3464
3465 define_order_index(ordidx, list.ele_count, com->alloc_idx);
3466
3467 if (! list_order_index_sort(&ordidx, full->offidx,
3468 AS_CDT_SORT_ASCENDING)) {
3469 cf_warning(AS_PARTICLE, "list_set_flags() invalid list");
3470 return -AS_ERR_PARAMETER;
3471 }
3472
3473 list_order_index_pack(&ordidx, full->offidx, ptr, &new_offidx);
3474 }
3475
3476#ifdef LIST_DEBUG_VERIFY
3477 if (! list_verify(&com->ctx)) {
3478 cdt_bin_print(com->ctx.b, "set_flags");
3479 cdt_context_print(&com->ctx, "ctx");
3480 cdt_mem *mem = (cdt_mem *)com->ctx.orig;
3481 print_packed(mem->data, mem->sz, "orig particle");
3482 list_print(&list, "original list");
3483 cf_crash(AS_PARTICLE, "set_flags: set_flags %u", set_flags);
3484 }
3485#endif
3486
3487 return AS_OK;
3488}
3489
3490static int
3491list_append(cdt_op_mem *com, const cdt_payload *payload, bool payload_is_list,
3492 uint64_t mod_flags)
3493{
3494 packed_list list;
3495
3496 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3497 cf_warning(AS_PARTICLE, "list_append() invalid packed list");
3498 return -AS_ERR_PARAMETER;
3499 }
3500
3501 if (list_is_ordered(&list)) {
3502 if (! payload_is_list) {
3503 return packed_list_add_ordered(&list, com, payload, mod_flags);
3504 }
3505
3506 return packed_list_add_items_ordered(&list, com, payload, mod_flags);
3507 }
3508
3509 return packed_list_insert(&list, com, (int64_t)list.ele_count, payload,
3510 payload_is_list, mod_flags, true);
3511}
3512
3513static int
3514list_insert(cdt_op_mem *com, int64_t index, const cdt_payload *payload,
3515 bool payload_is_list, uint64_t mod_flags)
3516{
3517 packed_list list;
3518
3519 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3520 cf_warning(AS_PARTICLE, "list_insert() invalid list");
3521 return -AS_ERR_PARAMETER;
3522 }
3523
3524 if (list_is_ordered(&list)) {
3525 cf_warning(AS_PARTICLE, "list_insert() invalid op on ORDERED list");
3526 return -AS_ERR_OP_NOT_APPLICABLE;
3527 }
3528
3529 return packed_list_insert(&list, com, index, payload, payload_is_list,
3530 mod_flags, true);
3531}
3532
3533static int
3534list_set(cdt_op_mem *com, int64_t index, const cdt_payload *value,
3535 uint64_t mod_flags)
3536{
3537 packed_list list;
3538
3539 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3540 cf_warning(AS_PARTICLE, "list_set() invalid list");
3541 return -AS_ERR_PARAMETER;
3542 }
3543
3544 if (list_is_ordered(&list)) {
3545 cf_warning(AS_PARTICLE, "list_set() invalid op on ORDERED list");
3546 return -AS_ERR_OP_NOT_APPLICABLE;
3547 }
3548
3549 uint32_t ele_count = list.ele_count;
3550
3551 if (index >= ele_count) {
3552 return packed_list_insert(&list, com, index, value, false, mod_flags,
3553 false);
3554 }
3555
3556 if (index > UINT32_MAX || (index = calc_index(index, ele_count)) < 0) {
3557 cf_warning(AS_PARTICLE, "list_set() index %ld out of bounds for ele_count %d", index > 0 ? index : index - ele_count, ele_count);
3558 return -AS_ERR_OP_NOT_APPLICABLE;
3559 }
3560
3561 if (mod_flags_is_unique(mod_flags)) {
3562 uint32_t rank;
3563 uint32_t count;
3564 uint64_t idx;
3565
3566 // Use non-multi-find scan to optimize for 0 or 1 copies of element.
3567 // 2 or more copies will result in an additional multi-find scan below.
3568 if (! packed_list_find_rank_range_by_value_interval_unordered(&list,
3569 value, value, &rank, &count, &idx, false, false)) {
3570 return -AS_ERR_PARAMETER;
3571 }
3572
3573 if (count != 0) {
3574 if (idx != (uint64_t)index) {
3575 return mod_flags_return_exists(mod_flags);
3576 }
3577
3578 // Need second scan since the dup found is at the index being set.
3579 if (! packed_list_find_rank_range_by_value_interval_unordered(&list,
3580 value, value, &rank, &count, NULL, false, true)) {
3581 return -AS_ERR_PARAMETER;
3582 }
3583
3584 if (count > 1) {
3585 return mod_flags_return_exists(mod_flags);
3586 }
3587 }
3588 }
3589
3590 uint32_t uindex = (uint32_t)index;
3591 define_packed_list_op(op, &list);
3592 setup_list_must_have_full_offidx(full, &list, com->alloc_idx);
3593
3594 if (! packed_list_op_remove(&op, uindex, 1)) {
3595 cf_warning(AS_PARTICLE, "list_set() as_packed_list_remove failed");
3596 return -AS_ERR_PARAMETER;
3597 }
3598
3599 op.new_content_sz += value->sz;
3600
3601 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list.ext_flags,
3602 op.new_content_sz, ele_count, uindex, &list.offidx, NULL);
3603
3604 ptr += packed_list_op_write_seg1(&op, ptr);
3605
3606 memcpy(ptr, value->ptr, value->sz);
3607 ptr += value->sz;
3608
3609 packed_list_op_write_seg2(&op, ptr);
3610
3611 return AS_OK;
3612}
3613
3614static int
3615list_increment(cdt_op_mem *com, int64_t index, cdt_payload *delta_value,
3616 uint64_t mod_flags)
3617{
3618 packed_list list;
3619
3620 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3621 cf_warning(AS_PARTICLE, "list_increment() invalid list");
3622 return -AS_ERR_PARAMETER;
3623 }
3624
3625 if (index > INT32_MAX || (index = calc_index(index, list.ele_count)) < 0) {
3626 cf_warning(AS_PARTICLE, "list_increment() index %ld out of bounds for ele_count %d", index > 0 ? index : index - list.ele_count, list.ele_count);
3627 return -AS_ERR_OP_NOT_APPLICABLE;
3628 }
3629
3630 uint32_t uindex = (uint32_t)index;
3631 cdt_calc_delta calc_delta;
3632
3633 if (! cdt_calc_delta_init(&calc_delta, delta_value, false)) {
3634 return -AS_ERR_PARAMETER;
3635 }
3636
3637 setup_list_must_have_full_offidx(full, &list, com->alloc_idx);
3638
3639 if (uindex < list.ele_count) {
3640 uint32_t offset = packed_list_find_idx_offset(&list, uindex);
3641
3642 if (uindex != 0 && offset == 0) {
3643 cf_warning(AS_PARTICLE, "list_increment() unable to unpack element at %u", uindex);
3644 return -AS_ERR_PARAMETER;
3645 }
3646
3647 as_unpacker pk = {
3648 .buffer = list.contents + offset,
3649 .length = list.content_sz - offset
3650 };
3651
3652 if (! cdt_calc_delta_add(&calc_delta, &pk)) {
3653 return -AS_ERR_PARAMETER;
3654 }
3655 }
3656 else {
3657 if (! cdt_calc_delta_add(&calc_delta, NULL)) {
3658 return -AS_ERR_PARAMETER;
3659 }
3660 }
3661
3662 uint8_t value_buf[CDT_MAX_PACKED_INT_SZ];
3663 cdt_payload value = { value_buf, CDT_MAX_PACKED_INT_SZ };
3664
3665 cdt_calc_delta_pack_and_result(&calc_delta, &value, com->result.result);
3666
3667 if (list_is_ordered(&list)) {
3668 return packed_list_replace_ordered(&list, com, uindex, &value,
3669 mod_flags);
3670 }
3671
3672 return list_set(com, (int64_t)uindex, &value, mod_flags);
3673}
3674
3675static int
3676list_sort(cdt_op_mem *com, as_cdt_sort_flags sort_flags)
3677{
3678 packed_list list;
3679
3680 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3681 cf_warning(AS_PARTICLE, "list_sort() invalid list");
3682 return -AS_ERR_PARAMETER;
3683 }
3684
3685 if (list.ele_count <= 1) {
3686 return AS_OK;
3687 }
3688
3689 setup_list_must_have_full_offidx(full, &list, com->alloc_idx);
3690
3691 if (! list_full_offset_index_fill_all(full->offidx)) {
3692 cf_warning(AS_PARTICLE, "list_sort() invalid list");
3693 return -AS_ERR_PARAMETER;
3694 }
3695
3696 define_order_index(ordidx, list.ele_count, com->alloc_idx);
3697
3698 if (list_is_ordered(&list)) {
3699 for (uint32_t i = 0; i < list.ele_count; i++) {
3700 order_index_set(&ordidx, i, i);
3701 }
3702 }
3703 else if (! list_order_index_sort(&ordidx, full->offidx, sort_flags)) {
3704 cf_warning(AS_PARTICLE, "list_sort() invalid list");
3705 return -AS_ERR_PARAMETER;
3706 }
3707
3708 uint32_t rm_count = 0;
3709 uint32_t rm_sz = 0;
3710
3711 if ((sort_flags & AS_CDT_SORT_DROP_DUPLICATES) != 0 &&
3712 ! order_index_sorted_mark_dup_eles(&ordidx, full->offidx, &rm_count,
3713 &rm_sz)) {
3714 cf_warning(AS_PARTICLE, "list_sort() invalid list");
3715 return -AS_ERR_PARAMETER;
3716 }
3717
3718 offset_index new_offidx;
3719 uint8_t *ptr = list_setup_bin_ctx(&com->ctx, list.ext_flags,
3720 list.content_sz - rm_sz, list.ele_count - rm_count, 0, &list.offidx,
3721 &new_offidx);
3722
3723 ptr = list_order_index_pack(&ordidx, full->offidx, ptr, &new_offidx);
3724
3725#ifdef LIST_DEBUG_VERIFY
3726 if (! list_verify(&com->ctx)) {
3727 cdt_bin_print(com->ctx.b, "list_sort");
3728 list_print(&list, "original");
3729 cf_crash(AS_PARTICLE, "list_sort: sort_flags %d", sort_flags);
3730 }
3731#endif
3732
3733 return AS_OK;
3734}
3735
3736static int
3737list_remove_by_index_range(cdt_op_mem *com, int64_t index, uint64_t count)
3738{
3739 packed_list list;
3740
3741 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3742 cf_warning(AS_PARTICLE, "list_remove_by_index_range() invalid list");
3743 return -AS_ERR_PARAMETER;
3744 }
3745
3746 return packed_list_get_remove_by_index_range(&list, com, index, count);
3747}
3748
3749static int
3750list_remove_by_value_interval(cdt_op_mem *com, const cdt_payload *value_start,
3751 const cdt_payload *value_end)
3752{
3753 packed_list list;
3754
3755 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3756 cf_warning(AS_PARTICLE, "list_remove_by_value_interval() invalid packed list, ele_count=%d", list.ele_count);
3757 return -AS_ERR_PARAMETER;
3758 }
3759
3760 return packed_list_get_remove_by_value_interval(&list, com, value_start,
3761 value_end);
3762}
3763
3764static int
3765list_remove_by_rank_range(cdt_op_mem *com, int64_t rank, uint64_t count)
3766{
3767 packed_list list;
3768
3769 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3770 cf_warning(AS_PARTICLE, "list_remove_by_rank_range() invalid list");
3771 return -AS_ERR_PARAMETER;
3772 }
3773
3774 return packed_list_get_remove_by_rank_range(&list, com, rank, count);
3775}
3776
3777static int
3778list_remove_all_by_value_list(cdt_op_mem *com, const cdt_payload *value_list)
3779{
3780 packed_list list;
3781
3782 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3783 cf_warning(AS_PARTICLE, "list_remove_all_by_value_list() invalid list");
3784 return -AS_ERR_PARAMETER;
3785 }
3786
3787 return packed_list_get_remove_all_by_value_list(&list, com, value_list);
3788}
3789
3790static int
3791list_remove_by_rel_rank_range(cdt_op_mem *com, const cdt_payload *value,
3792 int64_t rank, uint64_t count)
3793{
3794 packed_list list;
3795
3796 if (! packed_list_init_from_ctx(&list, &com->ctx)) {
3797 cf_warning(AS_PARTICLE, "list_remove_by_rel_rank_range() invalid list");
3798 return -AS_ERR_PARAMETER;
3799 }
3800
3801 return packed_list_get_remove_by_rel_rank_range(&list, com, value, rank,
3802 count);
3803}
3804
3805// Return ptr to packed + ele_start.
3806static uint8_t *
3807list_setup_bin(as_bin *b, rollback_alloc *alloc_buf, uint8_t flags,
3808 uint32_t content_sz, uint32_t ele_count, uint32_t idx_trunc,
3809 const offset_index *old_offidx, offset_index *new_offidx)
3810{
3811 bool set_ordered = flags_is_ordered(flags);
3812 uint32_t ext_content_sz = list_calc_ext_content_sz(ele_count, content_sz,
3813 set_ordered);
3814 uint32_t ext_sz = (ext_content_sz == 0 && ! set_ordered) ?
3815 0 : as_pack_ext_header_get_size(ext_content_sz) + ext_content_sz;
3816 list_mem *p_list_mem = list_create(alloc_buf,
3817 ele_count + (ext_sz == 0 ? 0 : 1), ext_sz + content_sz);
3818
3819 cf_assert(p_list_mem, AS_PARTICLE, "p_list_mem NULL");
3820 b->particle = (as_particle *)p_list_mem;
3821
3822 as_packer pk = {
3823 .buffer = p_list_mem->data,
3824 .capacity = p_list_mem->sz
3825 };
3826
3827 if (ext_sz == 0) {
3828 as_pack_list_header(&pk, ele_count);
3829
3830 if (new_offidx) {
3831 list_offset_index_init(new_offidx, NULL, ele_count, NULL,
3832 content_sz);
3833 }
3834
3835 return pk.buffer + pk.offset;
3836 }
3837
3838 as_pack_list_header(&pk, ele_count + 1);
3839 as_pack_ext_header(&pk, ext_content_sz, get_ext_flags(set_ordered));
3840
3841 uint8_t * const ptr = pk.buffer + pk.offset;
3842 offset_index offidx_temp;
3843 uint8_t * const contents = pk.buffer + pk.offset + ext_content_sz;
3844
3845 if (! new_offidx) {
3846 new_offidx = &offidx_temp;
3847 }
3848
3849 if (! set_ordered) {
3850 list_offset_index_init(new_offidx, ptr, ele_count, contents,
3851 content_sz);
3852 idx_trunc /= PACKED_LIST_INDEX_STEP;
3853 }
3854 else {
3855 list_full_offset_index_init(new_offidx, ptr, ele_count, contents,
3856 content_sz);
3857 }
3858
3859 if (idx_trunc == 0 || ! old_offidx || offset_index_is_null(old_offidx)) {
3860 offset_index_set_filled(new_offidx, 1);
3861 }
3862 else {
3863 idx_trunc = MIN(idx_trunc, offset_index_get_filled(old_offidx));
3864 offset_index_copy(new_offidx, old_offidx, 0, 0, idx_trunc, 0);
3865 offset_index_set_filled(new_offidx, idx_trunc);
3866 }
3867
3868 return contents;
3869}
3870
3871static uint8_t *
3872list_setup_bin_ctx(cdt_context *ctx, uint8_t flags, uint32_t content_sz,
3873 uint32_t ele_count, uint32_t idx_trunc, const offset_index *old_offidx,
3874 offset_index *new_offidx)
3875{
3876 if (ctx->data_sz == 0) {
3877 return list_setup_bin(ctx->b, ctx->alloc_buf, flags, content_sz,
3878 ele_count, idx_trunc, old_offidx, new_offidx);
3879 }
3880
3881 bool set_ordered = flags_is_ordered(flags);
3882 uint32_t ext_sz = (! set_ordered) ? 0 : as_pack_ext_header_get_size(0);
3883 uint32_t hdr_count = ele_count + (! set_ordered ? 0 : 1);
3884 uint32_t list_sz = as_pack_list_header_get_size(hdr_count) + ext_sz +
3885 content_sz;
3886 uint8_t *ptr = cdt_context_create_new_particle(ctx, list_sz);
3887
3888 as_packer pk = {
3889 .buffer = ptr,
3890 .capacity = list_sz
3891 };
3892
3893 int check = as_pack_list_header(&pk, hdr_count);
3894 cf_assert(check == 0, AS_PARTICLE, "pack list header failed");
3895
3896 if (set_ordered) {
3897 as_pack_ext_header(&pk, 0,
3898 set_ordered ? AS_PACKED_LIST_FLAG_ORDERED : 0);
3899 }
3900
3901 if (new_offidx) {
3902 offset_index_init(new_offidx, NULL, ele_count, NULL, content_sz);
3903 }
3904
3905 return pk.buffer + pk.offset;
3906}
3907
3908
3909//==========================================================
3910// cdt_list_builder
3911//
3912
3913void
3914cdt_list_builder_start(cdt_container_builder *builder,
3915 rollback_alloc *alloc_buf, uint32_t ele_count, uint32_t max_sz)
3916{
3917 uint32_t sz = sizeof(list_mem) + sizeof(uint64_t) + 1 + max_sz;
3918 list_mem *p_list_mem = (list_mem *)rollback_alloc_reserve(alloc_buf, sz);
3919
3920 p_list_mem->type = AS_PARTICLE_TYPE_LIST;
3921 p_list_mem->sz = list_pack_header(p_list_mem->data, ele_count);
3922
3923 builder->particle = (as_particle *)p_list_mem;
3924 builder->write_ptr = p_list_mem->data + p_list_mem->sz;
3925 builder->ele_count = 0;
3926 builder->sz = &p_list_mem->sz;
3927}
3928
3929
3930//==========================================================
3931// cdt_process_state_packed_list
3932//
3933
3934bool
3935cdt_process_state_packed_list_modify_optype(cdt_process_state *state,
3936 cdt_op_mem *com)
3937{
3938 cdt_context *ctx = &com->ctx;
3939 as_cdt_optype optype = state->type;
3940
3941 if (ctx->data_sz == 0 && as_bin_inuse(ctx->b) &&
3942 ! is_list_type(as_bin_get_particle_type(ctx->b))) {
3943 cf_warning(AS_PARTICLE, "cdt_process_state_packed_list_modify_optype() invalid type %d", as_bin_get_particle_type(ctx->b));
3944 com->ret_code = -AS_ERR_INCOMPATIBLE_TYPE;
3945 return false;
3946 }
3947
3948 int ret = AS_OK;
3949 cdt_result_data *result = &com->result;
3950
3951 switch (optype) {
3952 case AS_CDT_OP_LIST_SET_TYPE: {
3953 uint64_t list_type;
3954
3955 if (! CDT_OP_TABLE_GET_PARAMS(state, &list_type)) {
3956 com->ret_code = -AS_ERR_PARAMETER;
3957 return false;
3958 }
3959
3960 cdt_context_use_static_list_if_notinuse(ctx, AS_PACKED_LIST_FLAG_NONE);
3961 ret = list_set_flags(com, (uint8_t)list_type);
3962 break;
3963 }
3964 case AS_CDT_OP_LIST_APPEND: {
3965 cdt_payload value;
3966 uint64_t create_type = AS_PACKED_LIST_FLAG_NONE;
3967 uint64_t modify = AS_CDT_LIST_MODIFY_DEFAULT;
3968
3969 if (! CDT_OP_TABLE_GET_PARAMS(state, &value, &create_type, &modify)) {
3970 com->ret_code = -AS_ERR_PARAMETER;
3971 return false;
3972 }
3973
3974 cdt_context_use_static_list_if_notinuse(ctx, create_type);
3975 ret = list_append(com, &value, false, modify);
3976 break;
3977 }
3978 case AS_CDT_OP_LIST_APPEND_ITEMS: {
3979 cdt_payload items;
3980 uint64_t create_type = AS_PACKED_LIST_FLAG_NONE;
3981 uint64_t modify = AS_CDT_LIST_MODIFY_DEFAULT;
3982
3983 if (! CDT_OP_TABLE_GET_PARAMS(state, &items, &create_type, &modify)) {
3984 com->ret_code = -AS_ERR_PARAMETER;
3985 return false;
3986 }
3987
3988 cdt_context_use_static_list_if_notinuse(ctx, create_type);
3989 ret = list_append(com, &items, true, modify);
3990 break;
3991 }
3992 case AS_CDT_OP_LIST_INSERT: {
3993 int64_t index;
3994 cdt_payload value;
3995 uint64_t modify = AS_CDT_LIST_MODIFY_DEFAULT;
3996
3997 if (! CDT_OP_TABLE_GET_PARAMS(state, &index, &value, &modify)) {
3998 com->ret_code = -AS_ERR_PARAMETER;
3999 return false;
4000 }
4001
4002 cdt_context_use_static_list_if_notinuse(ctx, AS_PACKED_LIST_FLAG_NONE);
4003 ret = list_insert(com, index, &value, false, modify);
4004 break;
4005 }
4006 case AS_CDT_OP_LIST_INSERT_ITEMS: {
4007 int64_t index;
4008 cdt_payload items;
4009 uint64_t modify = AS_CDT_LIST_MODIFY_DEFAULT;
4010
4011 if (! CDT_OP_TABLE_GET_PARAMS(state, &index, &items, &modify)) {
4012 com->ret_code = -AS_ERR_PARAMETER;
4013 return false;
4014 }
4015
4016 cdt_context_use_static_list_if_notinuse(ctx, AS_PACKED_LIST_FLAG_NONE);
4017 ret = list_insert(com, index, &items, true, modify);
4018 break;
4019 }
4020 case AS_CDT_OP_LIST_SET: {
4021 int64_t index;
4022 cdt_payload value;
4023 uint64_t modify = AS_CDT_LIST_MODIFY_DEFAULT;
4024
4025 if (! CDT_OP_TABLE_GET_PARAMS(state, &index, &value, &modify)) {
4026 com->ret_code = -AS_ERR_PARAMETER;
4027 return false;
4028 }
4029
4030 cdt_context_use_static_list_if_notinuse(ctx, AS_PACKED_LIST_FLAG_NONE);
4031 ret = list_set(com, index, &value, modify);
4032 break;
4033 }
4034 case AS_CDT_OP_LIST_REMOVE:
4035 case AS_CDT_OP_LIST_POP: {
4036 if (! as_bin_inuse(ctx->b)) {
4037 return true; // no-op
4038 }
4039
4040 int64_t index;
4041
4042 if (! CDT_OP_TABLE_GET_PARAMS(state, &index)) {
4043 com->ret_code = -AS_ERR_PARAMETER;
4044 return false;
4045 }
4046
4047 result_data_set(result, optype == AS_CDT_OP_LIST_REMOVE ?
4048 RESULT_TYPE_COUNT : RESULT_TYPE_VALUE, false);
4049 ret = list_remove_by_index_range(com, index, 1);
4050 break;
4051 }
4052 case AS_CDT_OP_LIST_REMOVE_RANGE:
4053 case AS_CDT_OP_LIST_POP_RANGE: {
4054 if (! as_bin_inuse(ctx->b)) {
4055 return true; // no-op
4056 }
4057
4058 int64_t index;
4059 uint64_t count = UINT32_MAX;
4060
4061 if (! CDT_OP_TABLE_GET_PARAMS(state, &index, &count)) {
4062 com->ret_code = -AS_ERR_PARAMETER;
4063 return false;
4064 }
4065
4066 result_data_set(result, optype == AS_CDT_OP_LIST_REMOVE_RANGE ?
4067 RESULT_TYPE_COUNT : RESULT_TYPE_VALUE, true);
4068 ret = list_remove_by_index_range(com, index, count);
4069 break;
4070 }
4071 case AS_CDT_OP_LIST_TRIM: {
4072 if (! as_bin_inuse(ctx->b)) {
4073 return true; // no-op
4074 }
4075
4076 int64_t index;
4077 uint64_t count = UINT32_MAX;
4078
4079 if (! CDT_OP_TABLE_GET_PARAMS(state, &index, &count)) {
4080 com->ret_code = -AS_ERR_PARAMETER;
4081 return false;
4082 }
4083
4084 result->type = RESULT_TYPE_COUNT;
4085 result->flags = AS_CDT_OP_FLAG_INVERTED;
4086 result->is_multi = true;
4087 ret = list_remove_by_index_range(com, index, count);
4088 break;
4089 }
4090 case AS_CDT_OP_LIST_CLEAR: {
4091 if (! as_bin_inuse(ctx->b)) {
4092 return true; // no-op
4093 }
4094
4095 packed_list list;
4096
4097 if (! packed_list_init_from_ctx(&list, ctx)) {
4098 cf_warning(AS_PARTICLE, "LIST_CLEAR: invalid list");
4099 com->ret_code = -AS_ERR_PARAMETER;
4100 return false;
4101 }
4102
4103 cdt_context_set_empty_list(ctx, list_is_ordered(&list));
4104 break;
4105 }
4106 case AS_CDT_OP_LIST_INCREMENT: {
4107 int64_t index;
4108 cdt_payload delta = { NULL };
4109 uint64_t create = AS_PACKED_LIST_FLAG_NONE;
4110 uint64_t modify = AS_CDT_LIST_MODIFY_DEFAULT;
4111
4112 if (! CDT_OP_TABLE_GET_PARAMS(state, &index, &delta, &create,
4113 &modify)) {
4114 com->ret_code = -AS_ERR_PARAMETER;
4115 return false;
4116 }
4117
4118 cdt_context_use_static_list_if_notinuse(ctx, create);
4119 ret = list_increment(com, index, &delta, modify);
4120 break;
4121 }
4122 case AS_CDT_OP_LIST_SORT: {
4123 if (! as_bin_inuse(ctx->b)) {
4124 com->ret_code = -AS_ERR_INCOMPATIBLE_TYPE;
4125 return false;
4126 }
4127
4128 uint64_t flags = 0;
4129
4130 if (! CDT_OP_TABLE_GET_PARAMS(state, &flags)) {
4131 com->ret_code = -AS_ERR_PARAMETER;
4132 return false;
4133 }
4134
4135 ret = list_sort(com, (as_cdt_sort_flags)flags);
4136 break;
4137 }
4138 case AS_CDT_OP_LIST_REMOVE_BY_INDEX: {
4139 if (! as_bin_inuse(ctx->b)) {
4140 return true; // no-op
4141 }
4142
4143 uint64_t result_type;
4144 int64_t index;
4145
4146 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index)) {
4147 com->ret_code = -AS_ERR_PARAMETER;
4148 return false;
4149 }
4150
4151 result_data_set(result, result_type, false);
4152 ret = list_remove_by_index_range(com, index, 1);
4153 break;
4154 }
4155 case AS_CDT_OP_LIST_REMOVE_ALL_BY_VALUE:
4156 case AS_CDT_OP_LIST_REMOVE_BY_VALUE: {
4157 if (! as_bin_inuse(ctx->b)) {
4158 return true; // no-op
4159 }
4160
4161 uint64_t result_type;
4162 cdt_payload value;
4163
4164 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value)) {
4165 com->ret_code = -AS_ERR_PARAMETER;
4166 return false;
4167 }
4168
4169 result_data_set(result, result_type,
4170 optype == AS_CDT_OP_LIST_REMOVE_ALL_BY_VALUE);
4171 ret = list_remove_by_value_interval(com, &value, &value);
4172 break;
4173 }
4174 case AS_CDT_OP_LIST_REMOVE_BY_RANK: {
4175 if (! as_bin_inuse(ctx->b)) {
4176 return true; // no-op
4177 }
4178
4179 uint64_t result_type;
4180 int64_t rank;
4181
4182 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &rank)) {
4183 com->ret_code = -AS_ERR_PARAMETER;
4184 return false;
4185 }
4186
4187 result_data_set(result, result_type, false);
4188 ret = list_remove_by_rank_range(com, rank, 1);
4189 break;
4190 }
4191 case AS_CDT_OP_LIST_REMOVE_ALL_BY_VALUE_LIST: {
4192 if (! as_bin_inuse(ctx->b)) {
4193 return true; // no-op
4194 }
4195
4196 uint64_t result_type;
4197 cdt_payload items;
4198
4199 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &items)) {
4200 com->ret_code = -AS_ERR_PARAMETER;
4201 return false;
4202 }
4203
4204 result_data_set(result, result_type, true);
4205 ret = list_remove_all_by_value_list(com, &items);
4206 break;
4207 }
4208 case AS_CDT_OP_LIST_REMOVE_BY_INDEX_RANGE: {
4209 if (! as_bin_inuse(ctx->b)) {
4210 return true; // no-op
4211 }
4212
4213 uint64_t result_type;
4214 int64_t index;
4215 uint64_t count = UINT32_MAX;
4216
4217 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index, &count)) {
4218 com->ret_code = -AS_ERR_PARAMETER;
4219 return false;
4220 }
4221
4222 result_data_set(result, result_type, true);
4223 ret = list_remove_by_index_range(com, index, count);
4224 break;
4225 }
4226 case AS_CDT_OP_LIST_REMOVE_BY_VALUE_INTERVAL: {
4227 if (! as_bin_inuse(ctx->b)) {
4228 return true; // no-op
4229 }
4230
4231 uint64_t result_type;
4232 cdt_payload value_start;
4233 cdt_payload value_end = { NULL };
4234
4235 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value_start,
4236 &value_end)) {
4237 com->ret_code = -AS_ERR_PARAMETER;
4238 return false;
4239 }
4240
4241 result_data_set(result, result_type, true);
4242 ret = list_remove_by_value_interval(com, &value_start, &value_end);
4243 break;
4244 }
4245 case AS_CDT_OP_LIST_REMOVE_BY_RANK_RANGE: {
4246 if (! as_bin_inuse(ctx->b)) {
4247 return true; // no-op
4248 }
4249
4250 uint64_t result_type;
4251 int64_t rank;
4252 uint64_t count = UINT32_MAX;
4253
4254 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &rank, &count)) {
4255 com->ret_code = -AS_ERR_PARAMETER;
4256 return false;
4257 }
4258
4259 result_data_set(result, result_type, true);
4260 ret = list_remove_by_rank_range(com, rank, count);
4261 break;
4262 }
4263 case AS_CDT_OP_LIST_REMOVE_BY_VALUE_REL_RANK_RANGE: {
4264 if (! as_bin_inuse(ctx->b)) {
4265 return true; // no-op
4266 }
4267
4268 uint64_t result_type;
4269 cdt_payload value;
4270 int64_t rank;
4271 uint64_t count = UINT32_MAX;
4272
4273 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value, &rank,
4274 &count)) {
4275 com->ret_code = -AS_ERR_PARAMETER;
4276 return false;
4277 }
4278
4279 result_data_set(result, result_type, true);
4280 ret = list_remove_by_rel_rank_range(com, &value, rank, count);
4281 break;
4282 }
4283 default:
4284 cf_warning(AS_PARTICLE, "cdt_process_state_packed_list_modify_optype() invalid cdt op: %d", optype);
4285 com->ret_code = -AS_ERR_PARAMETER;
4286 return false;
4287 }
4288
4289 if (ret != AS_OK) {
4290 cf_warning(AS_PARTICLE, "%s: failed", cdt_process_state_get_op_name(state));
4291 com->ret_code = ret;
4292 return false;
4293 }
4294
4295 // In case of no-op.
4296 if (ctx->b->particle == (const as_particle *)&list_mem_empty) {
4297 cdt_context_set_empty_list(ctx, false);
4298 }
4299 else if (ctx->b->particle == (const as_particle *)&list_ordered_empty) {
4300 cdt_context_set_empty_list(ctx, true);
4301 }
4302
4303 return true;
4304}
4305
4306bool
4307cdt_process_state_packed_list_read_optype(cdt_process_state *state,
4308 cdt_op_mem *com)
4309{
4310 const cdt_context *ctx = &com->ctx;
4311 as_cdt_optype optype = state->type;
4312
4313 if (ctx->data_sz == 0 && ! is_list_type(as_bin_get_particle_type(ctx->b))) {
4314 com->ret_code = -AS_ERR_INCOMPATIBLE_TYPE;
4315 return false;
4316 }
4317
4318 packed_list list;
4319
4320 if (! packed_list_init_from_ctx(&list, ctx)) {
4321 cf_warning(AS_PARTICLE, "%s: invalid list", cdt_process_state_get_op_name(state));
4322 com->ret_code = -AS_ERR_INCOMPATIBLE_TYPE;
4323 return false;
4324 }
4325
4326 int ret = AS_OK;
4327 cdt_result_data *result = &com->result;
4328
4329 switch (optype) {
4330 case AS_CDT_OP_LIST_GET: {
4331 int64_t index;
4332
4333 if (! CDT_OP_TABLE_GET_PARAMS(state, &index)) {
4334 com->ret_code = -AS_ERR_PARAMETER;
4335 return false;
4336 }
4337
4338 result_data_set(result, RESULT_TYPE_VALUE, false);
4339 ret = packed_list_get_remove_by_index_range(&list, com, index, 1);
4340 break;
4341 }
4342 case AS_CDT_OP_LIST_GET_RANGE: {
4343 int64_t index;
4344 uint64_t count = UINT32_MAX;
4345
4346 if (! CDT_OP_TABLE_GET_PARAMS(state, &index, &count)) {
4347 com->ret_code = -AS_ERR_PARAMETER;
4348 return false;
4349 }
4350
4351 result_data_set(result, RESULT_TYPE_VALUE, true);
4352 ret = packed_list_get_remove_by_index_range(&list, com, index, count);
4353 break;
4354 }
4355 case AS_CDT_OP_LIST_SIZE: {
4356 as_bin_set_int(result->result, list.ele_count);
4357 break;
4358 }
4359 case AS_CDT_OP_LIST_GET_BY_INDEX: {
4360 uint64_t result_type;
4361 int64_t index;
4362
4363 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index)) {
4364 com->ret_code = -AS_ERR_PARAMETER;
4365 return false;
4366 }
4367
4368 result_data_set(result, result_type, false);
4369 ret = packed_list_get_remove_by_index_range(&list, com, index, 1);
4370 break;
4371 }
4372 case AS_CDT_OP_LIST_GET_ALL_BY_VALUE:
4373 case AS_CDT_OP_LIST_GET_BY_VALUE: {
4374 uint64_t result_type;
4375 cdt_payload value;
4376
4377 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value)) {
4378 com->ret_code = -AS_ERR_PARAMETER;
4379 return false;
4380 }
4381
4382 result_data_set(result, result_type,
4383 optype == AS_CDT_OP_LIST_GET_ALL_BY_VALUE);
4384 ret = packed_list_get_remove_by_value_interval(&list, com, &value,
4385 &value);
4386 break;
4387 }
4388 case AS_CDT_OP_LIST_GET_BY_RANK: {
4389 uint64_t result_type;
4390 int64_t rank;
4391
4392 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &rank)) {
4393 com->ret_code = -AS_ERR_PARAMETER;
4394 return false;
4395 }
4396
4397 result_data_set(result, result_type, false);
4398 ret = packed_list_get_remove_by_rank_range(&list, com, rank, 1);
4399 break;
4400 }
4401 case AS_CDT_OP_LIST_GET_ALL_BY_VALUE_LIST: {
4402 uint64_t result_type;
4403 cdt_payload value_list;
4404
4405 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value_list)) {
4406 com->ret_code = -AS_ERR_PARAMETER;
4407 return false;
4408 }
4409
4410 result_data_set(result, result_type, true);
4411 ret = packed_list_get_remove_all_by_value_list(&list, com,
4412 &value_list);
4413 break;
4414 }
4415 case AS_CDT_OP_LIST_GET_BY_INDEX_RANGE: {
4416 uint64_t result_type;
4417 int64_t index;
4418 uint64_t count = UINT32_MAX;
4419
4420 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &index, &count)) {
4421 com->ret_code = -AS_ERR_PARAMETER;
4422 return false;
4423 }
4424
4425 result_data_set(result, result_type, true);
4426 ret = packed_list_get_remove_by_index_range(&list, com, index, count);
4427 break;
4428 }
4429 case AS_CDT_OP_LIST_GET_BY_VALUE_INTERVAL: {
4430 uint64_t result_type;
4431 cdt_payload value_start;
4432 cdt_payload value_end = { NULL };
4433
4434 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value_start,
4435 &value_end)) {
4436 com->ret_code = -AS_ERR_PARAMETER;
4437 return false;
4438 }
4439
4440 result_data_set(result, result_type, true);
4441 ret = packed_list_get_remove_by_value_interval(&list, com,
4442 &value_start, &value_end);
4443 break;
4444 }
4445 case AS_CDT_OP_LIST_GET_BY_RANK_RANGE: {
4446 uint64_t result_type;
4447 int64_t rank;
4448 uint64_t count = UINT32_MAX;
4449
4450 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &rank, &count)) {
4451 com->ret_code = -AS_ERR_PARAMETER;
4452 return false;
4453 }
4454
4455 result_data_set(result, result_type, true);
4456 ret = packed_list_get_remove_by_rank_range(&list, com, rank, count);
4457 break;
4458 }
4459 case AS_CDT_OP_LIST_GET_BY_VALUE_REL_RANK_RANGE: {
4460 uint64_t result_type;
4461 cdt_payload value;
4462 int64_t rank;
4463 uint64_t count = UINT32_MAX;
4464
4465 if (! CDT_OP_TABLE_GET_PARAMS(state, &result_type, &value, &rank,
4466 &count)) {
4467 com->ret_code = -AS_ERR_PARAMETER;
4468 return false;
4469 }
4470
4471 result_data_set(result, result_type, true);
4472 ret = packed_list_get_remove_by_rel_rank_range(&list, com, &value,
4473 rank, count);
4474 break;
4475 }
4476 default:
4477 cf_warning(AS_PARTICLE, "cdt_process_state_packed_list_read_optype() invalid cdt op: %d", optype);
4478 com->ret_code = -AS_ERR_PARAMETER;
4479 return false;
4480 }
4481
4482 if (ret != AS_OK) {
4483 cf_warning(AS_PARTICLE, "%s: failed", cdt_process_state_get_op_name(state));
4484 com->ret_code = ret;
4485 return false;
4486 }
4487
4488 return true;
4489}
4490
4491
4492//==========================================================
4493// list_offset_index
4494//
4495
4496static inline uint32_t
4497list_offset_partial_index_count(uint32_t ele_count)
4498{
4499 if (ele_count != 0) {
4500 ele_count--;
4501 ele_count /= PACKED_LIST_INDEX_STEP;
4502
4503 if (ele_count != 0) {
4504 ele_count++;
4505 }
4506 }
4507
4508 return ele_count;
4509}
4510
4511static inline void
4512list_offset_index_init(offset_index *offidx, uint8_t *idx_mem_ptr,
4513 uint32_t ele_count, const uint8_t *contents, uint32_t content_sz)
4514{
4515 ele_count = list_offset_partial_index_count(ele_count);
4516 offset_index_init(offidx, idx_mem_ptr, ele_count, contents, content_sz);
4517 offidx->is_partial = true;
4518}
4519
4520static void
4521list_offset_index_rm_mask_cpy(offset_index *dst, const offset_index *full_src,
4522 const uint64_t *rm_mask, uint32_t rm_count)
4523{
4524 cf_assert(rm_mask && rm_count != 0, AS_PARTICLE, "list_offset_index_rm_mask_cpy() should not do no-op copy");
4525
4526 uint32_t ele_count = full_src->_.ele_count;
4527
4528 if (! dst->is_partial) {
4529 uint32_t delta = 0;
4530 uint32_t prev = 0;
4531 uint32_t idx = 0;
4532
4533 for (uint32_t i = 0; i < rm_count; i++) {
4534 idx = cdt_idx_mask_find(rm_mask, idx, ele_count, false);
4535 uint32_t sz = offset_index_get_delta_const(full_src, idx);
4536 uint32_t diff = idx - prev;
4537
4538 for (uint32_t j = 1; j < diff; j++) {
4539 uint32_t offset = offset_index_get_const(full_src, prev + j);
4540
4541 offset_index_set(dst, prev + j - i, offset - delta);
4542 }
4543
4544 prev = idx;
4545 delta += sz;
4546 idx++;
4547 }
4548
4549 uint32_t diff = full_src->_.ele_count - prev;
4550
4551 for (uint32_t i = 1; i < diff; i++) {
4552 uint32_t offset = offset_index_get_const(full_src, prev + i);
4553 offset_index_set(dst, prev + i - rm_count, offset - delta);
4554 }
4555
4556 offset_index_set_filled(dst, dst->_.ele_count);
4557 return;
4558 }
4559
4560 uint32_t delta = 0;
4561 uint32_t prev_pt_idx = 0;
4562 uint32_t idx = 0;
4563
4564 for (uint32_t i = 0; i < rm_count; i++) {
4565 idx = cdt_idx_mask_find(rm_mask, idx, ele_count, false);
4566 uint32_t sz = offset_index_get_delta_const(full_src, idx);
4567 uint32_t pt_idx = (idx - i) / PACKED_LIST_INDEX_STEP;
4568 uint32_t diff = pt_idx - prev_pt_idx + 1;
4569
4570 for (uint32_t j = 1; j < diff; j++) {
4571 uint32_t offset = offset_index_get_const(full_src,
4572 (prev_pt_idx + j) * PACKED_LIST_INDEX_STEP + i);
4573 offset_index_set(dst, prev_pt_idx + j, offset - delta);
4574 }
4575
4576 prev_pt_idx = pt_idx;
4577 delta += sz;
4578 idx++;
4579 }
4580
4581 uint32_t new_ele_count = full_src->_.ele_count - rm_count;
4582 uint32_t max_idx = list_offset_partial_index_count(new_ele_count);
4583 uint32_t diff = max_idx - prev_pt_idx;
4584
4585 for (uint32_t j = 1; j < diff; j++) {
4586 uint32_t offset = offset_index_get_const(full_src,
4587 (prev_pt_idx + j) * PACKED_LIST_INDEX_STEP + rm_count);
4588 offset_index_set(dst, prev_pt_idx + j, offset - delta);
4589 }
4590
4591 offset_index_set_filled(dst, max_idx);
4592}
4593
4594
4595//==========================================================
4596// list_full_offset_index
4597//
4598
4599static inline void
4600list_full_offset_index_init(offset_index *offidx, uint8_t *idx_mem_ptr,
4601 uint32_t ele_count, const uint8_t *contents, uint32_t content_sz)
4602{
4603 offset_index_init(offidx, idx_mem_ptr, ele_count, contents, content_sz);
4604}
4605
4606static bool
4607list_full_offset_index_fill_to(offset_index *offidx, uint32_t index,
4608 bool check_storage)
4609{
4610 uint32_t start = offset_index_get_filled(offidx);
4611
4612 index = MIN(index + 1, offidx->_.ele_count);
4613
4614 if (start >= index) {
4615 return true;
4616 }
4617
4618 msgpack_in pk = {
4619 .buf = offidx->contents,
4620 .buf_sz = offidx->content_sz,
4621 .offset = offset_index_get_const(offidx, start - 1)
4622 };
4623
4624 for (uint32_t i = start; i < index; i++) {
4625 if (msgpack_sz(&pk) == 0 || (check_storage && pk.has_nonstorage)) {
4626 return false;
4627 }
4628
4629 offset_index_set(offidx, i, pk.offset);
4630 }
4631
4632 offset_index_set_filled(offidx, index);
4633
4634 return true;
4635}
4636
4637bool
4638list_full_offset_index_fill_all(offset_index *offidx)
4639{
4640 return list_full_offset_index_fill_to(offidx, offidx->_.ele_count, true);
4641}
4642
4643
4644//==========================================================
4645// list_order_index
4646//
4647
4648static int
4649list_order_index_sort_cmp_fn(const void *x, const void *y, void *p)
4650{
4651 list_order_index_sort_userdata *udata = p;
4652
4653 if (udata->error) {
4654 return 0;
4655 }
4656
4657 const order_index *order = udata->order;
4658 uint32_t a = order_index_ptr2value(order, x);
4659 uint32_t b = order_index_ptr2value(order, y);
4660
4661 const offset_index *offsets = udata->offsets;
4662 const uint8_t *buf = udata->offsets->contents;
4663 uint32_t len = udata->offsets->content_sz;
4664 uint32_t x_off = offset_index_get_const(offsets, a);
4665 uint32_t y_off = offset_index_get_const(offsets, b);
4666
4667 msgpack_in x_pk = {
4668 .buf = buf + x_off,
4669 .buf_sz = len - x_off
4670 };
4671
4672 msgpack_in y_pk = {
4673 .buf = buf + y_off,
4674 .buf_sz = len - y_off
4675 };
4676
4677 msgpack_compare_t cmp = msgpack_cmp_peek(&x_pk, &y_pk);
4678
4679 switch (cmp) {
4680 case MSGPACK_COMPARE_EQUAL:
4681 return 0;
4682 case MSGPACK_COMPARE_LESS:
4683 if (udata->flags & AS_CDT_SORT_DESCENDING) {
4684 cmp = MSGPACK_COMPARE_GREATER;
4685 }
4686 break;
4687 case MSGPACK_COMPARE_GREATER:
4688 if (udata->flags & AS_CDT_SORT_DESCENDING) {
4689 cmp = MSGPACK_COMPARE_LESS;
4690 }
4691 break;
4692 default:
4693 udata->error = true;
4694 return 0;
4695 }
4696
4697 return (cmp == MSGPACK_COMPARE_LESS) ? -1 : 1;
4698}
4699
4700bool
4701list_order_index_sort(order_index *ordidx, const offset_index *full_offidx,
4702 as_cdt_sort_flags flags)
4703{
4704 uint32_t ele_count = ordidx->_.ele_count;
4705 list_order_index_sort_userdata udata = {
4706 .order = ordidx,
4707 .offsets = full_offidx,
4708 .flags = flags
4709 };
4710
4711 for (uint32_t i = 0; i < ele_count; i++) {
4712 order_index_set(ordidx, i, i);
4713 }
4714
4715 if (ele_count <= 1) {
4716 return true;
4717 }
4718
4719 qsort_r(order_index_get_mem(ordidx, 0), ele_count, ordidx->_.ele_sz,
4720 list_order_index_sort_cmp_fn, (void *)&udata);
4721
4722 return ! udata.error;
4723}
4724
4725static uint8_t *
4726list_order_index_pack(const order_index *ordidx,
4727 const offset_index *full_offidx, uint8_t *buf, offset_index *new_offidx)
4728{
4729 cf_assert(new_offidx, AS_PARTICLE, "new_offidx null");
4730 cf_assert(full_offidx->_.ele_count != 0, AS_PARTICLE, "ele_count == 0");
4731
4732 const uint8_t *contents = full_offidx->contents;
4733 uint32_t buf_off = 0;
4734 uint32_t write_count = 0;
4735
4736 for (uint32_t i = 0; i < full_offidx->_.ele_count; i++) {
4737 uint32_t idx = order_index_get(ordidx, i);
4738
4739 if (idx == full_offidx->_.ele_count) {
4740 continue;
4741 }
4742
4743 uint32_t off = offset_index_get_const(full_offidx, idx);
4744 uint32_t sz = offset_index_get_delta_const(full_offidx, idx);
4745
4746 memcpy(buf + buf_off, contents + off, sz);
4747 buf_off += sz;
4748 write_count++;
4749
4750 if (offset_index_is_null(new_offidx)) {
4751 continue;
4752 }
4753
4754 if (! new_offidx->is_partial) {
4755 offset_index_set(new_offidx, write_count, buf_off);
4756 }
4757 else if (write_count % PACKED_LIST_INDEX_STEP == 0 &&
4758 new_offidx->_.ele_count != 0) {
4759 uint32_t new_idx = write_count / PACKED_LIST_INDEX_STEP;
4760 offset_index_set(new_offidx, new_idx, buf_off);
4761 }
4762 }
4763
4764 if (! offset_index_is_null(new_offidx)) {
4765 offset_index_set_filled(new_offidx, (new_offidx->is_partial ?
4766 new_offidx->_.ele_count : write_count));
4767 }
4768
4769 return buf + buf_off;
4770}
4771
4772
4773//==========================================================
4774// list_order_heap
4775//
4776
4777static msgpack_compare_t
4778list_order_heap_cmp_fn(const void *udata, uint32_t idx1, uint32_t idx2)
4779{
4780 const packed_list *list = (const packed_list *)udata;
4781 const offset_index *offidx = &list->full_offidx;
4782
4783 msgpack_in pk1 = {
4784 .buf = list->contents,
4785 .buf_sz = list->content_sz,
4786 .offset = offset_index_get_const(offidx, idx1)
4787 };
4788
4789 msgpack_in pk2 = {
4790 .buf = list->contents,
4791 .buf_sz = list->content_sz,
4792 .offset = offset_index_get_const(offidx, idx2)
4793 };
4794
4795 return msgpack_cmp_peek(&pk1, &pk2);
4796}
4797
4798
4799//==========================================================
4800// list_result_data
4801//
4802
4803static bool
4804list_result_data_set_not_found(cdt_result_data *rd, int64_t index)
4805{
4806 switch (rd->type) {
4807 case RESULT_TYPE_KEY:
4808 case RESULT_TYPE_MAP:
4809 return false;
4810 default:
4811 break;
4812 }
4813
4814 return result_data_set_not_found(rd, index);
4815}
4816
4817// Does not respect inverted flag.
4818static void
4819list_result_data_set_values_by_mask(cdt_result_data *rd, const uint64_t *mask,
4820 const offset_index *full_offidx, uint32_t count, uint32_t sz)
4821{
4822 if (sz == 0) {
4823 sz = cdt_idx_mask_get_content_sz(mask, count, full_offidx);
4824 }
4825
4826 cdt_container_builder builder;
4827 cdt_list_builder_start(&builder, rd->alloc, count, sz);
4828
4829 const uint8_t *end = cdt_idx_mask_write_eles(mask, count, full_offidx,
4830 builder.write_ptr, false);
4831
4832 cf_assert(end - builder.write_ptr == sz, AS_PARTICLE, "size mismatch end - ptr %zu != sz %u", end - builder.write_ptr, sz);
4833 cdt_container_builder_add_n(&builder, NULL, count, sz);
4834 cdt_container_builder_set_result(&builder, rd);
4835}
4836
4837// Does not respect inverted flag.
4838static void
4839list_result_data_set_values_by_idxcount(cdt_result_data *rd,
4840 const order_index *idxcnt, const offset_index *full_offidx)
4841{
4842 uint32_t items_count = idxcnt->_.ele_count / 2;
4843 uint32_t sz = 0;
4844 uint32_t ret_count = 0;
4845
4846 for (uint32_t i = 0; i < items_count; i++) {
4847 uint32_t idx = order_index_get(idxcnt, 2 * i);
4848 uint32_t count = order_index_get(idxcnt, (2 * i) + 1);
4849
4850 for (uint32_t j = 0; j < count; j++) {
4851 sz += offset_index_get_delta_const(full_offidx, idx + j);
4852 }
4853 }
4854
4855 cdt_container_builder builder;
4856 cdt_list_builder_start(&builder, rd->alloc, ret_count, sz);
4857
4858 for (uint32_t i = 0; i < items_count; i++) {
4859 uint32_t idx = order_index_get(idxcnt, 2 * i);
4860 uint32_t count = order_index_get(idxcnt, (2 * i) + 1);
4861
4862 if (count == 0) {
4863 continue;
4864 }
4865
4866 uint32_t offset = offset_index_get_const(full_offidx, idx);
4867 uint32_t end = offset_index_get_const(full_offidx, idx + count);
4868
4869 cdt_container_builder_add_n(&builder, full_offidx->contents + offset,
4870 count, end - offset);
4871 }
4872
4873 cdt_container_builder_set_result(&builder, rd);
4874}
4875
4876// Does not respect inverted flag.
4877static bool
4878list_result_data_set_values_by_ordidx(cdt_result_data *rd,
4879 const order_index *ordidx, const offset_index *full_offidx,
4880 uint32_t count, uint32_t sz)
4881{
4882 if (! rd->is_multi) {
4883 if (count != 0) {
4884 uint32_t i = order_index_get(ordidx, 0);
4885 uint32_t offset = offset_index_get_const(full_offidx, i);
4886 uint32_t sz = offset_index_get_delta_const(full_offidx, i);
4887
4888 return as_bin_particle_alloc_from_msgpack(rd->result,
4889 full_offidx->contents + offset, sz) == AS_OK;
4890 }
4891
4892 return true;
4893 }
4894
4895 if (sz == 0) {
4896 sz = order_index_get_ele_size(ordidx, count, full_offidx);
4897 }
4898
4899 uint8_t *ptr;
4900
4901 rd->result->particle = list_simple_create(rd->alloc, count, sz,
4902 &ptr);
4903 order_index_write_eles(ordidx, count, full_offidx, ptr, false);
4904 as_bin_state_set_from_type(rd->result, AS_PARTICLE_TYPE_LIST);
4905
4906 return true;
4907}
4908
4909
4910//==========================================================
4911// Debugging support.
4912//
4913
4914void
4915list_print(const packed_list *list, const char *name)
4916{
4917 print_packed(list->packed, list->packed_sz, name);
4918}
4919
4920static bool
4921list_verify_fn(const cdt_context *ctx, rollback_alloc *alloc_idx)
4922{
4923 if (! ctx->b) {
4924 return true;
4925 }
4926
4927 packed_list list;
4928 uint8_t type = as_bin_get_particle_type(ctx->b);
4929
4930 if (type != AS_PARTICLE_TYPE_LIST && type != AS_PARTICLE_TYPE_MAP) {
4931 cf_warning(AS_PARTICLE, "list_verify() non-cdt type: %u", type);
4932 return false;
4933 }
4934
4935 // Check header.
4936 if (! packed_list_init_from_ctx(&list, ctx)) {
4937 cdt_context_print(ctx, "ctx");
4938 cf_warning(AS_PARTICLE, "list_verify() invalid packed list");
4939 return false;
4940 }
4941
4942 offset_index *offidx = list_full_offidx_p(&list);
4943 bool check_offidx = offset_index_is_valid(offidx);
4944 uint32_t filled = 0;
4945 define_offset_index(temp_offidx, list.contents, list.content_sz,
4946 list.ele_count, alloc_idx);
4947
4948 msgpack_in pk = {
4949 .buf = list.contents,
4950 .buf_sz = list.content_sz
4951 };
4952
4953 if (check_offidx) {
4954 filled = offset_index_get_filled(offidx);
4955 cf_assert(filled != 0, AS_PARTICLE, "filled should be at least 1 for valid offsets");
4956
4957 if (list.ele_count > 1) {
4958 offset_index_copy(&temp_offidx, offidx, 0, 0, filled, 0);
4959 }
4960 }
4961
4962 // Check offsets.
4963 for (uint32_t i = 0; i < list.ele_count; i++) {
4964 uint32_t offset;
4965
4966 if (check_offidx) {
4967 if (list_is_ordered(&list)) {
4968 if (i < filled) {
4969 offset = offset_index_get_const(offidx, i);
4970
4971 if (pk.offset != offset) {
4972 cf_warning(AS_PARTICLE, "list_verify() i=%u offset=%u expected=%u", i, offset, pk.offset);
4973 return false;
4974 }
4975 }
4976 else {
4977 offset_index_set(&temp_offidx, i, pk.offset);
4978 }
4979 }
4980 else if ((i % PACKED_LIST_INDEX_STEP) == 0) {
4981 uint32_t step_i = i / PACKED_LIST_INDEX_STEP;
4982
4983 if (i < filled) {
4984 offset = offset_index_get_const(offidx, i);
4985
4986 if (pk.offset != offset) {
4987 cf_warning(AS_PARTICLE, "list_verify() i=%u step %u offset=%u expected=%u", i, step_i, offset, pk.offset);
4988 return false;
4989 }
4990 }
4991 }
4992 }
4993 else {
4994 offset_index_set(&temp_offidx, i, pk.offset);
4995 }
4996
4997 offset = pk.offset;
4998
4999 if (msgpack_sz(&pk) == 0) {
5000 cf_warning(AS_PARTICLE, "list_verify() i=%u offset=%u pk.offset=%u invalid key", i, offset, pk.offset);
5001 return false;
5002 }
5003 }
5004
5005 // Check packed size.
5006 if (list.content_sz != pk.offset) {
5007 cf_warning(AS_PARTICLE, "list_verify() content_sz=%u expected=%u", list.content_sz, pk.offset);
5008 cdt_context_print(ctx, "ctx");
5009 return false;
5010 }
5011
5012 pk.offset = 0;
5013
5014 msgpack_in pk_value = pk;
5015
5016 // Check ordered list.
5017 if (list_is_ordered(&list) && list.ele_count > 0) {
5018 if (msgpack_sz(&pk) == 0) {
5019 cf_warning(AS_PARTICLE, "list_verify() pk.offset=%u invalid value", pk.offset);
5020 return false;
5021 }
5022
5023 for (uint32_t i = 1; i < list.ele_count; i++) {
5024 uint32_t offset = pk.offset;
5025 msgpack_compare_t cmp = msgpack_cmp(&pk_value, &pk);
5026
5027 if (cmp == MSGPACK_COMPARE_ERROR) {
5028 cf_warning(AS_PARTICLE, "list_verify() i=%u/%u offset=%u pk.offset=%u invalid element", i, list.ele_count, offset, pk.offset);
5029 return false;
5030 }
5031
5032 if (cmp == MSGPACK_COMPARE_GREATER) {
5033 cf_warning(AS_PARTICLE, "list_verify() i=%u offset=%u pk.offset=%u ele_count=%u element not in order", i, offset, pk.offset, list.ele_count);
5034 return false;
5035 }
5036 }
5037 }
5038
5039 return true;
5040}
5041
5042bool
5043list_verify(const cdt_context *ctx)
5044{
5045 define_rollback_alloc(alloc_idx, NULL, 8, false); // for temp indexes
5046 bool ret = list_verify_fn(ctx, alloc_idx);
5047
5048 rollback_alloc_rollback(alloc_idx);
5049
5050 return ret;
5051}
5052