message/internal/map_sorter.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 // EVERYTHING BELOW THIS LINE IS INTERNAL - DO NOT USE /////////////////////////
0009
0010 #ifndef UPB_MESSAGE_INTERNAL_MAP_SORTER_H_
0011 #define UPB_MESSAGE_INTERNAL_MAP_SORTER_H_
0012
0013 #include <stdlib.h>
0014
0015 #include "upb/base/descriptor_constants.h"
0016 #include "upb/base/string_view.h"
0017 #include "upb/mem/alloc.h"
0018 #include "upb/message/internal/extension.h"
0019 #include "upb/message/internal/map.h"
0020 #include "upb/message/internal/map_entry.h"
0021
0022 // Must be last.
0023 #include "upb/port/def.inc"
0024
0025 #ifdef __cplusplus
0026 extern "C" {
0027 #endif
0028
0029 // _upb_mapsorter sorts maps and provides ordered iteration over the entries.
0030 // Since maps can be recursive (map values can be messages which contain other
0031 // maps), _upb_mapsorter can contain a stack of maps.
0032
0033 typedef struct {
0034   void const** entries;
0035   int size;
0036   int cap;
0037 } _upb_mapsorter;
0038
0039 typedef struct {
0040   int start;
0041   int pos;
0042   int end;
0043 } _upb_sortedmap;
0044
0045 UPB_INLINE void _upb_mapsorter_init(_upb_mapsorter* s) {
0046   s->entries = NULL;
0047   s->size = 0;
0048   s->cap = 0;
0049 }
0050
0051 UPB_INLINE void _upb_mapsorter_destroy(_upb_mapsorter* s) {
0052   if (s->entries) upb_gfree(s->entries);
0053 }
0054
0055 UPB_INLINE bool _upb_sortedmap_next(_upb_mapsorter* s,
0056                                     const struct upb_Map* map,
0057                                     _upb_sortedmap* sorted, upb_MapEntry* ent) {
0058   if (sorted->pos == sorted->end) return false;
0059   const upb_tabent* tabent = (const upb_tabent*)s->entries[sorted->pos++];
0060   upb_StringView key = upb_tabstrview(tabent->key);
0061   _upb_map_fromkey(key, &ent->k, map->key_size);
0062   upb_value val = {tabent->val.val};
0063   _upb_map_fromvalue(val, &ent->v, map->val_size);
0064   return true;
0065 }
0066
0067 UPB_INLINE bool _upb_sortedmap_nextext(_upb_mapsorter* s,
0068                                        _upb_sortedmap* sorted,
0069                                        const upb_Extension** ext) {
0070   if (sorted->pos == sorted->end) return false;
0071   *ext = (const upb_Extension*)s->entries[sorted->pos++];
0072   return true;
0073 }
0074
0075 UPB_INLINE void _upb_mapsorter_popmap(_upb_mapsorter* s,
0076                                       _upb_sortedmap* sorted) {
0077   s->size = sorted->start;
0078 }
0079
0080 bool _upb_mapsorter_pushmap(_upb_mapsorter* s, upb_FieldType key_type,
0081                             const struct upb_Map* map, _upb_sortedmap* sorted);
0082
0083 bool _upb_mapsorter_pushexts(_upb_mapsorter* s, const upb_Extension* exts,
0084                              size_t count, _upb_sortedmap* sorted);
0085
0086 #ifdef __cplusplus
0087 } /* extern "C" */
0088 #endif
0089
0090 #include "upb/port/undef.inc"
0091
0092 #endif /* UPB_MESSAGE_INTERNAL_MAP_SORTER_H_ */