General Tips for Correct Linking in C/C++

Question

I always run into troubles, when I am trying to work with more than two C/C++ files.

For example: Main.cpp

// 
// Created by Niclas Schwalbe on 02.03.21.
//

#include "bTree.h"

int main(){
    BTree<int> * tree = new BTree<int>(2048, [](int a, int b) {return a < b;}, [](int a){printf("%d", a);});
    srand (0);

    for(int i = 0; i < 100000; i++){
        tree->insert(rand());
    }

    tree->print();
}

BTree.cpp

/* B-Tree
 * Author:  Caleb Baker
 * Date:    10/8/17
 * Summary: A B-Tree data structure. Supports lg(n) time search, insert, and delete.
 */

#include "bTree.h"


// Constructor for b tree.
// t is the minimum degree of the tree.
// compare is the comparison function used for managing elements within the tree.
// printK is a function that prints keys.
template <typename T>
BTree<T>::BTree(unsigned t, std::function<bool(T,T)> compare, std::function<void(T)> printK) {
    //Code
}


// Destructor.
template <typename T>
BTree<T>::~BTree<T>() {
    //Code
}


// Inserts the key k into the tree.
template <typename T>
void BTree<T>::insert(T k) {

    // Code
}


// Removes k from the tree. Returns the removed key.
// Throws a BTREE_EXCEPTION if key is not found.
template <typename T>
T BTree<T>::remove(T k) {
    //Code
}


// Function to find a key in the tree.
// returnValue.first is the node the item is in.
// returnValue.second is the correct index in that node's key array
template <typename T>
std::pair<BNode<T>*, unsigned> BTree<T>::search(T k) {

    //Code
}


// Function to find a key in the tree.
// Returns the key.
// If the item was not found an exception is thrown.
template <typename T>
T BTree<T>::searchKey(T k) {
    //Code
}


// Function for printing a tree.
template <typename T>
void BTree<T>::print() {
    //Code
}


// Initialize a b tree node.
// x is a pointer to the node
// t is the minimum degree of the tree.
template <typename T>
void BTree<T>::initializeNode(BNode<T> *x) {
    //Code
}


// Recursively deletes the subtree rooted at x.
// Does the dirty work for the destructor.
template <typename T>
void BTree<T>::freeNode(BNode<T> *x) {
    //Code
}


// Finds the index of k in x->key.
// If k is not present, returns the index of the subtree
// that could contain k in x->child.
template <typename T>
unsigned BTree<T>::findIndex(BNode<T> *x, T k) {
    //Code
}


// Inserts k into x.
// Returns the index of k in x->key.
template <typename T>
unsigned BTree<T>::nodeInsert(BNode<T> *x, T k) {
    //Code
}


// Deletes the indexth element from x->key.
// Returns deleted key.
template <typename T>
T BTree<T>::nodeDelete(BNode<T> *x, unsigned index) {
//Code
}


// Function for splitting nodes that are too full.
// x points to the parent of the node to splits.
// i is the index in x's child array of the node to split.
template <typename T>
void BTree<T>::splitChild(BNode<T> *x, int i) {
      //Code
}


// Merges the (i + 1)th child of parent with the ith child of parent.
// Returns an indicator of whether the change affected the root.
template <typename T>
char BTree<T>::mergeChildren(BNode<T> *parent, unsigned i) {

    //Code 
}


// Makes sure parent->child[index] has at least minDegree items.
// If it doesn't, then things are changed to make sure it does.
// Returns a code indicating what action was taken.
template <typename T>
char BTree<T>::fixChildSize(BNode<T> *parent, unsigned index) {
    //Code
}


// Recursize function for printing a tree or subtree.
// node is the root of the subtree to be printed.
// tab is how far to indent the subtree.
template <typename T>
void BTree<T>::printNode(BNode<T> *node, unsigned tab) {
//Code
}

BTree.h

/* B-Tree
 * Author:  Caleb Baker
 * Date:    10/8/17
 * Summary: A B-Tree data structure.
 *          Most standard operations run in O(lg(n)) time.
 *          Uses O(n) memory.
 *          Where n is the number of items in the tree.
 */


