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 // EVERYTHING BELOW THIS LINE IS INTERNAL - DO NOT USE /////////////////////////
29
30 #ifndef UPB_COLLECTIONS_MAP_SORTER_INTERNAL_H_
31 #define UPB_COLLECTIONS_MAP_SORTER_INTERNAL_H_
32
33 #include <stdlib.h>
34
35 #include "upb/collections/map_internal.h"
36 #include "upb/message/extension_internal.h"
37 #include "upb/mini_table/message_internal.h"
38
39 // Must be last.
40 #include "upb/port/def.inc"
41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45
46 // _upb_mapsorter sorts maps and provides ordered iteration over the entries.
47 // Since maps can be recursive (map values can be messages which contain other
48 // maps), _upb_mapsorter can contain a stack of maps.
49
50 typedef struct {
51 void const** entries;
52 int size;
53 int cap;
54 } _upb_mapsorter;
55
56 typedef struct {
57 int start;
58 int pos;
59 int end;
60 } _upb_sortedmap;
61
_upb_mapsorter_init(_upb_mapsorter * s)62 UPB_INLINE void _upb_mapsorter_init(_upb_mapsorter* s) {
63 s->entries = NULL;
64 s->size = 0;
65 s->cap = 0;
66 }
67
_upb_mapsorter_destroy(_upb_mapsorter * s)68 UPB_INLINE void _upb_mapsorter_destroy(_upb_mapsorter* s) {
69 if (s->entries) free(s->entries);
70 }
71
_upb_sortedmap_next(_upb_mapsorter * s,const upb_Map * map,_upb_sortedmap * sorted,upb_MapEntry * ent)72 UPB_INLINE bool _upb_sortedmap_next(_upb_mapsorter* s, const upb_Map* map,
73 _upb_sortedmap* sorted, upb_MapEntry* ent) {
74 if (sorted->pos == sorted->end) return false;
75 const upb_tabent* tabent = (const upb_tabent*)s->entries[sorted->pos++];
76 upb_StringView key = upb_tabstrview(tabent->key);
77 _upb_map_fromkey(key, &ent->data.k, map->key_size);
78 upb_value val = {tabent->val.val};
79 _upb_map_fromvalue(val, &ent->data.v, map->val_size);
80 return true;
81 }
82
_upb_sortedmap_nextext(_upb_mapsorter * s,_upb_sortedmap * sorted,const upb_Message_Extension ** ext)83 UPB_INLINE bool _upb_sortedmap_nextext(_upb_mapsorter* s,
84 _upb_sortedmap* sorted,
85 const upb_Message_Extension** ext) {
86 if (sorted->pos == sorted->end) return false;
87 *ext = (const upb_Message_Extension*)s->entries[sorted->pos++];
88 return true;
89 }
90
_upb_mapsorter_popmap(_upb_mapsorter * s,_upb_sortedmap * sorted)91 UPB_INLINE void _upb_mapsorter_popmap(_upb_mapsorter* s,
92 _upb_sortedmap* sorted) {
93 s->size = sorted->start;
94 }
95
96 bool _upb_mapsorter_pushmap(_upb_mapsorter* s, upb_FieldType key_type,
97 const upb_Map* map, _upb_sortedmap* sorted);
98
99 bool _upb_mapsorter_pushexts(_upb_mapsorter* s,
100 const upb_Message_Extension* exts, size_t count,
101 _upb_sortedmap* sorted);
102
103 #ifdef __cplusplus
104 } /* extern "C" */
105 #endif
106
107 #include "upb/port/undef.inc"
108
109 #endif /* UPB_COLLECTIONS_MAP_SORTER_INTERNAL_H_ */
110