The QBNews Page 22 Volume 1, Number 4 September 3, 1990 ---------------------------------------------------------------------- A l g o r i t h m s ---------------------------------------------------------------------- Improving your IQUEUE by Jim Mack With all that's been added to the BASIC language in the past few years, it might be hard to believe that there's a more-or- less elementary data structure that's been ignored. Actually, "ignored" is a bit strong, since you can build this structure out of more primitive elements using the core language, but I'll bet most of you never have. You've probably gathered from the title that what I'm talking about is a data stack. Now, whether a stack is an essential data structure is certainly debatable: after all, aren't high-level languages supposed to insulate you from such machine-like things as registers and stacks? And haven't you gotten along for years without a queue? If you've never programmed in MASM (or Forth), you might be blissfully unaware of the possibilities of just "pushing" data somewhere and later "popping" it back... and of the concept of feeding data to another process faster than it can be absorbed. Well, you're in for a not-too-rude awakening here, as we explore the world of buffered data. We'll discover two useful sets of routines and see how you might apply them to some common programming tasks. "Queue". The word is so weird-looking, let's get it out of the way first. Pronounced "Q" (then why are all those other letters there?), it's just another word for a "line" such as you might encounter at a theater or bank. We used to say as children "it forms at the end"... not strictly true, but close enough. People (or objects) are "handled" in the same order that they join the line: first come, first served. Another common way of saying this is FIFO (arf!) or first-in, first-out. If there's room in a theater lobby for 20 people to wait in line ("on" line for you New Yorkers), then we can think of the lobby as buffering 20 items. When the lobby is full, no one may enter until someone leaves at the head. It's the same for data. If one process generates data items at roughly the same rate that another process uses them, but with bursts of activity followed by periods of calm, a buffer can smooth out the peaks. The originating process can place items into a queue as fast as it likes, while the receiving process can take time to work with an item, and get a new one as it requires. A good example of this activity is QB's RS-232 serial COM. Characters arriving at the port interrupt normal processing and are quickly placed into a queue. As your program becomes aware of them, The QBNews Page 23 Volume 1, Number 4 September 3, 1990 it retrieves characters and, well, does what it does with them. If your program empties the bucket roughly as fast as it's filling up, then the queue provides some leeway for those characters which might need a little more processing. The larger the buffer, the "spongier" the process can be. There are two ways of handling buffered data. One way is to let the buffer fill up, then disallow any more input until it's emptied again. A movie theater functions like that: if you don't get in at 6, you wait until 8... and nobody goes in at 8 until the 6 o'clock crowd has left. Far more useful for data is the "circular" queue, often called a ring buffer (note to jewelers: I know this isn't what *you* call a ring buffer. Don't write). There are analogies for both in the real world. The theater line is a straight queue. A service department might instead use a "take a number" scheme with tickets numbered from 1 to 100. Once number 100 is serviced, number 1 is next, and so on. "Take a number" also introduces the idea of a pointer. In a theater, the entire line moves forward whenever someone leaves from the head. In the service department, folks may move around until their number comes up. In data terms, the "theater" method is terribly inefficient. Instead, we use pointers to indicate where the current head and tail of the queue are. With pointers, the size of the queue doesn't affect the speed of operations, so enqueueing and dequeueing data items can be very fast. We turn an ordinary queue into a circular one by the simple action of "wrapping" the pointers, or in more technical terms, by incrementing them MOD the length of the queue... 99 + 1 = 100, but 100 + 1 = 1. A queue has two pointers. The "write" pointer indicates where in the buffer any new item will be stored. The "read" pointer gives the location from which the oldest item will be retrieved. These are circular if they're wrapped around when about to point off the end. The queue is full if incrementing the write pointer would cause it to equal the read pointer. So now, at least in concept, you know all about the queue. It's a form of buffer, a FIFO stack. It's really that simple... but not as simple as the LIFO (last-in, first-out) stack. To review what a LIFO stack is, we move from the theater to the restaurant (almost like real life, isn't it?). Norton's First Law of Computer Explication states, in part, that "...every treatise on The Stack will begin by discussing dinner plates...", so here we go. The QBNews Page 24 Volume 1, Number 4 September 3, 1990 Ever eaten in a cafeteria? Sure you have. Then you've seen those "plate-o-matic" devices that, when you take the top plate, another one springs up behind it...? Let's perform what nuclear theorists call a "thought experiment". How do plates get there in the first place? Do you suppose the cafeteria, having studied queues, replaces them at the bottom as they're taken off the top? Right. They operate on a last-washed first-dirtied basis, just like the stack we think of in CPU terms. Items are "pushed" onto a LIFO stack, and later "popped" back off. Technically, a FIFO queue is a stack too, but we usually reserve the word "stack" for the LIFO version. A LIFO stack can be managed with only one pointer: where the next pushed item will go or from where the next popped item will come. You could shuffle all the data each time you push or pop a data item, but as we saw with queues, a pointer is a lot more efficient. So, a stack is a temporary holding area for data. It can be used for other things, but that pretty much sums it up. It's tough to come up with any other real-world example of a LIFO stack. Fortunately most of us are already familiar with the idea because nearly every computer operation involves some use of the CPU's system stack. But while we realize how vital a stack is for the CPU, what does it buy us at the program level to have our own stack? After all, in QB if we need somewhere to put an item aside temporarily, why, we just reference a new variable... it might even be created on the system stack, and we'd never need to know. Well, there are times when an algorithm runs more smoothly, or is easier to implement, using a stack. Too, you may not want the overhead of another temporary variable (or ten), or may not want to dream up Yet Another Unique Variable Name. If so, the stack's the ticket. A data stack can also allow you to perform some recursive operations within an otherwise STATIC procedure. One example of a technique well suited to a stack is Help. I've written a "hyper-help" utility, wherein the user can follow links embedded in the text to jump from one topic (page) to another in any sequence that pleases her. Keeping track of the path being followed so we can unwind to any point (and branch again from there), is potentially a nightmare. But with a stack the job is trivial: whenever she negotiates a link, we just push the current location. When she wishes to back up, we pop page locations back off the stack. Simple, direct, and obvious. A queue can find use in passing a variable number of arguments to a procedure, something QB can't do on its own. Put as many items into the queue as you like... the called procedure just pops them out until there are no more. Queues find their best use with asynchronous The QBNews Page 25 Volume 1, Number 4 September 3, 1990 processes, for example when passing data from an interrupt handler to a program, or vice versa. Now for the details. I've written this so there's one stack and one queue, each 255 items long. The code for them is in IQUEUE.ASM and ISTACK.ASM, two small MASM files which define several new QB SUBs and FUNCTIONs, and which reserve the space for the buffers. There's nothing to stop you from using more than one of each, but you'll have to extend the concept on your own. Once you've had a look at the MASM code, you'll see just how simple all this really is. There are three nice things about doing it in MASM. First, it takes up no precious DGROUP data space (well, 6 bytes for pointers, but who's counting?). The reason we don't need any DGROUP space for the buffers is that we put them into the code segments we declare for the procedures. Second, everything about these is automatically global to every procedure in any module which DECLAREs them. This applies to linked- in libraries, run-time libs... anything which "knows" about these can share the procedures and the data without resorting to COMMON or SHARED declarations. Third and most important, it "encapsulates" the queue and the stack, so you can tell everyone you're using "object-oriented techniques" in your programming. Of course I'm joking, right? Well, only a little... Here are the DECLAREs you'll need to include. For IQUEUE: DECLARE SUB IQflush () DECLARE SUB IQput (intvalue%) DECLARE FUNCTION IQget% () DECLARE FUNCTION IQfree% () DECLARE FUNCTION IQavail% () DECLARE SUB ISclear () DECLARE SUB ISpush (intvalue%) DECLARE FUNCTION ISpop% () DECLARE FUNCTION ISfree% () DECLARE FUNCTION ISavail% () You can use these for integers or characters. The listings include versions for long integers as well. Naturally, you can use the long-integer version for smaller objects too, but you'll have to explicitly convert from integer to long, etc, to do that. If you don't like these names, or if they conflict with names you're already using, you can use ALIAS to rename them without going to the bother of editing and reassembling the MASM code. For example: The QBNews Page 26 Volume 1, Number 4 September 3, 1990 DECLARE SUB PushError ALIAS "ISPush" (intval%) You can then use PushError instead of ISPush to refer to the same routine. So let's see how these work in QB. The IQFlush procedure does what its name implies: it empties the queue of all data. For speed, all it really does is reset the pointers, since the contents of the queue don't matter if the pointers say it's empty. So to start from scratch at any time, just say: IQFlush To place an element into the queue is just as easy: IQPut AnyInteger% IQPut ComplexType.IntArray(elno) IQPut SADD(j$) IQPut (((1000 * 2) \ 3) + 7) ^ 2 Anything which evaluates to an integer can be put into the queue, but watch it... if the queue is full when you try to PUT an element, you'll generate an Overflow Error in QB. If this might be a problem, use the IQFree function: IF IQFree THEN 'meaning "if there's any room" IQPut MyElement% END IF Note that the reason you get an Overflow Error is because that's the way I designed it: if you want the code to whistle "Lara's Theme" or format your hard disk, you can replace my very minimal QUERR with your own error handler. Overflow is an easy error to generate, and it does more or less correspond with this condition. To retrieve an element from the queue, use IQGet. You can treat IQGet just as though it were a simple integer: PRINT IQGet k = IQGet MOD 3 CALL MySub(r$, hpos%, IQGet%) But as with PUT, if you try to GET when the queue is empty, you'll get an Overflow. To guard against that, use IQAvail: IF IQAvail THEN 'meaning "if anything's there" k = IQGet + 19 END IF And that's it. The STACK routines are exactly analogous to the QUEUE routines, so there's no need to review them separately. The MASM listings are commented well enough that if you need to modify them, The QBNews Page 27 Volume 1, Number 4 September 3, 1990 you can. You'll need MASM 5.1 to reassemble these if you make changes. Two notes: to make underflow and overflow detection easier in the IQUEUE procedures, the actual number of elements you can store at once is one less than the EQU'd size of the queue. And if you intend to use the queue with interrupts, you'll want to surround any pointer operations with CLI/STI to avoid collisions. If you run into any problems, you can reach me via CompuServe at 76630,2012, or on BIX as "jsmack". Your comments are always welcome. ********************************************************************** Jim Mack is a programmer specializing in real-time systems for the entertainment industry. He can be reached via CIS ID 76630,2012 on the MSSYS forum in the BASIC or MASM sections, or at Editing Services Co., PO Box 599, Plymouth MI 48170, (313) 459-4618 ********************************************************************** [EDITOR'S NOTE] You can find the ASM source and assembled .OBJ's for this article in the file IQUEUE.ZIP.