Changeset 07eaeea in mainline
- Timestamp:
- 2018-07-05T21:41:25Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 3ae7827
- Parents:
- 65ee021
- git-author:
- Dzejrou <dzejrou@…> (2018-07-03 18:04:10)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:25)
- Location:
- uspace/lib/cpp/include/__bits/adt
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/__bits/adt/hash_table.hpp
r65ee021 r07eaeea 212 212 iterator erase(const_iterator it) 213 213 { 214 if (it == cend()) 215 return end(); 216 214 217 auto node = it.node(); 215 218 auto idx = it.idx(); … … 234 237 delete node; 235 238 236 return res; 239 if (empty()) 240 return end(); 241 else 242 return res; 237 243 } 238 244 … … 282 288 current = current->next; 283 289 } 284 while (current != head);290 while (current && current != head); 285 291 286 292 return end(); -
uspace/lib/cpp/include/__bits/adt/hash_table_bucket.hpp
r65ee021 r07eaeea 92 92 delete tmp; 93 93 } 94 while (current != head);94 while (current && current != head); 95 95 96 96 head = nullptr; -
uspace/lib/cpp/include/__bits/adt/hash_table_policies.hpp
r65ee021 r07eaeea 47 47 { 48 48 auto idx = table.get_bucket_idx_(key); 49 return make_tuple(50 &table.table_[idx],51 table.table_[idx].head,52 idx53 );54 }55 56 template<class Table, class Key>57 static typename Table::size_type erase(Table& table, const Key& key)58 {59 auto idx = table.get_bucket_idx_(key);60 49 auto head = table.table_[idx].head; 61 auto current = head;62 63 if (!current)64 return 0;65 66 do67 {68 if (table.keys_equal(key, current->value))69 {70 --table.size_;71 72 if (current == head)73 {74 if (current->next != head)75 table.table_[idx].head = current->next;76 else77 table.table_[idx].head = nullptr;78 }79 80 current->unlink();81 delete current;82 83 return 1;84 }85 else86 current = current->next;87 }88 while (current != head);89 90 return 0;91 }92 93 template<class Table, class Key>94 static pair<95 typename Table::iterator,96 typename Table::iterator97 > equal_range(Table& table, const Key& key)98 {99 auto it = table.find(key);100 return make_pair(it, ++it);101 }102 103 template<class Table, class Key>104 static pair<105 typename Table::const_iterator,106 typename Table::const_iterator107 > equal_range_const(const Table& table, const Key& key)108 { // Note: We cannot overload by return type, so we use a different name.109 auto it = table.find(key);110 return make_pair(it, ++it);111 }112 113 /**114 * Note: We have to duplicate code for emplace, insert(const&)115 * and insert(&&) here, because the node (which makes distinction116 * between the arguments) is only created if the value isn't117 * in the table already.118 */119 120 template<class Table, class... Args>121 static pair<122 typename Table::iterator, bool123 > emplace(Table& table, Args&&... args)124 {125 using value_type = typename Table::value_type;126 using node_type = typename Table::node_type;127 using iterator = typename Table::iterator;128 129 table.increment_size();130 131 auto val = value_type{forward<Args>(args)...};132 const auto& key = table.get_key(val);133 auto [bucket, target, idx] = table.find_insertion_spot(key);134 135 if (!bucket)136 return make_pair(table.end(), false);137 138 if (target && table.keys_equal(key, target->value))139 {140 table.decrement_size();141 142 return make_pair(143 iterator{144 table.table(), idx, table.bucket_count(),145 target146 },147 false148 );149 }150 else151 {152 auto node = new node_type{move(val)};153 bucket->prepend(node);154 155 return make_pair(iterator{156 table.table(), idx,157 table.bucket_count(),158 node159 }, true);160 }161 }162 163 template<class Table, class Value>164 static pair<165 typename Table::iterator, bool166 > insert(Table& table, const Value& val)167 {168 using node_type = typename Table::node_type;169 using iterator = typename Table::iterator;170 171 table.increment_size();172 173 const auto& key = table.get_key(val);174 auto [bucket, target, idx] = table.find_insertion_spot(key);175 176 if (!bucket)177 return make_pair(table.end(), false);178 179 if (target && table.keys_equal(key, target->value))180 {181 table.decrement_size();182 183 return make_pair(184 iterator{185 table.table(), idx, table.bucket_count(),186 target187 },188 false189 );190 }191 else192 {193 auto node = new node_type{val};194 bucket->prepend(node);195 196 return make_pair(iterator{197 table.table(), idx,198 table.bucket_count(),199 node200 }, true);201 }202 }203 204 template<class Table, class Value>205 static pair<206 typename Table::iterator, bool207 > insert(Table& table, Value&& val)208 {209 using value_type = typename Table::value_type;210 using node_type = typename Table::node_type;211 using iterator = typename Table::iterator;212 213 table.increment_size();214 215 const auto& key = table.get_key(val);216 auto [bucket, target, idx] = table.find_insertion_spot(key);217 218 if (!bucket)219 return make_pair(table.end(), false);220 221 if (target && table.keys_equal(key, target->value))222 {223 table.decrement_size();224 225 return make_pair(226 iterator{227 table.table(), idx, table.bucket_count(),228 target229 },230 false231 );232 }233 else234 {235 auto node = new node_type{forward<value_type>(val)};236 bucket->prepend(node);237 238 return make_pair(iterator{239 table.table(), idx,240 table.bucket_count(),241 node242 }, true);243 }244 }245 };246 247 struct hash_multi_policy248 {249 template<class Table, class Key>250 static typename Table::size_type count(const Table& table, const Key& key)251 {252 auto head = table.table_[table.get_bucket_idx_(key)].head;253 if (!head)254 return 0;255 256 auto current = head;257 typename Table::size_type res = 0;258 do259 {260 if (table.keys_equal(key, current->value))261 ++res;262 263 current = current->next;264 }265 while (current != head);266 267 return res;268 }269 270 template<class Table, class Key>271 static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)272 {273 auto idx = table.get_bucket_idx_(key);274 auto head = table.table_[idx].head;275 50 276 51 if (head) 277 { 52 { // Check if the key is present. 278 53 auto current = head; 279 54 do … … 289 64 290 65 current = current->next; 291 } while (current != head);66 } while (current && current != head); 292 67 } 293 68 … … 305 80 auto head = table.table_[idx].head; 306 81 auto current = head; 82 83 if (!current) 84 return 0; 85 86 do 87 { 88 if (table.keys_equal(key, current->value)) 89 { 90 --table.size_; 91 92 if (current == head) 93 { 94 if (current->next != head) 95 table.table_[idx].head = current->next; 96 else 97 table.table_[idx].head = nullptr; 98 } 99 100 current->unlink(); 101 delete current; 102 103 return 1; 104 } 105 else 106 current = current->next; 107 } 108 while (current && current != head); 109 110 return 0; 111 } 112 113 template<class Table, class Key> 114 static pair< 115 typename Table::iterator, 116 typename Table::iterator 117 > equal_range(Table& table, const Key& key) 118 { 119 auto it = table.find(key); 120 return make_pair(it, ++it); 121 } 122 123 template<class Table, class Key> 124 static pair< 125 typename Table::const_iterator, 126 typename Table::const_iterator 127 > equal_range_const(const Table& table, const Key& key) 128 { // Note: We cannot overload by return type, so we use a different name. 129 auto it = table.find(key); 130 return make_pair(it, ++it); 131 } 132 133 /** 134 * Note: We have to duplicate code for emplace, insert(const&) 135 * and insert(&&) here, because the node (which makes distinction 136 * between the arguments) is only created if the value isn't 137 * in the table already. 138 */ 139 140 template<class Table, class... Args> 141 static pair< 142 typename Table::iterator, bool 143 > emplace(Table& table, Args&&... args) 144 { 145 using value_type = typename Table::value_type; 146 using node_type = typename Table::node_type; 147 using iterator = typename Table::iterator; 148 149 table.increment_size(); 150 151 auto val = value_type{forward<Args>(args)...}; 152 const auto& key = table.get_key(val); 153 auto [bucket, target, idx] = table.find_insertion_spot(key); 154 155 if (!bucket) 156 return make_pair(table.end(), false); 157 158 if (target && table.keys_equal(key, target->value)) 159 { 160 table.decrement_size(); 161 162 return make_pair( 163 iterator{ 164 table.table(), idx, table.bucket_count(), 165 target 166 }, 167 false 168 ); 169 } 170 else 171 { 172 auto node = new node_type{move(val)}; 173 bucket->prepend(node); 174 175 return make_pair(iterator{ 176 table.table(), idx, 177 table.bucket_count(), 178 node 179 }, true); 180 } 181 } 182 183 template<class Table, class Value> 184 static pair< 185 typename Table::iterator, bool 186 > insert(Table& table, const Value& val) 187 { 188 using node_type = typename Table::node_type; 189 using iterator = typename Table::iterator; 190 191 table.increment_size(); 192 193 const auto& key = table.get_key(val); 194 auto [bucket, target, idx] = table.find_insertion_spot(key); 195 196 if (!bucket) 197 return make_pair(table.end(), false); 198 199 if (target && table.keys_equal(key, target->value)) 200 { 201 table.decrement_size(); 202 203 return make_pair( 204 iterator{ 205 table.table(), idx, table.bucket_count(), 206 target 207 }, 208 false 209 ); 210 } 211 else 212 { 213 auto node = new node_type{val}; 214 bucket->prepend(node); 215 216 return make_pair(iterator{ 217 table.table(), idx, 218 table.bucket_count(), 219 node 220 }, true); 221 } 222 } 223 224 template<class Table, class Value> 225 static pair< 226 typename Table::iterator, bool 227 > insert(Table& table, Value&& val) 228 { 229 using value_type = typename Table::value_type; 230 using node_type = typename Table::node_type; 231 using iterator = typename Table::iterator; 232 233 table.increment_size(); 234 235 const auto& key = table.get_key(val); 236 auto [bucket, target, idx] = table.find_insertion_spot(key); 237 238 if (!bucket) 239 return make_pair(table.end(), false); 240 241 if (target && table.keys_equal(key, target->value)) 242 { 243 table.decrement_size(); 244 245 return make_pair( 246 iterator{ 247 table.table(), idx, table.bucket_count(), 248 target 249 }, 250 false 251 ); 252 } 253 else 254 { 255 auto node = new node_type{forward<value_type>(val)}; 256 bucket->prepend(node); 257 258 return make_pair(iterator{ 259 table.table(), idx, 260 table.bucket_count(), 261 node 262 }, true); 263 } 264 } 265 }; 266 267 struct hash_multi_policy 268 { 269 template<class Table, class Key> 270 static typename Table::size_type count(const Table& table, const Key& key) 271 { 272 auto head = table.table_[table.get_bucket_idx_(key)].head; 273 if (!head) 274 return 0; 275 276 auto current = head; 277 typename Table::size_type res = 0; 278 do 279 { 280 if (table.keys_equal(key, current->value)) 281 ++res; 282 283 current = current->next; 284 } 285 while (current && current != head); 286 287 return res; 288 } 289 290 template<class Table, class Key> 291 static typename Table::place_type find_insertion_spot(const Table& table, const Key& key) 292 { 293 auto idx = table.get_bucket_idx_(key); 294 auto head = table.table_[idx].head; 295 296 if (head) 297 { 298 auto current = head; 299 do 300 { 301 if (table.keys_equal(key, current->value)) 302 { 303 return make_tuple( 304 &table.table_[idx], 305 current, 306 idx 307 ); 308 } 309 310 current = current->next; 311 } while (current && current != head); 312 } 313 314 return make_tuple( 315 &table.table_[idx], 316 table.table_[idx].head, 317 idx 318 ); 319 } 320 321 template<class Table, class Key> 322 static typename Table::size_type erase(Table& table, const Key& key) 323 { 324 auto idx = table.get_bucket_idx_(key); 325 auto head = table.table_[idx].head; 326 auto current = head; 307 327 table.table_[idx].head = nullptr; 328 decltype(head) last = nullptr; 308 329 309 330 if (!current) … … 321 342 auto tmp = current; 322 343 current = current->next; 323 344 tmp->unlink(); 345 346 --table.size_; 324 347 if (!table.keys_equal(key, tmp->value)) 325 table.table_[idx].append(tmp); 348 { 349 if (!last) 350 table.table_[idx].head = tmp; 351 else 352 last->append(tmp); 353 last = tmp; 354 } 326 355 else 327 356 { 328 357 ++res; 329 --table.size_;330 358 331 359 delete tmp; 332 360 } 333 361 } 334 while (current != head);362 while (current && current != head); 335 363 336 364 return res; … … 351 379 { 352 380 ++last; 353 } while ( table.keys_equal(key, *last));381 } while (last != table.end() && table.keys_equal(key, *last)); 354 382 355 383 return make_pair(first, last); … … 370 398 { 371 399 ++last; 372 } while ( table.keys_equal(key, *last));400 } while (last != table.end() && table.keys_equal(key, *last)); 373 401 374 402 return make_pair(first, last); … … 417 445 418 446 if (!bucket) 419 table.end();447 return table.end(); 420 448 421 449 if (target && table.keys_equal(key, target->value)) -
uspace/lib/cpp/include/__bits/adt/list_node.hpp
r65ee021 r07eaeea 64 64 void append(list_node* node) 65 65 { 66 if (!node) 67 return; 68 66 69 node->next = next; 67 70 node->prev = this; … … 72 75 void prepend(list_node* node) 73 76 { 77 if (!node) 78 return; 79 74 80 node->next = this; 75 81 node->prev = prev;
Note:
See TracChangeset
for help on using the changeset viewer.