Accessing node data through POSIX tdelete()

Question

The manpage for the POSIX binary tree functions includes the following statements:

tdelete() returns a pointer to the parent of the item deleted, or NULL if the item was not found.

tdelete() frees the memory required for the node in the tree. The user is responsible for freeing the memory for the corresponding data.

This means that there is no way to get access to a node's data for a given key from a tdelete() call. One would be required to call tfind() (rather than tsearch() so as not to add the given key), perform destruction of the node's data, and then call tdelete() with the same key to remove the node from the binary tree.

Have I interpreted this correctly? Is there some way around what I perceive to be limitations with this approach?

1. If the key is heap-allocated, it can't be freed (or made useless to the comparison function in use) before the node is deleted. This requires calling tfind() to obtain a pointer to the data, tdelete() to remove the node, and then destroying the data retrieved from the tfind() call.
2. Two lookups are required to delete a node and destroy it's enclosed data.

Answer 1

I've never used this set of functions before, but you appear to be correct. However, I would try using the pointer returned from tfind() as the rootp argument to tdelete(). This should make the second search essentially a no-op. AFAICT, the data structure allows any node to be treated as a root so you would find the node and then delete it from the subtree rooted at the node that you found.

Answer 2

Like D.Shawley, I have never used these function before, so I wrote a little test program that leaks memory.

#include <search.h>
#include <stdio.h>
#include <stdlib.h>

int fx(const void *a, const void *b) {
  if (*(int*)a < *(int*)b) return -1;
  return (*(int*)a > *(int*)b);
}

int main(void) {
  int i, *elem;
  void *root = NULL, *val;

  for (i = 0; i < 10; i++) {
    elem = malloc(sizeof *elem); /* LEAK, leak, leak */
    *elem = i/2;
    val = tsearch(elem, &root, fx); /* assume all OK */
    printf("i: %d; elem: %p (%d); val: %p (%x)\n",
           i, (void*)elem, *elem, val, *(int*)val);
  }

  for (i = -1; i < 6; i++) {
    val = tfind(&i, &root, fx);
    printf("i: %d; ", i);
    if (val) {
      printf("@%p (%x)\n", val, *(int*)val);
    } else {
      printf("NOT FOUND\n");
    }
  }

  return 0;
}

Running it outputs

i: 0; elem: 0xcb8010 (0); val: 0xcb8030 (cb8010)
i: 1; elem: 0xcb8060 (0); val: 0xcb8030 (cb8010)
i: 2; elem: 0xcb8080 (1); val: 0xcb80a0 (cb8080)
i: 3; elem: 0xcb80d0 (1); val: 0xcb80a0 (cb8080)
i: 4; elem: 0xcb80f0 (2); val: 0xcb8110 (cb80f0)
i: 5; elem: 0xcb8140 (2); val: 0xcb8110 (cb80f0)
i: 6; elem: 0xcb8160 (3); val: 0xcb8180 (cb8160)
i: 7; elem: 0xcb81b0 (3); val: 0xcb8180 (cb8160)
i: 8; elem: 0xcb81d0 (4); val: 0xcb81f0 (cb81d0)
i: 9; elem: 0xcb8220 (4); val: 0xcb81f0 (cb81d0)
i: -1; NOT FOUND
i: 0; @0xcb8030 (cb8010)
i: 1; @0xcb80a0 (cb8080)
i: 2; @0xcb8110 (cb80f0)
i: 3; @0xcb8180 (cb8160)
i: 4; @0xcb81f0 (cb81d0)
i: 5; NOT FOUND

Apparently the values "inside the binary tree" are copies of pointers to the data. The copies are managed by the <search.h> functions and the data should be managed by the program.

The memory 0xcb8030 should be freed by a call to tdelete(), the corresponding 0xcb8010 (elem with value 0) should be freed by the program (as well as the previously lost 0xcb8060).

Answer 3

Matt, I think that your interpretation is correct. For individual deletion of elements this seems unavoidable. (But anyhow it is only a factor of 2 for an operation of \Omega \log N cost ;)

Long time that I didn't use these function, but looking through old code it looks that you can avoid part of the overhead if you destroy the tree all at once (if this is your case) by using two calls of twalk:

1. count the number N of elements in your tree with an appropriate call to twalk
2. allocate an array of size N of pointers to tree items
3. fill this array by a second twalk through the tree
4. run through this array and for each tree node first delete its data and then the node itself

If your really need such a thing you can find a thread safe C++ encapsulation of these calls in our library parXXL in the directory par/sys.