Þ   briarpig  » thorn  » demos  » stack

     This problem statement uses definitions of box and peg from top column right, meaning gc node and gc arc. Briefly, everywhere you see "box" you can substitute "gc object."

     When Wil writes a dynamic language in C or C++ (for example, a Lisp implemenation) he finds his C/C++ code refers to objects called boxes living in gc space (garbage collection space) subject to gc, which can move boxes while he's using them. Two basic problems must be addressed in such cross language reference:

• preventing gc on boxes while used, and
• tracking new location when a box moves

     To prevent a box from being collected, it must be reachable from a garbage collection root (gc root or just "root" for short) so new and old boxes used in C must be guaranteed reachable in gc to prevent them vanishing at the next point gc can occur, which in some gc systems is the next allocation point.

     To track where a box in gc space is located now, if gc can move it, Wil's C++ code must put the peg pointing at that box in a root where gc updates the peg when a box moves. So a root safely addresses both problems: reachability under gc and current pointer address after moves.

     The purpose of the stack object described on this page is to act as an efficient collection of many gc roots at once, with reachable peg slots allocated in contiguous vectors called frames because they simulate the purpose and use of call frames for functions in programming languages.

     Because this problem has many degrees of freedom in choice of framing the problem itself, framing approaches to solving it, and framing metaphors in explanation, much of this demo will be written as a fictional dialog to help capture an elusive nature of options where no tactic is best or most clear.

     However, keep these essential factors in mind:

• more than one language is involved
• convenient use in C++ is emphasized here
• a stack of gc roots can mimic a thread stack
• call frames for code languages are related
• readers and interpreters are usage contexts
• Wil likes to use pages allocated from a pile
• incremental stacks are better than monolithic
• Wil remembers 68K assembler's LINK & UNLK
• either good docs or diagrams would help a lot
• fancy mechanics are overkill that will do harm
• unbounded stack growth should be curtailed
• Some folk may confuse yp pegs and yP pages
• Lower p is peg or pointer while upper P is page
• Wil calls this gc root stack a box pointer array
• Unlike vectors, Wil's arrays are discontiguous

     "Want to help walk through a stack design?" Wil asked.

     "Not really," Stu admitted. "I'm only barely interested in mechanics of gc roots. Will this be boring?"

     "Probably," Wil conceded. "But we can go fast, and some parts might help you do things later with pages."

     "Ugh," Stu clenched his eyes closed. "Okay. But I reserve the right to quit. Why do you call it an array?"

     "Terms array and vector are synonyms," Wil explained, "so in þ I use vector to mean a contiguous sequence; but an array might be discontiguous. So ybpa ends with a for array."

     "Because it represents your gc root 'stack' with more than one page as it grows?" Stu guessed.

     "Yep," Wil nodded. "And each page can hold up to 1024 pointers in a 4K page when pointers are 32-bits."

     "This array is an array of what again?" Stu asked. "Box pointers? And those are called pegs in your jargon?"

     "Yes," Wil confirmed. "But in addition to pegs, each page must also include some markup for framing, to show groups of pegs allocated together in batches, and so we can see how much of each page is used."

     "Is this markup text?" Stu asked. "Or more pointers? It sounds like more pointers since you have a pointer array."

     "That's right," Wil agreed. "The non-peg markup is more pointers, which point into each page to frame groups of allocated pegs. I bet you need a diagram right about now?"

     "That would be nice," Stu grinned. "I'm almost lost. How does your garbage collecter tell peg pointers apart from the surrounding markup pointers? Does it matter?"

     "It matters very much," Wil replied. "For gc to successfully copy reachable boxes, it must be able to tell slots that are pegs apart from slots holding stack frame markup."

     "Well how then?" Stu prompted. "Do you mark the pointers with magic tag bits or something?"

     "No, immediate peg values use tag bits to distinguish themselves from box pointers," Wil explained. "The markup pointers look just like box pointer except for one detail."

     "Is this a brain teaser?" Stu asked. "What's the detail?"

     "Framing markup pointers point into the page," Wil expanded. "Box pointers point somewhere else. Very simple."

     "That's kinda clever," Stu granted. "Does the framing use any pointers from one page to another?"

     "No," Wil wagged a cautionary finger. "I could do that if I wanted to chain stack frames across pages. But it would make the test for peg more expensive. So stack frame pointers only point into the same page containing the frame pointers."

     "Okay sure," Stu nodded. "Where's my diagram? Show me how it looks in one page — say the first page."

     "But your pointers have only two hex digits," Stu observed. "Is that a simplification?"

     "Yes, please bear with me," Wil began. "This figure shows one page at address 0xc0 as if that were page-aligned. Just pretend a page needs to align only the low four bits, and that each page contains just sixteen 8-bit pointers as shown."

     "Labeled by addresses 0xc0 through 0xcf?" Stu asked. "What about four byte alignment of each pointer?"

     "Yes, the pointers are four-byte aligned in 32-bit pointers," Wil granted. "But this figure doesn't show that. I just wanted to give extremely short addresses to each pointer slot. Pretending pointers are byte sized gives tiny addresses."

     "Well it worked," Stu agreed. "Now what does this mean? It looks like the first 0xc0 slot points at the 0xcc slot."

     "Yes," Wil nodded. "The first slot of each page contains a pointer to the highest used slot in the page."

     "Which is 0xcc?" Stu asked. "Does that mean 0xcd, 0xce, and 0xcf are unused? Does gc use this info?"

     "Yes," Wil replied. "Any gc code can see no slots above 0xcc are used, and can be ignored. Slot 0xcc holds the highest stored frame pointer in the page, chaining in a list back to 0xc0 like this: cc->c7, then c7->c3, then c3->c0, for three frames in all."

     "Is that a frame pointer list?" Stu asked. "Each frame pointer points where the last frame pointer value is located?"

     "That's right," Wil pointed at 0xc7. "When the topmost frame is popped, the new page frame pointer is 0xc7 and that gets stored in the slot at 0xc0."

     "Showing all slots above 0xc7 are no longer used," Stu anticipated. "I get it. I take it this figure C was created by three frame allocations of two slots, then three, and four?"

     "Yes, and I put dots in peg slots allocated to a caller, holding either box pointers or immediate constants," Wil said.

     "What happens if I now try to allocate a frame of five peg slots?" Stu asked. "That won't fit in this page, will it?"

     "That allocates a new page to hold a five slot frame," Wil replied. "Here's a new figure showing a new page at 0xd0."

     "Oh, I get it," Stu smiled. "Then you keep the pages in a stack. When this five slot frame in page 0xd0 is popped, you not only pop the frame but the entire page from the stack?"

     "Bingo," Wil grinned back. "Start to sound easy yet?"

     "But you haven't shown what keeps track of pages yet," Stu observed. "Where's the stack of pages? Inside ybpa?"

     "Yes," Wil sighed. "I guess we should start a class declaration for ybpa now. But we can build it up slowly, in pieces."

