| threaddb 2.0b A file mapped memory container extension

threaddbRGrid.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2019 by The ThreadDB Project
3 All Rights Reserved.
4
5 ThreadDB undergoes the BSD License 2.0. You should have received a copy along with this program; if not, write to the ThreadDB Project.
6 To obtain a full unlimited version contact thethreaddbproject(at)gmail.com.
7
8 threaddbRGrid.h - Data structure for efficient geometrical range queries.
9 */
10
11 #pragma once
12
13 #include <threaddbCPP.h>
14
26 #include <atomic>
27 #include <thread>
28 #include <mutex>
29 #include <condition_variable>
30 #include <cstddef>
31 #include <vector>
32 #include <istream>
33 #include <ostream>
34
35 namespace tdb
36 {
37 template< typename T >
38 struct array_deleter
39 {
40 void operator ()(T const* p)
41 {
42 delete[] p;
43 }
44 };
45
50 template< class T >
51 struct Functor
52 {
53 virtual void operator() (const T&) = 0;
54 };
55
60 template<typename T, size_t D>
61 struct Point
62 {
63 Point() {}
64 Point(T x_p)
65 {
66 x() = x_p;
67 }
68
69 Point(T x_p, T y_p)
70 {
71 x() = x_p;
72 y() = y_p;
73 }
74
75 Point(T x_p, T y_p, T z_p)
76 {
77 x() = x_p;
78 y() = y_p;
79 z() = z_p;
80 }
81
82 const T x()const { return _c[0]; }
83 T& x() { return _c[0]; }
84
85 const T y()const { return _c[1]; }
86 T& y() { return _c[1]; }
87
88 const T z()const { return _c[2]; }
89 T& z() { return _c[2]; }
90
91 Point& operator+=(const Point& rhs_p)
92 {
93 for(uint8_t i=0;i<D;++i)
94 _c[i] += rhs_p._c[i];
95 return *this;
96 }
97
98 Point& operator-=(const Point& rhs_p)
99 {
100 for (uint8_t i=0; i < D; ++i)
101 _c[i] -= rhs_p._c[i];
102 return *this;
103 }
104
105 size_t dimension() { return D; }
106
107 friend std::ostream& operator<<(std::ostream& os, const Point& P)
108 {
109 for (uint8_t i=0; i < D; ++i)
110 os.write((const char*)&P._c[i], sizeof(P._c[i]));
111 return os;
112 }
113
114 friend std::istream& operator>>(std::istream& is, Point& P)
115 {
116 for (uint8_t i=0; i < D; ++i)
117 is.read((char*)&P._c[i], sizeof(P._c[i]));
118 return is;
119 }
120
121 T _c[D];
122 };
123
128 template<class T, size_t D>
129 class Box {
130 public:
131 typedef Point<T, D> Point_;
132
133 Box() {}
134
135 Box(const Point_& rMin_p, const Point_& rMax_p) :
136 _min_corner(rMin_p),
137 _max_corner(rMax_p)
138 {
139 }
140
141 const Point_& min_corner()const { return _min_corner; }
142 Point_& min_corner() { return _min_corner; }
143
144 const Point_& max_corner()const { return _max_corner; }
145 Point_& max_corner() { return _max_corner; }
146
147 friend std::ostream& operator<<(std::ostream& os, const Box& L)
148 {
149 os << L._min_corner;
150 os << L._max_corner;
151 return os;
152 }
153
154 friend std::istream& operator>>(std::istream& is, Box& L)
155 {
156 is >> L._min_corner;
157 is >> L._max_corner;
158 return is;
159 }
160
161 private:
162 Point_ _min_corner;
163 Point_ _max_corner;
164 };
165
170 template<typename C, size_t D>
171 bool intersects(const Box<C, D>& rLhs_p, const Box<C, D>& rRhs_p)
172 {
173 for (uint8_t i=0; i < D; ++i)
174 {
175 if (rLhs_p.min_corner()._c[i] >= rRhs_p.max_corner()._c[i])
176 return false;
177 if (rLhs_p.max_corner()._c[i] <= rRhs_p.min_corner()._c[i])
178 return false;
179 }
180
181 return true;
182 }
183
184
185 template<class T, typename C, size_t D, class L>
186 class rgrid;
187
188 template<class T, typename C, size_t D, class L>
189 class rgrid_;
190
191 template<class L>
192 struct TaskInfo;
193
198 template<class T, typename C, size_t D>
199 struct Link
200 {
201 typedef Box<C, D> Box_;
202 typedef TaskInfo<Link> TaskInfo_;
203
204 Link() :
205 m_InsertMutex(),
206 m_pRgrid(new(m_Membuf) rgrid_<T, C, D, Link<T, C, D>>())
207 {
208 }
209
210 Link(const Box_& rTile_p, uint32_t Depth_p, tdb::database& rDb_p) :
211 m_InsertMutex(),
212 m_pRgrid(new(m_Membuf) rgrid_<T, C, D, Link<T, C, D>>(rTile_p, Depth_p - 1, rDb_p))
213 {
214 }
215
216 ~Link()
217 {
218 m_pRgrid->~rgrid_();
219 }
220
221 void add(const Box_& rBox_p, const T& rData_p, tdb::database& rDb_p);
222
223 bool intersects(const Box_& rBox_p) const;
224
225 void recurse(const Box_& rBox_p, Functor<T>& rCallback_p, tdb::database& rDb_p,
226 std::atomic<uint16_t>* pTaskCount_p,
227 std::mutex* pThreadMutex_p,
228 std::vector<TaskInfo_*>* pTaskHeap_p) const;
229
230 friend std::ostream& operator<<(std::ostream& os, const Link& L)
231 {
232 os << (*L.m_pRgrid);
233 return os;
234 }
235
236 friend std::istream& operator>>(std::istream& is, Link& L)
237 {
238 is >> (*L.m_pRgrid);
239 return is;
240 }
241
242 std::mutex m_InsertMutex;
243 char m_Membuf[sizeof(rgrid_<T, C, D, Link>)];
244 rgrid_<T, C, D, Link>* m_pRgrid;
245 };
246
251 template<class L>
252 struct TaskInfo
253 {
254 TaskInfo() : m_pNode(0) {}
255
256 std::shared_ptr<const L> m_pNode;
257 std::mutex m_Mutex;
258 std::condition_variable m_Signal;
259 };
260
265 template<typename C, size_t D>
266 std::pair<Box<C, D>, int32_t> index_(const Box<C, D>& lhs_p, const Box<C, D>& rhs_p)
267 {
268 int32_t idx(0);
269 uint8_t inc(1);
270 Box<C, D> box;
271
272 for (uint8_t i = 0; idx !=-1 && i < D; ++i)
273 {
274 C c = (lhs_p.max_corner()._c[i] - lhs_p.min_corner()._c[i]) / 2 + lhs_p.min_corner()._c[i];
275 if (rhs_p.min_corner()._c[i] >= c)
276 {
277 idx += inc;
278 box.min_corner()._c[i] = c;
279 box.max_corner()._c[i] = lhs_p.max_corner()._c[i];
280 }
281 else if (rhs_p.max_corner()._c[i] <= c)
282 {
283 box.min_corner()._c[i] = lhs_p.min_corner()._c[i];
284 box.max_corner()._c[i] = c;
285 }
286 else
287 {
288 idx = -1;
289 break;
290 }
291
292 inc <<= 1;
293 }
294
295 return std::make_pair(box, idx);
296 }
297
302 template<typename C>
303 std::pair<tdb::Box<C, 1>, int32_t> index_(const tdb::Box<C, 1>& lhs_p, const tdb::Box<C, 1>& rhs_p)
304 {
305 std::pair<tdb::Box<C, 1>, int32_t> index;
306
307 C x = (lhs_p.max_corner().x() - lhs_p.min_corner().x()) / 2 + lhs_p.min_corner().x();
308 if (rhs_p.min_corner().x() >= x)
309 {
310 index.second = 1;
311 index.first.min_corner().x() = x;
312 index.first.max_corner().x() = lhs_p.max_corner().x();
313 }
314 else if (rhs_p.max_corner().x() <= x)
315 {
316 index.second = 0;
317 index.first.min_corner().x() = lhs_p.min_corner().x();
318 index.first.max_corner().x() = x;
319 }
320 else
321 {
322 index.second = -1;
323 return index;
324 }
325
326 return index;
327 }
328
333 template<typename C>
334 std::pair<tdb::Box<C, 2>, int32_t> index_(const tdb::Box<C, 2>& lhs_p, const tdb::Box<C, 2>& rhs_p)
335 {
336 std::pair<tdb::Box<C, 2>, int32_t> index;
337
338 C x = (lhs_p.max_corner().x() - lhs_p.min_corner().x()) / 2 + lhs_p.min_corner().x();
339 if (rhs_p.min_corner().x() >= x)
340 {
341 index.second = 1;
342 index.first.min_corner().x() = x;
343 index.first.max_corner().x() = lhs_p.max_corner().x();
344 }
345 else if (rhs_p.max_corner().x() <= x)
346 {
347 index.second = 0;
348 index.first.min_corner().x() = lhs_p.min_corner().x();
349 index.first.max_corner().x() = x;
350 }
351 else
352 {
353 index.second = -1;
354 return index;
355 }
356
357 C y = (lhs_p.max_corner().y() - lhs_p.min_corner().y()) / 2 + lhs_p.min_corner().y();
358 if (rhs_p.min_corner().y() >= y)
359 {
360 index.second += 2;
361 index.first.min_corner().y() = y;
362 index.first.max_corner().y() = lhs_p.max_corner().y();
363 }
364 else if (rhs_p.max_corner().y() <= y)
365 {
366 index.first.min_corner().y() = lhs_p.min_corner().y();
367 index.first.max_corner().y() = y;
368 }
369 else
370 {
371 index.second = -1;
372 return index;
373 }
374
375 return index;
376 }
377
382 template<typename C>
383 std::pair<tdb::Box<C, 3>, int32_t> index_(const tdb::Box<C, 3>& lhs_p, const tdb::Box<C, 3>& rhs_p)
384 {
385 std::pair<tdb::Box<C, 3>, int32_t> index;
386
387 C x = (lhs_p.max_corner().x() - lhs_p.min_corner().x()) / 2 + lhs_p.min_corner().x();
388 if (rhs_p.min_corner().x() >= x)
389 {
390 index.second = 1;
391 index.first.min_corner().x() = x;
392 index.first.max_corner().x() = lhs_p.max_corner().x();
393 }
394 else if (rhs_p.max_corner().x() <= x)
395 {
396 index.second = 0;
397 index.first.min_corner().x() = lhs_p.min_corner().x();
398 index.first.max_corner().x() = x;
399 }
400 else
401 {
402 index.second = -1;
403 return index;
404 }
405
406 C y = (lhs_p.max_corner().y() - lhs_p.min_corner().y()) / 2 + lhs_p.min_corner().y();
407 if (rhs_p.min_corner().y() >= y)
408 {
409 index.second += 2;
410 index.first.min_corner().y() = y;
411 index.first.max_corner().y() = lhs_p.max_corner().y();
412 }
413 else if (rhs_p.max_corner().y() <= y)
414 {
415 index.first.min_corner().y() = lhs_p.min_corner().y();
416 index.first.max_corner().y() = y;
417 }
418 else
419 {
420 index.second = -1;
421 return index;
422 }
423
424 C z = (lhs_p.max_corner().z() - lhs_p.min_corner().z()) / 2 + lhs_p.min_corner().z();
425 if (rhs_p.min_corner().z() >= z)
426 {
427 index.second += 4;
428 index.first.min_corner().z() = z;
429 index.first.max_corner().z() = lhs_p.max_corner().z();
430 }
431 else if (rhs_p.max_corner().z() <= z)
432 {
433 index.first.min_corner().z() = lhs_p.min_corner().z();
434 index.first.max_corner().z() = z;
435 }
436 else
437 {
438 index.second = -1;
439 return index;
440 }
441
442 return index;
443 }
444
449 template<class T, typename C, size_t D, class L>
450 struct Cells
451 {
452 typedef Box<C, D> Box_;
453
454 Cells(const Box_& rBox_p) :
455 m_Box(rBox_p),
456 m_InsertMutex(),
457 m_Subcells(),
458 m_Subcount(0)
459 {
460 }
461
462 ~Cells()
463 {
464 }
465
466 size_t size() const { return 1 << D; }
467
468 std::pair<Box_, int32_t> index(const Box_& rBox_p) const
469 {
470 return index_<C,D>(m_Box, rBox_p);
471 }
472
473 const std::shared_ptr<L> operator[](size_t idx_p) const { return m_Subcells[idx_p]; }
474 std::shared_ptr<L> operator[](size_t idx_p) { return m_Subcells[idx_p]; }
475
476 void add(size_t Idx_p, const Box_& rTile_p, const Box_& rBox_p, uint32_t Depth_p, const T& rData_p, tdb::database& rDb_p)
477 {
478 if (m_Subcells[Idx_p] == 0)
479 {
480 std::lock_guard<std::mutex> lock(m_InsertMutex);
481 if (m_Subcells[Idx_p] == 0)
482 m_Subcells[Idx_p] = std::shared_ptr<L>(new L(rTile_p, Depth_p, rDb_p));
483 ++m_Subcount;
484 }
485 m_Subcells[Idx_p]->add(rBox_p, rData_p, rDb_p);
486 }
487
488 bool intersects(size_t Idx_p, const Box_& rBox_p) const
489 {
490 return (m_Subcells[Idx_p] != 0) && m_Subcells[Idx_p]->intersects(rBox_p);
491 }
492
493 friend std::ostream& operator<<(std::ostream& os, const Cells& C_)
494 {
495 os << C_.m_Box;
496 os.write((const char*)&C_.m_Subcount, sizeof(C_.m_Subcount));
497
498 for (size_t idx=0; idx <= D; ++idx)
499 {
500 if (C_.m_Subcells[idx])
501 {
502 os.write((const char*)&idx, sizeof(idx));
503 os << (*C_.m_Subcells[idx]);
504 }
505 }
506
507 return os;
508 }
509
510 friend std::istream& operator>>(std::istream& is, Cells& C_)
511 {
512 is >> C_.m_Box;
513 is.read((char*)&C_.m_Subcount, sizeof(C_.m_Subcount));
514
515 for (size_t idx(0); idx < C_.m_Subcount; ++idx)
516 {
517 size_t cidx(0);
518 is.read((char*)&cidx, sizeof(cidx));
519 C_.m_Subcells[cidx] = std::shared_ptr<L>(new L());
520 is >> (*C_.m_Subcells[cidx]);
521 }
522 return is;
523 }
524
525 Box_ m_Box;
526 std::mutex m_InsertMutex;
527
528 std::shared_ptr<L> m_Subcells[1 << D];
529 uint8_t m_Subcount;
530 };
531
536 template<class T, typename C, size_t D, class L>
537 class rgrid_
538 {
539 public:
540 typedef Box<C, D> Box_;
541 typedef TaskInfo<L> TaskInfo_;
542
543 rgrid_(const Box_& rBox_p, uint32_t Depth_p, tdb::database& rDb_p) :
544 m_PackageID(rDb_p.NewPackage()),
545 m_Depth(Depth_p),
546 m_Size(0),
547 m_MaxShapeSize(0),
548 m_Subcells(rBox_p)
549 {
550 }
551 ~rgrid_() {}
552
553 const Box_& bounding_box() const { return m_Subcells.m_Box; }
554
555 friend std::ostream& operator<<(std::ostream& os, const rgrid_& R)
556 {
557 os.write((const char*)&R.m_PackageID, sizeof(R.m_PackageID));
558 os.write((const char*)&R.m_Depth, sizeof(R.m_Depth));
559 os.write((const char*)&R.m_Size, sizeof(R.m_Size));
560 os.write((const char*)&R.m_MaxShapeSize, sizeof(R.m_MaxShapeSize));
561
562 os << R.m_Subcells;
563
564 return os;
565 }
566
567 friend std::istream& operator>>(std::istream& is, rgrid_& R)
568 {
569 is.read((char*)&R.m_PackageID, sizeof(R.m_PackageID));
570 is.read((char*)&R.m_Depth, sizeof(R.m_Depth));
571 is.read((char*)&R.m_Size, sizeof(R.m_Size));
572 is.read((char*)&R.m_MaxShapeSize, sizeof(R.m_MaxShapeSize));
573
574 is >> R.m_Subcells;
575
576 return is;
577 }
578
579 protected:
580 friend L;
581 friend class rgrid<T, C, D, L>;
582
583 rgrid_() :
584 m_PackageID(0),
585 m_Depth(0),
586 m_Size(0),
587 m_MaxShapeSize(0),
588 m_Subcells(Box_())
589 {
590 }
591
592 void add(const Box_& rBox_p, const T& rData_p, tdb::database& rDb_p);
593
594 void query(const Box_& rBox_p, Functor<T>& rCallback_p, tdb::database& rDb_p, uint8_t Threads_p);
595
596 static void loop(const Box_& rBox_p,
597 Functor<T>* pCallback_p,
598 tdb::database* pDb_p,
599 bool Continue_p,
600
601 TaskInfo_* pTaskInfo_p,
602 std::atomic<uint16_t>* pTaskCount_p,
603 std::mutex* pThreadMutex_p,
604 std::vector<TaskInfo_*>* pTaskHeap_p,
605 bool* pThreadExit_p);
606
607 void recurse(const Box_& rBox_p, Functor<T>& rCallback_p, tdb::database& rDb_p,
608 std::atomic<uint16_t>* pTaskCount_p,
609 std::mutex* pThreadMutex_p,
610 std::vector<TaskInfo_*>* pTaskHeap_p) const;
611
612 uint64_t m_PackageID;
613 uint32_t m_Depth;
614
615 std::atomic<size_t> m_Size;
616 std::atomic<size_t> m_MaxShapeSize;
617
618 Cells<T, C, D, L> m_Subcells;
619 };
620
625 template<class T, typename C, size_t D, class L = Link<T, C, D> >
626 class rgrid
627 {
628 public:
629 typedef Box<C, D> Box_;
630 typedef TaskInfo<L> TaskInfo_;
631
632 rgrid(const Box_& rBox_p, uint32_t Depth_p, tdb::database& rDb_p) :
633 m_rDatabase(rDb_p),
634 m_pRoot(new L(rBox_p, Depth_p, rDb_p)),
635 m_Depth(Depth_p)
636 {
637 }
638
639 rgrid(std::istream& is, tdb::database& rDb_p) :
640 m_rDatabase(rDb_p),
641 m_pRoot(new L()),
642 m_Depth(0)
643 {
644 is.read((char*)&m_Depth, sizeof(m_Depth));
645 is >> (*m_pRoot);
646 }
647
648 void add(const Box_& rBox_p, const T& rData_p)
649 {
650 m_pRoot->add(rBox_p, rData_p, m_rDatabase);
651 }
652
657 void query(const Box_& rBox_p, Functor<T>& rCallback_p, uint8_t Threads_p = 0)
658 {
659 std::mutex threadLock;
660 std::atomic<uint16_t> taskCount(0);
661 bool threadExit(false);
662
663 std::vector<std::pair<TaskInfo_, std::shared_ptr<std::thread>>> threadHeap(++Threads_p);
664 std::vector<TaskInfo_*> taskHeap;
665 for (size_t iter(1); iter < Threads_p; ++iter)
666 {
667 TaskInfo_& rTaskInfo(threadHeap[iter].first);
668
669 threadHeap[iter].second =
670 std::shared_ptr<std::thread>(new std::thread(&rgrid_<T, C, D, L>::loop, rBox_p, &rCallback_p, &m_rDatabase,
671 true, &rTaskInfo, &taskCount, &threadLock, &taskHeap, &threadExit));
672 taskHeap.push_back(&rTaskInfo);
673 }
674
675 TaskInfo_* pTaskInfo = &threadHeap.front().first;
676 pTaskInfo->m_pNode = m_pRoot;
677 ++taskCount;
678
679 while (taskCount != 0)
680 {
681 rgrid_<T, C, D, L>::loop(rBox_p, &rCallback_p, &m_rDatabase, false, pTaskInfo, &taskCount, &threadLock, &taskHeap, &threadExit);
682 }
683
684 threadExit = true;
685 for (size_t iter(1); iter < Threads_p; ++iter)
686 {
687 TaskInfo_& rTaskInfo(threadHeap[iter].first);
688 {
689 std::lock_guard<std::mutex> lock(rTaskInfo.m_Mutex);
690 rTaskInfo.m_Signal.notify_one();
691 }
692 threadHeap[iter].second->join();
693 }
694 }
695
696 friend std::ostream& operator<<(std::ostream& os, const rgrid& R)
697 {
698 os.write((const char*)&R.m_Depth, sizeof(R.m_Depth));
699 os << (*R.m_pRoot);
700
701 return os;
702 }
703
704 private:
705 tdb::database& m_rDatabase;
706 std::shared_ptr<L> m_pRoot;
707 uint32_t m_Depth;
708 };
709 };
710
715 template<class T, typename C, size_t D, class L>
716 void tdb::rgrid_<T, C, D, L>::add(const tdb::Box<C, D>& rBox_p, const T& rData_p, tdb::database& rDb_p)
717 {
718 ++m_Size;
719 const std::pair<Box<C, D>, int32_t> idx(m_Depth > 0 ? m_Subcells.index(rBox_p) : std::make_pair(m_Subcells.m_Box, int32_t(-1)));
720
721 if (idx.second < 0)
722 {
723 size_t dataSize = rData_p.size();
724 do
725 {
726 dataSize = m_MaxShapeSize.exchange(std::max(m_MaxShapeSize.load(), dataSize));
727 } while (dataSize > m_MaxShapeSize);
728
729 rDb_p.Store(m_PackageID, rData_p.size(), (const char*)& rData_p);
730 }
731 else
732 {
733 m_Subcells.add(idx.second, idx.first, rBox_p, m_Depth, rData_p, rDb_p);
734 }
735 }
736
741 template<class T, typename C, size_t D, class L>
742 void tdb::rgrid_<T, C, D, L>::loop(const Box<C, D>& rBox_p,
743 tdb::Functor<T>* pCallback_p,
744 tdb::database* pDb_p,
745 bool Continue_p,
746
747 TaskInfo<L>* pTaskInfo_p,
748 std::atomic<uint16_t>* pTaskCount_p,
749 std::mutex* pThreadMutex_p,
750 std::vector<TaskInfo<L>*>* pTaskHeap_p,
751 bool* pThreadExit_p)
752 {
753 bool continueLoop(Continue_p);
754 do
755 {
756 std::unique_lock<std::mutex> lock(pTaskInfo_p->m_Mutex);
757
758 if (pTaskInfo_p->m_pNode)
759 {
760 try
761 {
762 pTaskInfo_p->m_pNode->recurse(rBox_p, *pCallback_p, (*pDb_p), pTaskCount_p, pThreadMutex_p, pTaskHeap_p);
763 }
764 catch (...)
765 {
766 continueLoop = false;
767 }
768
769 pTaskInfo_p->m_pNode.reset();
770 --(*pTaskCount_p);
771
772 if (continueLoop)
773 {
774 std::lock_guard<std::mutex> lock_(*pThreadMutex_p);
775 (*pTaskHeap_p).push_back(pTaskInfo_p);
776 }
777 }
778 else if (continueLoop)
779 {
780 pTaskInfo_p->m_Signal.wait_for(lock, std::chrono::milliseconds(10));
781 }
782
783 continueLoop &= (*pThreadExit_p == false);
784 } while (continueLoop);
785
786 {
787 std::unique_lock<std::mutex> lock(pTaskInfo_p->m_Mutex);
788 pTaskInfo_p->m_pNode.reset();
789 }
790 }
791
796 template<class T, typename C, size_t D, class L>
797 void tdb::rgrid_<T, C, D, L>::recurse(const Box<C, D>& rBox_p, tdb::Functor<T>& rCallback_p, tdb::database& rDb_p,
798
799 std::atomic<uint16_t>* pTaskCount_p,
800 std::mutex* pThreadMutex_p,
801 std::vector<TaskInfo<L>*>* pTaskHeap_p) const
802 {
803 tdb::ReadInfo readHandle = rDb_p.Open(m_PackageID);
804
805 uint8_t subCells = m_Subcells.m_Subcount;
806 for (uint8_t idx(0); idx < m_Subcells.size(); ++idx)
807 {
808 if (m_Subcells.intersects(idx, rBox_p))
809 {
810 std::unique_lock<std::mutex> lock(*pThreadMutex_p);
811
812 if (((*pTaskHeap_p).empty() == false) && (subCells > 1))
813 {
814 TaskInfo<L>* pTaskInfo((*pTaskHeap_p).back());
815 (*pTaskHeap_p).pop_back();
816 ++(*pTaskCount_p);
817 lock.unlock();
818
819 std::lock_guard<std::mutex>(pTaskInfo->m_Mutex);
820 pTaskInfo->m_pNode = m_Subcells[idx];
821 pTaskInfo->m_Signal.notify_one();
822 }
823 else
824 {
825 lock.unlock();
826 m_Subcells[idx]->recurse(rBox_p, rCallback_p, rDb_p, pTaskCount_p, pThreadMutex_p, pTaskHeap_p);
827 }
828 }
829 --subCells;
830 }
831
832 if (m_MaxShapeSize > 0)
833 {
834 std::shared_ptr<char> pBuffer(new char[m_MaxShapeSize], tdb::array_deleter<char>());
835 while (rDb_p.End(readHandle) == false)
836 {
837 T* pShape = new(pBuffer.get())T(rDb_p, readHandle);
838
839 if (intersects<C, D>((*pShape).bounding_box(), rBox_p))
840 rCallback_p(*pShape);
841 }
842 }
843 }
844
849 template<class T, typename C, size_t D>
850 void tdb::Link<T, C, D>::add(const Box<C, D>& rBox_p, const T& rData_p, tdb::database& rDb_p)
851 {
852 m_pRgrid->add(rBox_p, rData_p, rDb_p);
853 }
854
859 template<class T, typename C, size_t D>
860 bool tdb::Link<T, C, D>::intersects(const Box<C, D>& rBox_p) const
861 {
862 return tdb::intersects<C, D>(rBox_p, m_pRgrid->bounding_box());
863 }
864
869 template<class T, typename C, size_t D>
870 void tdb::Link<T, C, D>::recurse(const Box<C, D>& rBox_p, tdb::Functor<T>& rCallback_p, tdb::database& rDb_p,
871 std::atomic<uint16_t>* pTaskCount_p,
872 std::mutex* pThreadMutex_p,
873 std::vector<TaskInfo<Link<T, C, D>>*>* pTaskHeap_p) const
874 {
875 m_pRgrid->recurse(rBox_p, rCallback_p, rDb_p, pTaskCount_p, pThreadMutex_p, pTaskHeap_p);
876 }
877
882 template<typename C, size_t D>
883 tdb::Point<C, D> operator+(const tdb::Point<C, D>& a, const tdb::Point<C, D>& b)
884 {
885 return tdb::Point<C, D>(a) += b;
886 }
887
892 template<typename C, size_t D>
893 tdb::Point<C, D> operator-(const tdb::Point<C, D>& a, const tdb::Point<C, D>& b)
894 {
895 return tdb::Point<C, D>(a) -= b;
896 }
897
902 template<typename C, size_t D>
903 tdb::Box<C, D>& operator+=(tdb::Box<C, D>& a, const tdb::Point<C, D>& b)
904 {
905 a.min_corner() += b;
906 a.max_corner() += b;
907 return a;
908 }
tdb::Point::operator<<
friend std::ostream & operator<<(std::ostream &os, const Point &P)
Definition: threaddbRGrid.h:107
tdb::rgrid_::m_Depth
uint32_t m_Depth
Definition: threaddbRGrid.h:613
tdb::TaskInfo::m_Mutex
std::mutex m_Mutex
Definition: threaddbRGrid.h:257
tdb::Link::add
void add(const Box_ &rBox_p, const T &rData_p, tdb::database &rDb_p)
Routine to add a data element to the rgrid.
Definition: threaddbRGrid.h:850
tdb::Cells::intersects
bool intersects(size_t Idx_p, const Box_ &rBox_p) const
Definition: threaddbRGrid.h:488
tdb::rgrid_::bounding_box
const Box_ & bounding_box() const
Definition: threaddbRGrid.h:553
tdb::Link::Link
Link(const Box_ &rTile_p, uint32_t Depth_p, tdb::database &rDb_p)
Definition: threaddbRGrid.h:210
tdb::Box
Box basic class definition.
Definition: threaddbRGrid.h:129
tdb::array_deleter::operator()
void operator()(T const *p)
Definition: threaddbRGrid.h:40
tdb::ReadInfo
C++ wrapper class to the threadDB_ReadInfo control structure.
Definition: threaddbCPP.h:70
tdb::Box::max_corner
Point_ & max_corner()
Definition: threaddbRGrid.h:145
tdb::TaskInfo::TaskInfo
TaskInfo()
Definition: threaddbRGrid.h:254
tdb::Point::z
const T z() const
Definition: threaddbRGrid.h:88
tdb::Cells::add
void add(size_t Idx_p, const Box_ &rTile_p, const Box_ &rBox_p, uint32_t Depth_p, const T &rData_p, tdb::database &rDb_p)
Definition: threaddbRGrid.h:476
tdb::Box::Box
Box()
Definition: threaddbRGrid.h:133
tdb::rgrid_::rgrid_
rgrid_(const Box_ &rBox_p, uint32_t Depth_p, tdb::database &rDb_p)
Definition: threaddbRGrid.h:543
tdb::Cells::Box_
Box< C, D > Box_
Definition: threaddbRGrid.h:452
tdb::Cells
Definition of a ode of the rgrid.
Definition: threaddbRGrid.h:450
threaddbCPP.h
Interface C++ wrapper classes.
tdb::Point::x
T & x()
Definition: threaddbRGrid.h:83
tdb::index_
std::pair< Box< C, D >, int32_t > index_(const Box< C, D > &lhs_p, const Box< C, D > &rhs_p)
Range index calculation specialization for n dimensional scenarios.
Definition: threaddbRGrid.h:266
tdb::Functor
Functor class receiving the queried elements.
Definition: threaddbRGrid.h:51
tdb::Link::m_pRgrid
rgrid_< T, C, D, Link > * m_pRgrid
Definition: threaddbRGrid.h:244
operator+=
tdb::Box< C, D > & operator+=(tdb::Box< C, D > &a, const tdb::Point< C, D > &b)
Box increment operator.
Definition: threaddbRGrid.h:903
tdb::rgrid_::query
void query(const Box_ &rBox_p, Functor< T > &rCallback_p, tdb::database &rDb_p, uint8_t Threads_p)
tdb::rgrid_::Box_
Box< C, D > Box_
Definition: threaddbRGrid.h:540
tdb::Link::Box_
Box< C, D > Box_
Definition: threaddbRGrid.h:201
tdb::Point::Point
Point(T x_p, T y_p, T z_p)
Definition: threaddbRGrid.h:75
tdb::TaskInfo
Query task information.
Definition: threaddbRGrid.h:192
tdb::rgrid_::m_PackageID
uint64_t m_PackageID
Definition: threaddbRGrid.h:612
tdb::Link::~Link
~Link()
Definition: threaddbRGrid.h:216
tdb::rgrid::Box_
Box< C, D > Box_
Definition: threaddbRGrid.h:629
tdb::rgrid::query
void query(const Box_ &rBox_p, Functor< T > &rCallback_p, uint8_t Threads_p=0)
Main entry for query operation over multiple threads.
Definition: threaddbRGrid.h:657
tdb::rgrid::TaskInfo_
TaskInfo< L > TaskInfo_
Definition: threaddbRGrid.h:630
tdb::TaskInfo::m_pNode
std::shared_ptr< const L > m_pNode
Definition: threaddbRGrid.h:256
tdb::rgrid_::m_Subcells
Cells< T, C, D, L > m_Subcells
Definition: threaddbRGrid.h:618
tdb::database::Store
void Store(uint64_t Package_p, size_t Size_p, const char pData_p[], threadDB_ItemInfo *pItemHandle_p=0)
C++ wrapper to store a data item in the selected package see ThreadDB_Store.
Definition: threaddbCPP.h:234
tdb::Link::m_InsertMutex
std::mutex m_InsertMutex
Definition: threaddbRGrid.h:242
tdb::intersects
bool intersects(const Box< C, D > &rLhs_p, const Box< C, D > &rRhs_p)
Check intersection of two Boxes.
Definition: threaddbRGrid.h:171
tdb::Point
Point basic class definition.
Definition: threaddbRGrid.h:61
tdb::rgrid::add
void add(const Box_ &rBox_p, const T &rData_p)
Definition: threaddbRGrid.h:648
tdb::Point::_c
T _c[D]
Definition: threaddbRGrid.h:121
tdb::Point::z
T & z()
Definition: threaddbRGrid.h:89
tdb::rgrid
External representation of the rgrid structure.
Definition: threaddbRGrid.h:186
tdb
Definition: threaddbCPP.h:28
tdb::rgrid_::L
friend L
Definition: threaddbRGrid.h:580
operator+
tdb::Point< C, D > operator+(const tdb::Point< C, D > &a, const tdb::Point< C, D > &b)
Point increment operator.
Definition: threaddbRGrid.h:883
tdb::Link::operator>>
friend std::istream & operator>>(std::istream &is, Link &L)
Definition: threaddbRGrid.h:236
tdb::Link::recurse
void recurse(const Box_ &rBox_p, Functor< T > &rCallback_p, tdb::database &rDb_p, std::atomic< uint16_t > *pTaskCount_p, std::mutex *pThreadMutex_p, std::vector< TaskInfo_ * > *pTaskHeap_p) const
Recursion into the next cell level.
Definition: threaddbRGrid.h:870
tdb::database::End
bool End(const tdb::ReadInfo &rReadInfo_p) const
C++ wrapper for stream end indicator see ThreadDB_PackageEnd.
Definition: threaddbCPP.h:302
tdb::Point::operator>>
friend std::istream & operator>>(std::istream &is, Point &P)
Definition: threaddbRGrid.h:114
tdb::Link::intersects
bool intersects(const Box_ &rBox_p) const
Box intersection of two elements.
Definition: threaddbRGrid.h:860
tdb::rgrid_::rgrid_
rgrid_()
Definition: threaddbRGrid.h:583
tdb::Box::Box
Box(const Point_ &rMin_p, const Point_ &rMax_p)
Definition: threaddbRGrid.h:135
tdb::Cells::~Cells
~Cells()
Definition: threaddbRGrid.h:462
tdb::Functor::operator()
virtual void operator()(const T &)=0
tdb::Cells::size
size_t size() const
Definition: threaddbRGrid.h:466
tdb::TaskInfo::m_Signal
std::condition_variable m_Signal
Definition: threaddbRGrid.h:258
tdb::rgrid::rgrid
rgrid(std::istream &is, tdb::database &rDb_p)
Definition: threaddbRGrid.h:639
tdb::rgrid_::add
void add(const Box_ &rBox_p, const T &rData_p, tdb::database &rDb_p)
Routine to add a new element to the rgrid.
Definition: threaddbRGrid.h:716
tdb::Point::Point
Point(T x_p, T y_p)
Definition: threaddbRGrid.h:69
tdb::Box::Point_
Point< T, D > Point_
Definition: threaddbRGrid.h:131
tdb::Box::operator>>
friend std::istream & operator>>(std::istream &is, Box &L)
Definition: threaddbRGrid.h:154
tdb::Box::min_corner
const Point_ & min_corner() const
Definition: threaddbRGrid.h:141
tdb::Link::m_Membuf
char m_Membuf[sizeof(rgrid_< T, C, D, Link >)]
Definition: threaddbRGrid.h:243
tdb::Cells::index
std::pair< Box_, int32_t > index(const Box_ &rBox_p) const
Definition: threaddbRGrid.h:468
tdb::rgrid_::operator>>
friend std::istream & operator>>(std::istream &is, rgrid_ &R)
Definition: threaddbRGrid.h:567
tdb::Link::operator<<
friend std::ostream & operator<<(std::ostream &os, const Link &L)
Definition: threaddbRGrid.h:230
tdb::Point::Point
Point()
Definition: threaddbRGrid.h:63
tdb::rgrid_::m_MaxShapeSize
std::atomic< size_t > m_MaxShapeSize
Definition: threaddbRGrid.h:616
tdb::Cells::operator>>
friend std::istream & operator>>(std::istream &is, Cells &C_)
Definition: threaddbRGrid.h:510
tdb::Cells::m_Subcells
std::shared_ptr< L > m_Subcells[1<< D]
Definition: threaddbRGrid.h:528
tdb::Point::y
T & y()
Definition: threaddbRGrid.h:86
tdb::database
C++ wrapper class of the threadDB file mapped memory container extension.
Definition: threaddbCPP.h:97
tdb::Cells::operator[]
std::shared_ptr< L > operator[](size_t idx_p)
Definition: threaddbRGrid.h:474
tdb::Point::x
const T x() const
Definition: threaddbRGrid.h:82
tdb::Link::TaskInfo_
TaskInfo< Link > TaskInfo_
Definition: threaddbRGrid.h:202
tdb::rgrid::operator<<
friend std::ostream & operator<<(std::ostream &os, const rgrid &R)
Definition: threaddbRGrid.h:696
tdb::Box::min_corner
Point_ & min_corner()
Definition: threaddbRGrid.h:142
tdb::Box::max_corner
const Point_ & max_corner() const
Definition: threaddbRGrid.h:144
tdb::Cells::m_Box
Box_ m_Box
Definition: threaddbRGrid.h:525
tdb::Point::dimension
size_t dimension()
Definition: threaddbRGrid.h:105
tdb::rgrid_::operator<<
friend std::ostream & operator<<(std::ostream &os, const rgrid_ &R)
Definition: threaddbRGrid.h:555
tdb::Cells::m_Subcount
uint8_t m_Subcount
Definition: threaddbRGrid.h:529
tdb::rgrid_::recurse
void recurse(const Box_ &rBox_p, Functor< T > &rCallback_p, tdb::database &rDb_p, std::atomic< uint16_t > *pTaskCount_p, std::mutex *pThreadMutex_p, std::vector< TaskInfo_ * > *pTaskHeap_p) const
Recursion into next level of the rgrid cells.
Definition: threaddbRGrid.h:797
tdb::rgrid_::TaskInfo_
TaskInfo< L > TaskInfo_
Definition: threaddbRGrid.h:541
tdb::Cells::operator<<
friend std::ostream & operator<<(std::ostream &os, const Cells &C_)
Definition: threaddbRGrid.h:493
tdb::Box::operator<<
friend std::ostream & operator<<(std::ostream &os, const Box &L)
Definition: threaddbRGrid.h:147
tdb::rgrid_::~rgrid_
~rgrid_()
Definition: threaddbRGrid.h:551
tdb::Point::Point
Point(T x_p)
Definition: threaddbRGrid.h:64
tdb::rgrid::rgrid
rgrid(const Box_ &rBox_p, uint32_t Depth_p, tdb::database &rDb_p)
Definition: threaddbRGrid.h:632
operator-
tdb::Point< C, D > operator-(const tdb::Point< C, D > &a, const tdb::Point< C, D > &b)
Point subtract operator.
Definition: threaddbRGrid.h:893
tdb::Cells::m_InsertMutex
std::mutex m_InsertMutex
Definition: threaddbRGrid.h:526
tdb::database::Open
tdb::ReadInfo Open(uint64_t Package_p)
C++ wrapper to open a package for stream reading see ThreadDB_Open.
Definition: threaddbCPP.h:263
tdb::Point::operator+=
Point & operator+=(const Point &rhs_p)
Definition: threaddbRGrid.h:91
tdb::Link::Link
Link()
Definition: threaddbRGrid.h:204
tdb::rgrid_::loop
static void loop(const Box_ &rBox_p, Functor< T > *pCallback_p, tdb::database *pDb_p, bool Continue_p, TaskInfo_ *pTaskInfo_p, std::atomic< uint16_t > *pTaskCount_p, std::mutex *pThreadMutex_p, std::vector< TaskInfo_ * > *pTaskHeap_p, bool *pThreadExit_p)
Main query loop for parallel thread execution.
Definition: threaddbRGrid.h:742
tdb::Point::y
const T y() const
Definition: threaddbRGrid.h:85
tdb::Cells::operator[]
const std::shared_ptr< L > operator[](size_t idx_p) const
Definition: threaddbRGrid.h:473
tdb::Point::operator-=
Point & operator-=(const Point &rhs_p)
Definition: threaddbRGrid.h:98
tdb::array_deleter
Definition: threaddbRGrid.h:38
tdb::Link
Link helper class to the next node level.
Definition: threaddbRGrid.h:199
tdb::rgrid_::m_Size
std::atomic< size_t > m_Size
Definition: threaddbRGrid.h:615
tdb::Cells::Cells
Cells(const Box_ &rBox_p)
Definition: threaddbRGrid.h:454
tdb::rgrid_
Internal representation of the rgrid structure.
Definition: threaddbRGrid.h:189