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_New)(upb_Arena* arena,
0077                                                          size_t init_capacity,
0078                                                          int elem_size_lg2) {
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   struct upb_Array* array = (struct upb_Array*)upb_Arena_Malloc(arena, bytes);
0085   if (!array) return NULL;
0086   UPB_PRIVATE(_upb_Array_SetTaggedPtr)
0087   (array, UPB_PTR_AT(array, array_size, void), elem_size_lg2);
0088   array->UPB_ONLYBITS(size) = 0;
0089   array->UPB_PRIVATE(capacity) = init_capacity;
0090   return array;
0091 }
0092
0093 // Resizes the capacity of the array to be at least min_size.
0094 bool UPB_PRIVATE(_upb_Array_Realloc)(struct upb_Array* array, size_t min_size,
0095                                      upb_Arena* arena);
0096
0097 UPB_API_INLINE bool upb_Array_Reserve(struct upb_Array* array, size_t size,
0098                                       upb_Arena* arena) {
0099   UPB_ASSERT(!upb_Array_IsFrozen(array));
0100   if (array->UPB_PRIVATE(capacity) < size)
0101     return UPB_PRIVATE(_upb_Array_Realloc)(array, size, arena);
0102   return true;
0103 }
0104
0105 // Resize without initializing new elements.
0106 UPB_INLINE bool UPB_PRIVATE(_upb_Array_ResizeUninitialized)(
0107     struct upb_Array* array, size_t size, upb_Arena* arena) {
0108   UPB_ASSERT(!upb_Array_IsFrozen(array));
0109   UPB_ASSERT(size <= array->UPB_ONLYBITS(size) ||
0110              arena);  // Allow NULL arena when shrinking.
0111   if (!upb_Array_Reserve(array, size, arena)) return false;
0112   array->UPB_ONLYBITS(size) = size;
0113   return true;
0114 }
0115
0116 // This function is intended for situations where elem_size is compile-time
0117 // constant or a known expression of the form (1 << lg2), so that the expression
0118 // i*elem_size does not result in an actual multiplication.
0119 UPB_INLINE void UPB_PRIVATE(_upb_Array_Set)(struct upb_Array* array, size_t i,
0120                                             const void* data,
0121                                             size_t elem_size) {
0122   UPB_ASSERT(!upb_Array_IsFrozen(array));
0123   UPB_ASSERT(i < array->UPB_ONLYBITS(size));
0124   UPB_ASSERT(elem_size == 1U << UPB_PRIVATE(_upb_Array_ElemSizeLg2)(array));
0125   char* arr_data = (char*)upb_Array_MutableDataPtr(array);
0126   memcpy(arr_data + (i * elem_size), data, elem_size);
0127 }
0128
0129 UPB_API_INLINE size_t upb_Array_Size(const struct upb_Array* arr) {
0130   return arr->UPB_ONLYBITS(size);
0131 }
0132
0133 // LINT.ThenChange(GoogleInternalName0)
0134
0135 #ifdef __cplusplus
0136 } /* extern "C" */
0137 #endif
0138
0139 #undef _UPB_ARRAY_MASK_IMM
0140 #undef _UPB_ARRAY_MASK_LG2
0141 #undef _UPB_ARRAY_MASK_ALL
0142
0143 #include "upb/port/undef.inc"
0144
0145 #endif /* UPB_MESSAGE_INTERNAL_ARRAY_H_ */