CODEWITHSUNDEEP
cbinary-search-tree
kishore .
kishore .

Reputation: 2293

Design of API's for data structures and algorithms

I recently implemented binary search tree, linked lists etc as a learning exercise. II implemented several API's like Insert,delete etc. For example the Insert node API looks like

 void insertNode(Node** root, Node* node)

The application would allocate memory for the node to be inserted. i.e node and assign the value/key and pass to this function.

1) My question is whether this is right approach in general? Or does the application only need to pass the value/key to insertNode function and the this function allocates memory?

  i.e void insertNode(Node** root, int key)
      {
            malloc for node here
      }

2) What is a good design practice- the application handles allocating memory and free or this library of APi's ?

Thanks

Upvotes: 0

Views: 207

Answers (1)

djna
djna

Reputation: 55907

General principles:

  1. Whoever allocates memory should also have responsibility to delete it.
  2. Make the client's job as easy as possible
  3. Think about thread safety

So, don't have client allocate the memory being managed by the tree. However we then need to think carefully about what a find or search should return.

You might look at example code to see what policies other folk have taken for collection APIs. For example.

In passing you don't need the double pointer for your root.

If someone has root pointing to an object { left -> ..., right -> ...} then if you pass root as Node* your code can write

 root->left = newValue;

you're modifying what root points to not root itself. By passing the double pointer you're allowing the structure to be completely relocated because someone can write:

 *root = completelyNewTree

which I doubt you intend.

Now for inserting I'd suggest passing in the new value, but have the collection allocate space and copy it. The collection now has complete control over the data it holds, and anything it returns should be copied. We don't want clients messing with the tree directly (thread safety).

This implies that for result of a find either the caller must pre-allocate a buffer or we must clearly document that the collection is returning an allocated copy that the caller must delete.

And yes, working in any Garbage Collecting language is much easier!

Upvotes: 1

Related Questions