message/internal/array.h

0001 // Protocol Buffers - Google's data interchange format
0002 // Copyright 2023 Google LLC.  All rights reserved.
0003 //
0004 // Use of this source code is governed by a BSD-style
0005 // license that can be found in the LICENSE file or at
0006 // https://developers.google.com/open-source/licenses/bsd
0007
0008 #ifndef UPB_MESSAGE_INTERNAL_ARRAY_H_
0009 #define UPB_MESSAGE_INTERNAL_ARRAY_H_
0010
0011 #include <stdint.h>
0012 #include <string.h>
0013
0014 #include "upb/mem/arena.h"
0015
0016 // Must be last.
0017 #include "upb/port/def.inc"
0018
0019 #define _UPB_ARRAY_MASK_IMM 0x4  // Frozen/immutable bit.
0020 #define _UPB_ARRAY_MASK_LG2 0x3  // Encoded elem size.
0021 #define _UPB_ARRAY_MASK_ALL (_UPB_ARRAY_MASK_IMM | _UPB_ARRAY_MASK_LG2)
0022
0023 #ifdef __cplusplus
0024 extern "C" {
0025 #endif
0026
0027 // LINT.IfChange(upb_Array)
0028
0029 // Our internal representation for repeated fields.
0030 struct upb_Array {
0031   // This is a tagged pointer. Bits #0 and #1 encode the elem size as follows:
0032   //   0 maps to elem size 1
0033   //   1 maps to elem size 4
0034   //   2 maps to elem size 8
0035   //   3 maps to elem size 16
0036   //
0037   // Bit #2 contains the frozen/immutable flag.
0038   uintptr_t UPB_ONLYBITS(data);
0039
0040   size_t UPB_ONLYBITS(size);     // The number of elements in the array.
0041   size_t UPB_PRIVATE(capacity);  // Allocated storage. Measured in elements.
0042 };
0043
0044 UPB_INLINE void UPB_PRIVATE(_upb_Array_ShallowFreeze)(struct upb_Array* arr) {
0045   arr->UPB_ONLYBITS(data) |= _UPB_ARRAY_MASK_IMM;
0046 }
0047
0048 UPB_API_INLINE bool upb_Array_IsFrozen(const struct upb_Array* arr) {
0049   return (arr->UPB_ONLYBITS(data) & _UPB_ARRAY_MASK_IMM) != 0;
0050 }
0051
0052 UPB_INLINE void UPB_PRIVATE(_upb_Array_SetTaggedPtr)(struct upb_Array* array,
0053                                                      void* data, size_t lg2) {
0054   UPB_ASSERT(lg2 != 1);
0055   UPB_ASSERT(lg2 <= 4);
0056   const size_t bits = lg2 - (lg2 != 0);
0057   array->UPB_ONLYBITS(data) = (uintptr_t)data | bits;
0058 }
0059
0060 UPB_INLINE size_t
0061 UPB_PRIVATE(_upb_Array_ElemSizeLg2)(const struct upb_Array* array) {
0062   const size_t bits = array->UPB_ONLYBITS(data) & _UPB_ARRAY_MASK_LG2;
0063   const size_t lg2 = bits + (bits != 0);
0064   return lg2;
0065 }
0066
0067 UPB_API_INLINE const void* upb_Array_DataPtr(const struct upb_Array* array) {
0068   UPB_PRIVATE(_upb_Array_ElemSizeLg2)(array);  // Check assertions.
0069   return (void*)(array->UPB_ONLYBITS(data) & ~(uintptr_t)_UPB_ARRAY_MASK_ALL);
0070 }
0071
0072 UPB_API_INLINE void* upb_Array_MutableDataPtr(struct upb_Array* array) {
0073   return (void*)upb_Array_DataPtr(array);
0074 }
0075
0076 UPB_INLINE struct upb_Array* UPB_PRIVATE(_upb_Array_NewMaybeAllowSlow)(
0077     upb_Arena* arena, size_t init_capacity, int elem_size_lg2,
0078     bool allow_slow) {
0079   UPB_ASSERT(elem_size_lg2 != 1);
0080   UPB_ASSERT(elem_size_lg2 <= 4);
0081   const size_t array_size =
0082       UPB_ALIGN_UP(sizeof(struct upb_Array), UPB_MALLOC_ALIGN);
0083   const size_t bytes = array_size + (init_capacity << elem_size_lg2);
0084   size_t span = UPB_PRIVATE(_upb_Arena_AllocSpan)(bytes);
0085   if (!allow_slow && UPB_PRIVATE(_upb_ArenaHas)(arena) < span) return NULL;
0086   struct upb_Array* array = (struct upb_Array*)upb_Arena_Malloc(arena, bytes);
0087   if (!array) return NULL;
0088   UPB_PRIVATE(_upb_Array_SetTaggedPtr)
0089   (array, UPB_PTR_AT(array, array_size, void), elem_size_lg2);
0090   array->UPB_ONLYBITS(size) = 0;
0091   array->UPB_PRIVATE(capacity) = init_capacity;
0092   return array;
0093 }
0094
0095 UPB_INLINE struct upb_Array* UPB_PRIVATE(_upb_Array_New)(upb_Arena* arena,
0096                                                          size_t init_capacity,
0097                                                          int elem_size_lg2) {
0098   return UPB_PRIVATE(_upb_Array_NewMaybeAllowSlow)(arena, init_capacity,
0099                                                    elem_size_lg2, true);
0100 }
0101
0102 UPB_INLINE struct upb_Array* UPB_PRIVATE(_upb_Array_TryFastNew)(
0103     upb_Arena* arena, size_t init_capacity, int elem_size_lg2) {
0104   return UPB_PRIVATE(_upb_Array_NewMaybeAllowSlow)(arena, init_capacity,
0105                                                    elem_size_lg2, false);
0106 }
0107
0108 // Resizes the capacity of the array to be at least min_size.
0109 bool UPB_PRIVATE(_upb_Array_Realloc)(struct upb_Array* array, size_t min_size,
0110                                      upb_Arena* arena);
0111
0112 UPB_FORCEINLINE
0113 bool UPB_PRIVATE(_upb_Array_TryFastRealloc)(struct upb_Array* array,
0114                                             size_t capacity, int elem_size_lg2,
0115                                             upb_Arena* arena) {
0116   size_t old_bytes = array->UPB_PRIVATE(capacity) << elem_size_lg2;
0117   size_t new_bytes = capacity << elem_size_lg2;
0118   UPB_ASSUME(new_bytes > old_bytes);
0119   if (!upb_Arena_TryExtend(arena, array, old_bytes, new_bytes)) return false;
0120   array->UPB_PRIVATE(capacity) = capacity;
0121   return true;
0122 }
0123
0124 UPB_API_INLINE bool upb_Array_Reserve(struct upb_Array* array, size_t size,
0125                                       upb_Arena* arena) {
0126   UPB_ASSERT(!upb_Array_IsFrozen(array));
0127   if (array->UPB_PRIVATE(capacity) < size)
0128     return UPB_PRIVATE(_upb_Array_Realloc)(array, size, arena);
0129   return true;
0130 }
0131
0132 // Resize without initializing new elements.
0133 UPB_INLINE bool UPB_PRIVATE(_upb_Array_ResizeUninitialized)(
0134     struct upb_Array* array, size_t size, upb_Arena* arena) {
0135   UPB_ASSERT(!upb_Array_IsFrozen(array));
0136   UPB_ASSERT(size <= array->UPB_ONLYBITS(size) ||
0137              arena);  // Allow NULL arena when shrinking.
0138   if (!upb_Array_Reserve(array, size, arena)) return false;
0139   array->UPB_ONLYBITS(size) = size;
0140   return true;
0141 }
0142
0143 // This function is intended for situations where elem_size is compile-time
0144 // constant or a known expression of the form (1 << lg2), so that the expression
0145 // i*elem_size does not result in an actual multiplication.
0146 UPB_INLINE void UPB_PRIVATE(_upb_Array_Set)(struct upb_Array* array, size_t i,
0147                                             const void* data,
0148                                             size_t elem_size) {
0149   UPB_ASSERT(!upb_Array_IsFrozen(array));
0150   UPB_ASSERT(i < array->UPB_ONLYBITS(size));
0151   UPB_ASSERT(elem_size == 1U << UPB_PRIVATE(_upb_Array_ElemSizeLg2)(array));
0152   char* arr_data = (char*)upb_Array_MutableDataPtr(array);
0153   memcpy(arr_data + (i * elem_size), data, elem_size);
0154 }
0155
0156 UPB_API_INLINE size_t upb_Array_Size(const struct upb_Array* arr) {
0157   return arr->UPB_ONLYBITS(size);
0158 }
0159
0160 UPB_API_INLINE size_t upb_Array_Capacity(const struct upb_Array* arr) {
0161   return arr->UPB_PRIVATE(capacity);
0162 }
0163
0164 // LINT.ThenChange(GoogleInternalName0)
0165
0166 #ifdef __cplusplus
0167 } /* extern "C" */
0168 #endif
0169
0170 #undef _UPB_ARRAY_MASK_IMM
0171 #undef _UPB_ARRAY_MASK_LG2
0172 #undef _UPB_ARRAY_MASK_ALL
0173
0174 #include "upb/port/undef.inc"
0175
0176 #endif /* UPB_MESSAGE_INTERNAL_ARRAY_H_ */