class ybpa «

     "First note ybpa subclasses yqe," Wil showed Stu. "This is so a virtual machine can add each stack to a list of gc root containers associated with a gc address space."

     "What's this maxP constant?" Stu asked. "Is that max pages in one stack? Is that enough?"

     "Yes, maxP is the most pages one ybpa can hold right now," Wil explained. "That doesn't sound like much, does it?"

     "No, not really," Stu looked worried. "What about stack overflow? That's, uh, sixteen thousand pointers?"

     "We have to pick some number," Wil justified. "We can double it or more. But think of it this way: a typical stack frame might add two or three peg slots to a stack for reachable roots."

     "And your point would be ...?" Stu prompted.

     "You're thinking of a stack limited to just 64K, right?" Wil asked Stu, who nodded. "But actually these roots will point at more room allocated in gc space. These roots are just anchor points."

     "Ah, just the tip of a stack iceberg?" Stu guessed.

     "Yes, and typically a gc root stack might be reserved for a specific recursive data set," Wil elaborated. "Not everything you associate with a stack. So a 64K stack is big."

     Stu looked acutely bored. Wil quickly moved on.

array frame «

     "What's this nested ybpa::Af object?" Stu asked.

     "It's a nested class, as you noticed," Wil introduced. "It just defines a struct pointing to another instance of itself."

     "What's it good for?" Stu prompted.

     "Remember the frame pointers we showed inside a page format?" Wil reminded. Stu nodded. "Well those have type Af* in the sense each points to another frame pointer."

     Stu held up a hand. "Please proceed," he requested. "Do you declare a constant for how many pointers are in a page?"

     "Here it is," Wil produced ybpa::pmax —

     "Don't confuse this pmax count of pointers in a page with earlier maxP max pages in the stack," Wil warned.

     "I assume pages are allocated from a pile?" Stu asked.

     "Yes, pile a_H is source of all pages used," Wil showed.

