2

I'm trying to create a linked list for use on the Arduino, in the Eclipse IDE with the Arduino/Sloeber plugin. The linked list is written in a .h and .cpp file, and included locally in the project.

enter image description here

However, when building, I get the error undefined reference to Structures::LinkedList<int>::LinkedList().

And despite the fact that I've added the local folder to the list of includes (and it can find the top level file containing setup() and loop()), the problem persists;

enter image description here

My relevant file listings are below. Any ideas of what settings I can add to Eclipse in order to solve this? Potentially, could it be something to do with the use of template<typename T> in the header file?

Thanks very much,

David

FYI: This problem does not occur with the core libraries i.e. I can run examples like Serial and Blink.

My top level .cpp is pretty simple:

#include "LinkedList.h"
#include "RAStarSearch.h"
#include "Arduino.h"

using namespace Structures;
void setup() { }

void loop() {
  LinkedList<int> list = LinkedList<int>();
  return;
}

And the referenced .h is:

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "Arduino.h"

namespace Structures {
template<typename T>
class LinkedList {
  public:
    /// Struct inside the class LinkedList
    struct Link {
      T value;
      Link *next;
    };

    LinkedList<T>(); ///< Default constructor
    void addValue(T val); ///< prepends new value at beginning of list
    T popValue(); ///< returns first element and deletes Link.
    Link* peekLink(); ///< Looks at first value
  private:
    Link *head; // this is the private member variable. It is just a pointer to the first Node
};
const int ERRNUM = 0x8000000; ///<Error number used, as exceptions not supported
}
#endif /* LINKEDLIST_H_ */

EDIT

On request I have included my code for LinkedList.cpp

#include "LinkedList.h"
#include "Arduino.h"

namespace Structures {
  template<typename T>
  LinkedList<T>::LinkedList() {
    head = NULL; // set head to NULL
  }
  template<typename T>
  void LinkedList<T>::addValue(T val) {
    Link *n = new Link();   // create new Node
    n->value = val;             // set value]

    if (head == NULL) { //i.e. if list is empty
      n->next = head;         // make the node point to the next node or NULL
      head = n;    // last but not least, make the head point at the new node.
    } else {
      Link *it = head;
      Link *oldIt = NULL;
      //TODO check edge cases i.e. insertion at beginning and end of list
      while (n->value > it->value){ //until place in list is found, needs T to have > operator
        oldIt = it;
        it = it->next;
      }
      oldIt->next = n; //Set pointer to n
      n->next = it; //Set n pointer to next
    }
  }
  template<typename T>
  T LinkedList<T>::popValue() {
    T retval = ERRNUM;
    if (head != NULL) {
      Link *n = head;
      retval = head->value;
      head = head->next;
      delete n;
    }
    return retval;
  }
  template<typename T>
  typename LinkedList<T>::Link* LinkedList<T>::peekLink() {
    return head;
  }
}
2

Have you tried placing the H file in the same folder as you main cpp file. This should prove beyond all doubt that there is nothing wrong with the code (I can't see anything wrong).

I suspect its a path issue. You need to check that Eclipse is setup up properly to source the libraries from you custom location. Also it needs to be passing this location on to the compiler. I don't know how to do that in Eclipse but Google should point you in the right direction. Try this http://forum.arduino.cc/index.php?topic=39972.0 ?

Also you might find it easier to specify the include files in the order system, 3rd party libraries, local libraries and then local include files. This means that duplicate definition faults are reported against the files nearest to the ones you have written. If you define time_t using your ordering the fault will be reported against rather than your header file.

Also a using namespace foo statement removes the benefits that namespaces provide, so its best not to do it.

EDIT Doh - I should have spotted this sooner. Template classes have to have the functions inline not in a CPP file. This is because the CPP file can't change what T is at compile time, but because the H file is included in the file it is used in when it is preprocessed the object represented by T can change. Basically inline your functions and it will work.

  • Unfortunately they are already both in the same path, and thank you for the tip on namespaces! – davidhood2 Feb 15 '17 at 12:52
  • Sorry - The mistake is really obvious, but I had to compile it to realise what it was :) You need the functions implementing. You can't have a cpp file with a template so you need to inline the functions in the header file. (I recreated the error on a PC with Visual Studio, so its not paths) – Code Gorilla Feb 15 '17 at 13:02
  • 1
    I have been reading up on this. As Matt states this seems to be a FAQ template issue. Have you read this? isocpp.org/wiki/faq/templates#templates-defn-vs-decl – jantje Feb 15 '17 at 13:51
  • I've added the LinkedList.cpp file. Do I take it from this that to solve it I just need to inline all the functions into a single file? – davidhood2 Feb 15 '17 at 20:05
  • @Matt This seems to be correct - inlining, or #include LinkedList.cpp seems to have worked! If you update your answer to reflect the problem? – davidhood2 Feb 15 '17 at 20:40
0

The error you get is telling you that you have not implemented the method.

LinkedList<T>()

which you use in loop()

In other words: the header file is found and the correct references are made but when the linker tries to pack everything together he finds that he doesn't have an implementation.

The implementation is in LinkedList.cpp in your project but with templates this is not enough.You need to somehow explain the "toolchain" that your project needs a "instantiation of the template" of type int.

The fact you need to specify this is a "limitation" of the toolchain processong of templates and is well documented here https://isocpp.org/wiki/faq/templates#templates-defn-vs-decl.
The same link contains solutions.
The article states "This solution may (or may not!) cause significant code bloat" which is probably one of the reasons why template classes are not so popular in embedded development.
In your case I would simply include LinkedList.cpp in my .ino file and rename the .ino to .cpp.
As I do not have the source code I can not tell you whether this will work.

note that including the LinkedList.cpp in the .ino doesn work because the LinkedList.cpp is included 2 times and there are no include gards in the LinkedList.cpp file

  • LinkedList is there (see the image), I just didn't include the listing as I though it was somewhat trivial? – davidhood2 Feb 15 '17 at 13:45
  • As to the compiler the constructor LinkedList<T>(); ///< Default constructor is not implemented – jantje Feb 15 '17 at 13:46
  • 1
    I updated the answer with the new insights I have on behalf of template classes – jantje Feb 15 '17 at 15:04
  • I updated the answer now the source has been provided. – jantje Feb 16 '17 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.