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