C++ recursive templates with specialisation for tree algorithm

Question

I'm developing a tree-like algorithm using recursive c++ templates. I manage to reproduce my issues with the simplified algorithm below. The algorithm takes a single integer as an input. It computes two integers that are functions of the previous integer, and then it goes recursively: for each of the integers computed, it computes another two with the exact same function (which is also a function of the depth), until a stopping criterion is met.

I've written the following code using templates. I'm using this design choice because I ultimately want to implement the algorithm in HLS.

#define max_depth 5
#define two_to_maxdepth 32


// recursive template
template<unsigned int depth, unsigned int two_to_depth>
void split( int in[two_to_depth], int out[two_to_maxdepth], int aux[depth+1] )
{

  int next[two_to_depth*2];
  for (unsigned int ipart=0; ipart < two_to_depth; ++ipart){
    next[ipart]=ipart*in[ipart];
    next[ipart+two_to_depth]=ipart*in[ipart]+depth;
  }
  split<depth+1, two_to_depth*2>( next, out, aux);
}


// specialize
template<>
void split( int in[two_to_maxdepth], int out[two_to_maxdepth], int aux[max_depth+1])
{
  in=out;
}


int main()
{
  int in[1];
  int out[two_to_maxdepth];
  int aux[1];
  split<0,1>(in, out,aux);
}

However, it's not compiling, because it doesn't manage to infer the value of depth. I'm confused by this: the value of depth is specified in the template instantiation. Sorry if the question is too trivial, but I fail to see the reason.

Answer 1

Try this:

template<unsigned int depth_plus_one, unsigned int two_to_depth>
void split( int(& in)[two_to_depth], int (&out)[two_to_maxdepth], int (&aux)[depth_plus_one] )
{
  constexpr int depth=depth_plus_one-1;

This gets rid of forcing the compiler to invert x+1 to deduce x, and blocks function argument decay of arrays to pointers.

Also fix the termination case. Both references on the arrays, and in=out not doing what you think it does.

Using std::array instead of raw C style arrays may help. But even there, your out parameters should be references, and in.should be const references.

Now this still doesn't work, because aux is the wrong size in yohr recursive call. Why does aux even exist?

constexpr unsigned lg(unsigned x){
  if(x<=1) return 0;
  return 1+lg(x/2);
}

template<unsigned sz>
void split(int const(&In)[sz], int(&Out)[sz]){
  for(int i=0;i<sz;++i)
    Out[i]=In[i];
}

template<unsigned in, unsigned out>
void split( int const(&In)[in], int(&Out)[out] )
{
  int Next[in*2];

  for (unsigned i=0; i<In; ++i){
    Next[i]=i*In[i];
    Next[i+in]=i*In[i]+lg(in); // maybe +1?
  }
  split(Next, Out);
}