source: josm/trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java@ 17559

Last change on this file since 17559 was 17559, checked in by Don-vip, 3 years ago

fix #20587 - fix potential infinite loop in QuadBuckets toArray (patch by taylor.smock)
  • Property svn:eol-style set to native
File size: 18.5 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.osm;
3
4import java.util.ArrayList;
5import java.util.Arrays;
6import java.util.Collection;
7import java.util.Iterator;
8import java.util.LinkedHashSet;
9import java.util.List;
10import java.util.NoSuchElementException;
11import java.util.stream.IntStream;
12
13import org.openstreetmap.josm.data.IQuadBucketType;
14import org.openstreetmap.josm.data.coor.LatLon;
15import org.openstreetmap.josm.data.coor.QuadTiling;
16import org.openstreetmap.josm.tools.Logging;
17
18/**
19 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must
20 * be removed and re-added.
21 *
22 * This class is (no longer) thread safe.
23 * @param <T> type of object extending {@link IQuadBucketType}.
24 * @since 2165 ({@link IPrimitive} only), xxx for {@link IQuadBucketType}
25 */
26public class QuadBuckets<T extends IQuadBucketType> implements Collection<T> {
27 private static final boolean CONSISTENCY_TESTING = false;
28 private static final byte NW_INDEX = 1;
29 private static final byte NE_INDEX = 3;
30 private static final byte SE_INDEX = 2;
31 private static final byte SW_INDEX = 0;
32
33 static void abort(String s) {
34 throw new AssertionError(s);
35 }
36
37 private static final int MAX_OBJECTS_PER_NODE = 48;
38
39 static class QBLevel<T extends IQuadBucketType> extends BBox {
40 private final byte level;
41 private final byte index;
42 private final long quad;
43 private final QBLevel<T> parent;
44 private boolean isLeaf = true;
45
46 private List<T> content;
47 // child order by index is sw, nw, se, ne
48 private QBLevel<T> nw, ne, sw, se;
49
50 private QBLevel<T> getChild(byte index) {
51 switch (index) {
52 case NE_INDEX:
53 if (ne == null) {
54 ne = new QBLevel<>(this, index);
55 }
56 return ne;
57 case NW_INDEX:
58 if (nw == null) {
59 nw = new QBLevel<>(this, index);
60 }
61 return nw;
62 case SE_INDEX:
63 if (se == null) {
64 se = new QBLevel<>(this, index);
65 }
66 return se;
67 case SW_INDEX:
68 if (sw == null) {
69 sw = new QBLevel<>(this, index);
70 }
71 return sw;
72 default:
73 return null;
74 }
75 }
76
77 @SuppressWarnings("unchecked")
78 private QBLevel<T>[] getChildren() {
79 return new QBLevel[] {sw, nw, se, ne};
80 }
81
82 @Override
83 public String toString() {
84 return super.toString() + '[' + level + "]: ";
85 }
86
87 /**
88 * Constructor for root node
89 */
90 QBLevel() {
91 super(-180, 90, 180, -90);
92 level = 0;
93 index = 0;
94 quad = 0;
95 parent = null;
96 }
97
98 QBLevel(QBLevel<T> parent, byte index) {
99 this.parent = parent;
100 this.level = (byte) (parent.level + 1);
101 this.index = index;
102
103 int shift = (QuadTiling.NR_LEVELS - level) * 2;
104 long quadpart = (long) index << shift;
105 this.quad = parent.quad | quadpart;
106 LatLon bottomLeft = QuadTiling.tile2LatLon(this.quad);
107 xmin = bottomLeft.lon();
108 ymin = bottomLeft.lat();
109 xmax = xmin + parent.width() / 2;
110 ymax = ymin + parent.height() / 2;
111 }
112
113 QBLevel<T> findBucket(BBox bbox) {
114 if (!hasChildren())
115 return this;
116 else {
117 byte idx = bbox.getIndex(level);
118 if (idx == -1)
119 return this;
120 QBLevel<T> child = getChild(idx);
121 if (child == null)
122 return this;
123 return child.findBucket(bbox);
124 }
125 }
126
127 boolean removeContent(T o) {
128 // If two threads try to remove item at the same time from different buckets of this QBLevel,
129 // it might happen that one thread removes bucket but don't remove parent because it still sees
130 // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that
131 // changes made by threads will show up in children array too late, leading to QBLevel with all children
132 // set to null
133 if (content == null)
134 return false;
135 boolean ret = this.content.remove(o);
136 if (this.content.isEmpty()) {
137 this.content = null;
138 }
139 if (this.canRemove()) {
140 this.removeFromParent();
141 }
142 return ret;
143 }
144
145 /*
146 * There is a race between this and qb.nextContentNode().
147 * If nextContentNode() runs into this bucket, it may attempt to null out 'children' because it thinks this is a dead end.
148 */
149 void doSplit() {
150 List<T> tmpcontent = content;
151 content = null;
152
153 for (T o : tmpcontent) {
154 byte idx = o.getBBox().getIndex(level);
155 if (idx == -1) {
156 doAddContent(o);
157 } else {
158 QBLevel<T> child = getChild(idx);
159 if (child != null)
160 child.doAdd(o);
161 }
162 }
163 isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1)
164 }
165
166 boolean doAddContent(T o) {
167 // The split_lock will keep two concurrent calls from overwriting content
168 if (content == null) {
169 content = new ArrayList<>();
170 }
171 return content.add(o);
172 }
173
174 boolean matches(final T o, final BBox searchBbox) {
175 return o.getBBox().intersects(searchBbox);
176 }
177
178 private void searchContents(BBox searchBbox, List<T> result) {
179 /*
180 * It is possible that this was created in a split
181 * but never got any content populated.
182 */
183 if (content == null)
184 return;
185
186 for (T o : content) {
187 if (matches(o, searchBbox)) {
188 result.add(o);
189 }
190 }
191 }
192
193 /*
194 * This is stupid. I tried to have a QBLeaf and QBBranch
195 * class descending from a QBLevel. It's more than twice
196 * as slow. So, this throws OO out the window, but it
197 * is fast. Runtime type determination must be slow.
198 */
199 boolean isLeaf() {
200 return isLeaf;
201 }
202
203 boolean hasChildren() {
204 return nw != null || ne != null || sw != null || se != null;
205 }
206
207 QBLevel<T> findNextSibling() {
208 return (parent == null) ? null : parent.firstSiblingOf(this);
209 }
210
211 boolean hasContent() {
212 return content != null;
213 }
214
215 QBLevel<T> nextSibling() {
216 QBLevel<T> next = this;
217 QBLevel<T> sibling = next.findNextSibling();
218 // Walk back up the tree to find the next sibling node.
219 // It may be either a leaf or branch.
220 while (sibling == null) {
221 next = next.parent;
222 if (next == null) {
223 break;
224 }
225 sibling = next.findNextSibling();
226 }
227 return sibling;
228 }
229
230 QBLevel<T> firstChild() {
231 if (sw != null)
232 return sw;
233 if (nw != null)
234 return nw;
235 if (se != null)
236 return se;
237 return ne;
238 }
239
240 QBLevel<T> firstSiblingOf(final QBLevel<T> child) {
241 switch (child.index) {
242 case SW_INDEX:
243 if (nw != null)
244 return nw;
245 if (se != null)
246 return se;
247 return ne;
248 case NW_INDEX:
249 if (se != null)
250 return se;
251 return ne;
252 case SE_INDEX:
253 return ne;
254 default:
255 return null;
256 }
257 }
258
259 QBLevel<T> nextNode() {
260 if (!this.hasChildren())
261 return this.nextSibling();
262 return this.firstChild();
263 }
264
265 QBLevel<T> nextContentNode() {
266 QBLevel<T> next = this.nextNode();
267 if (next == null)
268 return next;
269 if (next.hasContent())
270 return next;
271 return next.nextContentNode();
272 }
273
274 void doAdd(T o) {
275 if (CONSISTENCY_TESTING) {
276 if (o instanceof Node && !matches(o, this)) {
277 o.getBBox().getIndex(level);
278 o.getBBox().getIndex(level - 1);
279 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString());
280 }
281 }
282 doAddContent(o);
283 if (level < QuadTiling.NR_LEVELS && isLeaf() && content.size() > MAX_OBJECTS_PER_NODE) {
284 doSplit();
285 }
286 }
287
288 void add(T o) {
289 findBucket(o.getBBox()).doAdd(o);
290 }
291
292 private void search(QuadBuckets<T> buckets, BBox searchBbox, List<T> result) {
293 if (!this.intersects(searchBbox))
294 return;
295 else if (this.bounds(searchBbox)) {
296 buckets.searchCache = this;
297 }
298
299 if (this.hasContent()) {
300 searchContents(searchBbox, result);
301 }
302
303 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
304
305 if (nw != null) {
306 nw.search(buckets, searchBbox, result);
307 }
308 if (ne != null) {
309 ne.search(buckets, searchBbox, result);
310 }
311 if (se != null) {
312 se.search(buckets, searchBbox, result);
313 }
314 if (sw != null) {
315 sw.search(buckets, searchBbox, result);
316 }
317 }
318
319 public String quads() {
320 return Long.toHexString(quad);
321 }
322
323 int indexOf(QBLevel<T> findThis) {
324 QBLevel<T>[] children = getChildren();
325 return IntStream.range(0, QuadTiling.TILES_PER_LEVEL)
326 .filter(i -> children[i] == findThis)
327 .findFirst().orElse(-1);
328 }
329
330 void removeFromParent() {
331 if (parent == null)
332 return;
333
334 if (!canRemove()) {
335 abort("attempt to remove non-empty child: " + this.content + ' ' + Arrays.toString(this.getChildren()));
336 }
337
338 if (parent.nw == this) {
339 parent.nw = null;
340 } else if (parent.ne == this) {
341 parent.ne = null;
342 } else if (parent.sw == this) {
343 parent.sw = null;
344 } else if (parent.se == this) {
345 parent.se = null;
346 }
347
348 if (parent.canRemove()) {
349 parent.removeFromParent();
350 }
351 }
352
353 boolean canRemove() {
354 return (content == null || content.isEmpty()) && !this.hasChildren();
355 }
356 }
357
358 private QBLevel<T> root;
359 private QBLevel<T> searchCache;
360 private int size;
361 private Collection<T> invalidBBoxPrimitives;
362
363 /**
364 * Constructs a new {@code QuadBuckets}.
365 */
366 public QuadBuckets() {
367 clear();
368 }
369
370 @Override
371 public final void clear() {
372 root = new QBLevel<>();
373 invalidBBoxPrimitives = new LinkedHashSet<>();
374 searchCache = null;
375 size = 0;
376 }
377
378 @Override
379 public boolean add(T n) {
380 if (n.getBBox().isValid()) {
381 root.add(n);
382 } else {
383 invalidBBoxPrimitives.add(n);
384 }
385 size++;
386 return true;
387 }
388
389 @Override
390 @SuppressWarnings("ModifyCollectionInEnhancedForLoop")
391 public boolean retainAll(Collection<?> objects) {
392 for (T o : this) {
393 if (objects.contains(o)) {
394 continue;
395 }
396 // In theory this could cause a ConcurrentModificationException
397 // but we never had such bug report in 8 years (since r2263)
398 if (!this.remove(o)) {
399 return false;
400 }
401 }
402 return true;
403 }
404
405 @Override
406 public boolean removeAll(Collection<?> objects) {
407 return objects.stream().map(this::remove).reduce(false, (a, b) -> a || b);
408 }
409
410 @Override
411 public boolean addAll(Collection<? extends T> objects) {
412 return objects.stream().map(this::add).reduce(false, (a, b) -> a || b);
413 }
414
415 @Override
416 public boolean containsAll(Collection<?> objects) {
417 return objects.stream().allMatch(this::contains);
418 }
419
420 @Override
421 public boolean remove(Object o) {
422 @SuppressWarnings("unchecked")
423 T t = (T) o;
424 searchCache = null; // Search cache might point to one of removed buckets
425 QBLevel<T> bucket = root.findBucket(t.getBBox());
426 boolean removed = bucket.removeContent(t);
427 if (!removed) {
428 removed = invalidBBoxPrimitives.remove(o);
429 }
430 if (removed) {
431 size--;
432 }
433 return removed;
434 }
435
436 @Override
437 public boolean contains(Object o) {
438 @SuppressWarnings("unchecked")
439 T t = (T) o;
440 if (!t.getBBox().isValid()) {
441 return invalidBBoxPrimitives.contains(o);
442 }
443 QBLevel<T> bucket = root.findBucket(t.getBBox());
444 return bucket != null && bucket.content != null && bucket.content.contains(t);
445 }
446
447 /**
448 * Converts to list.
449 * @return elements as list
450 */
451 public List<T> toList() {
452 return new ArrayList<>(this);
453 }
454
455 @Override
456 public Object[] toArray() {
457 // Don't call toList() -- in some cases, this can produce an infinite loop
458 // For example, ArrayList may call toArray to get the initial array. However, since we are
459 // creating a new ArrayList in toList with `this`, this creates an infinite recursion loop.
460 // So a `toArray` call becomes `toArray -> toList -> toArray -> toList -> toArray -> ...`
461 // For more information, see #20587.
462 return this.stream().toArray();
463 }
464
465 @Override
466 public <A> A[] toArray(A[] template) {
467 return this.toList().toArray(template);
468 }
469
470 class QuadBucketIterator implements Iterator<T> {
471 private QBLevel<T> currentNode;
472 private int contentIndex;
473 private final Iterator<T> invalidBBoxIterator = invalidBBoxPrimitives.iterator();
474 boolean fromInvalidBBoxPrimitives;
475 QuadBuckets<T> qb;
476
477 final QBLevel<T> nextContentNode(QBLevel<T> q) {
478 if (q == null)
479 return null;
480 QBLevel<T> orig = q;
481 QBLevel<T> next;
482 next = q.nextContentNode();
483 if (orig == next) {
484 abort("got same leaf back leaf: " + q.isLeaf());
485 }
486 return next;
487 }
488
489 QuadBucketIterator(QuadBuckets<T> qb) {
490 if (!qb.root.hasChildren() || qb.root.hasContent()) {
491 currentNode = qb.root;
492 } else {
493 currentNode = nextContentNode(qb.root);
494 }
495 this.qb = qb;
496 }
497
498 @Override
499 public boolean hasNext() {
500 if (this.peek() == null) {
501 fromInvalidBBoxPrimitives = true;
502 return invalidBBoxIterator.hasNext();
503 }
504 return true;
505 }
506
507 T peek() {
508 if (currentNode == null)
509 return null;
510 while ((currentNode.content == null) || (contentIndex >= currentNode.content.size())) {
511 contentIndex = 0;
512 currentNode = nextContentNode(currentNode);
513 if (currentNode == null) {
514 break;
515 }
516 }
517 if (currentNode == null || currentNode.content == null)
518 return null;
519 return currentNode.content.get(contentIndex);
520 }
521
522 @Override
523 public T next() {
524 if (fromInvalidBBoxPrimitives) {
525 return invalidBBoxIterator.next();
526 }
527 T ret = peek();
528 if (ret == null)
529 throw new NoSuchElementException();
530 contentIndex++;
531 return ret;
532 }
533
534 @Override
535 public void remove() {
536 if (fromInvalidBBoxPrimitives) {
537 invalidBBoxIterator.remove();
538 qb.size--;
539 } else {
540 // two uses
541 // 1. Back up to the thing we just returned
542 // 2. move the index back since we removed
543 // an element
544 contentIndex--;
545 T object = peek();
546 if (currentNode.removeContent(object))
547 qb.size--;
548
549 }
550 }
551 }
552
553 @Override
554 public Iterator<T> iterator() {
555 return new QuadBucketIterator(this);
556 }
557
558 @Override
559 public int size() {
560 return size;
561 }
562
563 @Override
564 public boolean isEmpty() {
565 return size == 0;
566 }
567
568 /**
569 * Search the tree for objects in the bbox (or crossing the bbox if they are ways)
570 * @param searchBbox the bbox
571 * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null.
572 */
573 public List<T> search(BBox searchBbox) {
574 List<T> ret = new ArrayList<>();
575 if (searchBbox == null || !searchBbox.isValid()) {
576 return ret;
577 }
578
579 // Doing this cuts down search cost on a real-life data set by about 25%
580 if (searchCache == null) {
581 searchCache = root;
582 }
583 // Walk back up the tree when the last search spot can not cover the current search
584 while (searchCache != null && !searchCache.bounds(searchBbox)) {
585 searchCache = searchCache.parent;
586 }
587
588 if (searchCache == null) {
589 searchCache = root;
590 Logging.info("bbox: " + searchBbox + " is out of the world");
591 }
592
593 // Save parent because searchCache might change during search call
594 QBLevel<T> tmp = searchCache.parent;
595
596 searchCache.search(this, searchBbox, ret);
597
598 // A way that spans this bucket may be stored in one
599 // of the nodes which is a parent of the search cache
600 while (tmp != null) {
601 tmp.searchContents(searchBbox, ret);
602 tmp = tmp.parent;
603 }
604 return ret;
605 }
606}
Note: See TracBrowser for help on using the repository browser.