home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compiler / 1887 < prev    next >
Encoding:
Text File  |  1992-11-16  |  1.4 KB  |  34 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: wendt@CS.ColoState.EDU (alan l wendt)
  4. Subject: Re: Modulo n arithmetics
  5. Reply-To: wendt@CS.ColoState.EDU (alan l wendt)
  6. Organization: Colorado State University, Computer Science Department
  7. Date: Sun, 15 Nov 1992 16:39:06 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-11-078@comp.compilers>
  10. Followup-To: comp.programming
  11. Keywords: arithmetic
  12. References: <92-11-029@comp.compilers> <92-11-043@comp.compilers>
  13. Sender: compilers-sender@iecc.cambridge.ma.us
  14. Lines: 18
  15.  
  16. Speaking of modulo-n buffering systems.  This is really the wrong group
  17. but I cannot help mentioning that the traditional head-and-tail pointer
  18. technique for circular buffering is the wrong way to do it.  The problem
  19. is that head==tail can mean that the queue is empty or that the queue is
  20. full, so most implementations waste a queue entry so that the queue never
  21. really gets full.
  22.  
  23. If the algorithm maintains the queue head pointer and the queue length,
  24. instead of head and tail, the two cases can be disambiguated easily!
  25.  
  26. Horowitz & Sahni (Fundamentals of Computer Algorithms) suggest that one
  27. might maintain an additional boolean to disambiguate the two situations,
  28. which I take as evidence that this idea is not widely disseminated.
  29.  
  30. Alan Wendt
  31. -- 
  32. Send compilers articles to compilers@iecc.cambridge.ma.us or
  33. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  34.