Data Structures: Memory

Data Structures: Memory

Overview

• This document serves as a comprehensive guide to the fundamental concepts of data structures with a focus on memory management, pointers, and records in programming, specifically in the context of the C programming language.

• Instructors: Amit Chopra

• Email: amit.chopra@lancaster.ac.uk

Byte Addressable Memory

• Definition: Computer memory is primarily byte addressable.

  • Memory can be visualized as an array of bytes, where each memory cell possesses a unique address.

  • Analogous to a character array where the address is akin to the index of an element (memory cell).

• Example of Memory Addresses and Their Content:

  • Address 40 30 1c; Content: 'H'

  • Address 40 30 1d; Content: 'e'

  • Address 40 30 1e; Content: 'l'

  • Address 40 30 1f; Content: 'l'

  • Address 40 30 20; Content: 'o'

  • Address 40 30 21; Content: ' ' (space)

  • Address 40 30 22; Content: 't'

  • Address 40 30 23; Content: 'h'

  • Address 40 30 24; Content: 'e'

  • Address 40 30 25; Content: 'r'

Word Size

• Definition: The size of a word can vary between machines, but in this course a word is defined as 32 bits (4 bytes) long.

• Integer Values: Often represented by the word size.

A Words-eye View

• Word Representation: Memory can also be examined in terms of 'words' (32-bit values occupying 4 bytes).

  • Memory addresses increase in increments of 4 bytes.

• Memory Address Mapping:

  • Address 40 30 04; Memory Content: 0

  • Address 40 30 08; Memory Content: 'll' (6c6c65)

  • Address 40 30 0c; Memory Content: 'he' (6874206f)

  • Address 40 30 10; Memory Content: ',re' (2c657265)

  • Address 40 30 14; Memory Content: 'lo' (6c6f6620)

  • Address 40 30 18; Memory Content: '!s' (21636b)

  • Each row illustrates that each address occupies multiple bytes.

Variables

• Attributes of a Variable:

  • A variable comprises three fundamental aspects:

  • Symbolic Name: Represents the identifier of the variable.

  • Value: The data that the variable currently holds.

  • Address: The specific location in memory where this variable is stored.

• Example Variable Declaration:

  • c char val; val = 3;

• Memory Representation of Variable:

  • Address: 40 63 e8; Value: 3; Variable Name: val.

  • Address: 40 63 e9; Value: ?? (next address).

Assignment Statements

• Understanding the Assignment: The interpretation of a variable differs based on the context in which it appears in an assignment statement.

Fetch and Store Mechanism

• Right-Hand Side (RHS) in Assignment:

  • Fetch the value from the memory address of the variable.

  • Applying expression:

  • c val = val + 2;

  • This results in evaluation: val = 3 + 2; hence, val becomes 5.

• Left-Hand Side (LHS) in Assignment: Store the evaluated result back into the variable's memory address.

Source and Destination in Assignment

• Example: When performing the assignment val = 5:

  • The source refers to the value being assigned (which is 5).

  • The destination refers to the memory location where this value will be stored.

Pointers

• Defining Pointers: C variables have a scope limited to the function in which they appear. Pointers allow the passing of memory addresses to work on conceptual objects within different functions.

• Usage of Pointers in C:

  • Example Pointer Code:

  • c char val; char* addr; val = 3; addr = &val;

  • This code associates addr with the address of val.

• Effect on Value:

  • Adding 2 to the value referenced by addr modifies val directly:

  • c *addr = *addr + 2;

  • Resulting output shows how val changes from 3 to 5.

Variable and Pointer Relationship

• Variable Declaration:

  • val: A normal character variable (single byte space).

  • addr: Pointer to a char; holds the address of the char variable.

  • Size of addr is 32 bits (to accommodate a memory address).

Operator Usage

• & Operator:

  • The & unary operator returns the address of the given operand, e.g., &val returns the address of val.

• Dereference Operator (*):

  • Used when obtaining value from an address held by a pointer. Example:

  • c *addr = *addr + 2;

  • Fetches the content at the memory address pointed to by addr.

Levels of Indirection

• Indirection Levels:

  • Illustrates evaluations through pointers.

  • Fetching leads to multiple levels of understanding where lines of code correspond to memory actions (like fetching and storing).

Records in Memory

• Record Definition:

  • A record is a compound data structure which can hold heterogeneous types (different fields). Each field is named—differentiating it from arrays which use indexing.

• Example of a Student Record:

  • Fields: Name, Age, Gender, Entry Year, Subject, Marital Status.

  • Types: String, Int, Char, etc.

Defining Records in C

• Struct Declaration in C:

  • c typedef struct student { char name[MAXSIZE]; int age; char gender; int entryYear; char subject[MAXSIZE]; char maritalStatus; } Student;

• Memory Allocation for Records:

  • Allocating memory for a new Student record is achieved through the malloc function, returning a pointer to the allocated space.

Using Arrow and Dot Operators

• Arrow (->) Operator: Used to access fields for a pointer to a record.

• Dot (.) Operator: Directly accesses fields of record instances.

• Examples of Usage:

  • To set record fields after allocation, such as using strcpy() for strings and direct assignment for integers and characters.

Arrays of Records

• Concept: A defined type like Student can be employed to create arrays, thereby enabling multiple record instances.

  • Example:

  • c Student* arrayOfStudents[2]; arrayOfStudents[0] = stu; arrayOfStudents[1] = &stu2;

Managing Values via Functions

• Implementing functions to set values, such as marital status with data validation can help maintain integrity within the entries.

• Marital Status Example Function:

  • c bool setMaritalStatus(Student* s, char x) { bool ok = false; switch (x) { case 'm': case 'w': case 's': case 'd': ok = true; break; }; if (ok) s->maritalStatus = x; return ok; }