linear-quadtree/lqt.h at master · rob05c/linear-quadtree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#ifndef lqtH
#define lqtH
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <limits.h>
#include <vector>
#include <utility>

typedef int key_t;
typedef float ord_t; // ordinate. There's only one, so it's not a coordinate.
typedef struct {
  ord_t x;
  ord_t y;
  key_t key;
} lqt_point;

typedef uint64_t location_t;
extern const location_t location_t_max;

typedef struct {
  location_t* locations;
  lqt_point*  points;
  size_t      length;
} linear_quadtree;

#define LINEAR_QUADTREE_DEPTH (sizeof(location_t) * CHAR_BIT / 2)

linear_quadtree lqt_create(lqt_point* points, size_t len,
                                  ord_t xstart, ord_t xend,
                                  ord_t ystart, ord_t yend,
                                  size_t* depth);
linear_quadtree lqt_nodify(lqt_point* points, size_t len,
                                  ord_t xstart, ord_t xend,
                                  ord_t ystart, ord_t yend,
                                  size_t* depth);
linear_quadtree lqt_sortify(linear_quadtree);

linear_quadtree lqt_create_cuda(lqt_point* points, size_t len,
                                       ord_t xstart, ord_t xend,
                                       ord_t ystart, ord_t yend,
                                       size_t* depth);
linear_quadtree lqt_create_cuda_slow(lqt_point* points, size_t len,
                                            ord_t xstart, ord_t xend,
                                            ord_t ystart, ord_t yend,
                                            size_t* depth);
linear_quadtree lqt_nodify_cuda(lqt_point* points, size_t len,
                                       ord_t xstart, ord_t xend,
                                       ord_t ystart, ord_t yend,
                                       size_t* depth);
linear_quadtree lqt_sortify_cuda(linear_quadtree);

void lqt_copy(linear_quadtree* destination, linear_quadtree* source);
void lqt_delete(linear_quadtree);
void lqt_print_node(const location_t* location, const lqt_point* point, const bool verbose);
void lqt_print_nodes(linear_quadtree lqt, const bool verbose);

typedef struct {
  lqt_point*  points;
  location_t* cuda_locations;
  lqt_point*  cuda_points;
  size_t      length;
} linear_quadtree_cuda;
linear_quadtree_cuda lqt_nodify_cuda_mem(lqt_point* points, size_t len,
                                                ord_t xstart, ord_t xend,
                                                ord_t ystart, ord_t yend,
                                                size_t* depth);
linear_quadtree lqt_sortify_cuda_mem(linear_quadtree_cuda);


///
/// unified / heterogeneous
///
typedef struct {
  location_t location;
  lqt_point  point;
} lqt_unified_node;

typedef struct {
  lqt_unified_node* nodes;
  size_t            length;
} linear_quadtree_unified;

void lqt_delete_unified(linear_quadtree_unified);

linear_quadtree_unified lqt_nodify_cuda_unified(lqt_point* points, size_t len,
                                                ord_t xstart, ord_t xend,
                                                ord_t ystart, ord_t yend,
                                                size_t* depth);
linear_quadtree_unified tbb_sortify_unified(linear_quadtree_unified lqt, const size_t threads);

linear_quadtree_unified lqt_create_heterogeneous(lqt_point* points, size_t len,
                                                 ord_t xstart, ord_t xend,
                                                 ord_t ystart, ord_t yend,
                                                 size_t* depth, const size_t threads);
linear_quadtree_unified lqt_create_sisd(lqt_point* points, size_t len,
                                        ord_t xstart, ord_t xend,
                                        ord_t ystart, ord_t yend,
                                        size_t* depth, const size_t threads);

linear_quadtree_unified lqt_create_heterogeneous_mergesort(lqt_point* points, size_t len,
                                                           ord_t xstart, ord_t xend,
                                                           ord_t ystart, ord_t yend,
                                                           size_t* depth, const size_t threads);

linear_quadtree_unified lqt_create_heterogeneous_samplesort(lqt_point* points, size_t len,
                                                            ord_t xstart, ord_t xend,
                                                            ord_t ystart, ord_t yend,
                                                            size_t* depth, const size_t threads);

linear_quadtree_unified merge_sortify_unified(linear_quadtree_unified lqt, const size_t threads);

std::vector<linear_quadtree_unified> lqt_create_pipelined(std::vector< std::pair<lqt_point*, size_t> > pointses,
                                                          ord_t xstart, ord_t xend,
                                                          ord_t ystart, ord_t yend,
                                                          size_t* depth, const size_t threads);

size_t tbb_num_default_thread();
void tbb_test_scheduler_init();

#endif