Memory and Data StructuresSlide 2Slide 3Slide 4Slide 5Storage of bytesPointers and ArraysSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Address vs. ValueAnother Need for AddressesExecuting the Swap FunctionPointers in CExampleExample: LC-3 CodeSlide 20Slide 21Slide 22Slide 23Slide 24StacksA Physical StackA Hardware ImplementationA Software ImplementationBasic Push and Pop CodePop with Underflow DetectionPush with Overflow DetectionSlide 32Arithmetic Using a StackExample: OpAddSlide 35QueuesSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Summary of Data StructuresQuestions?Slide 471Memory and Data Memory and Data Structures Structures Patt and Patel Ch. 10 & 16Patt and Patel Ch. 10 & 162MemoryMemory•This is the “RAM” in a systemThis is the “RAM” in a system•We have seen labels and addresses We have seen labels and addresses point to pieces of memory storing:point to pieces of memory storing:• wordswords• bytesbytes• stringsstrings• numbersnumbers•Memory is just a collection of bitsMemory is just a collection of bits•We could use it to represent integersWe could use it to represent integers•Or as an arbitrary set of bitsOr as an arbitrary set of bits3MemoryMemoryTreat memory as a giant arrayTreat memory as a giant array•Compiler or programmer decides what Compiler or programmer decides what use to make of it.use to make of it.•The element numbering starts at 0The element numbering starts at 0•The element number is an addressThe element number is an address•In “C” to allocate some memory:In “C” to allocate some memory:char m[size_of_array];char m[size_of_array];4Storage of DataStorage of Data•LC-3 architecture is “word LC-3 architecture is “word addressable” meaning that all addressable” meaning that all addresses are “word” addresses.addresses are “word” addresses.•This means the smallest unit of This means the smallest unit of memory we can allocate is 16-bits, a memory we can allocate is 16-bits, a word.word.•Use ‘LD’ (load) and ‘ST’ (store) to Use ‘LD’ (load) and ‘ST’ (store) to access this unit (or LDR & STR).access this unit (or LDR & STR).5ExampleExamplemychar mychar .BLKW.BLKW11newlinenewline.FILL.FILLxAxA…………LDLDR1, newlineR1, newlineGETCGETCSTSTR0, mycharR0, mycharJSRJSRSubSub; R2=R1-R0; R2=R1-R0BRzBRzfound_newlinefound_newline……found_newlinefound_newline……Storage of bytesStorage of bytes6Storage of bytesStorage of bytesThe data is placed in The data is placed in memory like this at memory like this at start up (assuming start up (assuming data section starts at data section starts at address 1). address 1). The mychar variable The mychar variable will change to the will change to the value of the value of the character entered by character entered by the user once stored.the user once stored.0011000000002200000A0A33MemoryMemorynewline newline variablevariablemychar mychar variablevariableaddresseaddressess7Pointers and ArraysPointers and ArraysWe've seen examples of both of these in our LC-We've seen examples of both of these in our LC-3 programs, lets see how these work in “C”3 programs, lets see how these work in “C”PointerPointer–Address of a variable in memory–Allows us to indirectly access variables•in other words, we can talk about its address rather than its valueArrayArray–A list of values arranged sequentially in memory–Example: a list of telephone numbers–Expression a[4] refers to the 5th element of the array a8ArraysArraysArray implementation is very importantArray implementation is very important•Most assembly languages have no concept of arraysMost assembly languages have no concept of arrays•From an array, any other data structure we mightFrom an array, any other data structure we mightwant can be builtwant can be built9Properties of arrays:Properties of arrays:–Each element is the same size–Elements are stored contiguously–First element at the smallest memory addressIn assembly language we mustIn assembly language we must–Allocate correct amount of space for an array–Map array addresses to memory addressesArraysArrays10ArraysArraysLC-3 declarations of arrays within memoryLC-3 declarations of arrays within memoryTo allocate a portion of memory (more than a singleTo allocate a portion of memory (more than a singlevariable’s worth)variable’s worth) variablenamevariablename.BLKW.BLKWnumelementsnumelementsnumelements is just that, numbering starts at 0 (as numelements is just that, numbering starts at 0 (as in C)in C)11Array of IntegersArray of IntegersCalculating the address of an array elementCalculating the address of an array elementint int myarray[7]myarray[7]/* C *//* C */myarraymyarray.BLKW.BLKW77; LC-3; LC-3•If base address of myarray is 25If base address of myarray is 25•Address of myarray[4] = 25 + 4 = 29Address of myarray[4] = 25 + 4 = 29•Base address + distance from the first elementBase address + distance from the first element002525112233445526262727282829292A2A662B2BElement indexElement indexaddressaddressmyarraymyarray12•Use the “load effective address” Use the “load effective address” instruction, “LEA”instruction, “LEA”•Keep clear the difference between an Keep clear the difference between an address and the contents of an address.address and the contents of an address.Addressing Byte ArraysAddressing Byte ArraysHow do you get the How do you get the address of address of myarraymyarray??13To get address of To get address of myarray[4]myarray[4] in LC-3, write the code… in LC-3, write the code…LEALEAR0, myarrayR0, myarrayADDADDR1, R0, #4R1, R0, #4If we wanted to increment element number 5 by 1…If we wanted to increment element number 5 by 1…LDRLDRR4, R1, #0R4, R1, #0ADDADDR4, R4, #1R4, R4, #1STRSTRR4, R1, #0R4, R1, #0Addressing Byte ArraysAddressing Byte Arrays14Address vs. ValueAddress vs. ValueSometimes we want to deal with the Sometimes we want to deal with the addressaddress of a of a memory location, rather than the memory location, rather than the valuevalue it contains. it contains.Recall example from Chapter 6:Recall example from Chapter 6:adding a column of numbers.adding a column of numbers.–R2 contains address of first location.–Read value, add to sum, andincrement R2 until all numbershave been processed.R2 is a pointer -- it contains theR2 is a pointer -- it contains theaddress of data we’re interested in.address of data we’re