home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / std / cplus / 1805 < prev    next >
Encoding:
Text File  |  1992-12-16  |  3.2 KB  |  84 lines
  1. Newsgroups: comp.std.c++
  2. Path: sparky!uunet!munnari.oz.au!metro!extro.ucc.su.OZ.AU!maxtal
  3. From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
  4. Subject: Re: Zero-length structures and pointer comparisons
  5. Message-ID: <1992Dec16.152718.8056@ucc.su.OZ.AU>
  6. Sender: news@ucc.su.OZ.AU
  7. Nntp-Posting-Host: extro.ucc.su.oz.au
  8. Organization: MAXTAL P/L C/- University Computing Centre, Sydney
  9. References: <1992Dec11.212831.19493@bcrka451.bnr.ca> <5366@miramon.lulea.trab.se> <1992Dec14.230730.24452@microsoft.com>
  10. Date: Wed, 16 Dec 1992 15:27:18 GMT
  11. Lines: 71
  12.  
  13. In article <1992Dec14.230730.24452@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
  14. >In article <5366@miramon.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
  15. >
  16. >What if ptrcmp [addrcmp] were allowed to return 0 for those objects
  17. >and/or systems that don't define an ordering for those objects?
  18. >
  19.  
  20.     Given a set of pointers p1, p2, p3, and some function f,
  21. we require that
  22.  
  23.     f(p1), f(p2), f(p3)
  24.  
  25. be a total order, and returning 0 always is clearly a trivial
  26. total order *of f(p)* in that case.
  27.  
  28.     Dag wanted to have
  29.  
  30.     p1 == p2  <==> ptrcmp(p1,p2)==0    (DC)
  31.  
  32. and this imposes some constraint on 'f' which would certainly
  33. mean that returning 0 always was not a total order.
  34.  
  35. Taking 'f' to be the underlying bits of a pointer makes 
  36. ptrcmp fast and useful, but DC will not be satisfied on
  37. the 8086.
  38.  
  39. The purpose of ptrcmp, surely, is to allow say sorting or btree
  40. algorithms to be applied to pointers AT ALL. It really
  41. doesnt matter what the order produced actually is.
  42. What's important is that the damn algorithms 
  43. work correctly, for example terminate in the case of a sort,
  44. or retrieve the pointer from a btree.
  45.  
  46. A completely randomly chosen total order will work for
  47. any algorithm not requiring equality tests.
  48. Sorts not requiring uniqueness will work.
  49.  
  50. Btrees require uniqueness so wont. They need condition DC.
  51. Otherwise they mnay fail to put some things into the tree
  52. (thinking there is duplication) and put others in twice
  53. (finding duplication where not intended).
  54.  
  55. So... how about TWO functions :-)
  56.  
  57.     anytorder(void*,void*); // might give 0 always
  58.     obeysDC(void*,void*); // must obey DC above
  59.  
  60. Now it was ALSO suggested that if < implement a partial
  61. order, the total order be compatible with it.
  62. If I remember my maths, this can always be done
  63. (assuming < is a partial order ... have to go back
  64. to my maths books and 8086 manuals here :-)
  65.  
  66. Anyhow, can we list all the possible reasonable functions,
  67. what properties they have, what the implications are, then
  68. pick a standard set for inclusion in the library?
  69.  
  70. Furthermore, we can also have an optional set, the condition
  71. is that they must have the listed properties IF they are
  72. implemented, otherwise they must NOT be implemented.
  73. (Or, they are all implemented, but might cause exceptions
  74. if not defined .. if you know what I mean :-)
  75.  
  76. That ensures that correct code will either work or
  77. fail gracefully, rather than yielding unexpected results.
  78.  
  79. -- 
  80. ;----------------------------------------------------------------------
  81.         JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
  82.     Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
  83. ;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------
  84.