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 // EVERYTHING BELOW THIS LINE IS INTERNAL - DO NOT USE /////////////////////////
9
10 #ifndef UPB_MESSAGE_INTERNAL_MAP_SORTER_H_
11 #define UPB_MESSAGE_INTERNAL_MAP_SORTER_H_
12
13 #include <stdlib.h>
14
15 #include "upb/base/descriptor_constants.h"
16 #include "upb/base/string_view.h"
17 #include "upb/mem/alloc.h"
18 #include "upb/message/internal/extension.h"
19 #include "upb/message/internal/map.h"
20 #include "upb/message/internal/map_entry.h"
21
22 // Must be last.
23 #include "upb/port/def.inc"
24
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28
29 // _upb_mapsorter sorts maps and provides ordered iteration over the entries.
30 // Since maps can be recursive (map values can be messages which contain other
31 // maps), _upb_mapsorter can contain a stack of maps.
32
33 typedef struct {
34 void const** entries;
35 int size;
36 int cap;
37 } _upb_mapsorter;
38
39 typedef struct {
40 int start;
41 int pos;
42 int end;
43 } _upb_sortedmap;
44
_upb_mapsorter_init(_upb_mapsorter * s)45 UPB_INLINE void _upb_mapsorter_init(_upb_mapsorter* s) {
46 s->entries = NULL;
47 s->size = 0;
48 s->cap = 0;
49 }
50
_upb_mapsorter_destroy(_upb_mapsorter * s)51 UPB_INLINE void _upb_mapsorter_destroy(_upb_mapsorter* s) {
52 if (s->entries) upb_gfree(s->entries);
53 }
54
_upb_sortedmap_next(_upb_mapsorter * s,const struct upb_Map * map,_upb_sortedmap * sorted,upb_MapEntry * ent)55 UPB_INLINE bool _upb_sortedmap_next(_upb_mapsorter* s,
56 const struct upb_Map* map,
57 _upb_sortedmap* sorted, upb_MapEntry* ent) {
58 if (sorted->pos == sorted->end) return false;
59 const upb_tabent* tabent = (const upb_tabent*)s->entries[sorted->pos++];
60 upb_StringView key = upb_tabstrview(tabent->key);
61 _upb_map_fromkey(key, &ent->k, map->key_size);
62 upb_value val = {tabent->val.val};
63 _upb_map_fromvalue(val, &ent->v, map->val_size);
64 return true;
65 }
66
_upb_sortedmap_nextext(_upb_mapsorter * s,_upb_sortedmap * sorted,const struct upb_Extension ** ext)67 UPB_INLINE bool _upb_sortedmap_nextext(_upb_mapsorter* s,
68 _upb_sortedmap* sorted,
69 const struct upb_Extension** ext) {
70 if (sorted->pos == sorted->end) return false;
71 *ext = (const struct upb_Extension*)s->entries[sorted->pos++];
72 return true;
73 }
74
_upb_mapsorter_popmap(_upb_mapsorter * s,_upb_sortedmap * sorted)75 UPB_INLINE void _upb_mapsorter_popmap(_upb_mapsorter* s,
76 _upb_sortedmap* sorted) {
77 s->size = sorted->start;
78 }
79
80 bool _upb_mapsorter_pushmap(_upb_mapsorter* s, upb_FieldType key_type,
81 const struct upb_Map* map, _upb_sortedmap* sorted);
82
83 bool _upb_mapsorter_pushexts(_upb_mapsorter* s,
84 const struct upb_Extension* exts, size_t count,
85 _upb_sortedmap* sorted);
86
87 #ifdef __cplusplus
88 } /* extern "C" */
89 #endif
90
91 #include "upb/port/undef.inc"
92
93 #endif /* UPB_MESSAGE_INTERNAL_MAP_SORTER_H_ */
94