Tangible Computing
11. Data Structures



11.1 Arrays and Address Arithmetic

As we have said many times, there are no arrays in C, just pointers to regions of memory containing the same type of data. Pointer arithmetic is then used to achieve array indexing. In pointer arithmetic, the address is adjusted by multiples of the size of the data being referenced.

Any time you have a pointer, you can perform address or poitner arithmetic on it. Address arithmetic enables us to move along memory in chunks that are the size of the thing being pointed to. This means that if you have these pointers:

char * c_p;
int16_t * i_p;
Then c_p+1 is the address of the next character immediately after the one pointed to by c_p, i.e. one byte later. Similarly, i_p+1 is the address of the next int16_t immediately after the one pointed to by i_p, BUT this is 2 bytes later.

In general, you have this relationship between things of type T and address arithmetic on a pointer p to a thing of type T:

T * p;
p + i is the address of the i'th T thing, which is at byte address p + i * sizeof(T)
so the array subscripting expression p[i] is exactly the same as if you said *(p + i). That is take the location pointed to by p, add i multiples of the sizeof a, and then dereference the resulting pointer.

Note that & and * are inverse operations in a sense. For a simple variable x, *&x is exactly the same as if you write just x, that is, get a pointer to x and then follow it to x.

Similarly, &*p is exactly the same as if you write just p, that is, the address of the thing pointed to by p, which is just is the value of p. This should work even if p is the null pointer, or there is a pointer expression present, as in &*(p+1) should be the value (p+1). But why would you do somehing like this?

11.2 Dynamically Allocated Arrays



When we declare an array explicitly, as in uint32_t data[200] we are letting the compiler decide what value to assign to the constant pointer data. We say "constant" because you cannot do something like
data = &x
to change where the array is located in memory.

Because arrays are just pointers, we can allocate the storage for an array at run time to get a dynamically allocated array. We saw how we can do this implicity when the array is allocated as a local variable on the stack. But suppose we want the array to stay around after the code that created the array is finished? Then we need to allocate the array on the heap using malloc.

To allocate an array of n items of type T, referenced by pointer a, we do
T * a;
a = (typeof(a)) malloc(n * sizeof(*a));
// always test the return code of malloc
// a null pointer means no memory available
// for the size of block you asked for
if ( a == 0 ) { Handle error }
note that typeof(a) is T, so in Cyou can also say
a = (T*) malloc(n * sizeof(T));
so either form will work. The advantage of the first form is that if you change the type of a, the first form will automatically be correct.

When you are finished with the array, you should always call
free(a);
to release the memory back to the heap, which will then shrink if possible to free up space for the stack.

Note: never call free twice on the same pointer!

As a general rule, you should always check that for every malloc you make there is exactly one corresponding free.

