微信客服：xiaoxionga100
微信客服：ITCS521
MCIT 593-c语言和assembly代写
时间：2022-12-03
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
DYNAMIC MEMORY ALLOCATION
2
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
What Is Dynamic Memory Allocation?
• “Dynamic” means “at run-time” (not “at compile-time”)
• Compiler does not have enough information to make final decision
• Unlike “automatic” or “static” memory allocation, e.g.: int a = 0 ;
• Dynamic memory allocation example
• We would love to make arrays of dynamic length!
• Our dream in C:
int length = 2 ;
int int_array [length] ; /* why won’t this compile? */
• Remember in assembly…
• If you could just find a free spot in memory, you could write to it
• We have the same thing in C (except it is a bit safer)
4
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
What Is The Heap?
• 3 possible places to store data in C on the LC4:
• The Stack (known at compile time)
• local variables, arguments, returns
• The Global Region (known at compile time)
• static vars (global or local static)
• The heap (accessible at runtime)
• x4000-x6FFF
• This region is the topic of this module
Global Region
(static vars)
Stack
(automatic vars)
x0000
x3FFF
x4000
x6FFF
x7000
x7FFF
x1FFF
x2000
Heap
(dynamic vars)
Program Memory
User Data Memory
partitioned further for C:
globals, heap, stack
5
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
ALLOCATING MEMORY
7
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API
• How does the programmer interface with “heap”?
• Two basic functions for heap: malloc() and free()
• Heap is managed by user-level C runtime library (libc)
• Interface function declarations found in stdlib.h
void* malloc(size_t size) ;
• Returns a pointer to a region on the heap of size size bytes
• If success, space is contiguous
• Recall that size_t is simply an typedef’d unsigned int
• Returns NULL if heap can’t fulfill request
• Recall that void* is “generic pointer” (C for “just an address”)
• Can pass it around, but not dereference
• Analogous to making a “reservation” for dinner – secures reservation, up to you to use!
8
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
FREEING MEMORY
10
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API
• How does the programmer interface with “heap”?
• Two basic functions for heap: malloc() and free()
• Heap is managed by user-level C runtime library (libc)
• Interface function declarations found in stdlib.h
void* malloc(size_t size) ;
• Returns a pointer to a region on the heap of size size bytes
• If success, space is contiguous
• If failure, returns NULL
• Analogous to making a “reservation” for dinner – secures reservation, up to you to use!
void free(void* ptr) ;
• Clears reservation for address pointed to be ptr
• The memory region pointed to by ptr, was previously given to you by malloc()
11
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 1: CREATING ARRAY
AT RUNTIME
13
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
Why can’t we do this?
pointer points
to nothing RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
stack memory
15
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
stack memory
Why can we do this now?
we have two spots
on the heap!
1
0
16
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
free() doesn’t actually modify *int_array or clear the heap!
stack memory
1
0
17Instead it releases your “reservation” on address x4000 for 8 bytes
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * ); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
sizeof() is actually an operator in C (not a function)
stack memory
1
0
18It can compute the size of its operand…works on any datatype…even structs!
sizeof(int)
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 2: RETURNING
ARRAY FROM FUNCTION
20
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
21
Heap API Example 2: Returning An “Array” From Function!
#include
int* create_array (int length) {
int* array = NULL ;
array = malloc (length * sizeof(int)) ;
return (array) ;
}
int main () {
int len = 2 ;
int* int_array = NULL ;
int_array = create_array(len) ;
if (int_array == NULL) return 1 ;
int_array[0]=0 ; // data is in heap!
int_array[1]=1 ;
free(int_array);
return 0 ;
} We are not returning a local variable’s address
Instead we are returning an address on the heap
RA
argsx7FFF
x7FFD
x7FFE RV
2x7FFB
R5
len
FPx7FFC
0x4006 int_array[0]
1x4007
heap memory
int_array[1]
NULLx7FFA *int_array
2
Xx7FF8
x7FF9
x7FF7 X
RV
length
RA
x7FF6 x7FFC FP
x7FF5 NULL *array
R5
x4006
x4006
x4006
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 3: STRINGS
(GLOBAL/STACK/HEAP)
23
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 3:
Strings (Global/Stack/Heap)
#include
char str_global[3] ;
int main () {
char* str_readonly = “Hi” ;
char str_stack[3] ;
char* str_heap ;
malloc (strlen(str_readonly)+1) ;
strcpy (str_global, str_readonly) ;
strcpy (str_stack, str_readonly) ;
strcpy (str_heap, str_readonly) ;
free(str_heap);
return 0 ;
} How long does heap memory last?
Until you free it!
Does it actually clear?
Does *str_heap change?
The other types are governed by compiler
RA
argsx7FFE
x7FFC
x7FFD RV
x200Dx7FFA
R5
*str_readonly
FPx7FFB
‘\0’x200C str_global[2]
‘H’x200D
Global/static Memory
‘\0’x7FF9 str_stack[2]
‘i’
‘H’str_stack
x7FF8
x7FF6 x4000
str_stack[0]
str_stack[1]
‘H’str_global str_global[0]
‘i’x200B str_global[1]
*str_heap
‘H’x4000 str_heap[0]
‘i’x4001 str_heap[1]
‘i’x200E str_readonly[1]
‘\0’x200F str_readonly[2]
‘\0’x4002 str_heap[2]
Heap Memory
Stack Memory
str_readonly[0]
=
24
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 4: STRUCTURES ON
STACK/ HEAP 1
26
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
27
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char name [4] ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name[3]
FPx7FFC
‘m’x7FFA my_cust.name[2]
X
Xx7FF8
x7FF9
x7FF7 X
my_cust.name[0]
my_cust.name[1]
my_cust.id
All data in this example lives on the stack!
stack memory
X
‘T’
‘o’
‘\0’
1234
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
28
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name[3]
FPx7FFC
Xx7FFA my_cust.name[2]
X
Xx7FF8
x7FF9
x7FF7 X
my_cust.name[0]
my_cust.name[1]
my_cust.id
What if we made this change?
Could I still do this? stack memory
‘T’
‘o’
‘\0’
1234
‘m’
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
29
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
What if we made this change?
Could I still do this? NO!
Is there an advantage to making “name” a pointer?
stack memory
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
30
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
Part of the structure is on the stack, part of it is on the heap!
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
x4000
stack memory
What is the advantage? We can hold any size name we’d like while running!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
31
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
We must free() memory, or we will have a memory leak
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
x4000
stack memory
Any call to malloc() must have a matching call to free()
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 5: STRUCTURES ON
STACK/ HEAP 2
33
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
34
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
x4000
stack memory
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
35
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
stack memory
What if we made my_cust a pointer?
Could I still do this?
x4000
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
36
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
my_cust is a pointer that points to nothing!
stack memory
What if we made my_cust a pointer?
Could I still do this? NO!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
37
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1234 ;
// allocate memory for “name” on the heap
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
*my_cust the pointer still lives on the stack
stack memory
We could allocate memory
for the customer on the heap!
Xx4000 id
Xx4001
heap memory
name*x4002
1234
Xx4002 name[0]‘T’
Xx4003 name[1]‘o’
Xx4004 ‘m’
Xx4005 ‘\0’
name[2]
name[3]
x4000
First call to malloc() allocates space for the struct
Second call to malloc() allocates space for the name array
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
38
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1234 ;
// allocate memory for “name” on the heap
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
free (my_cust) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
Memory leak = Memory on heap you can never reach!
stack memory
Xx4000 id
Xx4001
heap memory
name*x4002
1234
Xx4002 name[0]‘T’
Xx4003 name[1]‘o’
Xx4004 ‘m’
Xx4005 ‘\0’
name[2]
name[3]
x4000
Remember, each call to malloc() requires a corresponding call to free()
Freeing my_cust, before my_cust->name, will cause a memory leak
We could allocate memory
for the customer on the heap!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
39
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1234 ;
// allocate memory for “name” on the heap
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
free (my_cust.name) ; // free in proper order
free (my_cust) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
stack memory
Xx4000 id
Xx4001
heap memory
name*x4002
1234
Xx4002 name[0]‘T’
Xx4003 name[1]‘o’
Xx4004 ‘m’
Xx4005 ‘\0’
name[2]
name[3]
x4000
Two calls to malloc(), requires to calls to free(), in the proper order
What would heap look like if name was declared: char name[] ?
We could allocate memory
for the customer on the heap!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 6: LINKING
STRUCTURES ON THE HEAP
41
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
43
Heap API Example 6:
Linking Structures on the Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
int main () {
// allocate memory for 1st customer
customer* my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1 ;
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
// allocate memory for 2nd customer
my_cust->next = malloc ( sizeof(customer) ) ;
my_cust->next->id = 2 ;
my_cust->next->name = malloc (strlen(“Bob”) + 1) ;
strcpy (my_cust->next->name, “Bob”) ;
my_cust->next->next = NULL ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
Xx4002 next*x4007
Xx4009 next*NULL
This is known as a
“linked list”
data structure in C
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
What Have We Created?
• This notion of linking data structures together is referred to as a creating a “Linked List” in C
• A linked list is a type of data structure itself; the purpose of which is to “link” groups of data together
• We call the “groups” nodes in the context of a linked list
44
id
name
next
id
name
next
id
name
next
id
name
next NULL
NULL pointers act as signals…
…so we can find the end of the list
in cases where we might
be searching it!
Node 1 Node 2 Node 3 Node 4
Head Pointer
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Linked Lists Compared to Other Data Structures
• An array is also a data structure of sorts…
• Imagine: customer my_customer_list [100]
• This would give you 100 customer elements on the stack!
• Could even make an array on the heap:
• customer* my_customer_list = malloc (100* sizeof(customer))
• This would give you 100 customer elements on the heap!
• The problem with either type of array (stack or heap based); you must know its complete length when you create it
• We don’t need to know the length of the linked list when we allocate memory for it!
• This is due to our repeated use of calls to the heap
45
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Advantages/Disadvantages of a Linked List?
• What is the advantage of manually linking the nodes on our list using the heap?
• Growth of the list can be dynamic (occur while the programming is running)
• A more efficient use of memory (say you allocate 100 customers in an array, but only have 10!)
• Shrinking / reordering our list can also be dynamic
• These two advantages far outweigh the disadvantages!
• Compared to an array of data…
• Pointer & memory management is tricky (we have to become very good programmers)
• It’s more difficult to “traverse the list” (to find things)
• In an array, you simply index the array: my_customer_list[25], gets you the 25 customer
• Linked lists aren’t necessarily going to be in consecutive order on the heap (especially if we delete a node)
46
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LINKED LIST MANAGEMENT USING
HELPER FUNCTIONS
48
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Linked List Management Using Helper Functions
• Managing a linked list can be difficult
• Impossible if you try to do it all in main()!
• A common technique for managing a linked list is to create functions to help you accomplish common tasks:
• Adding Nodes to a Linked List, Deleting Nodes, Finding Nodes, Rearranging Nodes, Printing the list, etc.
• Over the next several segments we’ll create “helper” functions to
• We’ll use C’s “multifile” development capability to create a library that contains our helper function
• Multifile development simply refers to spreading your code across multiple files
• The intent is to centralize common code that other/future developers could use (in addition to yourself)
49
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• C allows you to put structure and function declarations in a special file called a “header file”
• A declaration in C is when you describe something to the compiler, but not actually ask for space for it
• For our linked list a prime example is our structure “declaration”
• The purpose of the file is to allow you to place common declarations you may make use of in future .C files
• You’ve used them many times already: stdio.h, string.h, but now you’re making your own!
50
Creating a Header File For Linked List
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer.h
A header file can be named
anything; must end in .h,
can only contain
“declarations”
not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: ADD_NODE()
ALGORITHM
52
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
id
name
next
Our First Helper Function: Add Node
• Adding a node to the end of the list, involves traversing the list to find its end
• We’ll create a “temporary pointer” to help us find the end of the list
• When: temp->next = NULL, we know we’re at the end of the list, we then attach “glue” on our new node
53
id
name
next
id
name
next
id
name
next NULL
Node 1 Node 2 Node 3
Temp Pointer
Head Pointer
Temp Pointer Temp Pointer
NULL
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
54
Recall…Example 6:
Linking Structures on the Heap
#include “customer.h”
#include
// definition of customer structure is in customer.h
int main () {
// allocate memory for 1st customer
customer* my_list = malloc ( sizeof(customer) ) ;
my_list->id = 1 ;
my_list->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_list->name, “Tom”) ;
my_list->next = NULL ;
// add second customer using helper function
add_customer (my_list, 2, “Bob”) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
x4000x7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
Xx4002 next*NULL
x4000x7FF8
2x7FF9
x2004x7FFA
list*
id
“Bob” (a literal)
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include customer structure declaration
#include
/* args: pointer to head of linked list + new customer info
returns: pointer to head of linked list */
customer* add_customer (customer* list, int id, char* name) {
/* allocate memory for a customer */
customer* new_cust = malloc ( sizeof(customer) ) ; // check!
new_cust->id = id ;
new_cust->name = malloc ( strlen(name) + 1) ;
strcpy (new_cust->name, name) ;
new_cust->next = NULL ;
/* if list was empty, return new customer as the head! */
if (list==NULL) {return (new_cust) ;}
/* otherwise, traverse list to the end, glue on new cust. */
customer* head = list ; // save start of list first
// traverse to the end
while (list->next != NULL) {list = list->next ;}
// glue new customer to the end of the list
list->next = new_cust ;
return (head) ; /* return “head” of the list */
}
56
Function to Add a Node to a Linked List 1x4000 idx4003x4001 name*
NULLx4002 next*
‘T’x4003 name[0]
‘o’x4004 name[1]
‘mx4005 name[2]
‘\0’x4006 name[3]
Xx4007 id
Xx4008 name*
Xx4009 next*
Xx400A name[0]
Xx400B name[1]
Xx400C name[2]
Xx400D name[3]
x4000x7FF3 head*
Xx7FF4 new_cust*
FP(x7FFC)x7FF5
RAx7FF6
RV(X)x7FF7
x4000x7FF8 arg: list*
2x7FF9 arg: id
X2004(Bob)x7FFA arg: name*
x4000x7FFB my_list*
FPx7FFC
RAx7FFD
RVx7FFE
argsx7FFF
R5
R5
main()’s
frame
x4007
2
x400A
‘B’
‘o’
‘b’
‘\0’
NULL
x4007
x4000)
customer.c - contains definition of add_customer()
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• We add to our header file
• We add the “declaration” of the function we just created: add_customer()
• Other developers could “include” this file and gain access to our functions
57
Update Our Header File
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
This is the declaration of add_customer(), since it is followed by a semicolon.
It is defined in customer.c
-the header file serves as an “advertisement” of the functions your have written
-think about strlen() – all you need to know if name, argument, return!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: ADD_NODE()
USING/CALLING ADD_NODE()
59
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include header file
#include
int main() {
// create the head node pointer
customer* my_list = NULL ;
// add the first customer/node
my_list =
add_customer (my_list, 1, “Tom”) ;
// add the second customer/node
add_customer (my_list, 2, “Bob”) ;
// we have more to do!
}
60
Let’s Update Our main()
RA
argsx7FFF
x7FFD
x7FFE RV
NULLx7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
NULLx4002 next*x4007
Xx4009 next*NULL
my_database.c
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• Recall that we must update the head pointer back in main() after a call to add_customer()
• This is only true during the first call to add_customer()
• We could update the head pointer inside add_customer() instead
61
Could We Have Used a Pointer to a Pointer Instead?
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name );
customer.h
This version of add_customer() internally updates the “head” pointer
-returns an “int” to give status to caller
Could you envision the code to make it work?
-how would you pass the list to add_customer2() from main()?
int add_customer2 (customer** list, int id, char* name);
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: SEARCH_NODE()
63
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include customer structure declaration
#include
/* args: pointer to head of linked list + customer ID to find
returns: pointer to matching customer on heap if found (else NULL) */
customer* find_customer_by_ID (customer* list, int id) {
/* traverse the list until we find first node with matching ID */
while ( (list != NULL) && (list->id != id) )
list = list->next ;
/* return either the found customer, or NULL */
return (list) ;
}
// notice this function works even if list was empty (NULL)
64
Function to Search for a Node in a Linked List
customer.c
We are adding
To customer.c
add_node()
would be
above this!
Notice, we keep changing list’s address
--Are we actually changing the head pointer in main()?
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• We add to our header file
• We add the “declaration” of the function we just created: find_customer_by_ID()
• Now we can make use of find customer in main()
65
Update Our Header File
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer* find_customer_by_ID (customer* list, int id) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include header file
#include
int main() {
// create head node, add customers
customer* my_list = NULL ;
my_list = add_customer (my_list, 1, “Tom”) ;
my_list = add_customer (my_list, 2, “Bob”) ;
// search for customer 2
customer* a_customer = NULL ;
a_customer
= find_customer_by_ID (my_list, 2) ;
// print out customer details
if (a_customer != NULL)
printf (“Customer ID=%d, Name=%s\n”,
a_customer->id, a_customer->name );
// more to implement
}
66
Let’s Update Our main()
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
Xx4002 next*x4007
Xx4009 next*NULL
my_database.c
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: DELETE_NODE()
68
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
id
name
next
Deleting a Node from a Linked List
• Deleting a Node involves finding the node to delete, then performing “surgery” on the list and free the node
• We’ll need 2 temporary pointers…one that points to node we wish to delete & the node before it!
• temp1->next = temp2->next
69
id
name
next
id
name
next
id
name
next
Node 1 Node 2 Node 3
Temp Pointer2
Head Pointer
Temp Pointer2
NULL
Temp Pointer2
Temp Pointer1 Temp Pointer1
….then we can free NODE3 using temp2!
Node 4
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include customer structure declaration
#include
/* args: pointer to head of linked list + customer ID to delete
returns: pointer to head of list */
customer* delete_customer_by_ID (customer* list, int id) {
// set two temporary pointers to the head of the list
customer* temp1 = temp2 = list ; // note: this is pseudo-code
// advance each pointer until we find node to delete
// then perform ‘surgery’ on the list
temp1->next = temp2->next ;
// deallocate ALL memory for the customer
free (temp2->name) ; // every call to malloc()…
free (temp2) ; // must have corresponding call to free()
// return head pointer – just in case we deleted the original!
}
70
Function to Delete a Node from a Linked List
customer.c
We are adding
to customer.c
Don’t forget to account for
the possibility of the
head of the list being the
one to delete!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• We add to our header file
• We add the “declaration” of the function we just created: delete_customer_by_ID()
• Now we can make use of delete customer in main()
71
Update Our Header File
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer* find_customer_by_ID (customer* list, int id) ;
customer* delete_customer_by_ID (customer* list, int id) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
An aside…
• Imagine you create a linked list, add many nodes…
• Then you delete a few nodes
• Perhaps you sort a few nodes
• This is all well and good, but…
• Try to imagine what the “heap” looks like!
• It is a mess, but it is your mess J
• It certainly won’t be in “order” in the way we would consider the stack in order
• The order is up to you! Unlike the stack, the programming is in charge of it
• As long as you have pointers to all memory you have allocated,
• you can properly manage your usage of the heap
72
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: ADDITIONAL
HELPER FUNCTIONS
74
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• You are welcome to add any functions related to linked list management to the header file
• I’ve added a few examples
• While the functions are common to most LLs, they depend upon the underlying struct
75
Adding Additional Functionality to Our Library
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer* find_customer_by_ID (customer* list, int id) ;
customer* delete_customer_by_ID (customer* list, int id) ;
customer* delete_all_customers (customer* list) ;
void print_all_customers (customer* list) ;
…
customer* find_customer_by_Name (customer* list, char* name) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include header file
#include
int main() {
// create head node, add customers
customer* my_list = NULL ;
my_list = add_customer (my_list, 1, “Tom”) ;
my_list = add_customer (my_list, 2, “Bob”) ;
// do some fun stuff with our DB
// before we leave main() we must free() all
my_list = delete_all_customers (my_list) ;
return 0 ;
}
76
Let’s Update Our main()
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
Xx4002 next*x4007
Xx4009 next*NULL
my_database.c
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
DYNAMIC MEMORY ALLOCATION
PITFALLS
78
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
80
Dynamic Memory Allocation Pitfalls
Creativity is a poor substitute for knowing what you’re doing.
–Albert Einstein? Bob Colwell?
• Must have been talking about dynamic memory allocation
• (Then it couldn’t have been Einstein)
• Get one pointer wrong and the whole thing breaks
• In mysterious and hard-to-find ways
• What can go wrong? Glad you asked…
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
81
Memory Leaks
• If a heap block gets “lost”
• Most common cause
• You were done with memory you had allocated…
• Then you overwrote the last pointer that pointed to it…
• BUT you forgot to call free() on it first!
• This is called a “memory leak”
• Block is gone (cannot be reallocated) for duration of program
• If you do this repeatedly, your program won’t have heap anymore
• Garbage collection
• Helps avoid leaks while saving you from having to call free()
• “Reclaims” everything in heap region that is not pointed to
• C does not have this ( Java does)
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
82
Other Pitfalls
• “Buffer overflows”
• Example: ask for 10 bytes but write 11
• Bad to do in general but especially bad in the heap
• C does not check for this ( Java does)
• Not checking (or handling) NULL mallocs
• malloc() is allowed to return NULL (out of memory)
• Should check for NULL after every call to malloc()
• Passing a pointer to the middle of allocated region to free()
• free() won’t be able to find the block
MCIT 593 - Introduction to Computer Systems
DYNAMIC MEMORY ALLOCATION
2
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
What Is Dynamic Memory Allocation?
• “Dynamic” means “at run-time” (not “at compile-time”)
• Compiler does not have enough information to make final decision
• Unlike “automatic” or “static” memory allocation, e.g.: int a = 0 ;
• Dynamic memory allocation example
• We would love to make arrays of dynamic length!
• Our dream in C:
int length = 2 ;
int int_array [length] ; /* why won’t this compile? */
• Remember in assembly…
• If you could just find a free spot in memory, you could write to it
• We have the same thing in C (except it is a bit safer)
4
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
What Is The Heap?
• 3 possible places to store data in C on the LC4:
• The Stack (known at compile time)
• local variables, arguments, returns
• The Global Region (known at compile time)
• static vars (global or local static)
• The heap (accessible at runtime)
• x4000-x6FFF
• This region is the topic of this module
Global Region
(static vars)
Stack
(automatic vars)
x0000
x3FFF
x4000
x6FFF
x7000
x7FFF
x1FFF
x2000
Heap
(dynamic vars)
Program Memory
User Data Memory
partitioned further for C:
globals, heap, stack
5
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
ALLOCATING MEMORY
7
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API
• How does the programmer interface with “heap”?
• Two basic functions for heap: malloc() and free()
• Heap is managed by user-level C runtime library (libc)
• Interface function declarations found in stdlib.h
void* malloc(size_t size) ;
• Returns a pointer to a region on the heap of size size bytes
• If success, space is contiguous
• Recall that size_t is simply an typedef’d unsigned int
• Returns NULL if heap can’t fulfill request
• Recall that void* is “generic pointer” (C for “just an address”)
• Can pass it around, but not dereference
• Analogous to making a “reservation” for dinner – secures reservation, up to you to use!
8
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
FREEING MEMORY
10
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API
• How does the programmer interface with “heap”?
• Two basic functions for heap: malloc() and free()
• Heap is managed by user-level C runtime library (libc)
• Interface function declarations found in stdlib.h
void* malloc(size_t size) ;
• Returns a pointer to a region on the heap of size size bytes
• If success, space is contiguous
• If failure, returns NULL
• Analogous to making a “reservation” for dinner – secures reservation, up to you to use!
void free(void* ptr) ;
• Clears reservation for address pointed to be ptr
• The memory region pointed to by ptr, was previously given to you by malloc()
11
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 1: CREATING ARRAY
AT RUNTIME
13
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
Why can’t we do this?
pointer points
to nothing RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
stack memory
15
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
stack memory
Why can we do this now?
we have two spots
on the heap!
1
0
16
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
free() doesn’t actually modify *int_array or clear the heap!
stack memory
1
0
17Instead it releases your “reservation” on address x4000 for 8 bytes
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * ); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
sizeof() is actually an operator in C (not a function)
stack memory
1
0
18It can compute the size of its operand…works on any datatype…even structs!
sizeof(int)
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 2: RETURNING
ARRAY FROM FUNCTION
20
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
21
Heap API Example 2: Returning An “Array” From Function!
#include
int* create_array (int length) {
int* array = NULL ;
array = malloc (length * sizeof(int)) ;
return (array) ;
}
int main () {
int len = 2 ;
int* int_array = NULL ;
int_array = create_array(len) ;
if (int_array == NULL) return 1 ;
int_array[0]=0 ; // data is in heap!
int_array[1]=1 ;
free(int_array);
return 0 ;
} We are not returning a local variable’s address
Instead we are returning an address on the heap
RA
argsx7FFF
x7FFD
x7FFE RV
2x7FFB
R5
len
FPx7FFC
0x4006 int_array[0]
1x4007
heap memory
int_array[1]
NULLx7FFA *int_array
2
Xx7FF8
x7FF9
x7FF7 X
RV
length
RA
x7FF6 x7FFC FP
x7FF5 NULL *array
R5
x4006
x4006
x4006
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 3: STRINGS
(GLOBAL/STACK/HEAP)
23
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 3:
Strings (Global/Stack/Heap)
#include
char str_global[3] ;
int main () {
char* str_readonly = “Hi” ;
char str_stack[3] ;
char* str_heap ;
malloc (strlen(str_readonly)+1) ;
strcpy (str_global, str_readonly) ;
strcpy (str_stack, str_readonly) ;
strcpy (str_heap, str_readonly) ;
free(str_heap);
return 0 ;
} How long does heap memory last?
Until you free it!
Does it actually clear?
Does *str_heap change?
The other types are governed by compiler
RA
argsx7FFE
x7FFC
x7FFD RV
x200Dx7FFA
R5
*str_readonly
FPx7FFB
‘\0’x200C str_global[2]
‘H’x200D
Global/static Memory
‘\0’x7FF9 str_stack[2]
‘i’
‘H’str_stack
x7FF8
x7FF6 x4000
str_stack[0]
str_stack[1]
‘H’str_global str_global[0]
‘i’x200B str_global[1]
*str_heap
‘H’x4000 str_heap[0]
‘i’x4001 str_heap[1]
‘i’x200E str_readonly[1]
‘\0’x200F str_readonly[2]
‘\0’x4002 str_heap[2]
Heap Memory
Stack Memory
str_readonly[0]
=
24
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 4: STRUCTURES ON
STACK/ HEAP 1
26
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
27
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char name [4] ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name[3]
FPx7FFC
‘m’x7FFA my_cust.name[2]
X
Xx7FF8
x7FF9
x7FF7 X
my_cust.name[0]
my_cust.name[1]
my_cust.id
All data in this example lives on the stack!
stack memory
X
‘T’
‘o’
‘\0’
1234
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
28
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name[3]
FPx7FFC
Xx7FFA my_cust.name[2]
X
Xx7FF8
x7FF9
x7FF7 X
my_cust.name[0]
my_cust.name[1]
my_cust.id
What if we made this change?
Could I still do this? stack memory
‘T’
‘o’
‘\0’
1234
‘m’
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
29
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
What if we made this change?
Could I still do this? NO!
Is there an advantage to making “name” a pointer?
stack memory
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
30
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
Part of the structure is on the stack, part of it is on the heap!
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
x4000
stack memory
What is the advantage? We can hold any size name we’d like while running!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
31
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
We must free() memory, or we will have a memory leak
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
x4000
stack memory
Any call to malloc() must have a matching call to free()
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 5: STRUCTURES ON
STACK/ HEAP 2
33
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
34
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
x4000
stack memory
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
35
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name *
FPx7FFC
1234x7FFA my_cust.id
Xx4000 [0]
Xx4001
heap memory
[1]‘o’
‘T’
Xx4002 [2]‘m’
Xx4003 [3]‘\0’
stack memory
What if we made my_cust a pointer?
Could I still do this?
x4000
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
36
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust.id = 1234 ;
// allocate memory for “name” on the heap
my_cust.name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust.name, “Tom”) ;
free (my_cust.name) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
my_cust is a pointer that points to nothing!
stack memory
What if we made my_cust a pointer?
Could I still do this? NO!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
37
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1234 ;
// allocate memory for “name” on the heap
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
*my_cust the pointer still lives on the stack
stack memory
We could allocate memory
for the customer on the heap!
Xx4000 id
Xx4001
heap memory
name*x4002
1234
Xx4002 name[0]‘T’
Xx4003 name[1]‘o’
Xx4004 ‘m’
Xx4005 ‘\0’
name[2]
name[3]
x4000
First call to malloc() allocates space for the struct
Second call to malloc() allocates space for the name array
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
38
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1234 ;
// allocate memory for “name” on the heap
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
free (my_cust) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
Memory leak = Memory on heap you can never reach!
stack memory
Xx4000 id
Xx4001
heap memory
name*x4002
1234
Xx4002 name[0]‘T’
Xx4003 name[1]‘o’
Xx4004 ‘m’
Xx4005 ‘\0’
name[2]
name[3]
x4000
Remember, each call to malloc() requires a corresponding call to free()
Freeing my_cust, before my_cust->name, will cause a memory leak
We could allocate memory
for the customer on the heap!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
39
Heap API Example 5: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer* my_cust ; // allocate *my_cust on stack
my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1234 ;
// allocate memory for “name” on the heap
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
free (my_cust.name) ; // free in proper order
free (my_cust) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
stack memory
Xx4000 id
Xx4001
heap memory
name*x4002
1234
Xx4002 name[0]‘T’
Xx4003 name[1]‘o’
Xx4004 ‘m’
Xx4005 ‘\0’
name[2]
name[3]
x4000
Two calls to malloc(), requires to calls to free(), in the proper order
What would heap look like if name was declared: char name[] ?
We could allocate memory
for the customer on the heap!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 6: LINKING
STRUCTURES ON THE HEAP
41
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
43
Heap API Example 6:
Linking Structures on the Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
int main () {
// allocate memory for 1st customer
customer* my_cust = malloc ( sizeof(customer) ) ;
my_cust->id = 1 ;
my_cust->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_cust->name, “Tom”) ;
// allocate memory for 2nd customer
my_cust->next = malloc ( sizeof(customer) ) ;
my_cust->next->id = 2 ;
my_cust->next->name = malloc (strlen(“Bob”) + 1) ;
strcpy (my_cust->next->name, “Bob”) ;
my_cust->next->next = NULL ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_cust
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
Xx4002 next*x4007
Xx4009 next*NULL
This is known as a
“linked list”
data structure in C
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
What Have We Created?
• This notion of linking data structures together is referred to as a creating a “Linked List” in C
• A linked list is a type of data structure itself; the purpose of which is to “link” groups of data together
• We call the “groups” nodes in the context of a linked list
44
id
name
next
id
name
next
id
name
next
id
name
next NULL
NULL pointers act as signals…
…so we can find the end of the list
in cases where we might
be searching it!
Node 1 Node 2 Node 3 Node 4
Head Pointer
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Linked Lists Compared to Other Data Structures
• An array is also a data structure of sorts…
• Imagine: customer my_customer_list [100]
• This would give you 100 customer elements on the stack!
• Could even make an array on the heap:
• customer* my_customer_list = malloc (100* sizeof(customer))
• This would give you 100 customer elements on the heap!
• The problem with either type of array (stack or heap based); you must know its complete length when you create it
• We don’t need to know the length of the linked list when we allocate memory for it!
• This is due to our repeated use of calls to the heap
45
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Advantages/Disadvantages of a Linked List?
• What is the advantage of manually linking the nodes on our list using the heap?
• Growth of the list can be dynamic (occur while the programming is running)
• A more efficient use of memory (say you allocate 100 customers in an array, but only have 10!)
• Shrinking / reordering our list can also be dynamic
• These two advantages far outweigh the disadvantages!
• Compared to an array of data…
• Pointer & memory management is tricky (we have to become very good programmers)
• It’s more difficult to “traverse the list” (to find things)
• In an array, you simply index the array: my_customer_list[25], gets you the 25 customer
• Linked lists aren’t necessarily going to be in consecutive order on the heap (especially if we delete a node)
46
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LINKED LIST MANAGEMENT USING
HELPER FUNCTIONS
48
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Linked List Management Using Helper Functions
• Managing a linked list can be difficult
• Impossible if you try to do it all in main()!
• A common technique for managing a linked list is to create functions to help you accomplish common tasks:
• Adding Nodes to a Linked List, Deleting Nodes, Finding Nodes, Rearranging Nodes, Printing the list, etc.
• Over the next several segments we’ll create “helper” functions to
• We’ll use C’s “multifile” development capability to create a library that contains our helper function
• Multifile development simply refers to spreading your code across multiple files
• The intent is to centralize common code that other/future developers could use (in addition to yourself)
49
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• C allows you to put structure and function declarations in a special file called a “header file”
• A declaration in C is when you describe something to the compiler, but not actually ask for space for it
• For our linked list a prime example is our structure “declaration”
• The purpose of the file is to allow you to place common declarations you may make use of in future .C files
• You’ve used them many times already: stdio.h, string.h, but now you’re making your own!
50
Creating a Header File For Linked List
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer.h
A header file can be named
anything; must end in .h,
can only contain
“declarations”
not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: ADD_NODE()
ALGORITHM
52
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
id
name
next
Our First Helper Function: Add Node
• Adding a node to the end of the list, involves traversing the list to find its end
• We’ll create a “temporary pointer” to help us find the end of the list
• When: temp->next = NULL, we know we’re at the end of the list, we then attach “glue” on our new node
53
id
name
next
id
name
next
id
name
next NULL
Node 1 Node 2 Node 3
Temp Pointer
Head Pointer
Temp Pointer Temp Pointer
NULL
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
54
Recall…Example 6:
Linking Structures on the Heap
#include “customer.h”
#include
// definition of customer structure is in customer.h
int main () {
// allocate memory for 1st customer
customer* my_list = malloc ( sizeof(customer) ) ;
my_list->id = 1 ;
my_list->name = malloc (strlen(“Tom”) + 1) ;
strcpy (my_list->name, “Tom”) ;
my_list->next = NULL ;
// add second customer using helper function
add_customer (my_list, 2, “Bob”) ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
x4000x7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
Xx4002 next*NULL
x4000x7FF8
2x7FF9
x2004x7FFA
list*
id
“Bob” (a literal)
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include customer structure declaration
#include
/* args: pointer to head of linked list + new customer info
returns: pointer to head of linked list */
customer* add_customer (customer* list, int id, char* name) {
/* allocate memory for a customer */
customer* new_cust = malloc ( sizeof(customer) ) ; // check!
new_cust->id = id ;
new_cust->name = malloc ( strlen(name) + 1) ;
strcpy (new_cust->name, name) ;
new_cust->next = NULL ;
/* if list was empty, return new customer as the head! */
if (list==NULL) {return (new_cust) ;}
/* otherwise, traverse list to the end, glue on new cust. */
customer* head = list ; // save start of list first
// traverse to the end
while (list->next != NULL) {list = list->next ;}
// glue new customer to the end of the list
list->next = new_cust ;
return (head) ; /* return “head” of the list */
}
56
Function to Add a Node to a Linked List 1x4000 idx4003x4001 name*
NULLx4002 next*
‘T’x4003 name[0]
‘o’x4004 name[1]
‘mx4005 name[2]
‘\0’x4006 name[3]
Xx4007 id
Xx4008 name*
Xx4009 next*
Xx400A name[0]
Xx400B name[1]
Xx400C name[2]
Xx400D name[3]
x4000x7FF3 head*
Xx7FF4 new_cust*
FP(x7FFC)x7FF5
RAx7FF6
RV(X)x7FF7
x4000x7FF8 arg: list*
2x7FF9 arg: id
X2004(Bob)x7FFA arg: name*
x4000x7FFB my_list*
FPx7FFC
RAx7FFD
RVx7FFE
argsx7FFF
R5
R5
main()’s
frame
x4007
2
x400A
‘B’
‘o’
‘b’
‘\0’
NULL
x4007
x4000)
customer.c - contains definition of add_customer()
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• We add to our header file
• We add the “declaration” of the function we just created: add_customer()
• Other developers could “include” this file and gain access to our functions
57
Update Our Header File
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
This is the declaration of add_customer(), since it is followed by a semicolon.
It is defined in customer.c
-the header file serves as an “advertisement” of the functions your have written
-think about strlen() – all you need to know if name, argument, return!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: ADD_NODE()
USING/CALLING ADD_NODE()
59
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include header file
#include
int main() {
// create the head node pointer
customer* my_list = NULL ;
// add the first customer/node
my_list =
add_customer (my_list, 1, “Tom”) ;
// add the second customer/node
add_customer (my_list, 2, “Bob”) ;
// we have more to do!
}
60
Let’s Update Our main()
RA
argsx7FFF
x7FFD
x7FFE RV
NULLx7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
NULLx4002 next*x4007
Xx4009 next*NULL
my_database.c
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• Recall that we must update the head pointer back in main() after a call to add_customer()
• This is only true during the first call to add_customer()
• We could update the head pointer inside add_customer() instead
61
Could We Have Used a Pointer to a Pointer Instead?
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name );
customer.h
This version of add_customer() internally updates the “head” pointer
-returns an “int” to give status to caller
Could you envision the code to make it work?
-how would you pass the list to add_customer2() from main()?
int add_customer2 (customer** list, int id, char* name);
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: SEARCH_NODE()
63
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include customer structure declaration
#include
/* args: pointer to head of linked list + customer ID to find
returns: pointer to matching customer on heap if found (else NULL) */
customer* find_customer_by_ID (customer* list, int id) {
/* traverse the list until we find first node with matching ID */
while ( (list != NULL) && (list->id != id) )
list = list->next ;
/* return either the found customer, or NULL */
return (list) ;
}
// notice this function works even if list was empty (NULL)
64
Function to Search for a Node in a Linked List
customer.c
We are adding
To customer.c
add_node()
would be
above this!
Notice, we keep changing list’s address
--Are we actually changing the head pointer in main()?
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• We add to our header file
• We add the “declaration” of the function we just created: find_customer_by_ID()
• Now we can make use of find customer in main()
65
Update Our Header File
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer* find_customer_by_ID (customer* list, int id) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include header file
#include
int main() {
// create head node, add customers
customer* my_list = NULL ;
my_list = add_customer (my_list, 1, “Tom”) ;
my_list = add_customer (my_list, 2, “Bob”) ;
// search for customer 2
customer* a_customer = NULL ;
a_customer
= find_customer_by_ID (my_list, 2) ;
// print out customer details
if (a_customer != NULL)
printf (“Customer ID=%d, Name=%s\n”,
a_customer->id, a_customer->name );
// more to implement
}
66
Let’s Update Our main()
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
Xx4002 next*x4007
Xx4009 next*NULL
my_database.c
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: DELETE_NODE()
68
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
id
name
next
Deleting a Node from a Linked List
• Deleting a Node involves finding the node to delete, then performing “surgery” on the list and free the node
• We’ll need 2 temporary pointers…one that points to node we wish to delete & the node before it!
• temp1->next = temp2->next
69
id
name
next
id
name
next
id
name
next
Node 1 Node 2 Node 3
Temp Pointer2
Head Pointer
Temp Pointer2
NULL
Temp Pointer2
Temp Pointer1 Temp Pointer1
….then we can free NODE3 using temp2!
Node 4
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include customer structure declaration
#include
/* args: pointer to head of linked list + customer ID to delete
returns: pointer to head of list */
customer* delete_customer_by_ID (customer* list, int id) {
// set two temporary pointers to the head of the list
customer* temp1 = temp2 = list ; // note: this is pseudo-code
// advance each pointer until we find node to delete
// then perform ‘surgery’ on the list
temp1->next = temp2->next ;
// deallocate ALL memory for the customer
free (temp2->name) ; // every call to malloc()…
free (temp2) ; // must have corresponding call to free()
// return head pointer – just in case we deleted the original!
}
70
Function to Delete a Node from a Linked List
customer.c
We are adding
to customer.c
Don’t forget to account for
the possibility of the
head of the list being the
one to delete!
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• We add to our header file
• We add the “declaration” of the function we just created: delete_customer_by_ID()
• Now we can make use of delete customer in main()
71
Update Our Header File
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer* find_customer_by_ID (customer* list, int id) ;
customer* delete_customer_by_ID (customer* list, int id) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
An aside…
• Imagine you create a linked list, add many nodes…
• Then you delete a few nodes
• Perhaps you sort a few nodes
• This is all well and good, but…
• Try to imagine what the “heap” looks like!
• It is a mess, but it is your mess J
• It certainly won’t be in “order” in the way we would consider the stack in order
• The order is up to you! Unlike the stack, the programming is in charge of it
• As long as you have pointers to all memory you have allocated,
• you can properly manage your usage of the heap
72
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
LL HELPER FUNCTIONS: ADDITIONAL
HELPER FUNCTIONS
74
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
• You are welcome to add any functions related to linked list management to the header file
• I’ve added a few examples
• While the functions are common to most LLs, they depend upon the underlying struct
75
Adding Additional Functionality to Our Library
typedef struct cust_struct {
int id ;
char* name ;
struct cust_struct *next ;
} customer ;
customer* add_customer (customer* list, int id, char* name) ;
customer* find_customer_by_ID (customer* list, int id) ;
customer* delete_customer_by_ID (customer* list, int id) ;
customer* delete_all_customers (customer* list) ;
void print_all_customers (customer* list) ;
…
customer* find_customer_by_Name (customer* list, char* name) ;
customer.h
A header file can be named
anything, must end in .h
but can only contain
“declarations”
And not “definitions”
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
#include “customer.h” // include header file
#include
int main() {
// create head node, add customers
customer* my_list = NULL ;
my_list = add_customer (my_list, 1, “Tom”) ;
my_list = add_customer (my_list, 2, “Bob”) ;
// do some fun stuff with our DB
// before we leave main() we must free() all
my_list = delete_all_customers (my_list) ;
return 0 ;
}
76
Let’s Update Our main()
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*my_list
FPx7FFC
Xx4000 id
Xx4001 name*x4003
1
Xx4003 name[0]‘T’
Xx4004 name[1]‘o’
Xx4005 ‘m’
Xx4006 ‘\0’
name[2]
name[3]
x4000
Xx4007 id
Xx4008 name*x400A
2
Xx400A name[0]‘B’
Xx400B name[1]‘o’
Xx400C ‘b’
Xx400D ‘\0’
name[2]
name[3]
Xx4002 next*x4007
Xx4009 next*NULL
my_database.c
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
DYNAMIC MEMORY ALLOCATION
PITFALLS
78
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
80
Dynamic Memory Allocation Pitfalls
Creativity is a poor substitute for knowing what you’re doing.
–Albert Einstein? Bob Colwell?
• Must have been talking about dynamic memory allocation
• (Then it couldn’t have been Einstein)
• Get one pointer wrong and the whole thing breaks
• In mysterious and hard-to-find ways
• What can go wrong? Glad you asked…
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
81
Memory Leaks
• If a heap block gets “lost”
• Most common cause
• You were done with memory you had allocated…
• Then you overwrote the last pointer that pointed to it…
• BUT you forgot to call free() on it first!
• This is called a “memory leak”
• Block is gone (cannot be reallocated) for duration of program
• If you do this repeatedly, your program won’t have heap anymore
• Garbage collection
• Helps avoid leaks while saving you from having to call free()
• “Reclaims” everything in heap region that is not pointed to
• C does not have this ( Java does)
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
82
Other Pitfalls
• “Buffer overflows”
• Example: ask for 10 bytes but write 11
• Bad to do in general but especially bad in the heap
• C does not check for this ( Java does)
• Not checking (or handling) NULL mallocs
• malloc() is allowed to return NULL (out of memory)
• Should check for NULL after every call to malloc()
• Passing a pointer to the middle of allocated region to free()
• free() won’t be able to find the block
