1 #ifndef OSMIUM_RELATIONS_RELATIONS_DATABASE_HPP 2 #define OSMIUM_RELATIONS_RELATIONS_DATABASE_HPP 3 4 /* 5 6 This file is part of Osmium (https://osmcode.org/libosmium). 7 8 Copyright 2013-2021 Jochen Topf <jochen@topf.org> and others (see README). 9 10 Boost Software License - Version 1.0 - August 17th, 2003 11 12 Permission is hereby granted, free of charge, to any person or organization 13 obtaining a copy of the software and accompanying documentation covered by 14 this license (the "Software") to use, reproduce, display, distribute, 15 execute, and transmit the Software, and to prepare derivative works of the 16 Software, and to permit third-parties to whom the Software is furnished to 17 do so, all subject to the following: 18 19 The copyright notices in the Software and this entire statement, including 20 the above license grant, this restriction and the following disclaimer, 21 must be included in all copies of the Software, in whole or in part, and 22 all derivative works of the Software, unless such copies or derivative 23 works are solely in the form of machine-executable object code generated by 24 a source language processor. 25 26 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 27 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 28 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 29 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 30 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 31 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 32 DEALINGS IN THE SOFTWARE. 33 34 */ 35 36 #include <osmium/osm/relation.hpp> 37 #include <osmium/storage/item_stash.hpp> 38 39 #include <algorithm> 40 #include <cassert> 41 #include <cstddef> 42 #include <utility> 43 #include <vector> 44 45 namespace osmium { 46 47 namespace relations { 48 49 class RelationHandle; 50 51 /** 52 * The RelationsDatabase is used for bringing relations and their 53 * members together. It stores the relations in memory and keeps 54 * track of how many members are needed to "complete" the relation. 55 * It is intended to work together with the MembersDatabase template 56 * class and usually used by relations manager classes. 57 * 58 * To access relations stored in the database a RelationHandle is 59 * used. It is returned from the add() function. The handle is used 60 * for all operations on the database contents, such as accessing 61 * the stored relation, incrementing the member count or removing a 62 * relation from the database. 63 * 64 * From the handle a "position" can be accessed, which, together with 65 * the database object, can be turned into a handle again. The position 66 * alone is smaller than the handle, so it can be stored elsewhere more 67 * efficiently. Specifically this is used in the MembersDatabase. 68 * 69 * @code 70 * osmium::ItemStash stash; 71 * osmium::relations::RelationsDatabase db{stash}; 72 * auto handle = db.add(relation); 73 * auto pos = handle.pos(); 74 * auto second_handle = db[pos]; 75 * @endcode 76 * 77 * Now the `handle` and `second_handle` refer to the same relation. 78 * 79 * See the RelationHandle for information about what you can do with 80 * it. 81 */ 82 class RelationsDatabase { 83 84 friend class RelationHandle; 85 86 struct element { 87 88 /// A handle to the relation in the ItemStash. 89 osmium::ItemStash::handle_type handle; 90 91 /** 92 * The number of members still needed before the relation is 93 * complete. This will be set to the number of members we are 94 * interested in (which can be all members of a relation or 95 * a subset of them) and then count down for every member we 96 * find. When it is 0, the relation is complete. 97 */ 98 std::size_t members; 99 100 }; // struct element 101 102 osmium::ItemStash& m_stash; 103 std::vector<element> m_elements; 104 get_relation(std::size_t pos)105 osmium::Relation& get_relation(std::size_t pos) { 106 assert(pos < m_elements.size()); 107 return m_stash.get<osmium::Relation>(m_elements[pos].handle); 108 } 109 110 /** 111 * Access the number of members of the entry at the specified 112 * position. This returns a reference so it can be changed. 113 */ members(std::size_t pos)114 std::size_t& members(std::size_t pos) noexcept { 115 return m_elements[pos].members; 116 } 117 remove(std::size_t pos)118 void remove(std::size_t pos) { 119 auto& elem = m_elements[pos]; 120 m_stash.remove_item(elem.handle); 121 elem = element{osmium::ItemStash::handle_type{}, 0}; 122 } 123 124 public: 125 126 /** 127 * Construct a RelationsDatabase. 128 * 129 * @param stash Reference to an ItemStash object. All relations 130 * will be stored in this stash. It must be available 131 * until the RelationsDatabase is destroyed. 132 */ RelationsDatabase(osmium::ItemStash & stash)133 explicit RelationsDatabase(osmium::ItemStash& stash) : 134 m_stash(stash) { 135 } 136 137 /** 138 * Return an estimate of the number of bytes currently needed for 139 * the RelationsDatabase. This does NOT include the memory used 140 * in the stash. Used for debugging. 141 * 142 * Complexity: Constant. 143 */ used_memory() const144 std::size_t used_memory() const noexcept { 145 return sizeof(element) * m_elements.capacity() + 146 sizeof(RelationsDatabase); 147 } 148 149 /** 150 * The number of relations stored in the database. Includes 151 * relations marked as removed. 152 * 153 * Complexity: Constant. 154 */ size() const155 std::size_t size() const noexcept { 156 return m_elements.size(); 157 } 158 159 /** 160 * Insert a relation into the database. The relation is copied 161 * into the stash. 162 * 163 * Complexity: Amortized constant. 164 * 165 * @param relation The relation to be copied into the database. 166 * @returns A handle to the relation. 167 */ 168 RelationHandle add(const osmium::Relation& relation); 169 170 /** 171 * Return a handle to the relation at the specified position in 172 * the database. 173 * 174 * Complexity: Constant. 175 */ 176 RelationHandle operator[](std::size_t pos) noexcept; 177 178 /** 179 * Return the number of non-removed relations in the database. 180 * 181 * Complexity: Linear in the number of relations (as returned 182 * by size()). 183 */ count_relations() const184 std::size_t count_relations() const noexcept { 185 return std::count_if(m_elements.cbegin(), m_elements.cend(), [&](const element& elem) { 186 return elem.handle.valid(); 187 }); 188 } 189 190 /** 191 * Iterate over all (not-removed) relations in the database. 192 * 193 * @tparam TFunc Function with type void(const RelationHandle&). 194 * @param func Callback function which will be called for every 195 * not-removed relation with a RelationHandle. 196 */ 197 template <typename TFunc> 198 void for_each_relation(TFunc&& func); 199 200 }; // RelationsDatabase 201 202 /** 203 * A RelationHandle is used to access elements in a RelationsDatabase. 204 * 205 * RelationHandles can not be created by user code, they are only 206 * given out by a RelationsDatabase object. 207 */ 208 class RelationHandle { 209 210 friend class RelationsDatabase; 211 212 RelationsDatabase* m_relation_database; 213 std::size_t m_pos; 214 RelationHandle(RelationsDatabase * relation_database,std::size_t pos)215 RelationHandle(RelationsDatabase* relation_database, std::size_t pos) : 216 m_relation_database(relation_database), 217 m_pos(pos) { 218 } 219 220 public: 221 222 /** 223 * The RelationsDatabase this handle refers to. 224 */ relation_database() const225 RelationsDatabase* relation_database() const noexcept { 226 return m_relation_database; 227 } 228 229 /** 230 * The position of the element in the RelationsDatabase. Use the 231 * RelationsDatabase::operator[] to get the handle back from this 232 * position: 233 * @code 234 * auto pos = handle.pos(); 235 * auto second_handle = relation_db[pos]; 236 * @endcode 237 */ pos() const238 std::size_t pos() const noexcept { 239 return m_pos; 240 } 241 242 /** 243 * Access the relation stored in the database. 244 */ operator *()245 Relation& operator*() { 246 return m_relation_database->get_relation(m_pos); 247 } 248 249 /** 250 * Access the relation stored in the database. 251 */ operator *() const252 const Relation& operator*() const { 253 return m_relation_database->get_relation(m_pos); 254 } 255 256 /** 257 * Call a function on the relation stored in the database. 258 */ operator ->()259 Relation* operator->() { 260 return &m_relation_database->get_relation(m_pos); 261 } 262 263 /** 264 * Call a function on the relation stored in the database. 265 */ operator ->() const266 const Relation* operator->() const { 267 return &m_relation_database->get_relation(m_pos); 268 } 269 270 /** 271 * Remove the relation referred to by this handle from the database. 272 * All handles referring to this database element become invalid. 273 */ remove()274 void remove() { 275 m_relation_database->remove(pos()); 276 } 277 278 /** 279 * Set the number of relation members that we want to track. 280 */ set_members(std::size_t value)281 void set_members(std::size_t value) noexcept { 282 m_relation_database->members(m_pos) = value; 283 } 284 285 /** 286 * Increment the number of relation members that we want to track. 287 */ increment_members()288 void increment_members() noexcept { 289 ++(m_relation_database->members(m_pos)); 290 } 291 292 /** 293 * Decrement the number of relation members that we want to track. 294 * 295 * @pre @code has_all_members() == false @endcode 296 */ decrement_members()297 void decrement_members() noexcept { 298 assert(m_relation_database->members(m_pos) > 0); 299 --(m_relation_database->members(m_pos)); 300 } 301 302 /** 303 * Do we have all members? This is true if the number of tracked 304 * members is zero. 305 */ has_all_members() const306 bool has_all_members() const noexcept { 307 return m_relation_database->members(m_pos) == 0; 308 } 309 310 }; // class RelationHandle 311 operator [](std::size_t pos)312 inline RelationHandle RelationsDatabase::operator[](std::size_t pos) noexcept { 313 assert(pos < m_elements.size()); 314 return {this, pos}; 315 } 316 add(const osmium::Relation & relation)317 inline RelationHandle RelationsDatabase::add(const osmium::Relation& relation) { 318 m_elements.push_back(element{m_stash.add_item(relation), 0}); 319 return {this, m_elements.size() - 1}; 320 } 321 322 template <typename TFunc> for_each_relation(TFunc && func)323 void RelationsDatabase::for_each_relation(TFunc&& func) { 324 for (std::size_t pos = 0; pos < m_elements.size(); ++pos) { 325 if (m_elements[pos].handle.valid()) { 326 func(RelationHandle{this, pos}); 327 } 328 } 329 } 330 331 } // namespace relations 332 333 } // namespace osmium 334 335 #endif // OSMIUM_RELATIONS_RELATIONS_DATABASE_HPP 336