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                 :     497558 :                 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         [ +  - ]:      43997 :             child_id_list_t generate_child_ids(size_t parent_id, size_t count = MAX_CHILDREN)
      48                 :            :             {
      49                 :            :                 child_id_list_t c;
      50         [ +  - ]:      43997 :                 c.resize(count);
      51                 :      43997 :                 c[0] = parent_id; // FIXME: Remove this hack which suppresses warning
      52                 :            : 
      53         [ +  + ]:     394027 :                 for (auto& i : c)
      54                 :            :                 {
      55                 :            :                     // cppcheck-suppress useStlAlgorithm
      56                 :     350030 :                     i = get_next_tet_id();
      57                 :            :                 }
      58                 :            : 
      59                 :      43997 :                 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