1 // Copyright 2018 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15
16 // Author: ericv@google.com (Eric Veach)
17
18 #ifndef S2_ENCODED_S2POINT_VECTOR_H_
19 #define S2_ENCODED_S2POINT_VECTOR_H_
20
21 #include <atomic>
22 #include "absl/types/span.h"
23 #include "s2/encoded_string_vector.h"
24 #include "s2/encoded_uint_vector.h"
25 #include "s2/s2point.h"
26
27 namespace s2coding {
28
29 // Controls whether to optimize for speed or size when encoding points. (Note
30 // that encoding is always lossless, and that currently compact encodings are
31 // only possible when points have been snapped to S2CellId centers.)
32 enum class CodingHint : uint8 { FAST, COMPACT };
33
34 // Encodes a vector of S2Points in a format that can later be decoded as an
35 // EncodedS2PointVector.
36 //
37 // REQUIRES: "encoder" uses the default constructor, so that its buffer
38 // can be enlarged as necessary by calling Ensure(int).
39 void EncodeS2PointVector(absl::Span<const S2Point> points, CodingHint hint,
40 Encoder* encoder);
41
42 // This class represents an encoded vector of S2Points. Values are decoded
43 // only when they are accessed. This allows for very fast initialization and
44 // no additional memory use beyond the encoded data. The encoded data is not
45 // owned by this class; typically it points into a large contiguous buffer
46 // that contains other encoded data as well.
47 //
48 // This is one of several helper classes that allow complex data structures to
49 // be initialized from an encoded format in constant time and then decoded on
50 // demand. This can be a big performance advantage when only a small part of
51 // the data structure is actually used.
52 class EncodedS2PointVector {
53 public:
54 // Constructs an uninitialized object; requires Init() to be called.
EncodedS2PointVector()55 EncodedS2PointVector() {}
56
57 // Initializes the EncodedS2PointVector.
58 //
59 // REQUIRES: The Decoder data buffer must outlive this object.
60 bool Init(Decoder* decoder);
61
62 // Returns the size of the original vector.
63 size_t size() const;
64
65 // Returns the element at the given index.
66 S2Point operator[](int i) const;
67
68 // Decodes and returns the entire original vector.
69 std::vector<S2Point> Decode() const;
70
71 // TODO(ericv): Consider adding a method that returns an adjacent pair of
72 // points. This would save some decoding overhead.
73
74 private:
75 friend void EncodeS2PointVector(absl::Span<const S2Point>, CodingHint,
76 Encoder*);
77 friend void EncodeS2PointVectorFast(absl::Span<const S2Point>, Encoder*);
78 friend void EncodeS2PointVectorCompact(absl::Span<const S2Point>, Encoder*);
79
80 bool InitUncompressedFormat(Decoder* decoder);
81 bool InitCellIdsFormat(Decoder* decoder);
82 S2Point DecodeCellIdsFormat(int i) const;
83
84 // We use a tagged union to represent multiple formats, as opposed to an
85 // abstract base class or templating. This represents the best compromise
86 // between performance, space, and convenience. Note that the overhead of
87 // checking the tag is trivial and will typically be branch-predicted
88 // perfectly.
89 //
90 // TODO(ericv): Once additional formats have been implemented, consider
91 // using std::variant<> instead. It's unclear whether this would have
92 // better or worse performance than the current approach.
93
94 // dd: These structs are anonymous in the upstream S2 code; however,
95 // this generates CMD-check failure due to the [-Wnested-anon-types]
96 // (anonymous types declared in an anonymous union are an extension)
97 // The approach here just names the types.
98 struct CellIDStruct {
99 EncodedStringVector blocks;
100 uint64 base;
101 uint8 level;
102 bool have_exceptions;
103
104 // TODO(ericv): Use std::atomic_flag to cache the last point decoded in
105 // a thread-safe way. This reduces benchmark times for actual polygon
106 // operations (e.g. S2ClosestEdgeQuery) by about 15%.
107 };
108
109 struct UncompressedStruct {
110 const S2Point* points;
111 };
112
113 enum Format : uint8 {
114 UNCOMPRESSED = 0,
115 CELL_IDS = 1,
116 };
117 Format format_;
118 uint32 size_;
119 union {
120 struct UncompressedStruct uncompressed_;
121 struct CellIDStruct cell_ids_;
122 };
123 };
124
125
126 ////////////////// Implementation details follow ////////////////////
127
128
size()129 inline size_t EncodedS2PointVector::size() const {
130 return size_;
131 }
132
133 inline S2Point EncodedS2PointVector::operator[](int i) const {
134 switch (format_) {
135 case Format::UNCOMPRESSED:
136 return uncompressed_.points[i];
137
138 case Format::CELL_IDS:
139 return DecodeCellIdsFormat(i);
140
141 default:
142 S2_LOG(DFATAL) << "Unrecognized format";
143 return S2Point();
144 }
145 }
146
147 } // namespace s2coding
148
149 #endif // S2_ENCODED_S2POINT_VECTOR_H_
150