TRANSLATING SOME WELL-KNOWN PROBLEMS

20.01

It is an extremely useful exercise to translate some well-known 
imortant programming problems into the language of pointers and 
pointer arithmetic:
 
•	selection sort
•	insertion sort
•	binary search recursive version
	binary search iterative version

These problems have been treated during Programming 1 and
there you can find complete versions of their designs (HC 07.10-13).

20.01

TABLE OF CONTENTS HC 20

20.02

SELECTION SORT

20.02

Selection sort:
•	remember the design principles:
	•	swap a[0] with smallest elt in a[0..n)
	•	sort the remaining part a[1..n)

	void selection_sort(int *a, int n) {
		if (n) {
			swap(a, min(a, a + n - 1));
			selection_sort(++a, --n);  // continue recursively
		}
	}

	int* min(int* a, int *b) {
		return((a == b) ? b : min2(a, min(a + 1, b)));
	}
	int* min2(int* a, int* b) {
		return((*a < *b) ? a : b);
	}

	void swap(int* a, int* b) {
		int c = *a; *a = *b; *b = c;
	}

20.01

TABLE OF CONTENTS HC 20

20.03

INSERTION SORT

20.03

Insertion sort:
•	remember the design principles:
	•	if a[0..m) is sorted shift/rotate a[m] to the left
		until it arrives at its proper location
	•	apply the shift/rotation for m = 2 .. n-1

	void insertion_sort(int *a, int n) {
		int *ubnd = a,             // ptr to first element
	   		*z = a + n;            // ptr beyond the last elt
		while (++ubnd < z) {       // investigate [a..ubnd) 
			int *lbnd = a;             // init lbnd for shift
			while (*ubnd >= *lbnd)     // get actual lbnd 
				lbnd++;
			rotate(lbnd, ubnd);        // perform rotation
		}
	}
	void rotate(int *lbnd, int* ubnd) {
		int cur = *ubnd;         // value to investigate
		while (ubnd-- > lbnd)
			*(ubnd + 1) = *ubnd; // shift elements
		*(ubnd + 1) = cur;       // put cur in empty loc
	}

20.02

TABLE OF CONTENTS HC 20

20.04

BINARY SEARCH

20.04

Binary search:
•	remember the design principles:
	•	divide search domain into equal parts
	•	decide where the search must continue

int* bins_rec(int to_be_found, int* lbnd, int* ubnd) {
	int* mid = NULL;
	if (lbnd > ubnd)
		return(NULL);
	mid = lbnd + (ubnd - lbnd) /2;
	switch (compare(to_be_found, *mid)) {
		case -1: return(bins_rec(to_be_found, lbnd, mid - 1));
		case  0: return(mid);
		case +1: return(bins_rec(to_be_found, mid + 1, ubnd));
	}
}
int compare(int a, int b) {
	if (a < b) return(-1);
	if (a > b) return(+1);
	return(0);
}

20.03

TABLE OF CONTENTS HC 20

20.05

BINARY SEARCH

20.05

Binary search:
•	remember the design principles:
	•	divide search domain into equal parts
	•	decide where the search must continue

int* bins_iter(int to_be_found, int* lbnd, int* ubnd) {
	int* mid = NULL;
	while(lbnd <= ubnd) {
		mid = lbnd + (ubnd - lbnd) /2;
		switch (compare(to_be_found, *mid)) {
			case -1: ubnd = mid - 1; break;
			case  0: return(mid);
			case +1: lbnd = mid + 1; break;
		}
	}
	return(NULL);
}
int compare(int a, int b) {
	if (a < b) return(-1);
	if (a > b) return(+1);
	return(0);
}

20.04

TABLE OF CONTENTS HC 20

20.06

MEMORY MANAGEMENT

20.06

•	Compile-time memory allocation
	When you declare a simple variable, 
		int n;
	a struct with several members, 
		typedef struct multi {
			int digits[4096];
			int msd;
		} multi m1, m2;
	or a huge array, 
		double sin_values[1024],
		       cos_values[1024];
	the compiler automatically allocates the correct amount of memory
	and this is called static- or compile-time memory allocation.
	
•	Run-time memory allocation
	It is frequently desirable, even necessary in many situations, to be able
	to allocate memory while the program is running.
	We will discuss:
	•	allocating and releasing memory,
	•	dangling pointers,
	•	memory leaks.

20.05

TABLE OF CONTENTS HC 20

20.07

DYNAMIC MEMORY ALLOCATION

20.07

