My Corner of the Web
C Pointers and Dynamic Memory Management
Michael C. Daconta
QED Publishing Group
* Over 150 Source Functions!
* Pointer Pointers and Function Pointers!
* Dangling Pointers and Other Traps!
* Memory Debugger and C lexical Analyzer!
* Memory Management and Data Structures!
* Free Source Disk!
TABLE OF CONTENTS
Chapter 1 - An intuitive approach
Chapter 2 - Globals, the Stack and Heap Space
2.1 Globals
2.2 The Stack
2.3 The compiler and the application stack
2.4 The heap
Chapter 3 - Declaring, Assigning, and Dereferencing
Chapter 4 - Pass by Value versus Pass by Reference
Chapter 5 - Arrays and Pointers
5.1 Code Review
Chapter 6 - Structures and Pointers
6.1 Code Review
Chapter 7 - Strings and Pointers
7.1 Code Review
Chapter 8 - Pointers and Dynamic Memory
8.1 Basic Building Blocks
8.2 Thinking Dynamic
Chapter 9 - Pointer Pointers and Dynamic Array Initialization
Chapter 10 - Pointer Pointers and Pointer Arrays
Chapter 11 - Pointers and Abstract Data Types
11.1 stacks
11.2 linked lists
11.3 binary trees
Chapter 12 - Function Pointers
12.1 Concept of function pointers
12.2 Syntax of function pointers
12.3 Applications of function pointers
Chapter 13 - Memory Management Internals
Chapter 14 - Pointer Traps and Pitfalls
14.1 Trap One: Forgetting the NUL terminator
14.2 Trap One Dissection
14.3 Trap One Solution
14.4 Trap Two: Asking malloc() for the wrong number of bytes
14.5 Trap Two Dissection
14.6 Trap Two Solution
14.7 Trap Two Catcher
14.8 Trap Three: Overrunning Arrays
14.9 Trap Three Dissection
14.10 Trap Three Catcher
14.11 Trap Four: Not freeing all memory
14.12 Trap Four Dissection
14.13 Trap Four Solution
14.14 The multi_free Solution
14.15 Trap Five: Incorrect Operator Precedence
14.16 Trap Five Dissection
14.17 Trap Five Solution
14.18 Trap Six: Dangling Pointers
14.19 Trap Six Solution
14.20 Other Traps
Chapter 15 - Code Libraries
15.1 ppbuf_utils
15.2 quicksort() to sort ppbufs
15.3 ppblock_utils
15.4 simple_clex and software validation
Appendix A
A.1 How does a memory location store a binary number?
A.2 The binary number system
A.3 How can a computer address a memory location?
A.4 The address bus
Glossary
Index
LIST OF ILLUSTRATIONS
Figure 1.1 A pointer as a container
Figure 1.2 Memory as a row of containers
Figure 2.1 A microcomputers memory
Figure 2.2 A classic stack
Figure 2.3 Stack as a LIFO structure
Figure 2.4 function as a black box
Figure 2.5 Parameter Copying
Figure 3.1 Paper Computer on pointer assignment
Figure 4.1 lvalue and rvalue of a variable
Figure 4.2 Paper Computer on pass by reference
Figure 5.1 An array as container
Figure 5.2 Paper Computer on array indexing
Figure 7.1 Strings as containers
Figure 8.1 Requesting a system resource
Figure 8.2 The free list
Figure 8.3 The dictionary pointer pointer
Figure 8.4 The rows of the pointer pointer
Figure 9.1 A pointer pointer as a container
Figure 9.2 A Paper Computer on stack variables
Figure 10.1 How to set up a pointer array
Figure 10.2 A char ppbuf
Figure 10.3 Paper Computer on **argv
Figure 11.1 The string stack
Figure 11.2 A sample linked list
Figure 11.3 Adding a node to a linked lint
Figure 11.4 Deleting a node from a linked list
Figure 11.5 A sample binary tree
Figure 13.1 Memory Management Methodology
Figure 13.2 fooalign structure
Figure 13.3 A non-coalesced free list
Figure 13.4 A coalesced free list
Figure 13.5 A malloced memory block
Figure 13.6 Carving off a memory hunk
Figure 14.1 Heap dissection
Figure 14.2 Heap corruption
Figure 14.3 The parsing process
Figure 14.4 Operator precedence with containers
Figure A.1 A number system example
Figure A.2 Decimal to Binary
Figure A.3 A microprocessor bus scheme
LIST OF TABLES
Table 13.1 Default alignment and rounding on common computers
Table 14.1 Parser Operations
Table 14.2 Operator Precedence
Table A.1 Data sizes
LIST OF SOURCE CODE
Source 1.1 pointer_intro.c
Source 2.1 globals.c
Source 3.1 declare.c
Source 3.2 address_operator.c
Source 3.3 dereference.c
Source 4.1 stack_copy.c
Source 4.2 pass_address.c
Source 5.1 index.c
Source 5.2 test_scores.c
Source 6.1 struct_test.c
Source 6.2 tiny_dict.c
Source 7.1 traverse.c
Source 7.2 count.c
Source 8.1 strings.c
Source 8.2 string_tst.c
Source 8.3 dynamic_scores.c
Source 8.4 hyper_dict.c
Source 9.1 stack_variable.c
Source 9.2 dynamic_initialize.c
Source 10.1 class_ppbuf.c
Source 10.2 ppbuf_utils.c
Source 10.3 dissect.c
Source 10.4 cmd_line.c
Source 11.1 string_stack.c
Source 11.2 test_stack.c
Source 11.3 gll.c
Source 11.4 tstgll.c
Source 11.5 generic_tree.c
Source 12.1 funcptr.c
Source 12.3 dispatcher.c
Source 12.4 changeprio.c
Source 13.1 fooalign.c
Source 13.2 debug_memory.h
Source 13.3 set_mem function
Source 13.4 get_mem function
Source 13.5 check_magic function
Source 13.6 check_free_list function
Source 13.7 print_free_list function
Source 13.8 memory_map function
Source 13.9 check_heap function
Source 13.10 dbg_malloc function
Source 13.11 dbg_free function
Source 13.12 dbg_realloc function
Source 13.13 dbg_strdup function
Source 13.14 print_stats function
Source 13.15 memory_test.c
Source 14.1 forget_null.c
Source 14.2 bad_request.c
Source 14.3 bad_request2.c
Source 14.4 bad_array.c
Source 14.5 tokenize_it.c
Source 14.6 terminator.c
Source 14.7 BAD_multiple_exit.c
Source 14.8 BETTER_multiple_exit.c
Source 14.9 BAD_precedence.c
Source 14.10 dangling1.c
Source 14.11 dangling2.c
Preface
"What is confusing, though, is when a single system admits of two or more descriptions on different levels which nevertheless resemble each other in some way. Then we find it hard to avoid mixing levels when we think about the system, and can easily get totally lost."
- Godel, Escher, Bach: an eternal golden braid, Douglas Hofstadter
This book fills a gap not filled by the current scores of programming books on the market. I've read alot of those programming manuals and because they cover the whole C language they only give a cursory treatment of pointers. They leave the hard experimentation to the dedicated programmer. That is dangerous because many beginning and intermediate programmers do not have hours to spend experimenting with pointers. They have to get those programs to work now, and if that means doing it without pointers then they will use an inefficient and ugly method just to get the program to compile! I am dedicating this book to all those beginning and intermediate programmers on Prodigy¨ whose many pointer questions convinced me there was a gap to be filled. I hope that I am worthy for the task.
This book has been structured and written with many different programmers (of varying experience) in mind. Different people absorb information in different ways. This book provides three avenues of learning and experimentation:
1) Concepts - Explain the concepts of Pointers and Dynamic Memory Management in detail.
2) Code Reviews - Walk through working code examples (also use a "Paper Computer" to illustrate code execution).
3) Libraries - Provide generic code libraries to protect and enhance your own applications.
Acknowledgements
Thank you, Lynne, my wife, for struggling through this with me. Day by day. Page by page.
Thank you, Ed Kerr, President of QED Publishing Group, for helping me through my first book with patience and wise counsel.
Thank you, Everett Nelson, my friend, for proofing this, printing drafts and always being there.
Thank you, my other friends and co-workers at Mystech Associates, Inc. who reviewed pieces of the manuscript.
Thank you, computer friends on Prodigy, Compuserve and AppleLink for you inspiration and assistance.
Introduction
If you cringed when you saw the title of this book, this book is for you! So many programmers are down right petrified of pointers, that any mention of them will send novice programmers diving beneath their desks and grabbing for crosses! BACK! BACK, I SAY! Some programmers use pointers only when they are backed into a corner and forced to dig out their data structure text books. If you are one of those people, let me show you how simple pointers really are so you can unlock their power and take on challenging programming tasks! If you are already familiar with pointers this book will hone your skills to the point of mastery!
Why should I learn pointers? Pointers are a defining issue in the growth of a programmer. Until you vault the "pointer obstacle" you cannot move forward and grow further in your programming skills. Pointers are a defining issue because they are the keys to real data manipulation within a computer. Most advanced applications use data structures involving pointers. Pointers allow you to store data in an infinite variety of ways. The C language provides open access (and an open challenge) to the full scope and breadth of pointers. This book will guide you through each step of the way to vault the "pointer obstacle."
Why should I learn pointers through C? Why not learn Pascal pointers? Most languages protect both programs and programmers from the dangers of pointer errors by tightly controlling manipulation of pointers and by hiding operations only accomplished through pointers; on the other hand, C both encourages and sometimes forces programmers to pass and manipulate data through pointers! If you want to retrieve arguments from the command line you must use pointers. If you want to pass an argument into a function and have that function change its value you must pass a pointer to the variable. If you want to pass a variable number of arguments to a function, you must use pointers. The Bottom Line is that to program effectively in C you must love pointers!
Love pointers? Not in the romantic sense, but pointers have to thrill you! You should get excited when you see:
char **dynamic_string_array;
dynamic_string_array = (char **) malloc(sizeof(char *) * 10);
Don't be afraid of the symbology! Get used to (**) and (&) and (->) and even (array[*myvar]->yourvar)! After a few practice exercises in the following chapters you will see that those symbols are just funny shapes for (hammer) and (saw) and (screwdriver) - just funny symbols for programming tools! In the chapters ahead you will learn hundreds of reasons why pointers are the fastest and most efficient method of manipulating data!
What do I already need to know to understand this book? The only pre-requisite for this book is a basic understanding of the C programming language. If you know how to write and compile simple C programs then you can benefit from this book. Most everything else is explained in detail.
Questions and Comments:
This book is being written by a programmer for programmers. All comments, suggestions, questions, and advice is greatly appreciated from the entire computing community. My goal is to produce the best book possible and therefore I am always willing to improve upon my work. I can be reached on Prodigy (JFXV08A) or you can write to:
Michael Daconta
c/o
QED Technical Publishing
170 Linden Street
Wellesley, Massachusetts 02181-0013
;-)
2006 Comments:
Note1: The electronic and physical addresses above are no longer relevant.
Interesting facts:
I wrote this book after learning C for a simulation program I was working on. I had to convince my boss to let me use C because the main simulation was all written in Fortran. Since my new piece was an "add-on" to the simulation and not connected to the main process, I was given this flexibility. As I was learning C, I quickly realized that the hardest part of the language was pointers. Unfortunately, there was a discrepancy because all the books only gave a few pages to the subject. That made no sense to me. At the same time, I began answering questions about pointers on the prodigy forums. One day, I received a catalog from QED that had a "call for authors" on the back page. I sent my idea and 40 pages of answered questions from the forums to the publisher and he liked the idea. Thus, this book was born.
Amazingly, I wrote this book in an intensive 3-4 month period. No other book that I wrote ever matched that feat. Since I am now working on a new book, I look back at that in awe ... I really have no idea how I punched that one out so quickly (Ahhhh... to be young again ;^)