Containers

In the expr.c expression package, we maintain a pair of stacks - one for names, one for operators. As we parse the source code, we push names onto the names stack, and operators onto the operator stack. When we encounter an operator in the source with a lower priority than the operator at the top of the operator stack, we begin reducing the stacks. Take off the top operator, and the number of names it needs, and generate an expression node, and add that node to an output tree. Keep doing this until the operator at the top no longer has higher priority than the one we just read.

(It’s a bit more complex than that really - parenthesised expressions, function calls, array indices - but that’s the basic operation of an operator-precedence expression parser).

So - simple question - how big should the name and operator stacks be?

And of course the answer is “it depends”.

In earlier versions of expr.c, the easy way out was taken - the stacks were a fixed size and the error message “expression too complex” was given if their limits were surpassed. But that’s just nasty. 

So for teq, we have introduced a new useful building block, the Container.

typedef struct {

    char * name;

    uint32 max;         // max number of elements

    uint32 count;       // how many elements we have

    char ** data;       // array of pointers

} Container;

It’s a simple structure with pointer to an array of pointers (data) and some metadata - count and max. max defines the current capacity of the data array, count the number of pointers in the array.

When a Container is created, the capacity is set to some default value, the array f pointers is mallocd with that number of entries, and data is pointed at the allocated array.

Containers should be accessed only through the provided accessor functions (see below). When a pointer is added to a Container, the obvious check is done that this isn’t beyond capacity. If it is, we realloc() the data array to a capacity that is some multiple of the current capacity, check the realloc worked, and replace the data pointer if so.

Thus, we get self-growing arrays of exactly the right size.

container.h

//

//  container.h

//  teq

//

//  Created by Pete Wilson on 6/6/17.

//  Copyright © 2017 Kiva Design Groupe LLC. All rights reserved.

//

#ifndef container_h

#define container_h

typedef struct {

    char * name;

    uint32 max;         // max number of elements

    uint32 count;       // how many elements we have

    char ** data;       // array of pointers

} Container;

char * contNameAndVersion(void);

// containers are self-extending arrays of pointers

uint32 ContainerCount(Container * c);

uint32 allocateInContainer(Container * c);

Container * newContainer(uint32 count, char * name);

void zeroContainer(Container * c);

void printContainer(Container * c);

void * getPtrFromContainer(Container * c, uint64 n);        // get the n'th pointer; don't change the container

void addPtrToContainer(Container * c, void * p);            // add a pointer to the container

void pushPtrToContainer(Container * c, void * ptr);         // push a pointer into a container (same as add)

void * pullPtrFromContainer(Container * c);                 // pull a pointer from a container into ptr; return 1. If none, return 0

void * getTopPtrInContainer(Container * c);                 // if there is a pointer, copies top value into ptr and returns 1; else returns 0

#endif /* container_h */

container.c

//

//  container.c

//  teq

//

//  Created by Pete Wilson on 6/6/17.

//  Copyright © 2017 Kiva Design Groupe LLC. All rights reserved.

//

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define EXTERN extern

#include "types.h"

#include "container.h"

extern void allocError(uint64 s, char * msg);

static char * name_and_version = "containers 0.1v6 [September 23 2018]";

/*

 provides a uniform way of creating an array of objects which can grow in size

 Versions

    0.1v6 [September 28 2018]

        - all Containers now hold just pointers. No 'ptrContainers'. Errors remain..

    0.1v5 [April 16 2018]

        - changed API for int pullValFromContainer(). returns 1 if there was something in the container, and writes the value removed to a pointer's variable

    0.1v4 [November 2017]

        - added pointer only containers (type Container)

    0.1v3   August 14 2017

        - added a set of functions to more efficiently push and pull 'word-sized' (64 bit) values to and from a Container

 */

// ------------------------- contNameAndVersion --------------

char * contNameAndVersion(void) {

    return name_and_version;

}

// ------------------ printContainer --------------

void printContainer(Container * c) {

    printf("\n\nContainer '%s':", c -> name);

    printf("\n\tcapacity  = %d", c -> max);

    printf("\n\tcount     = %d", c -> count);

    // print the pointers

    for (int i = 0; i < c -> count; i++) {

        char * p = getPtrFromContainer(c, i);

        printf("\n\t\tptr %d: %p", i, p);

    }

    //fflush(stdout);

}

// ----------------- zeroContainer ----------

void zeroContainer(Container * c) {

    c -> count = 0;

}

// ------------------ ContainerCount -----------------

uint32 ContainerCount(Container * c) {

    return c -> count;

}

// ----------- allocateInContainer ------------

uint32 allocateInContainer(Container * c) {

    // allocate space for one more pointer in the container, and return the index to it

    if (c -> count >= c -> max) {

        // we need to grow the container - we use 50%

        uint32 newmax = (c -> max + (c -> max/2));

        //reallocate the data

        //printf("\n-- growing container %p from %lld to %lld pointers", c, c -> max, newmax);

        void * newdata = realloc(c -> data, newmax * sizeof(char *));

        if (newdata) {

            //printf("..succeeded.");

            c -> data = newdata;

            c -> max = newmax;

        }

        else {

            allocError(newmax * sizeof(char *), "reallocation of a container's data");

        }

    }

    // return the index to the current slot

    uint32 index = c -> count;

    

    // and increment the slot

    c -> count++;

    return index;

}

// -------------- getPtrFromContainer ---------

void * getPtrFromContainer(Container * c, uint64 n) {

    // Read the n'th pointer

    if (n >= c -> count) {

        printf("\n=== container error - asking for item %llu in container '%s' when count is %u", n, c -> name, c -> count);

        return NULL// safety - a NULL pointer should cause havoc 

    }

    char * ptr = c -> data[n];

    // printf("\nget ptr[%lld] %p from %s", n, ptr, c -> name);

    return ptr;

}


// -------------- addPtrToContainer ---------


void addPtrToContainer(Container * c, void * p) {

    // Add the pointer p to the container

    uint32 n = allocateInContainer(c);       // find index at which to store our pointer

    // printf("\nadd ptr %p to %s[%lld]", p, c -> name, n);

    c -> data[n] = p;                        // and store it

}


// ------------ newContainer --------------


Container * newContainer(uint32 count, char * name) {

    // create a new pointer container capable of holding up to 'count' pointers

    uint64 s = sizeof(Container);

    Container * c = malloc(s);

    if (c) {

        c -> name = strdup(name);

        c -> data = malloc((count + 1) * sizeof(void *));

        c -> max = count;

        c -> count = 0;

        if (c -> data == NULL) {

            allocError(count * sizeof(char *), "cannot allocate a pointer container's data array");

            free(c);

            c = NULL;

        }

   }

    else {

        allocError(s, "cannot allocate a pointer container");

    }

    return c;

}

// ------------ pushPtrToContainer --------------

void pushPtrToContainer(Container * c, void * ptr) {

    // push a pointer into a container. Same as add.

    addPtrToContainer(c, ptr);

}

// ------------ pullPtrFromContainer --------------

void * pullPtrFromContainer(Container * c) {

    // pull a pointer from a container into ptr; return 1. If none, return 0

    if (c -> count > 0) {

        char * p = getPtrFromContainer(c, c -> count - 1);

        c -> count--;

        return p;

    }

    return NULL;

}

// ------------ getTopPtrInContainer --------------

void * getTopPtrInContainer(Container * c) {

     // if there is a pointer, copies top value into ptr and returns 1; else returns 0

    uint64 n = c -> count;

    if (n == 0) {

        return NULL;

    }

    char * p = getPtrFromContainer(c, n - 1);

    return p;

}




© kiva design groupe • 2017