1 /*
2 * Copyright (c) 2009-2021, Google LLC
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Google LLC nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY DIRECT,
20 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #ifndef UPB_INTERNAL_ARRAY_INTERNAL_H_
29 #define UPB_INTERNAL_ARRAY_INTERNAL_H_
30
31 #include <string.h>
32
33 #include "upb/collections/array.h"
34
35 // Must be last.
36 #include "upb/port/def.inc"
37
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41
42 // LINT.IfChange(struct_definition)
43 // Our internal representation for repeated fields.
44 struct upb_Array {
45 uintptr_t data; /* Tagged ptr: low 3 bits of ptr are lg2(elem size). */
46 size_t size; /* The number of elements in the array. */
47 size_t capacity; /* Allocated storage. Measured in elements. */
48 };
49 // LINT.ThenChange(GoogleInternalName1)
50
_upb_Array_ElementSizeLg2(const upb_Array * arr)51 UPB_INLINE size_t _upb_Array_ElementSizeLg2(const upb_Array* arr) {
52 size_t ret = arr->data & 7;
53 UPB_ASSERT(ret <= 4);
54 return ret;
55 }
56
_upb_array_constptr(const upb_Array * arr)57 UPB_INLINE const void* _upb_array_constptr(const upb_Array* arr) {
58 _upb_Array_ElementSizeLg2(arr); // Check assertion.
59 return (void*)(arr->data & ~(uintptr_t)7);
60 }
61
_upb_array_tagptr(void * ptr,int elem_size_lg2)62 UPB_INLINE uintptr_t _upb_array_tagptr(void* ptr, int elem_size_lg2) {
63 UPB_ASSERT(elem_size_lg2 <= 4);
64 return (uintptr_t)ptr | elem_size_lg2;
65 }
66
_upb_array_ptr(upb_Array * arr)67 UPB_INLINE void* _upb_array_ptr(upb_Array* arr) {
68 return (void*)_upb_array_constptr(arr);
69 }
70
_upb_tag_arrptr(void * ptr,int elem_size_lg2)71 UPB_INLINE uintptr_t _upb_tag_arrptr(void* ptr, int elem_size_lg2) {
72 UPB_ASSERT(elem_size_lg2 <= 4);
73 UPB_ASSERT(((uintptr_t)ptr & 7) == 0);
74 return (uintptr_t)ptr | (unsigned)elem_size_lg2;
75 }
76
77 extern const char _upb_Array_CTypeSizeLg2Table[];
78
_upb_Array_CTypeSizeLg2(upb_CType ctype)79 UPB_INLINE size_t _upb_Array_CTypeSizeLg2(upb_CType ctype) {
80 return _upb_Array_CTypeSizeLg2Table[ctype];
81 }
82
_upb_Array_New(upb_Arena * a,size_t init_capacity,int elem_size_lg2)83 UPB_INLINE upb_Array* _upb_Array_New(upb_Arena* a, size_t init_capacity,
84 int elem_size_lg2) {
85 UPB_ASSERT(elem_size_lg2 <= 4);
86 const size_t arr_size = UPB_ALIGN_UP(sizeof(upb_Array), UPB_MALLOC_ALIGN);
87 const size_t bytes = arr_size + (init_capacity << elem_size_lg2);
88 upb_Array* arr = (upb_Array*)upb_Arena_Malloc(a, bytes);
89 if (!arr) return NULL;
90 arr->data = _upb_tag_arrptr(UPB_PTR_AT(arr, arr_size, void), elem_size_lg2);
91 arr->size = 0;
92 arr->capacity = init_capacity;
93 return arr;
94 }
95
96 // Resizes the capacity of the array to be at least min_size.
97 bool _upb_array_realloc(upb_Array* arr, size_t min_size, upb_Arena* arena);
98
_upb_array_reserve(upb_Array * arr,size_t size,upb_Arena * arena)99 UPB_INLINE bool _upb_array_reserve(upb_Array* arr, size_t size,
100 upb_Arena* arena) {
101 if (arr->capacity < size) return _upb_array_realloc(arr, size, arena);
102 return true;
103 }
104
105 // Resize without initializing new elements.
_upb_Array_ResizeUninitialized(upb_Array * arr,size_t size,upb_Arena * arena)106 UPB_INLINE bool _upb_Array_ResizeUninitialized(upb_Array* arr, size_t size,
107 upb_Arena* arena) {
108 UPB_ASSERT(size <= arr->size || arena); // Allow NULL arena when shrinking.
109 if (!_upb_array_reserve(arr, size, arena)) return false;
110 arr->size = size;
111 return true;
112 }
113
114 // This function is intended for situations where elem_size is compile-time
115 // constant or a known expression of the form (1 << lg2), so that the expression
116 // i*elem_size does not result in an actual multiplication.
_upb_Array_Set(upb_Array * arr,size_t i,const void * data,size_t elem_size)117 UPB_INLINE void _upb_Array_Set(upb_Array* arr, size_t i, const void* data,
118 size_t elem_size) {
119 UPB_ASSERT(i < arr->size);
120 UPB_ASSERT(elem_size == 1U << _upb_Array_ElementSizeLg2(arr));
121 char* arr_data = (char*)_upb_array_ptr(arr);
122 memcpy(arr_data + (i * elem_size), data, elem_size);
123 }
124
_upb_array_detach(const void * msg,size_t ofs)125 UPB_INLINE void _upb_array_detach(const void* msg, size_t ofs) {
126 *UPB_PTR_AT(msg, ofs, upb_Array*) = NULL;
127 }
128
129 #ifdef __cplusplus
130 } /* extern "C" */
131 #endif
132
133 #include "upb/port/undef.inc"
134
135 #endif /* UPB_INTERNAL_ARRAY_INTERNAL_H_ */
136