page stack «

     "Aha, there's the page stacks I was expecting," Stu noticed. "So a_vnh is the array's vector of node handles? And a_vnh is the vector of yP pages? Are both vectors really needed?"

     "Yes, vector a_vnh[] holds handles with refs keeping pages in a_vP[] alive," Wil confirmed. "We just need a_vnh[] to hold refs, but a_vP[] takes up little space and makes code explicit."

     "How do you know how many pages are allocated?" Stu asked.

     "Stack pointer a_sp points at the next available slot in a_vP so their difference, a_sp-a_vP, is the number of pages in the array," Wil explained.

     "Does that cover everything?" Stu asked. "Why are there more members still coming below?"

     "Technically," Wil admitted, "the topmost yP page in the stack contains everything we need to know, since the first slot holds the frame pointer in that page. And from that we can infer everything else. But resulting code might be hard to follow."

     "So you redundantly re-described how the page is interpreted, using the members below?" Stu guessed.

     "More or less," Wil agreed. "This helped define the format in my first draft, because I didn't write the long explanation with the figures you saw earlier."

     "Oh, I see," Stu nodded. "Without figures and explanations, the topmost page used alone would be mystifying by itself. So you reified the frame pointer idea as a member?"

frame pointer «

     "Yes, frame pointer a_fp contains the same value as the first slot in the topmost stack page in ybpa," Wil verified.

     "Sounds irritating to keep in sync," Stu winced.

     "Keeping it in sync is like documentation," Wil countered. "So code can assert the true meaning of each page's first slot."

     "Or it will look like gobbletygook," Stu complained.

     "I admit it took as long to figure out what this stack code does as it took to write the first time," Wil sighed.

     "Maybe it'll go faster next time now you've written this dialog," Stu suggested.

     "That's exactly the idea," Wil affirmed. "Let's go on to the conventional origin, cursor, and max members next.

buffer triple «

     "You do this a lot, right?" Stu asked. "You use triple (o_0, o_p, o_x) in the out demo, and triple (i_0, i_p, i_x) in the in demo. I take it this triple (a_0, a_p, a_x) in the array is similar?"

     "Yes, the zero member a_0 is always the start of a buffer," Wil confirmed. "It's the origin: the first page slot in this case."

     "It's the same as the page address in the top yP of the stack?" Stu guessed. "What a mouthful — a_0 abbreviates that?"

     "Yes and pointer member a_p is always a cursor," Wil continued. "Here it's the next free slot in the top stack page."

     "And max member a_x is always one past the last usable slot," Stu remembered. "So here the difference of a_x and a_p is the remaining number of slots in the top page?"

     "That's right," Wil congratulated. "Let's look at the last example figure we saw earlier, but with these members added."

     "That's what I thought," Stu was pleased. "But you didn't show a_sp — I guess it points above the slot for this page. Should we go on to inline methods now? How do you test is-empty?"

     "First let's finish private members," Wil begged. "The next three track statistics. Number of frames added and removed are counted by a_up and a_down, while a_min is a low water mark in available array slots, showing how full the stack ever got."

usage stats «

     "I guess you have public getters for those?" Stu asked.

     "Sure, let's start the public api," Wil replied.

     "I see amax() is constant," Stu observed. "And values of a_up and a_down clearly just count frames we add and remove. But how does the value of a_min for amin() get populated?"

     "Method alow() above approximates number of pointers left in a current page and potential pages above," Wil said. "This value goes into a_min when it hits a new low."

     "Aproximates?" Stu asked. "Looks exact to me."

     "I think the current page actually has room for a_x-a_p+1 pointers," Wil explained, "because a slot at a_p is empty."

     "Well, to allocate a new frame, you'd need space to write one more frame pointer too," Stu observed. "Any more methods like sp_left() starting with sp_ instead of a?"

     "A couple," Wil nodded. "Full and empty predicates."

full and empty «

     Stu considered. "Since you have a_sp specific methods, do you also need a_fp frame pointer methods too?" Stu asked.

     "Yes, the very same predicates about the current page alone instead of all the pages," Wil replied.

     "Except I see you didn't count the pointer at empty slot a_p once again," Stu noticed.

     "Yes," Wil confirmed. "But to use any pointers left as a frame, you'd have to use one to store a new frame pointer."

     "Then why write N+1 in fp_full() below?" Stu asked.

     "Uh," Wil looked closely. "You're right. I should probably take off the extra +1 and just write N. I worry about folks tweaking the code later though, removing the extra slot."

     "No biggy," Stu waved. "Let's go on. Why do you define aprevPage() next? What's it for?"

     "It's only used in logging," Wil expained, "when unlinking a frame, if it doesn't appear to be in the same page as a_0 where it should be. Maybe the caller skipped a frame."

     "You should prevent skipped frames on unlink using one of those RAII guard thingies you like," Stu advised.

     "I do have a guard class," Wil pointed out. "We just haven't gotten to it yet. Still it's good to log any error context."