code/Memory/Mem09/Mem09.ino

    // Using the heap for memory allocation
     
    #include "mem_syms.h"
    #define ADDR DEC
     
    void print_heap_stats() {
      Serial.print("Avail mem:");  Serial.println(AVAIL_MEM, DEC);
      Serial.print("Heap size:");  Serial.println(HEAP_SIZE, DEC);
      Serial.print("Heap starts at:");  Serial.println((unsigned int) HEAP_START, ADDR);
      Serial.print("Heap ends at:");  Serial.println( (unsigned int) HEAP_END, ADDR);
    }
     
    void print_array(int a[], unsigned int len) {
      Serial.print("array at ");
      Serial.print( (unsigned int) a, ADDR);
      Serial.print(" has len ");
      Serial.println(len);
      
      if ( ! a ) {
        // oops, no array
        Serial.println("Null pointer!");
        return;
      }
      
      for (int i=0; i < len; i++ ) {
        Serial.print(a[i], DEC);
        if (i < len-1) { Serial.print(","); }
      }
      Serial.println(".");
    }
     
    // create a new array of ints, of length len, and fill with 
    // some data
    int * make_random_array(unsigned int len) {
      Serial.println("make random array");
      int *a;
      a = (typeof(a)) malloc(sizeof(*a) * len);
      // always check the return code of malloc
      if ( a == 0 ) {
         Serial.println("No memory!");
         while ( 1 ) {}
         }
     
      for (int i=0; i < len; i++) {
        // note a[i] is just shorthand for *(a+i)
        // where the units of i are sizeof thing pointed to by a
        a[i] = random(0, 100);
      }
      return a;
    }
     
    void setup()
    {
      Serial.begin(9600);
      
      Serial.println("MEM09 - dynamic arrays");
     
      unsigned int array_1_len;
      int * array_1;
      
      unsigned int array_2_len;
      int * array_2;
     
      unsigned int array_3_len;
      int * array_3;
     
      print_heap_stats();
      array_1_len = 20;
      array_1 = make_random_array(array_1_len);
      print_heap_stats();
      print_array(array_1, array_1_len);
      Serial.println("free 1");
      free(array_1);
      print_heap_stats();
      
      array_2_len = 10;
      array_2 = make_random_array(array_2_len);
      print_heap_stats();
      print_array(array_2, array_2_len);
      
      array_3_len = 10;
      array_3 = make_random_array(array_3_len);
      print_heap_stats();
      print_array(array_3, array_3_len);
     
      Serial.println("free 2");
      free(array_2);
      print_heap_stats();
     
      Serial.println("free 3");
      free(array_3);
      print_heap_stats();
     
    }
     
    void loop() {
    }


11.3 Dynamically Allocating a Singleton

A singleton is the term used for a single unit of data of some type T. You allocate a singleton instance of a type T referenced by pointer p using malloc as:
T * p;
p = (typeof(p)) malloc(sizeof(*p));
or
T * p;
p = (T *) malloc(sizeof(T));
where T is any type. Remember, the expression sizeof(*p) gives the number of bytes required by the variable pointed to by p. This is the same as sizeof(T). The result of the malloc call is of type (void *) so the result needs to be cast to the proper type, in this case a pointer to a T, which is T *. The gcc compiler extensions introduced the typeof() operator, which means that typeof(p) is the type used to declare pointer p, that is T *.

IMPORTANT: Although we did not do so in the example below, you should always check the return of malloc to see if it is 0, the null pointer. If there is no memory available, malloc will return 0. In most machines, attempting to use a null pointer causes an invalid address exception. This is not the case in the arduino! It will happilly address into the portion of memory that is mapped to the registers, and will cause very strange things to happen. code/Memory/Mem08/Mem08.ino

    // Using the heap for memory allocation
     
    #include "mem_syms.h"
    #define ADDR DEC
     
    void setup() {
      // a pointer to an int
      long int * x_p;
      // a pointer to a char
      char * y_p;
     
      // to keep track of where the heap starts and ends for us
      // there might already be stuff on the heap, which we want to
      // ignore.
      char * hs;
      char * he;
      char * p;
      
      Serial.begin(9600);
        
      Serial.println("MEM07");
      
      Serial.print("Avail mem:");  Serial.println(AVAIL_MEM, DEC);
      Serial.print("Heap starts at:");  Serial.println((unsigned int) HEAP_START, ADDR);
      Serial.print("Heap ends at:");  Serial.println((unsigned int) HEAP_END, ADDR);
      
      /* allocate memory for an int from the heap and remember its address
         we could say:
         x_p = (int *) malloc(sizeof(int));
         but then if we changed the type of x_p we would probably forget
         to fix the malloc call and things would break, subtly and horribly
         So instead we use the typeof and sizeof compiler operators
      */
      
      Serial.print("Allocate a chunk, size:");
      Serial.println(sizeof(*x_p));
     
      hs = HEAP_END;
      x_p = (typeof(x_p)) malloc(sizeof(*x_p));
      
      // why is this an inefficeint use of memory?
      //X y_p = (typeof(y_p)) malloc(sizeof(*y_p));
     
      he = HEAP_END;
     
      // if x_p == 0, the null pointer value, then malloc failed
     
      Serial.print("Avail mem:");  Serial.println(AVAIL_MEM, DEC);
      Serial.print("Heap starts at:");  Serial.println((unsigned int) HEAP_START, ADDR);
      Serial.print("Heap ends at:");  Serial.println( (unsigned int) HEAP_END, ADDR);
     
     
      // why did we use 2 bytes from the heap more than we expect for x_p?
      
      *x_p = 0x89abcdef;
      Serial.print("x_p:");
      Serial.println( (unsigned int) x_p, ADDR);
      Serial.print("*x_p:");
      Serial.println( (unsigned int) *x_p, HEX);
      
      Serial.print("y_p:");
      Serial.println( (unsigned int) y_p, ADDR);
     
      //Y *y_p = 'H';
      
      Serial.print("*y_p:");
      Serial.println(*y_p);
     
     
      // print the contents of the heap we just allocated from
      
      Serial.print("Heap:");
      for ( p = hs; p < he; p++) {
        unsigned char c = *p;
        Serial.print( c, HEX );
        Serial.print(" ");
      }
      Serial.println();
        
     }
     
    void loop() {
    }


11.4 Making composite data structures

Here we will demonstrate how to collect information related to drawing a line into one 'item', called a struct. An example of this includes the following files to draw random lines on the screen:
  1. graphics_line.h - for defining a struct to hold all of the information for drawing the line on the screen.
  2. rand_lines.ino - the main program which draws the lines on the screen.
  3. assert.h and assert.cpp for using assert.
You will need to hook up the LCD screen as well as a pushbutton to Pin 9 for assert. Once you've uploaded the code, you can open the Serial Monitor for instructions. Press the pushbutton to begin the line drawing.

Here is the code for defining the struct.
code/Memory/rand_lines/graphics_line.h

    // idiom to include only once
    #ifndef graphics_line_h
    #define graphics_line_h
     
    /*
     
    Typedefs for manipulating lines on the LCD.
     
    Each line consists of a start point (xs, ys) an end point (xe, ye), and a
    color.  We want to put all of these attributes into a single container called a
    struct so that we can move a line around as a single item of data.
     
    We define a new type called graphics_line below.  If s is an instance of
    graphics_line, then we can manipulate single as a single piece of data, or we
    can access its fields (attributes) using . notation as follows:
        single.xs
     
    If you have an array list of graphics lines, then you can first get to the 
    struct, then access the fields
        list[i].color
     
    If you have a pointer p to an instance of the graphics_line type then the
    whole structure is accessed as
        *p
    while if you want to get to an attribute, you use -> notation
        p->ye
    or 
        (*p).ye
     
    */
    typedef struct {
        int xs;
        int ys;
        int xe;
        int ye;
        unsigned int color;
        } graphics_line;
     
    #endif


In the main program we can manipulate arrays of graphic_lines.
code/Memory/rand_lines/rand_lines.ino

    #include <string.h>
    #include "graphics_line.h"
    #include "assert.h"
     
    #include <Adafruit_ST7735.h>
    #include <Adafruit_GFX.h>
    #include <SPI.h>
     
    /* now we have an array of graphics_line */
     
    /* remember graphics_line lines[] is the same as
        graphics_line *line, but the [] reminds us that we are passing an
        array, not a single element.
    */
     
    #define CS   6
    #define DC   7 
    #define RST  8
     
    // Colour definition
    #define BLACK           0x0000
     
    Adafruit_ST7735 tft = Adafruit_ST7735(CS, DC, RST);
     
    void draw_lines(int num_lines, graphics_line lines[]){
      for (int i=0; i < num_lines; i++) {
        // note how the . "dot" notation gets the field of the struct
        tft.drawLine(lines[i].xs, lines[i].ys, 
                     lines[i].xe, lines[i].ye,
                     lines[i].color);
      }
    }
     
    // creates num_lines random lines with random colors and returns pointer
    // to the list containing them
    graphics_line * make_random_lines(int num_lines) {
      graphics_line * list;
     
      // a temporary line
      graphics_line tmp;
        
      list = (typeof(list)) malloc(num_lines * sizeof(*list));
     
      assert(list != 0, 2);
     
      for (int i=0; i < num_lines; i++) {
        tmp.xs = random(0, tft.width());
        tmp.ys = random(0, tft.height());
        tmp.xe = random(0, tft.width());
        tmp.ye = random(0, tft.height());
        tmp.color = tft.Color565(random(0, 255), random(0, 255), random(0, 255));
        
        list[i] = tmp;
      }
     
      return list;
    }
        
     
    void setup() {
      int num_lines = 128;
      graphics_line *random_lines;
           
      Serial.begin( 9600 );
      
      // wait for button press to start
      button_pause("Press button to start");
     
      tft.initR(INITR_REDTAB);   // initialize a ST7735R chip, red tab
     
      Serial.println("Generating lines");
      random_lines = make_random_lines(num_lines);
     
      Serial.println("Drawing lines");
      tft.fillScreen(BLACK);
      draw_lines(num_lines, random_lines);
     
      Serial.println("Freeing lines");
      free(random_lines);
    }
     
     
    void loop() {
     
    }


Here are some useful utilities for pausing and debugging.
code/Memory/rand_lines/assert.h

    #ifndef assert_h
    #define assert_h
    /* assert(expr, error_code) 
     
    If expr is false, then the program enters a loop in which it keeps
    flashing error_code blinks
     
    */
    void assert(int expr, int error_code);
     
    /* button_pause(char *msg) 
     
    Display a message on the serial monitor and wait for button to be
    pushed.
    */
     
    void button_pause(char *msg);
     
    #endif

code/Memory/rand_lines/assert.cpp

    #include <Arduino.h>
    /* assert(expr, error_code) 
     
    If expr is false, then the program enters a loop in which it keeps
    flashing error_code blinks
     
    */
     
    static int assert_pin = 13;
    void assert(int expr, int error_code) {
      if ( expr ) { return; }
      pinMode(13, OUTPUT);
      while(1) {
        digitalWrite(assert_pin, HIGH);
        delay(1000);
        digitalWrite(assert_pin, LOW);
        for (int i=0; i < error_code-1; i++) {
          delay(100);
          digitalWrite(assert_pin, HIGH);
          delay(200);
          digitalWrite(assert_pin, LOW);
        }
        delay(100);
      }
    }
     
    // Attach a pushbutton between ground and pin 9 for pause control
    static int pauseButton = 9;
     
    void button_pause(char *msg) {
      if ( msg ) {
        Serial.print(msg);
      }
      else {
        Serial.print("B?");
      }
     
      // set pauseButton to INPUT and 
      pinMode(pauseButton, INPUT);
      // turn on internal pull up resistor 
      digitalWrite(pauseButton, HIGH);
     
      while( digitalRead(pauseButton) ) { delay(200); }
      while( ! digitalRead(pauseButton) ) { delay(200); }
      Serial.println("!");
    }
     


11.5 Reading and Writing to the SD card

The SD card can be viewed as just a chunk of memory. Here we write random 8 bit values to each index in a block, and the write that block to the SD. We then read it back to confirm the data was written to the card properly.

code/Memory/SDCard/SDCard.ino

    #include <string.h>
    #include "assert.h"
     
    #include <Adafruit_ST7735.h>
    #include <Adafruit_GFX.h>
    #include <SPI.h>
    #include <SD.h>
     
    #define SD_CS    5  // Chip select line for SD card
    #define CS       6
    #define DC       7 
    #define RST      8
     
    Adafruit_ST7735 tft = Adafruit_ST7735(CS, DC, RST);
     
    Sd2Card card;
     
    /* The 1.8" LCD has a uSD (micro SD) card slot, which can be used to store
    data, images, or graphics programs.
     
    A SD card is organized as blocks of 512 bytes.  You cannot read or write
    individual bytes, an entire block must be moved in and out.  So what this
    means is that you need a 512 byte buffer for I/O.  Even though there are
    byte address commands available, they still cause blocks to move, and so
    are very expensive, and cause needless writes to the card.
     
    Also, writes are much more expensive than reads, so if you do not need to
    write anything, don't.
     
    Some displays recognize that the uSD card might have a 
    FAT file system on them, and so reads and writes the data in a form that 
    allows you to also read and write to the card as if it was a memory stick.
    Not for our screen, so you will not be able to mount this card in your own
    machine.  But, you can still access the raw data using the dd command in
    OSX and Linux.
     
    To address a block on the card you need to provide a sector address, which
    is 3 bytes long.  This means that a sector addres ranges
        0 .. 16777215, or 0x0 .. 0xffffff
    first.
     
    The Sd2card.h header file defines various useful types for accessing
    the memory card:
        unsigned char - sector address
    and these basic operations to read and write a block
        uint8_t readBlock(uint32_t block, uint8_t* dst);
        uint8_t writeBlock(uint32_t blockNumber, const uint8_t* src);
     
    */
     
    #define BLOCK_SIZE 512
    unsigned char out_buf[BLOCK_SIZE];
    unsigned char in_buf[BLOCK_SIZE];
     
    uint32_t start_time;
    uint32_t stop_time;
     
     
     
    void start_clock() {
      start_time = millis();
    }
     
    uint32_t stop_clock() {
      unsigned long elapsed_time;
      stop_time = millis();
      elapsed_time = stop_time - start_time;
      Serial.print("Elapsed time ");
      Serial.println(elapsed_time);
      return elapsed_time;
    }
     
    void setup() {
     
      /* write at the 1G mark so we skip the useful data on the beginning
        of the card */
      uint32_t start_sector;
      uint32_t end_sector;
      uint32_t cur_sector;
           
      Serial.begin( 9600 );
      
      // wait for button press to start
       button_pause("Press button to start");
     
      tft.initR(INITR_REDTAB);   // initialize a ST7735R chip, red tab
     
      // initialize memory card
      if (!card.init(SPI_HALF_SPEED, SD_CS)) {
        Serial.println("initialization failed. Things to check:");
        Serial.println("* is a card is inserted?");
        Serial.println("* Is your wiring correct?");
        return;
      } else {
       Serial.println("Wiring is correct and a card is present."); 
      }
      
      // Select starting and end sector
      start_sector = 2097152;
      end_sector = start_sector + 32;
      cur_sector = start_sector;
     
      for (cur_sector = start_sector; cur_sector < end_sector; cur_sector++) {
     
        // write a block of data to the SD card
        for (int i=0; i < BLOCK_SIZE; i++) {
          out_buf[i] = random(0, 256);
        }
     
        Serial.print("Writing block ");
        Serial.println(cur_sector);
     
        start_clock();
        card.writeBlock(cur_sector, out_buf);
        stop_clock();
          
        // read it back for comparison
        Serial.print("Reading block ");
        Serial.println(cur_sector);
     
        start_clock();
        card.readBlock(cur_sector, in_buf);
        stop_clock();
     
        // compare what we wrote to the SD card and what we just read
        for (int i=0; i < BLOCK_SIZE; i++) {
          if ( in_buf[i] != out_buf[i] ) {
            Serial.print(" Byte mismatch ");
            Serial.print( i );
            Serial.print(" in:");
            Serial.print( in_buf[i], HEX );
            Serial.print(" out:");
            Serial.println( out_buf[i], HEX );
     
            button_pause("Continue?");
     
            break;
          }
        }
      }
    }
     
    void loop() {
     
    }
11. Data Structures
Tangible Computing / Version 3.20 2013-03-25