#ifndef BTREE_H
#define BTREE_H

#include <utility>
#include <stdlib.h>
#include <stdio.h>
#include <functional>

#define SEARCH_KEY_NOT_FOUND 's'
#define REMOVE_KEY_NOT_FOUND 'r'

#define NEW_ROOT 2
#define MODIFIED_NOT_ROOT 1
#define NOT_MODIFIED 0


// struct for representing nodes of a b tree
template <typename T>
struct BNode {
    BNode<T> **child;   // Array of pointers to children.
    T *key;             // Array of keys.
    unsigned size;      // Number of keys.
    bool leaf;          // Whether the node is a leaf.
};


typedef char BTREE_EXCEPTION;


// class for representing b trees.
template <typename T>
class BTree {
public:
    // Constructor
    // First parameter is the minimum degree of the tree.
    // Second parameter is the tree's key-comparison function.
    // Third parameter is a function that prints keys.
    // Constant time.
    BTree(unsigned, std::function<bool(T,T)>, std::function<void(T)>);

    // Destructor.
    // Linear time.
    ~BTree<T>();

    // Inserts a key into the tree.
    // Logorithmic time.
    void insert(T);

    // Removes a key from the tree.
    // Throws a BTREE_EXCEPTION if no item was found to remove.
    // Logorithmic time.
    T remove(T);

    // Function to find a key in the tree.
    // returnValue.first is the node the item is in.
    // returnValue.second is the correct index in that node's key array
    // Logorithmic time.
    std::pair<BNode<T>*, unsigned> search(T);

    // Uses search but just returns the key rather than the whole node.
    // Useful when T is a key value pair and lessThan only looks at the key.
    // Throws a BTREE_EXCEPTION if no item matching the parameter is found
    // Logorithmic time.
    T searchKey(T);

    // Prints the tree.
    // Linear time
    void print();

private:

    // Used for initializing nodes.
    void initializeNode(BNode<T>*);

    // Recursive function called by destructor.
    void freeNode(BNode<T>*);

    // Finds the index of a key in a node.
    unsigned findIndex(BNode<T>*, T);

    // Inserts a key into a node.
    unsigned nodeInsert(BNode<T>*, T);

    // Deletes the key at a given index from a node.
    T nodeDelete(BNode<T>*, unsigned);

    // Function for splitting nodes that are too full.
    void splitChild(BNode<T>*, int);

    // Merges two children of a node at a given index into one child.
    char mergeChildren(BNode<T>*, unsigned);

    // Makes sure the child of a node at a specified index has >= minDegree items.
    char fixChildSize(BNode<T>*, unsigned);

    // Recursively prints a subtree.
    void printNode(BNode<T>*, unsigned);

    // Root node.
    BNode<T> *root;

    // Comparison function used for managing element placement.
    std::function<bool(T,T)> lessThan;

    // Function used to print items in the tree.
    std::function<void(T)> printKey;

    // Minimum degree of the tree.
    unsigned minDegree;
};

#endif

Compiling this with:

 gcc -std=c++11 -x c++ Main.cpp bTree.cpp

Will run into inexplainable linking errors, namley:

Undefined symbols for architecture x86_64:...

I already used guards and so on, so what am I doing wrong? Is there any approach, which can ensure that linking error cannot happen in general?

