Dynamic allocation & link lists (12)

Administrivia

Practice Web Page - http://www.cs.tau.ac.il/~efif/courses/Programming_Fall_04

Memory allocation

malloc - C's dynamic memory allocation function
malloc returns a pointer to the memory it gives us

read a line of input into a dynamic array

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

/* getline() reads one line from standard input and copies it to line array
 * (but no more than max chars).
 * It does not place the terminating \n in line array.
 * Returns line length, or 0 for empty line, or EOF for end-of-file.
 */
int getline(char line[], int max)
{
  int nch = 0, c;
  max = max - 1;			/* leave room for '\0' */

  while ((c = getchar()) != EOF) {
    if (c == '\n')
      break;

    if (nch < max) {
      line[nch] = c;
      nch = nch + 1;
    }
  }

  if (c == EOF && nch == 0)
    return EOF;

  line[nch] = '\0';
  return nch;
}

int main()
{
  char * line;
  int linelen;
  scanf("%d\n", &linelen);
  if (linelen <= 0) {
    printf("ERROR: line length must be positive!\n");
    return 1;
  }
  line = (char *) malloc(linelen);
  if (line == NULL) {
    printf("ERROR: out of memory!\n");
    return 1;
  }
  getline(line, linelen);
  printf("%s\n", line);
  return 0;
}

getline.c

Managing allocated memory

Dynamically allocated regions of storage are like arrays
- use array-like subscripting notation on them
- keep track of the memory which malloc has given you
It is easy to accidentally use a pointer which points "nowhere"
- actually it can point "somewhere", just not where you wanted it to
*p = 0;
the 0 gets written "somewhere"

Allocating memory for charcters

All strings have a terminating '\0' character

add 1 to the count that strlen return when calling malloc

char *somestring, *copy;
...
copy = (char *) malloc(strlen(somestring) + 1);		/* +1 for \0 */
/* check malloc's return value */
strcpy(copy, somestring);

Allocating memory for integers

Allocate 100 ints
It's much safer and more portable to let C compute the size for us
Recall the sizeof operator, that computes the size, in bytes, of a variable or type
int *ip = (int *) malloc(100 * sizeof(int));
- sizeof() is an operator, and it is evaluated at compile time

Accesing allocated memory

We can use array indexing syntax on pointers
We can treat a pointer variable returned by malloc almost exactly as if it were an array
int *ip = (int *) malloc(100 * sizeof(int));
we can access ip[0], ip[1], ... up to ip[99]
- even if you don't know until run time how big the array should be

Verifying allocated memory

No real computer has an infinite amount of memory available
No guarantee that malloc will be able to give us as much memory as we ask for
We're probably going to run out of memory if
- we call malloc(100000000), or
- we call malloc(10) 10,000,000 times
malloc returns a null pointer upon failure

It's vital to check the returned pointer before using it

int *ip = (int *) malloc(100 * sizeof(int));
if (ip == NULL) {
  printf("ERROR: out of memory\n");
  return -1;
}

Freeing memory

But it does not have to remain for the entire duration of your program
Memory is not inexhaustible
Deallocate (free) memory when you don't need it any more:
free(p);
p contains a pointer previously returned by malloc

Recycling memory

Freeing memory is recycling
It costs you almost nothing
The memory you give back is immediately usable by other parts of your program. (Theoretically, it may even be usable by other programs.)
Freeing unused memory is a good idea, but it's not mandatory
- Allocated memory is automatically released upon exit by the operating system

A thief with a key is still a thief

once you've freed some memory you must remember not to use it any more
after calling
free(p);
p still points at the same memory
record the fact that it's not to be used any more
free(p); p = NULL;

Keeping track

There is a big difference between a pointer and what it points to
You need at least one pointer to the memory to use it or free it
suppose
- you store the pointer that malloc gives you in a local pointer variable
- then, the function containing the local pointer variable returns
  - local variables have automatic duration
The pointer disappears when the function returns, but the memory remains allocated
- there is no way to use it or free it, if it contained the only copy of the pointer

Reallocating memory

realloc - accepts an old pointer and a new size
returns contiguous space of the new size
ip = realloc(ip, 200 * sizeof(int));
- If the old block can be made bigger, it returns the same pointer
- otherwise, it
  - Attempts to allocate new memory
  - If successful
    - Copies old data to new memory
    - Frees old memory block
    - Returns new pointer
  - Otherwise, returns NULL

example

reads lines of text from the user, treats each line as an integer by calling atoi, and stores each integer in a dynamically-allocated "array"

/* reads lines of text from the standard input. Treats each line as an integer
 * by calling atoi, and stores each integer in a
 * dynamically-allocated "array"
 */

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

#define MAXLINE 100
#define INITSIZE 2

int main()
{
  char line[MAXLINE];
  int *ip;
  int nalloc, nitems;

  nalloc = INITSIZE;
  ip = (int *) malloc(nalloc * sizeof(int));	/* initial allocation */
  if (ip == NULL)	{
    printf("out of memory\n");
    return -1;
  }

  nitems = 0;
  
  while (getline(line, MAXLINE) != EOF) {
    if (nitems >= nalloc) {			/* increase allocation */
      int *newp;
      nalloc *= 2;
      newp = realloc(ip, nalloc * sizeof(int));
      if (newp == NULL) {
        printf("out of memory\n");
        return -1;
      }
      ip = newp;
    }
    ip[nitems++] = atoi(line);
  }

  printf("Allocated %d items, initialize %d items\n", nalloc, nitems);
  return 0;
}

getmline.c

Prototype

malloc, free, and realloc are declared in <stdlib.h>
malloc and realloc return type is void *
- a pointer to void
a "generic" pointer type, which may be any pointer type
- assigned to or from

Pointer safety

Ensure that the memory pointers point to is valid
When a pointer doesn't point where you think it does, if you inadvertently access or modify the memory it points to, you can damage other parts of your program, or (in some cases) other programs or the operating system itself!
Be careful when pointing to arrays
- Ensure that the pointers always stay within the bounds of the array(s)
- when passing pointers to and returning them from functions
  - The code using the pointer may be far removed from the code that owns or allocated the memory
- strstr function returns either
  - a null pointer, or
  - a pointer that points into the input caller-supplied string
- Never return a pointer to one of its own, local, automatic-duration arrays
  - automatic-duration variables are deallocated and disappear when the function returns
Be most careful when allocating memory dynamically
- Doing dynamic memory allocation with malloc, realloc, and free can be dangerous
  - Dynamic allocation gives a lot more flexibility in how our programs use memory
- Reduce damaging possibilities by ensuring
  - that pointers are used correctly, and
  - that memory is always allocated and deallocated correctly

sizeof

sizeof() is a built-in C operator (just like +,-,*). The compiler replaces sizeof(data-type-name) or sizeof(variable)) with the number of bytes of storage allocated for the data-type or variable.

#include <stdio.h>

typedef struct item {
  int data;
  struct item * next;
} Item;

int main ()
{
  char carray[16];
  char * cp = (char *) malloc(16 * sizeof(char));

  printf("char\t\t%d bytes\n", sizeof(char));
  printf("unsigned char\t%d bytes\n", sizeof(unsigned char));
  printf("short\t\t%d bytes\n", sizeof(short));
  printf("unsigned short\t%d bytes\n", sizeof(unsigned short));
  printf("int\t\t%d bytes\n", sizeof(int));
  printf("unsigned int\t%d bytes\n", sizeof(unsigned int));
  printf("long\t\t%d bytes\n", sizeof(long));
  printf("unsigned long\t%d bytes\n", sizeof(unsigned long));
  printf("float\t\t%d bytes\n", sizeof(float));
  printf("double\t\t%d bytes\n", sizeof(double));
  printf("carray\t\t%d bytes\n", sizeof(carray));
  printf("cp\t\t%d bytes\n", sizeof(cp));
  printf("Item\t\t%d bytes\n", sizeof(Item));

  return 0;
}

info1.c

Linked list

Construct items, push items to end of the list, and print the list

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

typedef struct item {
  int data;
  struct item * next;
} Item;

Item * push_back(Item * head, int data)
{
  Item * tail = head;
   
  Item * new = (Item *) malloc(sizeof(Item));   /* construct new item */
  if (!new) {
    printf("ERROR: out of memory!\n");
    return NULL;
  }
  new->data = data;
  new->next = NULL;
  if (tail == NULL)                             /* empty list */
    return new;
  while (tail->next != NULL)                    /* search last item */
    tail = tail->next;
  tail->next = new;                             /* insert new item as last */
  return head;
}

void print(Item * head)
{
  if (!head) return;
  printf("%d", head->data);
  for (head = head->next; head; head = head->next)
    printf(" %d", head->data);
  printf("\n");
}

int main()
{
  Item * head = NULL;
  if (!(head = push_back(head, 1))) return -1;
  if (!(head = push_back(head, 2))) return -1;
  if (!(head = push_back(head, 3))) return -1;
  if (!(head = push_back(head, 4))) return -1;
  if (!(head = push_back(head, 5))) return -1;
  print(head);
  return 0;
}

list.c

Reverse

Reverse a linked list

Item * reverse1(Item * head)
{
  Item * item = head, * next;

  if (!head || !head->next)
    return head;
  next = head->next;
  head->next = NULL;
  while (next) {
    Item * tmp = next->next;
    next->next = item;
    item = next;
    next = tmp;
  }
  return item;
}

list.c

Reverse

Reverse a linked list using recursion

Item * reverse2(Item * head)
{
  Item * item, * next;
  
  if (!head || !head->next)
    return head;
  next = head->next;
  item = reverse2(head->next);
  next->next = head;
  head->next = NULL;
  return item;
}

list.c

List struct

Holds the size of the list and pointer to the head and tail of the list

typedef struct item {
  int data;
  struct item * next;
} Item;

typedef struct list {
  int size;
  Item * head;
  Item * tail;
} List;

slist.c

Doubly-connected linked list

Each item points to the next item and to the previous item

typedef struct item {
  int data;
  struct item * prev;
  struct item * next;
} Item;

typedef struct list {
  int size;
  Item * head;
  Item * tail;
} List;

dlist.c

Maintained by Efi Fogel. Last modified: January 28 2004.