link and unlink «

     "Hey, well what do you know!" Stu exclaimed. "We finally hit the methods fulfilling the purpose of ybpa, didn't we? Are these how frames of pegs are allocated from the stack?"

     Yes, alink() allocates and aunlink() later frees," Wil said. "The arg passed to aunlink() must match the last return from alink() or else an assert fires."

     "Ouch, can't you make that safer?" Stu wondered.

     "Yes, using guard class ybpvg shown a bit further below (cf ») instead of linking and unlinking directly," Wil said.

make and unmake «

     "I suppose clearing the array frees all pages and empties the stack?" Stu guessed.

     "That's right," Wil confirmed. "But it's not a good idea to use explicitly much. The destructor uses it."

     "The constructor takes a pile argument as the source of all pages allocated," Wil remarked.

     "When should the destructor execute?" Stu asked. "Can I allocate ybpa on the heap?"

     "That's a good question," Wil encouraged. "A heap based ybpa will work, but isn't the normal use case I expect, which is stack-based ybpa arrays used in recursive code declaring ybpvg guards in nested calls, unwinding later with a C++ stack."

     "Something seems strange about that," Stu squinted.

     Wil nodded. "The strange part is calling a C++ method to do part of a dynamic language's runtime," he suggested.

     "That's it!" Stu recognized. "Suddenly your stack class seems more like the work of a nutjob."

     Wil sighed. "Well, I plan to have more C++ influence than many folks would," he explained. "It particular, it will help with some bootstrapping code used as scaffolding, which can be removed later with equivalents written in the hosted dynamic language. Still sound like a nutjob?"

     Stu shrugged. "I wouldn't work that hard," he said.

printing api «

     "These printing methods are like your boilerplate in other demos, using api shown in the out and quote demos — am I close?" Stu guessed with mock eagerness.

     "I know, I say virtually the same thing lately at this point in demos," Wil admitted. "But you needn't rub it in."

     "A little suffering is good for your humility," Stu suggested. "I thought you might be running low."

     "Hmm," Wil mused. "Repetition makes you so cranky."

     "I'm going to become allergic to this boilerplate after seeing it so many times," Stu warned.

     "Come on," Wil coaxed. "I know you like the sample output in demos. Where else will it come from?"

