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/message/message.h"
17 #include "upb/mini_table/field.h"
18 #include "upb/mini_table/internal/size_log2.h"
19 #include "upb/mini_table/message.h"
20
21 // Must be last.
22 #include "upb/port/def.inc"
23
upb_Array_New(upb_Arena * a,upb_CType type)24 upb_Array* upb_Array_New(upb_Arena* a, upb_CType type) {
25 const int lg2 = UPB_PRIVATE(_upb_CType_SizeLg2)(type);
26 return UPB_PRIVATE(_upb_Array_New)(a, 4, lg2);
27 }
28
upb_Array_Get(const upb_Array * arr,size_t i)29 upb_MessageValue upb_Array_Get(const upb_Array* arr, size_t i) {
30 UPB_ASSERT(i < upb_Array_Size(arr));
31 upb_MessageValue ret;
32 const char* data = upb_Array_DataPtr(arr);
33 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
34 memcpy(&ret, data + (i << lg2), 1 << lg2);
35 return ret;
36 }
37
upb_Array_GetMutable(upb_Array * arr,size_t i)38 upb_MutableMessageValue upb_Array_GetMutable(upb_Array* arr, size_t i) {
39 UPB_ASSERT(i < upb_Array_Size(arr));
40 upb_MutableMessageValue ret;
41 char* data = upb_Array_MutableDataPtr(arr);
42 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
43 memcpy(&ret, data + (i << lg2), 1 << lg2);
44 return ret;
45 }
46
upb_Array_Set(upb_Array * arr,size_t i,upb_MessageValue val)47 void upb_Array_Set(upb_Array* arr, size_t i, upb_MessageValue val) {
48 UPB_ASSERT(!upb_Array_IsFrozen(arr));
49 UPB_ASSERT(i < upb_Array_Size(arr));
50 char* data = upb_Array_MutableDataPtr(arr);
51 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
52 memcpy(data + (i << lg2), &val, 1 << lg2);
53 }
54
upb_Array_Append(upb_Array * arr,upb_MessageValue val,upb_Arena * arena)55 bool upb_Array_Append(upb_Array* arr, upb_MessageValue val, upb_Arena* arena) {
56 UPB_ASSERT(!upb_Array_IsFrozen(arr));
57 UPB_ASSERT(arena);
58 if (!UPB_PRIVATE(_upb_Array_ResizeUninitialized)(
59 arr, arr->UPB_PRIVATE(size) + 1, arena)) {
60 return false;
61 }
62 upb_Array_Set(arr, arr->UPB_PRIVATE(size) - 1, val);
63 return true;
64 }
65
upb_Array_Move(upb_Array * arr,size_t dst_idx,size_t src_idx,size_t count)66 void upb_Array_Move(upb_Array* arr, size_t dst_idx, size_t src_idx,
67 size_t count) {
68 UPB_ASSERT(!upb_Array_IsFrozen(arr));
69 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
70 char* data = upb_Array_MutableDataPtr(arr);
71 memmove(&data[dst_idx << lg2], &data[src_idx << lg2], count << lg2);
72 }
73
upb_Array_Insert(upb_Array * arr,size_t i,size_t count,upb_Arena * arena)74 bool upb_Array_Insert(upb_Array* arr, size_t i, size_t count,
75 upb_Arena* arena) {
76 UPB_ASSERT(!upb_Array_IsFrozen(arr));
77 UPB_ASSERT(arena);
78 UPB_ASSERT(i <= arr->UPB_PRIVATE(size));
79 UPB_ASSERT(count + arr->UPB_PRIVATE(size) >= count);
80 const size_t oldsize = arr->UPB_PRIVATE(size);
81 if (!UPB_PRIVATE(_upb_Array_ResizeUninitialized)(
82 arr, arr->UPB_PRIVATE(size) + count, arena)) {
83 return false;
84 }
85 upb_Array_Move(arr, i + count, i, oldsize - i);
86 return true;
87 }
88
89 /*
90 * i end arr->size
91 * |------------|XXXXXXXX|--------|
92 */
upb_Array_Delete(upb_Array * arr,size_t i,size_t count)93 void upb_Array_Delete(upb_Array* arr, size_t i, size_t count) {
94 UPB_ASSERT(!upb_Array_IsFrozen(arr));
95 const size_t end = i + count;
96 UPB_ASSERT(i <= end);
97 UPB_ASSERT(end <= arr->UPB_PRIVATE(size));
98 upb_Array_Move(arr, i, end, arr->UPB_PRIVATE(size) - end);
99 arr->UPB_PRIVATE(size) -= count;
100 }
101
upb_Array_Resize(upb_Array * arr,size_t size,upb_Arena * arena)102 bool upb_Array_Resize(upb_Array* arr, size_t size, upb_Arena* arena) {
103 UPB_ASSERT(!upb_Array_IsFrozen(arr));
104 const size_t oldsize = arr->UPB_PRIVATE(size);
105 if (UPB_UNLIKELY(
106 !UPB_PRIVATE(_upb_Array_ResizeUninitialized)(arr, size, arena))) {
107 return false;
108 }
109 const size_t newsize = arr->UPB_PRIVATE(size);
110 if (newsize > oldsize) {
111 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(arr);
112 char* data = upb_Array_MutableDataPtr(arr);
113 memset(data + (oldsize << lg2), 0, (newsize - oldsize) << lg2);
114 }
115 return true;
116 }
117
UPB_PRIVATE(_upb_Array_Realloc)118 bool UPB_PRIVATE(_upb_Array_Realloc)(upb_Array* array, size_t min_capacity,
119 upb_Arena* arena) {
120 size_t new_capacity = UPB_MAX(array->UPB_PRIVATE(capacity), 4);
121 const int lg2 = UPB_PRIVATE(_upb_Array_ElemSizeLg2)(array);
122 size_t old_bytes = array->UPB_PRIVATE(capacity) << lg2;
123 void* ptr = upb_Array_MutableDataPtr(array);
124
125 // Log2 ceiling of size.
126 while (new_capacity < min_capacity) new_capacity *= 2;
127
128 const size_t new_bytes = new_capacity << lg2;
129 ptr = upb_Arena_Realloc(arena, ptr, old_bytes, new_bytes);
130 if (!ptr) return false;
131
132 UPB_PRIVATE(_upb_Array_SetTaggedPtr)(array, ptr, lg2);
133 array->UPB_PRIVATE(capacity) = new_capacity;
134 return true;
135 }
136
upb_Array_Freeze(upb_Array * arr,const upb_MiniTable * m)137 void upb_Array_Freeze(upb_Array* arr, const upb_MiniTable* m) {
138 if (upb_Array_IsFrozen(arr)) return;
139 UPB_PRIVATE(_upb_Array_ShallowFreeze)(arr);
140
141 if (m) {
142 const size_t size = upb_Array_Size(arr);
143
144 for (size_t i = 0; i < size; i++) {
145 upb_MessageValue val = upb_Array_Get(arr, i);
146 upb_Message_Freeze((upb_Message*)val.msg_val, m);
147 }
148 }
149 }
150