Austin Group Defect Tracker

Aardvark Mark IV

Main | My View | View Issues | Change Log | Docs
  

Viewing Issue Simple Details [ Jump to Notes ] [ Issue History ] [ Print ]
ID Category Severity Type Date Submitted Last Update
0000551 [1003.1(2008)/Issue 7] System Interfaces Editorial Clarification Requested 2012-03-30 16:34 2019-06-10 08:55
Reporter weeks View Status public  
Assigned To ajosey
Priority normal Resolution Accepted As Marked  
Status Closed  
Name Nathan Weeks
Organization USDA-ARS
User Reference
Section tdelete, tfind, tsearch, twalk
Page Number 2097-2099
Line Number 66353-66354,66389-66446,66451
Interp Status ---
Final Accepted Text see Note: 0001188
Summary 0000551: Clarify behavior when root node is deleted with tdelete() & binary search tree example
Description 1. There is a typo in the Application Usage section.

2. The standard states:

   "The variable pointed to by rootp shall be changed if the deleted
   node was the root of the tree."

   When the deleted node the root of the tree, and it has no children, the
   behavior Mac OS X 10.7, Cygwin 1.7.11-1, Solaris 10, RHEL 5.4, and FreeBSD
   9.0 (the environments in which I tested the attached examples) in this case
   is to set the variable pointed to by rootp to a null pointer. This allows
   the deletion of an entire (sub)tree using only a pointer to the root node;
   e.g.:

      while (rootp != NULL)
          tdelete(*(struct node **)rootp, &rootp, compar);

   Or, if memory for each element must be deallocated:

      typedef ... ELEMENT;
      ...
      while (rootp != NULL) {
          element = *(ELEMENT **)root;
          tdelete((void *)element, &rootp, delete_root);
          free(element);
      }

   glibc contains the tdestroy() routine to efficiently delete all nodes in a
   tree given only a pointer to root node. Without the above guarantee, other
   implementations require the application to maintain a list of all elements
   to use as "key" arguments to tdelete(), or to use twalk() to build such a
   list before deleting the (sub)tree.

3. There are few publicly-available examples demonstrating the use of these
   functions, and the details regarding pointer usage are easy to misinterpret.
   The example could be expanded to lower the barrier to entry for these
   functions.
Desired Action 1. Change

   "The tsearch() function uses preorder, postorder, and endorder..."

   to

   "The twalk() function uses preorder, postorder, and endorder..."

2. After

   "The variable pointed to by rootp shall be changed if the deleted
   node was the root of the tree."

   add

   "If the deleted node was the root of the tree and had no children, the
   variable pointed to by rootp shall be set to a null pointer."

3. Expand the example to include the use of tdelete() to delete an entire
   tree as in #2. I've attached two examples; feel free to incorporate any
   ideas you may find useful from either. The first (tree1.c) is a
   conservative modification of the existing example that implements the
   following changes:

   I. Check the return value of tsearch() to see if a node containing that element
       was previously inserted, and, if so, don't unnecessarily save a
       duplicate copy of the data.
   II. Use tdelete() in a loop to delete the entire tree.

   The second example implements the changes in tree1.c, and:

   I. Change "struct node" to "struct element" to emphasize the distinction
        between the nodes that are controlled by
        tsearch()/tdelete()/tfind()/twalk(), and the user-created data. This
        version stores the number of times the input string has been seen
        ("count") instead of the length of the string.

   II. Use dynamic memory allocation for the elements to emulate how these
        routines will typically be used in practice. When deleting the tree,
        this requires that the memory of the element be freed before invoking
        tdelete() on the node that points to it, as this example does not
        separately store pointers to the elements.

   III. Use a more efficient comparison function when explicitly deleting the
        root node.

   IV. gets() has been marked obsolescent in issue 7, has been removed from
        C11, and causes compiler/linker warnings on various systems when it is
        used. This example uses fgets(); getline() might be used instead.
Tags tc2-2008
Attached Files c file icon tree1.c [^] (2,000 bytes) 2012-03-30 16:34
c file icon tree2.c [^] (2,649 bytes) 2012-03-30 16:34

- Relationships
related to 0001011Appliedajosey Make the binary search tree functions friendlier to use: require balancing, add typing and allow destruction 

-  Notes
(0001188)
eblake (manager)
2012-04-05 15:35

 At line 66450 (page 2099), change 'tsearch' to 'twalk'.

