A NOTE has been added to this issue. 
====================================================================== 
http://austingroupbugs.net/view.php?id=1011 
====================================================================== 
Reported By:                EdSchouten
Assigned To:                ajosey
====================================================================== 
Project:                    1003.1(2008)/Issue 7
Issue ID:                   1011
Category:                   System Interfaces
Type:                       Enhancement Request
Severity:                   Comment
Priority:                   normal
Status:                     Under Review
Name:                       Ed Schouten 
Organization:                
User Reference:             Nuxi 
Section:                    search.h 
Page Number:                323 
Line Number:                10822 
Interp Status:              --- 
Final Accepted Text:         
====================================================================== 
Date Submitted:             2015-12-10 13:46 UTC
Last Modified:              2016-10-13 15:35 UTC
====================================================================== 
Summary:                    Make the binary search tree functions friendlier to
use: require balancing, add typing and allow destruction
======================================================================
Relationships       ID      Summary
----------------------------------------------------------------------
related to          0000551 Clarify behavior when root node is dele...
====================================================================== 

---------------------------------------------------------------------- 
 (0003410) rhansen (manager) - 2016-10-13 15:35
 http://austingroupbugs.net/view.php?id=1011#c3410 
---------------------------------------------------------------------- 
(The following page and line numbers are based on document C165, the merged
Issue 7+TC2 document.)

On page 327 after line 11111 (XBD <search.h> description), insert the
following new paragraph:<blockquote>The <b><search.h></b> header shall
define via typedef the <b>posix_tnode</b> type as an alias for
<b>void</b>.</blockquote>
On page 327 lines 11123-11130 (XBD <search.h> description),
change:<blockquote><pre>void *tdelete(const void *restrict, void
**restrict,
         int(*)(const void *, const void *));
void *tfind(const void *, void *const *,
         int(*)(const void *, const void *));
void *tsearch(const void *, void **,
         int(*)(const void *, const void *));
void twalk(const void *,
         void (*)(const void *, VISIT, int
));</pre></blockquote>to:<blockquote><pre>void *tdelete(const void
*restrict, posix_tnode **restrict,
    int (*)(const void *, const void *));
posix_tnode *tfind(const void *, posix_tnode *const *,
    int (*)(const void *, const void *));
posix_tnode *tsearch(const void *, posix_tnode **,
    int (*)(const void *, const void *));
void twalk(const posix_tnode *,
    void (*)(const posix_tnode *, VISIT, int));</pre></blockquote>
On page 327 line 11134 (XBD <search.h> rationale),
change:<blockquote>None.</blockquote>to:<blockquote>Earlier versions of
this standard explicitly used <b>void</b> for both node and key references
where this version now uses <b>posix_tnode</b> for nodes and keeps
<b>void</b> in the text referring only to keys. In order to preserve
backwards compatibility, this version defines <b>posix_tnode</b> as an
alias for <b>void</b>.  The change was made to make the function prototypes
more easily understandable.</blockquote>
On page 2136 line 68415 (XSH tdelete synopsis) change:<blockquote><pre>void
*tdelete(const void *restrict key, void **restrict rootp,
    int(*compar)(const void *, const void *));
void *tfind(const void *key, void *const *rootp,
    int(*compar)(const void *, const void *));
void *tsearch(const void *key, void **rootp,
    int (*compar)(const void *, const void *));
void twalk(const void *root,
    void (*action)(const void *, VISIT,
int));</pre></blockquote>to:<blockquote><pre>void *tdelete(const void
*restrict key, posix_tnode **restrict rootp,
    int (*compar)(const void *, const void *));
posix_tnode *tfind(const void *key, posix_tnode *const *rootp,
    int (*compar)(const void *, const void *));
posix_tnode *tsearch(const void *key, posix_tnode **rootp,
    int (*compar)(const void *, const void *));
void twalk(const posix_tnode *root,
    void (*action)(const posix_tnode *, VISIT, int));</pre></blockquote>
On page 2136 line 68445-68446 (XSH tdelete description)
change:<blockquote>The variable pointed to by <i>rootp</i> shall be changed
if the deleted node was the root of the
tree.</blockquote>to:<blockquote>The variable pointed to by <i>rootp</i>
shall be set to a pointer to the new root of the tree if the root of the
tree was changed.</blockquote>
On page 2137 line 68478 (XSH tdelete return value) add a new
paragraph:<blockquote>In all cases where a pointer to a node is returned,
the structure pointed to by the return value is unspecified and shall not
be modified by the application, but it shall be possible to cast a
pointer-to-node into a pointer-to-pointer-to-element to access the element
stored in the node.</blockquote>
On page 2137-2139 line as below (XSH tdelete examples) change void * to
posix_tnode * on the following lines:<blockquote><pre>68494  void *root =
NULL;
68500  void *node;
68501  void print_node(const void *, VISIT, int);
68562  print_node(const void *ptr, VISIT order, int
level)</pre></blockquote>
On page 2139 line 68578 (XSH tdelete application usage)
change:<blockquote>Since the return value of <i>tdelete</i>() is an
unspecified non-null pointer in the case that the root of the tree has been
deleted, applications should only use the return value of <i>tdelete</i>()
as indication of success or failure and should not assume it can be
dereferenced.</blockquote>to:<blockquote>Since the return value of
<i>tdelete</i>() is an unspecified non-null pointer in the case that the
root of the tree has been deleted, applications should only use the return
value of <i>tdelete</i>() as indication of success or failure in this case
and should not assume it can be dereferenced. However, the only way that
applications can tell if this case may have occurred is by checking whether
the variable pointed to by <i>rootp</i> changed.  Since this variable can
change for other reasons (e.g., tree balancing), using the return value of
<i>tdelete</i>() as anything other than a boolean indicator is unreliable
at best and is discouraged.</blockquote>
On page 2139 line 68584 (XSH tdelete rationale)
change:<blockquote>None.</blockquote>to:<blockquote>Implementations are
encouraged to use balanced trees to reduce the depth of the trees that are
created and improve tree search times.</blockquote> 

Issue History 
Date Modified    Username       Field                    Change               
====================================================================== 
2015-12-10 13:46 EdSchouten     New Issue                                    
2015-12-10 13:46 EdSchouten     Status                   New => Under Review 
2015-12-10 13:46 EdSchouten     Assigned To               => ajosey          
2015-12-10 13:46 EdSchouten     Name                      => Ed Schouten     
2015-12-10 13:46 EdSchouten     User Reference            => Nuxi            
2015-12-10 13:46 EdSchouten     Section                   => search.h        
2015-12-10 13:46 EdSchouten     Page Number               => 323             
2015-12-10 13:46 EdSchouten     Line Number               => 10822           
2015-12-10 17:56 nsz            Note Added: 0002973                          
2015-12-11 14:26 weeks          Note Added: 0002975                          
2015-12-11 14:28 weeks          Note Edited: 0002975                         
2015-12-11 19:15 nsz            Note Added: 0002976                          
2015-12-11 21:19 nsz            Note Added: 0002977                          
2015-12-14 20:19 shware_systems Note Added: 0002978                          
2016-08-18 16:27 nick           Relationship added       related to 0000551  
2016-09-01 14:10 shware_systems Note Edited: 0002978                         
2016-09-14 14:22 emaste         Issue Monitored: emaste                      
2016-10-13 15:35 rhansen        Note Added: 0003410                          
======================================================================


Reply via email to