class ybpvg «

     "Here's my shiny RAII guard class used with ybpa," Wil introduced. "You use the constructor instead of alink(), then the destructor automatically calls aunlink()."

     "What does the name mean?" Stu asked.

     "It means thorn box pointer vector guard," Wil replied. "Because a frame is contiguous, a frame is a vector of pegs and not an array. It guards only that one frame."

     "Not the whole array — I get it," Stu assured.

     "It's all inlines," Stu noticed. "Even so, the destructor still runs when you leave the scope in which ybpvg is declared?"

     "You know it does," Wil nudged. "Even if an exception is thrown — not that I encourage you to use exceptions in any shape, way, or form."

     "All the non-inline methods are for class ybpa then?" Stu asked. "Where are they? Right column?"

     "Yeah," Wil nodded. "Let's move over to the right column now to continue with code (cf »)."

     All this code is available only under the BriarPig mu-babel license described fully on the rights page. You do not have permission to reprint this page in any way. Neither feeds nor repackaging is allowed. You can link this page if you want folks to read it.

     thorn: todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack « Þ, atomic, lock, mutex, thread, map, meter, list, iter, ctype

     (mu: toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile)

     Some demos are stubs: todo is a demo guide. See toy for mu updates on language pages; names introduces naming schemes.

     Two definitions might greatly clarify this page's text, so you are asked to learn two short words about state subject to gc (garbage collection) corresponding to nodes and arcs in graphs:

     An object allocated in gc space is called a box. A box is the equivalent of struct in C and C++, and in fact a struct is used to represent each box format. Living in gc space is what makes a struct a box: it's subject to garbage collection. (This use of the term box is common to many gc systems: it's conventional.)

     A pointer to a box is called a peg when this pointer is stored somewhere in gc space. One box refers to another by means of a peg. A peg is almost identical in meaning to a C pointer, so it really just means pointer with this added: to a box. Except a peg can also hold an immediate value like a specially coded integer instead of a box pointer, collapsing state desired into the peg itself because it's small instead of consuming another box. (This use of the term peg is unique to Wil: it's unconventional.)

     If you think of computing systems as modeling graphs using nodes for vertices and arcs for edges, then a box is a graph node and a peg is a graph arc or edge. As a special case in optimization, a peg can represent a small literal node value immediately to mean things like nil or integers 1, 2, and 3, etc. (The special case of literal immediate in a peg can always be drawn as a graph with node value apart from the arc.)

     Wil coined the term peg around the year 2000 when thinking of a box as a collection of slots that contain values: it's a metaphor that means something that goes in slot, the same way you can stick a peg into a hole. A box is basically a collection of holes of uniform size, and peg is a value of that size which can go in a box hole.

     (For example, a Lisp pair or cons cell as a box is a pair of pegs: the car is the first peg slot and the cdr is a second peg.)

     In Wil's first toy language shown on this this site, a peg will be pointer sized: 32-bits on a 32-bit platform. This is a details with great latitude in possible choices for physical representation. Wil simply started with the simple, obvious option: a peg is the same size as a pointer, and can also encode immediates no bigger than a pointer in size.

     The ybpa stack class assumes as given a struct yp to represent a peg, where sizeof(yp) is exactly the same size as sizeof(void*): four bytes on a 32-bit platform.

     (Actually the peg metaphor is most precisely correct when you say yp is a slot into which you can put a peg. A slot has location and a peg is a value, but when a peg is in a given slot, there's little reason to distinguish between them: it's moot.)

     The following declaration excerpts a much longer real definition of yp to be shown in a later peg demo. All you really need to get from this is the size, which matches void*. If you like, you can simply think of yp as identical to void*.

     Here you can also see a definition of yp::i_nil, an immediate encoding for nil also used in the stack demo code.

     (Term lid used for an integer alternative view of a peg pointer is a kind of jest to associate a short mnemonic term related to box that isn't a box; lid is otherwise unused on this page.)

     This column now presents methods for peg array class ybpa developed in the left column. After methods from file ybpa.cpp, a little sample code at the end shows example usage and typical printed output when a ybpa stack is dumped.

ybpa.cpp «

     The constructor allocates no space. A first page from source pile a_H is fetched only when alink() below requests the first frame of N contiguous pegs in a vector.

     "Wait," objected Stu. "If frames are contiguous vectors of peg slots only, how can you allocate a frame bigger than a page?"

     "You can't," stated Wil. "The largest frame holds only pmax-2 pointers, because two slots are reserved for the frame pointer in *a_0 and the trailing frame pointer at a_fp."

     "But what if I need more than, um, 1022 pegs in one frame?" Stu asked while trying not to crack a smile.

     "Get real," Wil advised. "Suppose you're reading a serialized list while building up a singly linked list in Lisp style cons pairs. You only need two pegs for the head and tail of the list."

     "Oh, I see," Stu gathered. "You're basically asking: when was the last time I needed a thousand local variables in a method?"

     "Yes," Wil smiled pleasantly. "You said that so much more clearly than I did. Frame size is related to count of locals."

linking frames «

     "So above," Stu noticed, "we're almost done when the current page has enough frees slots remaining."

     "Yes," Wil granted. "But the else clause below allocates a new page and ignores any pegs in the last current page. A new page is stored at index i where a_sp points at a next free stack location."

     "I'm having trouble reading it," Stu admitted. "The code after page allocation looks a little strange."

     "Three of the lines mimic lines further down," Wil pointed. "Basically the new page is set up as if it had contained nothing but a frame pointer in the first slot; then N new peg slots are allocated as if it was the current page (which it is now) with enough room."

     "I get it now," Stu blurted. "It's necessary to re-target a_fp and triple (a_0, a_p, a_x) for each new stack page."

     "Here if we allocated a frame of N pointers," Stu narrated, "we need to establish the new markup around the frame."

     "Yes, first the old a_fp frame poiner is written after the N allocated pegs at a_p," Wil explained. "The a_fp becomes the new frame pointer at a_p and gets written into the first page slot at *a_0."

     "What about the loop writing yp::i_nil into the N pegs between old and new frame pointer locations?" asked Stu.

     "Nil is a safe starting value in each slot," Wil replied. "It's clearly not a box pointer when a garbage collector looks."

     "I see alink() returns the address of the first slot of N peg slots," Stu noticed. "So a caller sees no frame markup."

     "A caller shouldn't care how a frame of N pegs is allocated," Wil explained. "Only about where it's located."

     "We'll assume the caller used a ybpvg guard to call alink() indirectly," Stu suggested. "So the frame address from alink() is later passed back to aunlink() to free the frame."

unlinking frames «

     "That's a lot of error checking," Stu remarked. "How come you only log and don't also assert?"

     "Actually, each of those log messages should be followed by an assert," Wil conceded. "Those cases shouldn't happen."

     "Does checking them make code run slow?" Stu wondered.

     "Not really," Wil assured. "Because the yunlikely() macro shown in the node demo tells branch prediction to assume false is the expected value (cf «). So the next block is hit quickly."

     "The if clause above retires the topmost page," Wil explained, "when it contained only the frame being unlinked."

     "Then it puts ybpa members back the way they were before the last alink() call?" Stu suggested.

     "Bingo," Wil grinned. "That's exactly what it does."

     "So the else clause below only pops the last frame in the current page when more frames still remain," Stu inferred.

     "Yes," Wil agreed. "It only has to put the old frame pointer into a_fp and the first page slot at *a_0."

     "And then it checks whether the frame unlinked started at the slot just after the last frame pointer," Stu noted.

     "Sure," Wil said. "Otherwise the stack must be bad."

     "Somehow I thought linking and unlinking frames would be more complex," Stu seemed a little surprised.

     "Without docs and diagrams in the left column," Wil suggested, "it might be a lot harder to decipher this code."

shutdown «

     "Getting rid of all resources allocated is easy," Wil narrated. "All page handles are released, returning all pages to the a_H pile passed to the constructor."

     "What the heck is that ynil value assigned to the handle," Stu asked. "Did you override operator=() for a special nil object?"

     "Oh yeah," Wil chuckled. "I forgot about that. Yes that operator=() has the same effect as assigning a zero value."

dumping «

     "Your first draft of adump() below only cited each page used in the stack," Stu complained. "Why didn't you even try to show the frame list in each page? I wanna see it."

     "Oh all right," Wil sighed. "I'll comment out the original two lines for each page and substitute a _adumppage() method."

     "I see you use + for a_up, - for a_down, and n for page pegs left," Stu observed. "Abbreviate much?"

     "Trying to keep horizonal extent under control when printing," Wil justified. "Is there a problem?"

     "Okay, now let's see that new _adumppage() method for dumping each page," Stu chortled, rubbing hands together.

     "Let's do a simpler method named _apageframes() first," suggested Wil. "It can just count frames in a page and show the basic problem of frame pointer list traversal."

     "Are you going to explain it?" Stu prodded.

     "Do I have too?" Wil whined. "Good grief. Okay look, it gets the last frame pointer in the page from the first page slot, and then follows this linked list backward, but only as long as the location is still inside the page and gets progressively closer to page start."

     "In one breath even," Stu applauded. "Good enough."

frame counting «

     "Now in _adumppage() below we can call _apageframes() above first, to get a frame count for the opening tag," Wil explained.

     "Then you can do the same sort of loop again in _adumppage()," Stu guessed. "Only this time printing a frame description."

     "Sounds like a plan," Wil approved. "Okay, keep comparing code below to what you see in _apageframes()."

page dumping «

     "That looks plausible," Stu said. "Let's see what it does. Do you have a tiny unit test of some kind?"

     "Let's write a little main() method below," Wil suggested. "Then we can allocate enough pegs in a frame to use more than one page, and try some edge conditions."

sample main «

     "Here's what the code below does," Wil introduced. "After making a new empty ybpa array as a frame stack, we allocate four frames: 12, 24, 900, and then 500 pegs at one time."

     "The last one won't fit in the first page," Stu noticed. "Let's also print the array between each frame allocated. How about trying to allocate too many pegs in a frame?"

     "Sure, we can do that last," Wil agreed. "At the end I can try to allocate a frame of 2000 pegs."

     "That looks adequate, if a little oddly formatted," Stu remarked. "I guess you want to control when guards are destroyed on scope exit. So the array is empty again by the time print #5 occurs."

sample stdout «

     "Note the following output is slightly edited," Wil warned. "I removed the crc and page node address attributes from each page printed to make each line fit without a break."