EDIT: Full error message:

  "BTree<int>::print()", referenced from:
      _main in Main-ad069e.o
  "BTree<int>::insert(int)", referenced from:
      _main in Main-ad069e.o
  "BTree<int>::BTree(unsigned int, std::__1::function<bool (int, int)>, std::__1::function<void (int)>)", referenced from:
      _main in Main-ad069e.o
  "std::logic_error::logic_error(char const*)", referenced from:
      std::length_error::length_error(char const*) in Main-ad069e.o
  "std::length_error::~length_error()", referenced from:
      std::__1::__throw_length_error(char const*) in Main-ad069e.o
  "std::terminate()", referenced from:
      ___clang_call_terminate in Main-ad069e.o
  "typeinfo for std::length_error", referenced from:
      std::__1::__throw_length_error(char const*) in Main-ad069e.o
  "vtable for __cxxabiv1::__class_type_info", referenced from:
      typeinfo for std::__1::__function::__base<bool (int, int)> in Main-ad069e.o
      typeinfo for main::$_0 in Main-ad069e.o
      typeinfo for std::__1::__function::__base<void (int)> in Main-ad069e.o
      typeinfo for main::$_1 in Main-ad069e.o
  NOTE: a missing vtable usually means the first non-inline virtual member function has no definition.
  "vtable for __cxxabiv1::__si_class_type_info", referenced from:
      typeinfo for std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)> in Main-ad069e.o
      typeinfo for std::__1::__function::__func<main::$_1, std::__1::allocator<main::$_1>, void (int)> in Main-ad069e.o
  NOTE: a missing vtable usually means the first non-inline virtual member function has no definition.
  "vtable for std::length_error", referenced from:
      std::length_error::length_error(char const*) in Main-ad069e.o
  NOTE: a missing vtable usually means the first non-inline virtual member function has no definition.
  "operator delete(void*)", referenced from:
      _main in Main-ad069e.o
      std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)>::~__func() in Main-ad069e.o
      std::__1::_DeallocateCaller::__do_call(void*) in Main-ad069e.o
      std::__1::__function::__func<main::$_1, std::__1::allocator<main::$_1>, void (int)>::~__func() in Main-ad069e.o
  "operator new(unsigned long)", referenced from:
      _main in Main-ad069e.o
      std::__1::__libcpp_allocate(unsigned long, unsigned long) in Main-ad069e.o
  "___cxa_allocate_exception", referenced from:
      std::__1::__throw_length_error(char const*) in Main-ad069e.o
  "___cxa_begin_catch", referenced from:
      ___clang_call_terminate in Main-ad069e.o
  "___cxa_free_exception", referenced from:
      std::__1::__throw_length_error(char const*) in Main-ad069e.o
  "___cxa_pure_virtual", referenced from:
      vtable for std::__1::__function::__base<bool (int, int)> in Main-ad069e.o
      vtable for std::__1::__function::__base<void (int)> in Main-ad069e.o
  "___cxa_throw", referenced from:
      std::__1::__throw_length_error(char const*) in Main-ad069e.o
  "___gxx_personality_v0", referenced from:
      _main in Main-ad069e.o
      std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)>::__func(main::$_0&&, std::__1::allocator<main::$_0>&&) in Main-ad069e.o
      std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)>::__clone() const in Main-ad069e.o
      std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)>::destroy_deallocate() in Main-ad069e.o
      std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)>::target(std::type_info const&) const in Main-ad069e.o
      std::__1::__throw_length_error(char const*) in Main-ad069e.o
      std::__1::unique_ptr<std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)>, std::__1::__allocator_destructor<std::__1::allocator<std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)> > > >::unique_ptr<true, void>(std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)>*, std::__1::__dependent_type<std::__1::__unique_ptr_deleter_sfinae<std::__1::__allocator_destructor<std::__1::allocator<std::__1::__function::__func<main::$_0, std::__1::allocator<main::$_0>, bool (int, int)> > > >, true>::__good_rval_ref_type) in Main-ad069e.o
      ...
ld: symbol(s) not found for architecture x86_64

No, you get that when linking. You also shouldn't put the .h file in the compilation command. — interjay, Mar 02 '21 at 11:43
None of the questions listed above answer my problem, since I already applied the rules. — Niclas, Mar 02 '21 at 11:45
Take inspiration from existing open source C++ projects such as [ninja](https://ninja-build.org/) or [RefPerSys](http://refpersys.org/) or [fish](https://fishshelll.com/) or [Qt](https://qt.io/) — Basile Starynkevitch, Mar 02 '21 at 11:47

General Tips for Correct Linking in C/C++

0 Answers0