Found in 1 comment on Hacker News
svat · 2021-06-12 · Original thread
This may be a tangent but I've encountered this code comment before and been confused; nice to be able to reply to its author! The confusion is that there's no book by Knuth called "An Introduction to Data Structures With Applications" (and Knuth's TAOCP doesn't have a section 5.6; his Chapter 5 on Sorting ends with 5.5 and whatever stuff is in TAOCP about memory allocation is Chapter 2; page 501 would put you in "Answers to Exercises"). Most likely what was intended is the book "An Introduction to Data Structures With Applications" by Jean-Paul Tremblay and Paul G. Sorenson (https://www.amazon.com/dp/0070651574 , ISBN 0070651574, https://books.google.com/books?id=ha4mAAAAMAAJ) which from what I can find online has 7 chapters:

1. Information and its storage representation

2. The representation and manipulation of strings

3. Linear data structures and their storage representation

4. Linear data structures and their linked storage representation

5. Nonlinear data structures

6. Sorting and searching

7. File structures

And so Chapter 5 probably has a 5–6.2 and 5–6.3 that cover such a memory allocation algorithm.

Edit: I found a weird plagiarized/condensed version of the book online, and section 5.6 is indeed called "Memory Allocation; Garbage Collection", so quite likely that the book by Tremblay and Sorenson is what is meant.

Fresh book recommendations delivered straight to your inbox every Thursday.