]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | // This source code is licensed under the BSD-style license found in the | |
3 | // LICENSE file in the root directory of this source tree. An additional grant | |
4 | // of patent rights can be found in the PATENTS file in the same directory. | |
5 | ||
6 | #pragma once | |
7 | #ifndef ROCKSDB_LITE | |
8 | ||
9 | #include <string> | |
10 | #include <vector> | |
11 | ||
12 | #include "rocksdb/db.h" | |
13 | #include "rocksdb/slice.h" | |
14 | #include "rocksdb/utilities/stackable_db.h" | |
15 | ||
16 | namespace rocksdb { | |
17 | namespace spatial { | |
18 | ||
19 | // NOTE: SpatialDB is experimental and we might change its API without warning. | |
20 | // Please talk to us before developing against SpatialDB API. | |
21 | // | |
22 | // SpatialDB is a support for spatial indexes built on top of RocksDB. | |
23 | // When creating a new SpatialDB, clients specifies a list of spatial indexes to | |
24 | // build on their data. Each spatial index is defined by the area and | |
25 | // granularity. If you're storing map data, different spatial index | |
26 | // granularities can be used for different zoom levels. | |
27 | // | |
28 | // Each element inserted into SpatialDB has: | |
29 | // * a bounding box, which determines how will the element be indexed | |
30 | // * string blob, which will usually be WKB representation of the polygon | |
31 | // (http://en.wikipedia.org/wiki/Well-known_text) | |
32 | // * feature set, which is a map of key-value pairs, where value can be null, | |
33 | // int, double, bool, string | |
34 | // * a list of indexes to insert the element in | |
35 | // | |
36 | // Each query is executed on a single spatial index. Query guarantees that it | |
37 | // will return all elements intersecting the specified bounding box, but it | |
38 | // might also return some extra non-intersecting elements. | |
39 | ||
40 | // Variant is a class that can be many things: null, bool, int, double or string | |
41 | // It is used to store different value types in FeatureSet (see below) | |
42 | struct Variant { | |
43 | // Don't change the values here, they are persisted on disk | |
44 | enum Type { | |
45 | kNull = 0x0, | |
46 | kBool = 0x1, | |
47 | kInt = 0x2, | |
48 | kDouble = 0x3, | |
49 | kString = 0x4, | |
50 | }; | |
51 | ||
52 | Variant() : type_(kNull) {} | |
53 | /* implicit */ Variant(bool b) : type_(kBool) { data_.b = b; } | |
54 | /* implicit */ Variant(uint64_t i) : type_(kInt) { data_.i = i; } | |
55 | /* implicit */ Variant(double d) : type_(kDouble) { data_.d = d; } | |
56 | /* implicit */ Variant(const std::string& s) : type_(kString) { | |
57 | new (&data_.s) std::string(s); | |
58 | } | |
59 | ||
60 | Variant(const Variant& v) : type_(v.type_) { Init(v, data_); } | |
61 | ||
62 | Variant& operator=(const Variant& v); | |
63 | ||
64 | Variant(Variant&& rhs) : type_(kNull) { *this = std::move(rhs); } | |
65 | ||
66 | Variant& operator=(Variant&& v); | |
67 | ||
68 | ~Variant() { Destroy(type_, data_); } | |
69 | ||
70 | Type type() const { return type_; } | |
71 | bool get_bool() const { return data_.b; } | |
72 | uint64_t get_int() const { return data_.i; } | |
73 | double get_double() const { return data_.d; } | |
74 | const std::string& get_string() const { return *GetStringPtr(data_); } | |
75 | ||
76 | bool operator==(const Variant& other) const; | |
77 | bool operator!=(const Variant& other) const { return !(*this == other); } | |
78 | ||
79 | private: | |
80 | Type type_; | |
81 | ||
82 | union Data { | |
83 | bool b; | |
84 | uint64_t i; | |
85 | double d; | |
86 | // Current version of MS compiler not C++11 compliant so can not put | |
87 | // std::string | |
88 | // however, even then we still need the rest of the maintenance. | |
89 | char s[sizeof(std::string)]; | |
90 | } data_; | |
91 | ||
92 | // Avoid type_punned aliasing problem | |
93 | static std::string* GetStringPtr(Data& d) { | |
94 | void* p = d.s; | |
95 | return reinterpret_cast<std::string*>(p); | |
96 | } | |
97 | ||
98 | static const std::string* GetStringPtr(const Data& d) { | |
99 | const void* p = d.s; | |
100 | return reinterpret_cast<const std::string*>(p); | |
101 | } | |
102 | ||
103 | static void Init(const Variant&, Data&); | |
104 | ||
105 | static void Destroy(Type t, Data& d) { | |
106 | if (t == kString) { | |
107 | using std::string; | |
108 | GetStringPtr(d)->~string(); | |
109 | } | |
110 | } | |
111 | }; | |
112 | ||
113 | // FeatureSet is a map of key-value pairs. One feature set is associated with | |
114 | // each element in SpatialDB. It can be used to add rich data about the element. | |
115 | class FeatureSet { | |
116 | private: | |
117 | typedef std::unordered_map<std::string, Variant> map; | |
118 | ||
119 | public: | |
120 | class iterator { | |
121 | public: | |
122 | /* implicit */ iterator(const map::const_iterator itr) : itr_(itr) {} | |
123 | iterator& operator++() { | |
124 | ++itr_; | |
125 | return *this; | |
126 | } | |
127 | bool operator!=(const iterator& other) { return itr_ != other.itr_; } | |
128 | bool operator==(const iterator& other) { return itr_ == other.itr_; } | |
129 | map::value_type operator*() { return *itr_; } | |
130 | ||
131 | private: | |
132 | map::const_iterator itr_; | |
133 | }; | |
134 | FeatureSet() = default; | |
135 | ||
136 | FeatureSet* Set(const std::string& key, const Variant& value); | |
137 | bool Contains(const std::string& key) const; | |
138 | // REQUIRES: Contains(key) | |
139 | const Variant& Get(const std::string& key) const; | |
140 | iterator Find(const std::string& key) const; | |
141 | ||
142 | iterator begin() const { return map_.begin(); } | |
143 | iterator end() const { return map_.end(); } | |
144 | ||
145 | void Clear(); | |
146 | size_t Size() const { return map_.size(); } | |
147 | ||
148 | void Serialize(std::string* output) const; | |
149 | // REQUIRED: empty FeatureSet | |
150 | bool Deserialize(const Slice& input); | |
151 | ||
152 | std::string DebugString() const; | |
153 | ||
154 | private: | |
155 | map map_; | |
156 | }; | |
157 | ||
158 | // BoundingBox is a helper structure for defining rectangles representing | |
159 | // bounding boxes of spatial elements. | |
160 | template <typename T> | |
161 | struct BoundingBox { | |
162 | T min_x, min_y, max_x, max_y; | |
163 | BoundingBox() = default; | |
164 | BoundingBox(T _min_x, T _min_y, T _max_x, T _max_y) | |
165 | : min_x(_min_x), min_y(_min_y), max_x(_max_x), max_y(_max_y) {} | |
166 | ||
167 | bool Intersects(const BoundingBox<T>& a) const { | |
168 | return !(min_x > a.max_x || min_y > a.max_y || a.min_x > max_x || | |
169 | a.min_y > max_y); | |
170 | } | |
171 | }; | |
172 | ||
173 | struct SpatialDBOptions { | |
174 | uint64_t cache_size = 1 * 1024 * 1024 * 1024LL; // 1GB | |
175 | int num_threads = 16; | |
176 | bool bulk_load = true; | |
177 | }; | |
178 | ||
179 | // Cursor is used to return data from the query to the client. To get all the | |
180 | // data from the query, just call Next() while Valid() is true | |
181 | class Cursor { | |
182 | public: | |
183 | Cursor() = default; | |
184 | virtual ~Cursor() {} | |
185 | ||
186 | virtual bool Valid() const = 0; | |
187 | // REQUIRES: Valid() | |
188 | virtual void Next() = 0; | |
189 | ||
190 | // Lifetime of the underlying storage until the next call to Next() | |
191 | // REQUIRES: Valid() | |
192 | virtual const Slice blob() = 0; | |
193 | // Lifetime of the underlying storage until the next call to Next() | |
194 | // REQUIRES: Valid() | |
195 | virtual const FeatureSet& feature_set() = 0; | |
196 | ||
197 | virtual Status status() const = 0; | |
198 | ||
199 | private: | |
200 | // No copying allowed | |
201 | Cursor(const Cursor&); | |
202 | void operator=(const Cursor&); | |
203 | }; | |
204 | ||
205 | // SpatialIndexOptions defines a spatial index that will be built on the data | |
206 | struct SpatialIndexOptions { | |
207 | // Spatial indexes are referenced by names | |
208 | std::string name; | |
209 | // An area that is indexed. If the element is not intersecting with spatial | |
210 | // index's bbox, it will not be inserted into the index | |
211 | BoundingBox<double> bbox; | |
212 | // tile_bits control the granularity of the spatial index. Each dimension of | |
213 | // the bbox will be split into (1 << tile_bits) tiles, so there will be a | |
214 | // total of (1 << tile_bits)^2 tiles. It is recommended to configure a size of | |
215 | // each tile to be approximately the size of the query on that spatial index | |
216 | uint32_t tile_bits; | |
217 | SpatialIndexOptions() {} | |
218 | SpatialIndexOptions(const std::string& _name, | |
219 | const BoundingBox<double>& _bbox, uint32_t _tile_bits) | |
220 | : name(_name), bbox(_bbox), tile_bits(_tile_bits) {} | |
221 | }; | |
222 | ||
223 | class SpatialDB : public StackableDB { | |
224 | public: | |
225 | // Creates the SpatialDB with specified list of indexes. | |
226 | // REQUIRED: db doesn't exist | |
227 | static Status Create(const SpatialDBOptions& options, const std::string& name, | |
228 | const std::vector<SpatialIndexOptions>& spatial_indexes); | |
229 | ||
230 | // Open the existing SpatialDB. The resulting db object will be returned | |
231 | // through db parameter. | |
232 | // REQUIRED: db was created using SpatialDB::Create | |
233 | static Status Open(const SpatialDBOptions& options, const std::string& name, | |
234 | SpatialDB** db, bool read_only = false); | |
235 | ||
236 | explicit SpatialDB(DB* db) : StackableDB(db) {} | |
237 | ||
238 | // Insert the element into the DB. Element will be inserted into specified | |
239 | // spatial_indexes, based on specified bbox. | |
240 | // REQUIRES: spatial_indexes.size() > 0 | |
241 | virtual Status Insert(const WriteOptions& write_options, | |
242 | const BoundingBox<double>& bbox, const Slice& blob, | |
243 | const FeatureSet& feature_set, | |
244 | const std::vector<std::string>& spatial_indexes) = 0; | |
245 | ||
246 | // Calling Compact() after inserting a bunch of elements should speed up | |
247 | // reading. This is especially useful if you use SpatialDBOptions::bulk_load | |
248 | // Num threads determines how many threads we'll use for compactions. Setting | |
249 | // this to bigger number will use more IO and CPU, but finish faster | |
250 | virtual Status Compact(int num_threads = 1) = 0; | |
251 | ||
252 | // Query the specified spatial_index. Query will return all elements that | |
253 | // intersect bbox, but it may also return some extra elements. | |
254 | virtual Cursor* Query(const ReadOptions& read_options, | |
255 | const BoundingBox<double>& bbox, | |
256 | const std::string& spatial_index) = 0; | |
257 | }; | |
258 | ||
259 | } // namespace spatial | |
260 | } // namespace rocksdb | |
261 | #endif // ROCKSDB_LITE |