home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / cplus / 12439 < prev    next >
Encoding:
Internet Message Format  |  1992-08-17  |  1.8 KB
  1. Path: sparky!uunet!gumby!wupost!think.com!barmar
  2. From: barmar@think.com (Barry Margolin)
  3. Newsgroups: comp.lang.c++
  4. Subject: Doubly-linked list trick (was Re: Garbage Collection for C++)
  5. Date: 17 Aug 1992 19:49:54 GMT
  6. Organization: Thinking Machines Corporation, Cambridge MA, USA
  7. Lines: 31
  8. Message-ID: <16ovt2INN3nq@early-bird.think.com>
  9. References: <1992Aug14.021547.15215@news.mentorg.com>> <DAVEG.92Aug14194411@synaptx.synaptics.com> <2009@appli.se>
  10. NNTP-Posting-Host: telecaster.think.com
  11.  
  12. In article <2009@appli.se> niklas@appli.se (Niklas Hallqvist) writes:
  13. >When you want to do a doubly linked list to the cost of a singly
  14. >linked one (i.e. in mem. space).  Instead of having two pointers
  15. >for the link in each node, take the "previous" and "next" pointers
  16. >and XOR them, and store the result!
  17.  
  18. Problems:
  19.  
  20. 1) XOR isn't defined for pointers in C/C++.
  21.  
  22. 2) You could cast the pointers to suitably large integers and XOR those,
  23. but the result of casting the integers back into pointers is
  24. implementation-dependent or undefined (I don't remember which, but either
  25. way it's not portable).
  26.  
  27. 3) It's only useful if you always traverse the list from one end or the
  28. other, since you need to know what to XOR each combined pointer with in
  29. order to get one of the original pointers.  But one of the main reasons for
  30. using a doubly-linked list is so that you can start with any entry in the
  31. list and get to the rest.
  32.  
  33. 3a) In particular, how would you do a circular doubly-linked list with this
  34. scheme?  When it starts out, the node's previous and next pointers would
  35. both be the same (they point to itself) and the result of the XOR would be
  36. 0.  But that's also the result when the circular list has two elements,
  37. since the previous and next nodes would always be the "other" node.
  38. -- 
  39. Barry Margolin
  40. System Manager, Thinking Machines Corp.
  41.  
  42. barmar@think.com          {uunet,harvard}!think!barmar
  43.