1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google LLC. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 #include "upb/message/array.h"
9
10 #include <stdint.h>
11 #include <string.h>
12
13 #include "upb/base/descriptor_constants.h"
14 #include "upb/mem/arena.h"
15 #include "upb/message/internal/array.h"
16 #include "upb/mini_table/internal/size_log2.h"
17
18 // Must be last.
19 #include "upb/port/def.inc"
20
upb_Array_New(upb_Arena * a,upb_CType type)21 upb_Array* upb_Array_New(upb_Arena* a, upb_CType type) {
22 const int lg2 = UPB_PRIVATE(_upb_CType_SizeLg2)(type);
23 return UPB_PRIVATE(_upb_Array_New)(a, 4, lg2);
24 }
25
upb_Array_Get(const upb_Array * arr,size_t i)26 upb_MessageValue upb_Array_Get(const upb_Array* arr, size_t i) {
27 upb_MessageValue ret;
28 const char* data = upb_Array_DataPtr(arr);
29 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
30 UPB_ASSERT(i < arr->UPB_PRIVATE(size));
31 memcpy(&ret, data + (i << lg2), 1 << lg2);
32 return ret;
33 }
34
upb_Array_GetMutable(upb_Array * arr,size_t i)35 upb_MutableMessageValue upb_Array_GetMutable(upb_Array* arr, size_t i) {
36 upb_MutableMessageValue ret;
37 char* data = upb_Array_MutableDataPtr(arr);
38 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
39 UPB_ASSERT(i < arr->UPB_PRIVATE(size));
40 memcpy(&ret, data + (i << lg2), 1 << lg2);
41 return ret;
42 }
43
upb_Array_Set(upb_Array * arr,size_t i,upb_MessageValue val)44 void upb_Array_Set(upb_Array* arr, size_t i, upb_MessageValue val) {
45 char* data = upb_Array_MutableDataPtr(arr);
46 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
47 UPB_ASSERT(i < arr->UPB_PRIVATE(size));
48 memcpy(data + (i << lg2), &val, 1 << lg2);
49 }
50
upb_Array_Append(upb_Array * arr,upb_MessageValue val,upb_Arena * arena)51 bool upb_Array_Append(upb_Array* arr, upb_MessageValue val, upb_Arena* arena) {
52 UPB_ASSERT(arena);
53 if (!UPB_PRIVATE(_upb_Array_ResizeUninitialized)(
54 arr, arr->UPB_PRIVATE(size) + 1, arena)) {
55 return false;
56 }
57 upb_Array_Set(arr, arr->UPB_PRIVATE(size) - 1, val);
58 return true;
59 }
60
upb_Array_Move(upb_Array * arr,size_t dst_idx,size_t src_idx,size_t count)61 void upb_Array_Move(upb_Array* arr, size_t dst_idx, size_t src_idx,
62 size_t count) {
63 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
64 char* data = upb_Array_MutableDataPtr(arr);
65 memmove(&data[dst_idx << lg2], &data[src_idx << lg2], count << lg2);
66 }
67
upb_Array_Insert(upb_Array * arr,size_t i,size_t count,upb_Arena * arena)68 bool upb_Array_Insert(upb_Array* arr, size_t i, size_t count,
69 upb_Arena* arena) {
70 UPB_ASSERT(arena);
71 UPB_ASSERT(i <= arr->UPB_PRIVATE(size));
72 UPB_ASSERT(count + arr->UPB_PRIVATE(size) >= count);
73 const size_t oldsize = arr->UPB_PRIVATE(size);
74 if (!UPB_PRIVATE(_upb_Array_ResizeUninitialized)(
75 arr, arr->UPB_PRIVATE(size) + count, arena)) {
76 return false;
77 }
78 upb_Array_Move(arr, i + count, i, oldsize - i);
79 return true;
80 }
81
82 /*
83 * i end arr->size
84 * |------------|XXXXXXXX|--------|
85 */
upb_Array_Delete(upb_Array * arr,size_t i,size_t count)86 void upb_Array_Delete(upb_Array* arr, size_t i, size_t count) {
87 const size_t end = i + count;
88 UPB_ASSERT(i <= end);
89 UPB_ASSERT(end <= arr->UPB_PRIVATE(size));
90 upb_Array_Move(arr, i, end, arr->UPB_PRIVATE(size) - end);
91 arr->UPB_PRIVATE(size) -= count;
92 }
93
upb_Array_Resize(upb_Array * arr,size_t size,upb_Arena * arena)94 bool upb_Array_Resize(upb_Array* arr, size_t size, upb_Arena* arena) {
95 const size_t oldsize = arr->UPB_PRIVATE(size);
96 if (UPB_UNLIKELY(
97 !UPB_PRIVATE(_upb_Array_ResizeUninitialized)(arr, size, arena))) {
98 return false;
99 }
100 const size_t newsize = arr->UPB_PRIVATE(size);
101 if (newsize > oldsize) {
102 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
103 char* data = upb_Array_MutableDataPtr(arr);
104 memset(data + (oldsize << lg2), 0, (newsize - oldsize) << lg2);
105 }
106 return true;
107 }
108
UPB_PRIVATE(_upb_Array_Realloc)109 bool UPB_PRIVATE(_upb_Array_Realloc)(upb_Array* array, size_t min_capacity,
110 upb_Arena* arena) {
111 size_t new_capacity = UPB_MAX(array->UPB_PRIVATE(capacity), 4);
112 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(array);
113 size_t old_bytes = array->UPB_PRIVATE(capacity) << lg2;
114 void* ptr = upb_Array_MutableDataPtr(array);
115
116 // Log2 ceiling of size.
117 while (new_capacity < min_capacity) new_capacity *= 2;
118
119 const size_t new_bytes = new_capacity << lg2;
120 ptr = upb_Arena_Realloc(arena, ptr, old_bytes, new_bytes);
121 if (!ptr) return false;
122
123 UPB_PRIVATE(_upb_Array_SetTaggedPtr)(array, ptr, lg2);
124 array->UPB_PRIVATE(capacity) = new_capacity;
125 return true;
126 }
127