Branch data Line data Source code
1 : : #ifndef AMR_id_generator_h
2 : : #define AMR_id_generator_h
3 : :
4 : : #include <limits>
5 : : #include <cassert>
6 : :
7 : : // TODO: make this have a base class to support multiple generator schemes
8 : : // using the policy design pattern
9 : : namespace AMR {
10 : :
11 : : class id_generator_t {
12 : : public:
13 : : size_t start_id;
14 : :
15 : : // Used to track which tet_id to give the next parent
16 : : // The range between this and get_child_id(this) determinate how
17 : : // many tets can be on the first level
18 : : size_t next_tet_id;
19 : :
20 : : // Constructor
21 : : explicit id_generator_t(size_t start_tet_id = 0) :
22 : : start_id(start_tet_id),
23 : : next_tet_id(start_id)
24 : : {
25 : : }
26 : :
27 : : /**
28 : : * @brief Helper function to generate tet ids
29 : : *
30 : : * @return Id of the next tet
31 : : */
32 : : size_t get_next_tet_id()
33 : : {
34 : 1088577 : return next_tet_id++;
35 : : }
36 : :
37 : : /**
38 : : * Helper function to get all the child ids for a given parent
39 : : *
40 : : * WARNING: If you don't use all the children you ask for, you may have a bad time...
41 : : *
42 : : * @param parent_id The id of the parent
43 : : * @param count Number of children
44 : : *
45 : : * @return The list of children ids
46 : : */
47 [ + - ]: 14189 : child_id_list_t generate_child_ids(size_t parent_id, size_t count = MAX_CHILDREN)
48 : : {
49 : : child_id_list_t c;
50 [ + - ]: 14189 : c.resize(count);
51 : 14189 : c[0] = parent_id; // FIXME: Remove this hack which suppresses warning
52 : :
53 [ + + ]: 126217 : for (auto& i : c)
54 : : {
55 : : // cppcheck-suppress useStlAlgorithm
56 : 112028 : i = get_next_tet_id();
57 : : }
58 : :
59 : 14189 : return c;
60 : : }
61 : : };
62 : :
63 : : class morton_id_generator_t : public id_generator_t
64 : : {
65 : : public:
66 : : // This can be calculated as something like floor( num_bits - log_2(START_TET_ID) ) / log_2(MAX_CHILDREN)
67 : : // So for a simulation which supports an initial grid of ~1,048,576 elements in 3D:
68 : : // (64 - 20) / 3 = 14
69 : :
70 : : // This basically says the number of tets which can be in an initial grid
71 : : // A sensible value is 2^20 (1,048,576) for big simulations, and anything
72 : : // smaller for toy problems
73 : : #define START_TET_ID 1024
74 : :
75 : : // Constructor to reset START_TET_ID on the new value
76 : : morton_id_generator_t() : id_generator_t(START_TET_ID) {
77 : : // Empty
78 : : }
79 : :
80 : : /**
81 : : * @brief Helper function to convert from parent id to (base) child
82 : : * id
83 : : *
84 : : * @param parent_id Id of parent
85 : : *
86 : : * @return Id of child
87 : : */
88 : : static size_t get_child_id(size_t parent_id)
89 : : {
90 : : return parent_id << ID_SHIFT;
91 : : }
92 : :
93 : : /**
94 : : * @brief Helper function to get the all the child ids for a given
95 : : * parent
96 : : *
97 : : * @param parent_id The id of the parent
98 : : * @param count Number of children
99 : : *
100 : : * @return The list of children ids
101 : : */
102 : : static child_id_list_t generate_child_ids(size_t parent_id, size_t count = MAX_CHILDREN)
103 : : {
104 : : child_id_list_t c;
105 : : c.resize(count);
106 : : for (size_t i = 0; i < count; i++)
107 : : {
108 : : c[i] = get_child_id(parent_id, i);
109 : : }
110 : : return c;
111 : : }
112 : :
113 : : /**
114 : : * @brief Helper function to get the child id of a specific child
115 : : * of a parent
116 : : *
117 : : * @param parent_id id of the parent
118 : : * @param offset offset into the parent list (i.e number of child)
119 : : *
120 : : * @return the id of the given child
121 : : */
122 : : static size_t get_child_id(size_t parent_id, size_t offset)
123 : : {
124 : : // Try detect overflow
125 : : assert( parent_id <= get_parent_id(std::numeric_limits<size_t>::max()));
126 : : return get_child_id(parent_id) + offset;
127 : : }
128 : :
129 : : /**
130 : : * @brief Helper function to get the parent id of a child
131 : : *
132 : : * @param child_id Child for whom we should find the parent
133 : : *
134 : : * @return The parent id
135 : : */
136 : : static size_t get_parent_id(size_t child_id)
137 : : {
138 : : return (child_id >> ID_SHIFT);
139 : : }
140 : :
141 : : };
142 : : }
143 : :
144 : : #endif // guard
|
