IntroductionStringsStoring StringsAccessing StringsListing 1. String Storage ExampleListing 2. String Access ExampleString ApplicationsStacksStack Reading and WritingMCU Hardware StackHC05 StackHC08 StackStack ApplicationsListing 3. Software StackListing 4. Using the HC08 Stack OperationsQueuesReading and WritingQueue ErrorsQueue ApplicationsListing 5. Queue ExampleMACQ (Multiple Access Circular Queue)Reading and WritingApplicationsExampleListing 6. MACQTablesTable ApplicationsTable ExampleListing 7. TableLinked ListsLinked List ApplicationsState MachinesState Machine ExampleSimulationListing 8. Traffic Controller State MachineConclusion© Motorola, Inc., 1998, 2001 AN1752 — REV 1Order this documentby AN1752/DREV 1Motorola Semiconductor Application NoteAN1752Data Structures for 8-Bit MicrocontrollersBy Brad BierschenkConsumer Systems Group Applications EngineeringAustin, TexasIntroductionA data structure describes how information is organized and stored in a computer system. Although data structures are usually presented in the context of large computers, the same principles can be applied to embedded 8-bit processors. The efficient use of appropriate data structures can improve both the dynamic (time-based) and static (storage-based) performance of microcontroller software.This application note presents data structures which are useful in the development of microcontroller software. The applications presented here are by no means absolute. One can find an infinite variety of ways to apply these basic data structures in a microcontroller application.StringsA string is a sequence of elements accessed in sequential order. The string data structure usually refers to a sequence of characters. For example, a message which is to be output to a display is stored as a string of ASCII character bytes in memory. Freescale Semiconductor, I Freescale Semiconductor, Inc.For More Information On This Product, Go to: www.freescale.comnc...Application NoteAN1752 — REV 12 MOTOROLAStoring Strings A string of elements must be identified by a starting and ending address. A starting address for a string can be defined using an absolute address label or by using a base address of a group of strings and identifying particular strings with an offset into the group.There are several methods of terminating string information. One common way of terminating a string is by using a special character to mark the end of the string. One terminating character to use is the value $04, an ASCII EOT (end-of-transmission) byte.Figure 1 shows an example of string data.Figure 1. String Data StructureAnother method of terminating a string is to identify its length. Its length can then be used as a counter value, eliminating the need for an extra byte of storage for the end of the string.A string of ASCII characters can be terminated without using an extra byte of storage by using the sign bit (most significant bit) as an indicator of the last byte of the string. Because ASCII character data is only seven bits long, the last byte of a string can be indicated by a 1 in its most significant bit location. When using this method, the programmer must be careful to strip off the sign bit before using the ASCII character value.MESSAGE POINTER$50$51$52$53$54$55’O’’L’$04’H’’E’’L’ADDRESSDATA Freescale Semiconductor, I Freescale Semiconductor, Inc.For More Information On This Product, Go to: www.freescale.comnc...Application NoteStringsAN1752 — REV 1MOTOROLA 3Accessing Strings An efficient way of accessing a string is with the indexed addressing mode and the INCX or DECX instruction. Listing 1. String Storage Example and Listing 2. String Access Example illustrate this string storage scheme and how to use it.Listing 1. String Storage Example*-----------------------------------------------------------------------------------* Absolute string addresses* One way of specifying string data*-----------------------------------------------------------------------------------Message1 FCB ’This is a string’FCB $04Message2 FCB ’This is another string’FCB $04*-----------------------------------------------------------------------------------* Indexed string addressing* Another way of specifying string data*-----------------------------------------------------------------------------------Msgs EQU *Message3 EQU *-MsgsFCB ’This is a string’FCB $04Message4 EQU *-MsgsFCB ’This is another string’FCB $04Listing 2. String Access Example*-----------------------------------------------------------------------------------* String display code* A generic method of displaying an entire string.*-----------------------------------------------------------------------------------LoadMsg LDX #Message1 ;Offset into XLoop LDA Messages,X ;Load characterCMP #$04 ;Check for EOTBEQ StringDone ;End of stringJSR ShowByte ;Show characterINCX ;Point to nextBRA Loop*-----------------------------------------------------------------------------------* String storage code*-----------------------------------------------------------------------------------Messages EQU *Message1 EQU *-MessagesFCB ’This is a string’FCB $04 Freescale Semiconductor, I Freescale Semiconductor, Inc.For More Information On This Product, Go to: www.freescale.comnc...Application NoteAN1752 — REV 14 MOTOROLAString Applications Practical applications of strings include storing predefined "canned" messages. This is useful for applications which require output to text displays, giving users information or prompting users for input.Strings are also effective for storing initialization strings for hardware such as modems. Strings may also store predefined command and data sequences to communicate with other devices.StacksA stack is a series of data elements which can be accessed only at one end. An analogy for this data structure is a stack of dinner plates; the first plate placed on the stack is the last plate taken from the stack. For this reason, the stack is considered a LIFO (last in, first out) structure. The stack is useful when the latest data is desired. A stack will typically have a predefined maximum size. shows a representation of a stack.Figure 2. Stack Data StructureSTACK POINTERSTACK BOTTOMSTACK TOP(MAXIMUM)$50$51$52$53$54$55$57$56DATA BYTEDATA BYTEDATA BYTEDATA BYTEDATA BYTEEMPTYEMPTYEMPTYADDRESSSTACK GROWSIN