Let elt_type denote some structured type with two members
•	key		this member characterizes an element uniquely
•	data		this member stores the data of each element. 

	typedef ... key_type;
	typedef ... data_type;
	
	typedef struct {
		key_type key;
		data_type data;
	} elt_type;

	elt_type e;         // var e of type elt_type
	elt_type *p;        // var p of type ptr to elt_type
	                    // p has not yet been initialized
	                    // p is an invalid pointer
Previously we have seen
•	p = NULL;           // initializes p temporarily at NULL
	                            // p is a valid ptr but points nowhere!
•	p = &e;             // and now p refers to element e

20.06

TABLE OF CONTENTS HC 20

20.08

DYNAMIC MEMORY ALLOCATION

20.08

The third way to initialize p is the dynamic way (#include <stdlib.h>):

•	determine the size of memory to which the pointer should point
		1 * sizeof(elt_type)
•	request that amount of memory 
		malloc(1 * sizeof(elt_type))
•	cast the generic pointer returned by malloc() to the correct type
		(elt_type*)

All together:
		p = (elt_type*) malloc(1 * sizeof(elt_type));
Alternatively
		p = (elt_type*) calloc(1, sizeof(elt_type));

Remarks:
•	malloc() returns a pointer to dirty memory, but
	calloc() returns a pointer to clean memory (all bits of all bytes are 0)
•	the type of pointer returned by the functions malloc() and calloc() is
	called the generic pointer type i.e. void* or pointer to void!
	Think of a pointer of type void* as a pointer to a yet unknown type.
•	A memory request can fail and in that case the NULL pointer is returned
•	Always validate the result of your memory requests!

20.07

TABLE OF CONTENTS HC 20

20.09

DEALLOCATING THE MEMORY

20.09

Memory is a finite resource.
Dynamically allocated memory that is no longer needed should be released
in order to be reused by a next call to malloc() or calloc().

When the memory pointed at by p is not longer needed you just write

	free(p);

The pointer p is now just as invalid as it was after its declaration, but
but the situation can be worse. Maybe the run-time system does not reclaim 
the memory immediately and for some time you can read the value *p even
though the memory has been free'd. I will always write:

	free(p); p = NULL;

and now if I ask for *p I will get a severe warning (I hope):
cannot dereference a null pointer!.

Above we allocated memory for 1 element and then let p refer to it.

20.08

TABLE OF CONTENTS HC 20

20.10

AN EXAMPLE

20.10

Dynamic memory allocation is far more powerful however. Suppose that during
execution of the program you need an array of elt_type where the size is 
unknown but given by (the evaluation of) some expression:
		p = (elt_type*) malloc(expression * sizeof(elt_type));
		p = (elt_type*) calloc(expression,  sizeof(elt_type));
And again
	free(p); p = NULL;
will release this memory safely.

As an application I will write a function that can copy all elements of an 
arraysegment into an array of the corresponding size.

elt_type* copy_elts(elt_type* p, int lbnd, int ubnd) {
	elt_type* cp;
	cp = (elt_type*) calloc(ubnd - lbnd + 1, sizeof(elt_type));
	if (cp) {   // got the memory
		int i;
		for (i = 0 ; i < ubnd - lbnd; i++)
			*(cp+i) = *(p+i);  // actual copying
	}
	return (cp);
}

20.09

TABLE OF CONTENTS HC 20

20.11

THE FUNCTION realloc()

20.11

Usage:

	elt_type *elts, *copy;
	//
	//	elts is filled, used, processed ... and
	//	now we need a copy of the segment elts[lbn..ubnd]
	//
	copy = copy_elts(elts, 18, 54);
	if (copy == NULL) {
		printf("Copy failed! Think hard!\n");
		exit(1);
	}

The third function that is very useful, realloc() is used to enlarge or shorten 
a dynamically allocated array. 
The function imports a pointer to an old block of memory, and an integer n 
that determines the size of a new block of memory. 
It allocates the new block and copies the contents of the old block into the new
block (subject to restrictions concerning the old and the new size).

20.10

TABLE OF CONTENTS HC 20

20.12

THE FUNCTION realloc()

20.12

int cur_size = 32;
elt_type* elts = 
	(elt_type*) malloc (cur_size * sizeof(elt_type));
//
//	elts is filled, used, processed, ...
//	and now we need to enlarge it
//
//	increase the memory by an additional 24 elements
cur_size += 24;
elts = (elt_type*) realloc(elts, 
                           cur_size * sizeof(elt_type));
or
//	increase the memory by a factor of 2
elts = (elt_type*) realloc(elts, 
                          (cur_size *= 2) * sizeof(elt_type));

A small application that exhibits all new concepts is 
creating, filling, printing and releasing a wordlist:
The user supplies a number of words from the keyboard and this number is 
not known in advance. 
If more words are supplied than can be currently stored, 
the capacity of the wordlist is increased.

20.11

TABLE OF CONTENTS HC 20

20.13

EXAMPLE: WORD LIST

20.13

Some design decisions:

•	A word consists of letters ('a' .. 'z') 
	and the length of a word is always less than 64,
	word is of type pointer to char and is represented as a string 
	the last character of a string is '\0' (called EOS),
	words are stored in the minimal necessary amount of memory.
	
•	A wordlist consists of words 
	and the size of the list is always less than or equal to its capacity. 
	A wordlist is created with some small initial size, 
	then if more words are coming in the capacity is enlarged
	and finally the list is trimmed down to the minimal amount of memory.
•	The user indicates end of input by typing '!' (called EOI),
	(s)he enters zero or more words terminated by return (called EOL) and
	after each EOL (s)he is asked to continue or to terminate input.

20.12

TABLE OF CONTENTS HC 20

20.14

PROGRAM: WORD LIST

20.14

#include <stdio.h>
#include <stdlib.h>

#define EOL  '\n' 
#define EOS  '\0' 
#define EOI  '!' 
#define initial_capacity  5
#define buffer_size      64
typedef char*  word;
typedef word*  wordlist;

void fill_wordlist (wordlist* wl, int* n);
	void prompt_for_input(void) ;
	void eol_message(void) ;
	void get_word(int c, word w) ;
	void store_word(word w, wordlist wl, int i) ;

void show_wordlist (wordlist  wl, int  n);
void sort_wordlist (wordlist  wl, int  n);
void free_wordlist (wordlist* wl, int* n);

20.13

TABLE OF CONTENTS HC 20

20.15

WORD LIST: function main()

20.15

int main(void) {

	wordlist the_wordlist =
		(wordlist) malloc(initial_capacity * sizeof(word));
	int wordlist_size = initial_capacity;
	
	printf("FILL.\n");
	fill_wordlist(&the_wordlist, &wordlist_size);
	show_wordlist( the_wordlist,  wordlist_size);
	printf("SORT.\n");
	sort_wordlist( the_wordlist,  wordlist_size);
	show_wordlist( the_wordlist,  wordlist_size);
	printf("FREE.\n");
	free_wordlist(&the_wordlist, &wordlist_size);
	show_wordlist( the_wordlist,  wordlist_size);
	
	return(0);
}

20.14

TABLE OF CONTENTS HC 20

20.16

WORD LIST CONTINUED

20.16

void prompt_for_input(void)  {} // instructions for the user 
void eol_message(void)       {} // continue or terminate input?
void get_word(int c, word w) {} 

void store_word(word w, wordlist wl, int i) {
	*(wl+i) = (word) malloc((1+strlen(w)) * sizeof(char));
	strcpy(*(wl+i), w);
} 

void show_wordlist(wordlist wl, int n) {
	if (n == 0) {
		printf("Empty wordlist!\n");
		return;
	}
	int i;
	for (i = 0; i < n; i++)
		printf("%s\n", *(wl+i));
}

20.15

TABLE OF CONTENTS HC 20

20.17

THE FUNCTION fill_wordlist()

20.17

void fill_wordlist(wordlist *wl, int *n) {
	int  cur_size = *n, word_count = 0, cur_char;
	word buffer = (word) malloc(buffer_size * sizeof(char));
	prompt_for_input();
	while((cur_char = getchar()) != EOI) {
		if (cur_char == EOL)
			eol_message();
		else {
			get_word(cur_char, buffer);
			if (word_count == cur_size)
				*wl = (wordlist) realloc(*wl, 
					(cur_size *= 2) * sizeof(word));
			store_word(buffer, *wl, word_count++);
		}
	}
	fflush(stdin);
	free(buffer);
	if (cur_size > word_count)
	   *wl = (wordlist) realloc(*wl, word_count * sizeof(word));
	*n = word_count;
}

20.16

TABLE OF CONTENTS HC 20

20.18

free_ and sort_wordlist()

20.18

void free_wordlist(wordlist* wl, int* n) {
	word w;
	while (*n) {                // first release all words
		w = *(*wl + --(*n));        // get word (from z to a)
		free(w);                    // free word
	}
	free(*wl);                  // then release the list
}

void sort_wordlist(wordlist  wl, int  n) { // selection sort!!
	word *a = wl, *z = wl + n - 1;     // first and last word
	for ( ; a < z; a++) {
		word *min = a,                 // init min temporarily
		     *k = a+1,                 // start search for min
		     w;                        // used for the swap
		for (; k <= z; k++)            // get actual min
			if (strcmp(*min, *k) > 0) // libfunction strcmp
				min = k;
		w = *min; *min = *a; *a = w;   // swap a and min(a+1..z)
	}
}

20.17

TABLE OF CONTENTS HC 20

20.19

DANGLING POINTERS

20.19

A pointer that has never been initialized
	elt_type *p;
or a pointer that refers to memory that has been free'd
	free(p);
is called a dangling pointer. 

Dangling pointers point somewhere, but the memory is not yours!
And what you will find there (*p) will make no sense in general (garbage).

The main causes for dangling pointers are the following:

•	letting a pointer p that is declared outside function fun refer to a local
	variable inside the function:  
	int *p;
		void fun f(...) {
			int i = 13;
			p = &i;
			...
		}
	After execution of the function fun the pointer p refers to the address of
	a variable that does not exist any longer!

20.18

TABLE OF CONTENTS HC 20

20.20

DANGLING POINTERS

20.20

•	letting a function fun return a pointer to local data

		int* fun(...) {
			int a[32];
			...
			return(a);
		}
		
	int *res = fun(...);
	Now the function f returns the base address of array a but 
	this array does not exist any more after termination of the function.

•	letting a function f return the address of local data

		elt_type* fun(...) {
			elt_type e;
			...
			return(&e);
		}
		
	elt_type *pe = fun(...);

20.19

TABLE OF CONTENTS HC 20

20.21

MEMORY LEAKS

20.21

A memory leak occurs when memory has been dynamically allocated,
is no longer in use, but has not been free'd.
Computer memory is a finite resource and can be exhausted. 
If you then ask for more, you will get an MRF for sure. 
In C you have to take care of memory management yourself and this requires 
some knowledge and discipline.

Actual memory leaks often occur when nested structures must be free'd. 
If only the top level is released big memory leaks are certain to occur.
The general situation is like this:
•	top level: a dynamic array of pointers to elements,
•	sub level: elements are dynamically allocated blocks of memory 
	where actual data are stored.
•	Memory must be released bottom up!

Example: wordlist is a dynamic array of pointer to word.
•	first release the memory of all words in the wordlist,
•	next release the array of pointers to word.

20.20

TABLE OF CONTENTS HC 20

20.22

EXAMPLE OF MEMORY LEAK

20.22

void free_wordlist(wordlist* wl, int* n) {
	free(*wl); 
	*wl = NULL; 
	*n = 0;
}
gives rise to a huge memory leak. 

Only the elements of the wordlist (pointers to word) are released.
All words have now become inaccessable. But ...
the memory occupied by these words is lost forever!

Always release the memory bottom-up!!

void free_wordlist(wordlist* wl, int* n) {
	word w;
	while (*n) {                // release all words
		w = *(*wl + --(*n));        // from right to left
		free(w);                    // free word
	}
	free(*wl); *wl = NULL;      // release all pointers
	*n = 0;
}

20.21

TABLE OF CONTENTS HC 20

20.23

ARRAYs AND STRUCTs

20.23

Arrays are not value types but reference types! Why?
This language design decision has been taken for reasons of efficiency and
execution performance.
Arrays can store huge amounts of data and if arrays were passed by value the
corresponding formal parameter receives a copy of the actual argument.
Now
•	a copy of a huge amount of data costs a huge amount of memory, and
•	copying a huge amount of data takes some time.

By defining arrays as reference types arrays are passed by reference and the
formal parameter receives a copy of the base address of an actual argument.
•	only one pointer value needs to be copied 
•	and this takes nearly zero time.

The same arguments hold for struct's as well. Depending on its members a 
struct can also store enormous amounts of data. 
Nevertheless a struct is a value type, structs are passed by value and the 
corresponding formal parameter receives a copy of the actual argument.
As a consequence a struct can be copied by direct assignment!

20.22

TABLE OF CONTENTS HC 20

20.24

VALUE TYPE ...

20.24

Consider the multi's from PR 15/16:

	#define MAX_DIGITS    16384

	typedef struct multi {
		int J[MAX_DIGITS];
		int msd;
	} multi;              // sizeof(multi) == 65540 bytes!!!

	multi m_init (int n) ;        // translate n to multi 
	void  m_show (multi *m) ;     // by reference?? YES!!!

int main(void) {
	multi f, cf;
	f = m_init(123456789); m_show(&f);     //  f:  1 2345 6789
	cf = f;                m_show(&cf);    // cf:  1 2345 6789
	cf.J[0] = 0;           m_show(&cf);    // cf:  1 2345 0000
	                       m_show(&f);     //  f:  1 2345 6789
	return(0);
}

20.23

TABLE OF CONTENTS HC 20

20.25

...REFERENCE TYPE

20.25

multi m_init (int n) {
	multi m = {{0}, -1};
	do {
		m.J[++(m.msd)] = n % RADIX;
		n /= RADIX;
	} while (n);
	return(m);
}
void m_show (const multi* const m) {
	int j = 0, field_width = 5;
	while (j <= (*m).msd) {
		print_digit((*m).J[(*m).msd - j], field_width);
		if (++j % N_COLUMNS == 0)
			new_line;
	}
}
Explain why call by reference has been used!
Explain the use of const pointer to const data!
Together: efficiency using call by ref and protection using const. 

20.24

TABLE OF CONTENTS HC 20

20.26

MEMORY SHARING OR NOT

20.26

Note1: arrays can be copied if they have been encapsulated in a struct!
Note2: suppose however that our type multi was defined as 

	typedef struct multi {
		int*  J;
		int msd;
	} multi;              // sizeof(multi) == 8 bytes

and that m_init() has been rewritten accordingly.

int main(void) {
	multi f, cf;
	f = m_init(123456789); m_show(&f);     //  f:  1 2345 6789
	cf = f;                m_show(&cf);    // cf:  1 2345 6789
	cf.J[0] = 0;           m_show(&cf);    // cf:  1 2345 0000
	                       m_show(&f);     //  f:  1 2345 0000
	return(0);
}

Conclusion: the memory to which J points is shared by f.J and cf.J
or, stated otherwise: pointer members are copied but the memory to
which they refer is not!!

20.25

TABLE OF CONTENTS HC 20

20.27

SYNTAX POINTER TO STRUCT

20.27

Remarks on syntax of struct and pointer to struct:

	typedef struct {
		key_type key;
		data_type data;
	} elt_type e, *p;

defines 
•	the new type elt_type as a struct with two members key and data
•	one elt_type variable e, and 
•	one pointer variable p of type pointer to elt_type.

Access of the members of this struct:
•	e.key and e.data as usual and in the same spirit
•	(*p).key and (*p).data
	the parentheses are important on account of the priority properties 
	of the dereferencing- and member_access operator.
•	These ugly expressions occur so often that an abrreviated notation 
	has been introduced:
	p->member has exactly the samen meaning as (*p).member.

20.26

TABLE OF CONTENTS HC 20

20.28

ARRAYs OF POINTER TO STRUCT

20.28

In connection to pointer to struct the next two datastructures 
are of interest in combination with arrays:

•	static array of pointer to struct

	elt_type* static_aps[MAX_SIZE];
	
declares an array static_aps that contains MAX_SIZE pointers to elt_type,

•	dynamic array of pointer to struct

	elt_type* dynamic_aps[INITIAL_SIZE] =
		(elt_type*) calloc(INITIAL_SIZE, sizeof(elt_type));
	
declares an array dynamic_aps that contains INITIAL_SIZE pointers to 
elt_type and that can be resized run-time.

Example: Students follow courses:

20.27

TABLE OF CONTENTS HC 20

20.29

STUDENTs AND COURSEs

20.29

•	Any student is characterized by a unique registration number of type int
		typedef int key;
•	student information like name, address, study, ... is collected in a
	struct and student_information is a pointer to such a struct.
		typedef struct data {
			...
			...
		} data;
•	together
		typedef struct student {
			key   student_registration;
			data* student_information;
		} student;
•	Any course can accomodate at most 128 students

		#define MAX_STUD 128
		typedef student* course[MAX_STUD];
		course  logic, discrete_math, programming, ...;
		
	and these declarations define the type course as a static array of 128
	pointers to student.

20.28

TABLE OF CONTENTS HC 20

20.30

WHAT'S NEXT?

20.30

September 2003!

•	Function types
	•	Pointer to function
	•	Higher-order functions

•	Self referential structures
	•	key, data, elt, node and pointer to node
	•	lists: single- and double linked lists
	•	trees: binary search trees

•	Some basic datastructures
	•	Stack
	•	Queue
	•	Tree
	•	Table
	•	Dictionary	

Pleasant summer holidays!

20.29

TABLE OF CONTENTS HC 20

20.01

TABLE OF CONTENT HC 20

TOC

TOC