At line 66353 (page 2097), after the sentence:
"The variable pointed to by rootp shall be changed if the deleted node was the root of the tree."
insert a new sentence:
"If the deleted node was the root of the tree and had no children, the variable pointed to by rootp shall be set to a null pointer."

At lines 66392-66446, replace the example program with:

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

struct element { /* Pointers to these are stored in the tree. */
    int count;
    char string[];
};

void *root = NULL; /* This points to the root. */

int main(void)
{
    char str[_POSIX2_LINE_MAX+1];
    int length = 0;
    struct element *elementptr;
    void *node;
    void print_node(const void *, VISIT, int);
    int node_compare(const void *, const void *),
           delete_root(const void *, const void *);

    while (fgets(str, sizeof(str), stdin)) {
        /* Set element. */
        length = strlen(str);
        if (str[length-1] == '\n')
            str[--length] = '\0';
        elementptr = (struct element *)malloc(sizeof(struct element)
                                              + length + 1);
        strcpy(elementptr->string, str);
        elementptr->count = 1;
        /* Put element into the tree. */
        node = tsearch((void *)elementptr, &root, node_compare);
        if (node == NULL) {
            fprintf(stderr,
                    "tsearch: Not enough space avaialble\n");
            exit(EXIT_FAILURE);
        }
        else if (*(struct element **)node != elementptr) {
            /* A node containing the element already exists */
            (*(struct element **)node)->count++;
            free(elementptr);
        }
    }
    twalk(root, print_node);

    /* Delete all nodes in the tree */
    while (root != NULL) {
        elementptr = *(struct element **)root;
        printf("deleting node: string = %s, count = %d\n",
               elementptr->string,
               elementptr->count);
        tdelete((void *)elementptr, &root, delete_root);
        free(elementptr);
    }

    return 0;
}

/*
 * This routine compares two nodes, based on an
 * alphabetical ordering of the string field.
 */
int
node_compare(const void *node1, const void *node2)
{
    return strcmp(((const struct element *) node1)->string,
        ((const struct element *) node2)->string);
}

/*
 * This comparison routine can be used with tdelete()
 * when explicitly deleting a root node, as no comparison
 * is necessary.
 */
int
delete_root(const void *node1, const void *node2)
{
    return 0;
}

/*
 * This routine prints out a node, the second time
 * twalk encounters it or if it is a leaf.
 */
void
print_node(const void *ptr, VISIT order, int level)
{
    const struct element *p = *(const struct element **) ptr;


    if (order == postorder || order == leaf) {
        (void) printf("string = %s, count = %d\n",
            p->string, p->count);
    }
}
(0001189)
eblake (manager)
2012-04-05 15:37

 Although the desired action adds a new normative requirement, it is felt that all implementations already comply and no interpretation is required.

- Issue History
Date Modified Username Field Change
2012-03-30 16:34 weeks New Issue
2012-03-30 16:34 weeks Status New => Under Review
2012-03-30 16:34 weeks Assigned To => ajosey
2012-03-30 16:34 weeks File Added: tree1.c
2012-03-30 16:34 weeks Name => Nathan Weeks
2012-03-30 16:34 weeks Organization => USDA-ARS
2012-03-30 16:34 weeks Section => tdelete, tfind, tsearch, twalk
2012-03-30 16:34 weeks Page Number => 0
2012-03-30 16:34 weeks Line Number => 0
2012-03-30 16:34 weeks File Added: tree2.c
2012-03-30 17:02 Don Cragun Page Number 0 => 2097-2099
2012-03-30 17:02 Don Cragun Line Number 0 => 66353-66354,66389-66446,66451
2012-03-30 17:02 Don Cragun Interp Status => ---
2012-04-05 15:35 eblake Note Added: 0001188
2012-04-05 15:37 eblake Final Accepted Text => see Note: 0001188
2012-04-05 15:37 eblake Note Added: 0001189
2012-04-05 15:37 eblake Status Under Review => Resolved
2012-04-05 15:37 eblake Resolution Open => Accepted As Marked
2012-04-05 15:37 eblake Tag Attached: tc2-2008
2016-08-18 16:27 nick Relationship added related to 0001011
2019-06-10 08:55 agadmin Status Resolved => Closed

Mantis 1.1.6[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker