and two-dimensional arrays in C - Dive Into Systems

We can allocate an array with malloc(sizeof(int) * (3*. Figure 3. The results of allocating a 2D array with a single call to malloc. Like ... DiveIntoSystems DiveIntoSystems Authors Copyright Acknowledgements Preface 0.Introduction 1.BytheC,theBeautifulC 1.1.GettingStartedProgramminginC 1.2.Input/Output(printfandscanf) 1.3.ConditionalsandLoops 1.4.Functions 1.5.ArraysandStrings 1.6.Structs 1.7.Summary 1.8.Exercises 2.ADeeperDiveIntoC 2.1.PartsofProgramMemoryandScope 2.2.CPointerVariables 2.3.PointersandFunctions 2.4.DynamicMemoryAllocation 2.5.ArraysinC 2.6.StringsandtheStringLibrary 2.7.Structs 2.8.Input/OutputinC 2.9.AdvancedCFeatures 2.9.1.TheswitchStatement 2.9.2.CommandLineArguments 2.9.3.Thevoid*Type 2.9.4.PointerArithmetic 2.9.5.CLibraries:Using,CompilingandLinking 2.9.6.WritingandusingyourownClibraries(andcompilingmultiple.cand.hfiles) 2.9.7.CompilingCtoAssemblyandCompilingAssemblyCode 2.10.Summary 2.11.Exercises 3.CDebuggingTools 3.1.DebuggingwithGDB 3.2.GDBCommandsinDetail 3.3.DebuggingMemorywithValgrind 3.4.AdvancedGDBFeatures 3.5.DebuggingAssemblyCode 3.6.DebuggingMulti-threadedPrograms 3.7.Summary 4.BinaryandDataRepresentation 4.1.NumberBasesandUnsignedIntegers 4.2.ConvertingBetweenBases 4.3.SignedBinaryIntegers 4.4.BinaryIntegerArithmetic 4.4.1.Addition 4.4.2.Subtraction 4.4.3.Multiplication&Division 4.5.Overflow 4.6.BitwiseOperators 4.7.IntegerByteOrder 4.8.RealNumbersinBinary 4.9.Summary 4.10.Exercises 5.WhatvonNeumannKnew:ComputerArchitecture 5.1.TheOriginsofModernComputing 5.2.ThevonNeumannArchitecture 5.3.LogicGates 5.4.Circuits 5.4.1.ArithmeticandLogicCircuits 5.4.2.ControlCircuits 5.4.3.StorageCircuits 5.5.BuildingaProcessor 5.6.TheProcessor’sExecutionofProgramInstructions 5.7.PipeliningInstructionExecution 5.8.AdvancedPipeliningConsiderations 5.9.LookingAhead:CPUsToday 5.10.Summary 5.11.Exercises 6.UndertheC:DiveintoAssembly 7.64-bitx86Assembly 7.1.AssemblyBasics 7.2.CommonInstructions 7.3.AdditionalArithmeticInstructions 7.4.ConditionalControlandLoops 7.4.1.Preliminaries 7.4.2.IfStatements 7.4.3.Loops 7.5.FunctionsinAssembly 7.6.Recursion 7.7.ArraysinAssembly 7.8.MatricesinAssembly 7.9.StructsinAssembly 7.10.BufferOverflows 8.32-bitx86Assembly 8.1.AssemblyBasics 8.2.CommonInstructions 8.3.AdditionalArithmeticInstructions 8.4.ConditionalControlandLoops 8.4.1.Preliminaries 8.4.2.IfStatements 8.4.3.Loops 8.5.FunctionsinAssembly 8.6.Recursion 8.7.ArraysinAssembly 8.8.MatricesinAssembly 8.9.StructsinAssembly 8.10.BufferOverflows 9.ARMv8Assembly 9.1.AssemblyBasics 9.2.CommonInstructions 9.3.ArithmeticInstructions 9.4.ConditionalControlandLoops 9.4.1.Preliminaries 9.4.2.IfStatements 9.4.3.Loops 9.5.FunctionsinAssembly 9.6.Recursion 9.7.ArraysinAssembly 9.8.MatricesinAssembly 9.9.StructsinAssembly 9.10.BufferOverflows 10.KeyAssemblyTakeaways 11.StorageandtheMemoryHierarchy 11.1.TheMemoryHierarchy 11.2.StorageDevices 11.3.Locality 11.4.Caching 11.5.CacheAnalysisandCachegrind 11.6.LookingAhead:CachingonMulticoreProcessors 11.7.Summary 12.CodeOptimization 12.1.FirstSteps 12.2.OtherCompilerOptimizations 12.3.MemoryConsiderations 12.4.Summary 13.TheOperatingSystem 13.1.BootingandRunning 13.2.Processes 13.3.VirtualMemory 13.4.InterprocessCommunication 13.4.1.Signals 13.4.2.MessagePassing 13.4.3.SharedMemory 13.5.SummaryandOtherOSFunctionality 13.6.Exercises 14.LeveragingSharedMemoryintheMulticoreEra 14.1.ProgrammingMulticoreSystems 14.2.POSIXThreads 14.3.SynchronizingThreads 14.3.1.MutualExclusion 14.3.2.Semaphores 14.3.3.OtherSynchronizationConstructs 14.4.MeasuringParallelPerformance 14.4.1.ParallelPerformanceBasics 14.4.2.AdvancedTopics 14.5.CacheCoherence 14.6.ThreadSafety 14.7.ImplicitThreadingwithOpenMP 14.8.Summary 14.9.Exercises 15.LookingAhead:OtherParallelSystems 15.1.HardwareAccelerationandCUDA 15.2.DistributedMemorySystems 15.3.ToExascaleandBeyond DiveIntoSystems 1.0-RELEASECANDIDATE DiveIntoSystems 1.0-RELEASECANDIDATE DiveIntoSystems 2.ADeeperDiveIntoC 2.5.ArraysinC 2.5.ArraysinC Inthepreviouschapter weintroducedstaticallydeclaredone-dimensionalCarraysanddiscussedthe semanticsofpassingarraystofunctions.Inthe dynamicmemoryallocation sectionofthischapter,weintroduceddynamicallyallocatedonedimensional arraysanddiscussedthesemanticsofpassingthemtofunctions. Inthissection,wetakeamorein-depthlookatarraysinC.Wedescribeboth staticallyanddynamicallyallocatedarraysinmoredetailanddiscuss two-dimensionalarrays. 2.5.1.Single-DimensionalArrays StaticallyAllocated Beforejumpingintonewcontent,webrieflysummarizestaticarrayswithan example.Seetheprevious chapterformoredetailonstaticallydeclaredone-dimensionalarrays. Staticallydeclaredarraysareallocatedeitheronthestack(forlocal variables)orinthedataregionofmemory(forglobalvariables).A programmercandeclareanarrayvariablebyspecifyingitstype(thetype storedateachindex)anditstotalcapacity(numberofelements). Whenpassinganarraytoafunction,Ccopiesthevalueofthebaseaddressto theparameter.Thatis,boththeparameterandtheargumentrefertothesame memorylocations — theparameterpointerpointstotheargument’sarray elementsinmemory.Asaresult,modifyingthevaluesstoredinthearray throughanarrayparametermodifiesthevaluesstoredintheargumentarray. Herearesomeexamplesofstaticarraydeclarationanduse: //declarearraysspecifyingtheirtypeandtotalcapacity floataverages[30];//arrayoffloat,30elements charname[20];//arrayofchar,20elements inti; //accessarrayelements for(i=0;i<10;i++){ averages[i]=0.0+i; name[i]='a'+i; } name[10]='\0';//nameisbeingusedforstoringaC-stylestring //prints:3dabcdefghij printf("%g%c%s\n",averages[3],name[3],name); strcpy(name,"Hello"); printf("%s\n",name);//prints:Hello DynamicallyAllocated IntheDynamicMemory Allocationsectionofthischapter,weintroduceddynamicallyallocated one-dimensionalarrays,includingtheiraccesssyntaxandthesyntaxandsemantics ofpassingdynamicallyallocatedarraystofunctions.Here,wepresentashortrecap ofthatinformationwithanexample. Callingthemallocfunctiondynamicallyallocatesanarrayontheheapat runtime.Theaddressoftheallocatedheapspacecanbeassignedtoaglobal orlocalpointervariable,whichthenpointstothefirstelementofthearray. Todynamicallyallocatespace,passmallocthetotalnumberofbytesto allocateforthearray(usingthesizeofoperatortogetthesizeofa specifictype).Asinglecalltomallocallocatesacontiguouschunkofheap spaceoftherequestedsize.Forexample: //declareapointervariabletopointtoallocatedheapspace int*p_array; double*d_array; //callmalloctoallocatetheappropriatenumberofbytesforthearray p_array=malloc(sizeof(int)*50);//allocate50ints d_array=malloc(sizeof(double)*100);//allocate100doubles //alwaysCHECKRETURNVALUEoffunctionsandHANDLEERRORreturnvalues if((p_array==NULL)||(d_array==NULL)){ printf("ERROR:mallocfailed!\n"); exit(1); } //use[]notationtoaccessarrayelements for(i=0;i<50;i++){ p_array[i]=0; d_array[i]=0.0; } //freeheapspacewhendoneusingit free(p_array); p_array=NULL; free(d_array); d_array=NULL; ArrayMemoryLayout Whetheranarrayisstaticallydeclaredordynamicallyallocated viaasinglecalltomalloc,arrayelementsrepresentcontiguous memorylocations(addresses): array[0]:baseaddress array[1]:nextaddress array[2]:nextaddress ...... array[99]:lastaddress Thelocationofelementiisatanoffsetifromthebaseaddressofthe array.Theexactaddressoftheithelementdependsonthenumberofbytesof thetypestoredinthearray.Forexample,considerthefollowingarray declarations: intiarray[6];//anarrayofsixints,eachofwhichisfourbytes charcarray[4];//anarrayoffourchars,eachofwhichisonebyte Theaddressesoftheirindividualarrayelementsmightlook somethinglikethis: addrelement ----------- 1230:iarray[0] 1234:iarray[1] 1238:iarray[2] 1242:iarray[3] 1246:iarray[4] 1250:iarray[5] ... 1280:carray[0] 1281:carray[1] 1282:carray[2] 1283:carray[3] Inthisexample,1230isthebaseaddressofiarrayand1280the baseaddressofcarray.Notethatindividualelementsofeach arrayareallocatedtocontiguousmemoryaddresses:eachelement ofiarraystoresa4-byteintvalue,soitselementaddressesdiffer by4,andeachelementofcarraystoresa1-bytecharvalue,soits addressesdifferby1.Thereisnoguaranteethatthesetoflocal variablesareallocatedtocontiguousmemorylocationsonthestack (hence,therecouldbeagapintheaddressesbetweentheendof iarrayandthestartofcarray,asshowninthisexample.) 2.5.2.Two-DimensionalArrays Csupportsmultidimensionalarrays,butwelimitourdiscussionof multidimensionalarraystotwo-dimensional(2D)arrays,since1Dand2Darrays arethemostcommonlyusedbyCprogrammers. StaticallyAllocated2DArrays Tostaticallydeclareamultidimensionalarrayvariable,specifythesizeof eachdimension.Forexample: intmatrix[50][100]; shortlittle[10][10]; Here,matrixisa2Darrayofintvalueswith50rowsand100columns,and littleisa2Darrayofshortvalueswith10rowsand10columns. Toaccessanindividualelement,indicateboththerowandthecolumnindex: intval; shortnum; val=matrix[3][7];//getintvalueinrow3,column7ofmatrix num=little[8][4];//getshortvalueinrow8,column4oflittle Figure1illustratesthe2Darrayasamatrixofintegervalues, whereaspecificelementinthe2Darrayisindexedbyrowandcolumnindex values. Figure1.Atwo-dimensionalarrayrepresentedasamatrix.Accessingmatrix[2][3]islikeindexingintoagridatrow2andcolumn3. Programsoftenaccesstheelementsofa2Darraybyiteratingwith nestedloops.Forexample,thefollowingnestedloopinitializesallelements inmatrixto0: inti,j; for(i=0;i<50;i++){//foreachrowi for(j=0;j<100;j++){//iterateovereachcolumnelementinrowi matrix[i][j]=0; } } Two-DimensionalArrayParameters Thesamerulesforpassingone-dimensionalarrayargumentstofunctionsapply topassingtwo-dimensionalarrayarguments:theparametergetsthevalueofthe baseaddressofthe2Darray(&arr[0][0]).Inotherwords,theparameter pointstotheargument’sarrayelementsandthereforethefunctioncanchange valuesstoredinthepassedarray. Formultidimensionalarrayparameters,youmustindicatethattheparameteris amultidimensionalarray,butyoucanleavethesizeofthefirstdimension unspecified(forgoodgenericdesign).Thesizesofotherdimensionsmustbe fullyspecifiedsothatthecompilercangeneratethecorrectoffsetsintothe array.Here’sa2Dexample: //aCconstantdefinition:COLSisdefinedtobethevalue100 #defineCOLS(100) /* *init_matrix:initializesthepassedmatrixelementstothe *productoftheirindexvalues *m:a2Darray(thecolumndimensionmustbe100) *rows:thenumberofrowsinthematrix *return:doesnotreturnavalue */ voidinit_matrix(intm[][COLS],introws){ inti,j; for(i=0;i