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 #ifndef UPB_MESSAGE_INTERNAL_ARRAY_H_
9 #define UPB_MESSAGE_INTERNAL_ARRAY_H_
10
11 #include <stdint.h>
12 #include <string.h>
13
14 #include "upb/mem/arena.h"
15
16 // Must be last.
17 #include "upb/port/def.inc"
18
19 #define _UPB_ARRAY_MASK_IMM 0x4 // Frozen/immutable bit.
20 #define _UPB_ARRAY_MASK_LG2 0x3 // Encoded elem size.
21 #define _UPB_ARRAY_MASK_ALL (_UPB_ARRAY_MASK_IMM | _UPB_ARRAY_MASK_LG2)
22
23 #ifdef __cplusplus
24 extern "C" {
25 #endif
26
27 // LINT.IfChange(upb_Array)
28
29 // Our internal representation for repeated fields.
30 struct upb_Array {
31 // This is a tagged pointer. Bits #0 and #1 encode the elem size as follows:
32 // 0 maps to elem size 1
33 // 1 maps to elem size 4
34 // 2 maps to elem size 8
35 // 3 maps to elem size 16
36 //
37 // Bit #2 contains the frozen/immutable flag.
38 uintptr_t UPB_ONLYBITS(data);
39
40 size_t UPB_ONLYBITS(size); // The number of elements in the array.
41 size_t UPB_PRIVATE(capacity); // Allocated storage. Measured in elements.
42 };
43
UPB_PRIVATE(_upb_Array_ShallowFreeze)44 UPB_INLINE void UPB_PRIVATE(_upb_Array_ShallowFreeze)(struct upb_Array* arr) {
45 arr->UPB_ONLYBITS(data) |= _UPB_ARRAY_MASK_IMM;
46 }
47
upb_Array_IsFrozen(const struct upb_Array * arr)48 UPB_API_INLINE bool upb_Array_IsFrozen(const struct upb_Array* arr) {
49 return (arr->UPB_ONLYBITS(data) & _UPB_ARRAY_MASK_IMM) != 0;
50 }
51
UPB_PRIVATE(_upb_Array_SetTaggedPtr)52 UPB_INLINE void UPB_PRIVATE(_upb_Array_SetTaggedPtr)(struct upb_Array* array,
53 void* data, size_t lg2) {
54 UPB_ASSERT(lg2 != 1);
55 UPB_ASSERT(lg2 <= 4);
56 const size_t bits = lg2 - (lg2 != 0);
57 array->UPB_ONLYBITS(data) = (uintptr_t)data | bits;
58 }
59
60 UPB_INLINE size_t
UPB_PRIVATE(_upb_Array_ElemSizeLg2)61 UPB_PRIVATE(_upb_Array_ElemSizeLg2)(const struct upb_Array* array) {
62 const size_t bits = array->UPB_ONLYBITS(data) & _UPB_ARRAY_MASK_LG2;
63 const size_t lg2 = bits + (bits != 0);
64 return lg2;
65 }
66
upb_Array_DataPtr(const struct upb_Array * array)67 UPB_API_INLINE const void* upb_Array_DataPtr(const struct upb_Array* array) {
68 UPB_PRIVATE(_upb_Array_ElemSizeLg2)(array); // Check assertions.
69 return (void*)(array->UPB_ONLYBITS(data) & ~(uintptr_t)_UPB_ARRAY_MASK_ALL);
70 }
71
upb_Array_MutableDataPtr(struct upb_Array * array)72 UPB_API_INLINE void* upb_Array_MutableDataPtr(struct upb_Array* array) {
73 return (void*)upb_Array_DataPtr(array);
74 }
75
UPB_PRIVATE(_upb_Array_New)76 UPB_INLINE struct upb_Array* UPB_PRIVATE(_upb_Array_New)(upb_Arena* arena,
77 size_t init_capacity,
78 int elem_size_lg2) {
79 UPB_ASSERT(elem_size_lg2 != 1);
80 UPB_ASSERT(elem_size_lg2 <= 4);
81 const size_t array_size =
82 UPB_ALIGN_UP(sizeof(struct upb_Array), UPB_MALLOC_ALIGN);
83 const size_t bytes = array_size + (init_capacity << elem_size_lg2);
84 struct upb_Array* array = (struct upb_Array*)upb_Arena_Malloc(arena, bytes);
85 if (!array) return NULL;
86 UPB_PRIVATE(_upb_Array_SetTaggedPtr)
87 (array, UPB_PTR_AT(array, array_size, void), elem_size_lg2);
88 array->UPB_ONLYBITS(size) = 0;
89 array->UPB_PRIVATE(capacity) = init_capacity;
90 return array;
91 }
92
93 // Resizes the capacity of the array to be at least min_size.
94 bool UPB_PRIVATE(_upb_Array_Realloc)(struct upb_Array* array, size_t min_size,
95 upb_Arena* arena);
96
upb_Array_Reserve(struct upb_Array * array,size_t size,upb_Arena * arena)97 UPB_API_INLINE bool upb_Array_Reserve(struct upb_Array* array, size_t size,
98 upb_Arena* arena) {
99 UPB_ASSERT(!upb_Array_IsFrozen(array));
100 if (array->UPB_PRIVATE(capacity) < size)
101 return UPB_PRIVATE(_upb_Array_Realloc)(array, size, arena);
102 return true;
103 }
104
105 // Resize without initializing new elements.
UPB_PRIVATE(_upb_Array_ResizeUninitialized)106 UPB_INLINE bool UPB_PRIVATE(_upb_Array_ResizeUninitialized)(
107 struct upb_Array* array, size_t size, upb_Arena* arena) {
108 UPB_ASSERT(!upb_Array_IsFrozen(array));
109 UPB_ASSERT(size <= array->UPB_ONLYBITS(size) ||
110 arena); // Allow NULL arena when shrinking.
111 if (!upb_Array_Reserve(array, size, arena)) return false;
112 array->UPB_ONLYBITS(size) = size;
113 return true;
114 }
115
116 // This function is intended for situations where elem_size is compile-time
117 // constant or a known expression of the form (1 << lg2), so that the expression
118 // i*elem_size does not result in an actual multiplication.
UPB_PRIVATE(_upb_Array_Set)119 UPB_INLINE void UPB_PRIVATE(_upb_Array_Set)(struct upb_Array* array, size_t i,
120 const void* data,
121 size_t elem_size) {
122 UPB_ASSERT(!upb_Array_IsFrozen(array));
123 UPB_ASSERT(i < array->UPB_ONLYBITS(size));
124 UPB_ASSERT(elem_size == 1U << UPB_PRIVATE(_upb_Array_ElemSizeLg2)(array));
125 char* arr_data = (char*)upb_Array_MutableDataPtr(array);
126 memcpy(arr_data + (i * elem_size), data, elem_size);
127 }
128
upb_Array_Size(const struct upb_Array * arr)129 UPB_API_INLINE size_t upb_Array_Size(const struct upb_Array* arr) {
130 return arr->UPB_ONLYBITS(size);
131 }
132
133 // LINT.ThenChange(GoogleInternalName0)
134
135 #ifdef __cplusplus
136 } /* extern "C" */
137 #endif
138
139 #undef _UPB_ARRAY_MASK_IMM
140 #undef _UPB_ARRAY_MASK_LG2
141 #undef _UPB_ARRAY_MASK_ALL
142
143 #include "upb/port/undef.inc"
144
145 #endif /* UPB_MESSAGE_INTERNAL_ARRAY_H_ */
146