1libkd: a library for building and using kd-trees.
2
3libkd is Copyright 2006-2015 Dustin Lang and Keir Mierle.
4libkd is free software, licensed under a 3-clause BSD-style license.
5See the file LICENSE for the full terms.
6
7Dustin Lang is dstndstn (at) gmail (dot) com
8Keir Mierle is mierle (at) gmail (dot) com
9
10
11About the code internals:
12-------------------------
13
14We use some nasty preprocessors magic to support multiple data types.
15It probably would have been better to write them as C++ templates.
16One lives and learns.
17
18The instantiation of the "templates" happens in the files "kdint_*.c"
19and friends. These in turn #include one each of
20"kdint_[edt]type_*.h".
21
22There are three data types involved:
23
24 * the "external" type -- the type accepted by the external API, for
25 example, the datatype of the kdtree_nearest_neighbour() query
26 point.
27
28 * the "tree" type -- the type used to describe the bounding boxes or
29 splitting planes within the tree.
30
31 * the "data" type -- the type used to store the data points within
32 the tree.
33
34We also tried to write some functions so that the dimension of the
35tree could be declared constant at compile time -- so there would be
36separate compiled code for three-dimensional or two-dimensional trees.
37But that became hard to manage so we don't use it now.
38
39When instantiated, the function names have the datatypes appended to
40them. For example, if you look in the libkd.a file, you'll see:
41
42 > nm libkd/libkd.a | grep "T _kdtree_rangesearch_options"
43 0000000000000130 T _kdtree_rangesearch_options
44 00000000000009e0 T _kdtree_rangesearch_options_ddd
45 0000000000000a00 T _kdtree_rangesearch_options_fff
46 00000000000011e0 T _kdtree_rangesearch_options_ddu
47 0000000000001210 T _kdtree_rangesearch_options_duu
48 00000000000011e0 T _kdtree_rangesearch_options_dds
49 0000000000001240 T _kdtree_rangesearch_options_dss
50
51Where the first one is the entry-point which dispatches to the
52instantiated ones based on the kdtree_t.treetype value.
53
54(To make things more elaborate, we also started gathering the function
55pointers into a "vtable", kdtree_t.fun, and that is used in some
56places.)
57
58There are some preprocessor functions to support the name mangling.
59For example, take the function declared in kdtree.h:
60
61 kdtree_t* kdtree_convert_data(kdtree_t* kd, void *data,
62 int N, int D, int Nleaf, int treetype);
63
64The kdtree_convert_data entry point is in kdtree.c:
65
66 KD_DECLARE(kdtree_convert_data, kdtree_t*, (kdtree_t* kd, void* data, int N, int D, int Nleaf));
67
68 kdtree_t* kdtree_convert_data(kdtree_t* kd, void *data,
69 int N, int D, int Nleaf, int treetype) {
70 kdtree_t* res = NULL;
71 KD_DISPATCH(kdtree_convert_data, treetype, res=, (kd, data, N, D, Nleaf));
72 if (res)
73 res->converted_data = TRUE;
74 return res;
75 }
76
77and the actual implementation is in kdtree_internal.c:
78
79 kdtree_t* MANGLE(kdtree_convert_data)
80 (kdtree_t* kd, etype* edata, int N, int D, int Nleaf) {
81 dtype* ddata;
82 int i, d;
83 //// .....
84 }
85
86Note that in kdtree_interal.c you get to assume that "etype" is
87typedef'd to the external datatype, "dtype" is the tree's datatype,
88etc.
89
90
91
92