COMS 3157 Advanced Programming

Recitation: Pointers and Arrays

4.1 Classify pointer

First, implement the following function:

/** Whether a pointer points to stack memory.
 *
 *  Returns non-zero if p points to memory on the stack;
 *  returns zero otherwise.
 */
int on_stack(const void *p) {
    return ________________; // (4.1.1)
}

Now assume the classify_pointer() function exists, is correct, and behaves as follows:

/** Given a pointer p, classify_pointer():
 *
 *      prints "STACK" if p contains an address on the stack;
 *      prints "HEAP" if p contains an address on the heap;
 *      prints "NEITHER" otherwise.
 */
void classify_pointer(const void *p);

What does the following program print?

int g;
int *h = &g;

void cp(int **a) {
    int *x = *a;
    a = &x;

    classify_pointer(x);        // (4.1.2)
    classify_pointer(&a);       // (4.1.3)
    classify_pointer(a);        // (4.1.4)

    *a = malloc(sizeof(int) * 100);

    classify_pointer(a);        // (4.1.5)
    classify_pointer(++*a);     // (4.1.6)

    h = x;
}

int main(void) {
    cp(&h);

    // (4.1.7) INSERT HERE

    return 0;
}

(4.1.7) Does this program have any memory errors or leaks? If there are errors, where? If there are leaks, how much? Can you insert anything where it says “INSERT HERE” to fix any memory errors or leaks, if any?

Solutions

Check out the solutions by checking out the examples on CLAC:

git clone ~j-hui/cs3157-pub/examples/classify-pointer

In this repo, main.c implements the code shown here, with comments documenting what happens after each statement. classify_pointer() is implemented in classify-pointer.c; you do not need to understand the implementation of classify_pointer(), though it does make use of the same technique as on_stack() to determine whether its argument points to memory in the stack.

4.2 Debugging implementations

Debug these implementations of standard UNIX utilities and C library functions:

// echo
int main(int argc, char **argv) {
    argv++;                       // skip first argument, i.e., "./echo"
    while (argv)                  // for each argument
        printf("%s\n", *argv++);  // print the argument in its own line
    return 0;
}

void *memcpy(void *dest, void *src, size_t n) {
    char *d = dest, *s = src;     // cast to void * to char *
    int i = 0;                    // start at 0th byte
    while (i < n)                 // while within range
        d[i] = s[i++];            // copy over each byte
    return dest;                  // return pointer to destination
}

char *strcpy(char *dest, char *src) {
    while ((*dest++ = *src++) != 0) ;   // copy each byte from src to dest
    return dest;                        // return pointer to destination
}

char *strrchr(char *s, char c) {
    int i = sizeof(s);            // start at end of s
    while (i-- > 0)               // iterate through s backwards
        if (s[i] == c)            // check each character for match
            return s + i;         // return pointer if there is a match
    return NULL;
}

char *strncpy(char *dest, char *src, size_t n) {
    int i;

    // copy up to n bytes from src string to dest string,
    // stopping if we find null terminator character in src
    for (i = 0; i < n && src[i]; i++)
        dest[i] = src[i];

    // pad the rest of dest with additional null bytes,
    // to ensure that total of n bytes are written
    for ( ; i < n; i++)
       dest[i] = '0';

    return dest;
}

Solutions

Check out the solutions by checking out the examples on CLAC:

git clone ~j-hui/cs3157-pub/examples/debug-arrays

In this repo, each part is in its own subdirectory, where a Makefile builds an executable testing the implementation; see inline comments for explanations of the bugs present. Some of the bugs lead to compiler warnings, while some bugs only manifest as runtime errors.

Each buggy implementation is defined with a my prefix (e.g., mystrcpy or mymemcpy) so you can easily replace it with the correct implementation provided by the standard library (e.g., strcpy or memcpy).