Lecture 08 C Generics – Void *

c泛型Lecture08.pdfgeneric_stack.cint_stack.clive_stack.clive_stack_soln.crotate.crotate_soln.cswap.cswap_ends.c

memcpy

memmove

C Generics

Void * Pitfalls

#include <stdio.h>
#include <string.h>
typedef struct mystruct {
    int x;
    char *s;
} mystruct;
/* This is a generic swap function that can swap the data pointed
 * to by the two pointers, of the given size in bytes.
 */
void swap(void *data1ptr, void *data2ptr, size_t nbytes) {
    char temp[nbytes];
    memcpy(temp, data1ptr, nbytes);
    memcpy(data1ptr, data2ptr, nbytes);
    memcpy(data2ptr, temp, nbytes);
}
int main(int argc, char *argv[]) {
    // Example 1
    int x = 0xffffffff;
    int y = 0xeeeeeeee;
    printf("BEFORE: x = 0x%x, y = 0x%x\n", x, y);
    //swap(&x, &y, sizeof(x));
    swap(&x, &y, sizeof(short));  // what happens if we do this?
    printf("AFTER: x = 0x%x, y = 0x%x\n", x, y);
    // Example 2
    mystruct struct1 = {2, "Hello"};
    mystruct struct2 = {5, "Goodbye"};
    printf("BEFORE: struct1: x = %d, s = %s\n", struct1.x, struct1.s);
    printf("BEFORE: struct2: x = %d, s = %s\n", struct2.x, struct2.s);
    //swap(&struct1, &struct2, sizeof(mystruct));
    swap(&struct1, &struct2, sizeof(int));  // what happens if we do this?
    printf("AFTER: struct1: x = %d, s = %s\n", struct1.x, struct1.s);
    printf("AFTER: struct2: x = %d, s = %s\n", struct2.x, struct2.s);
    return 0;
}

Generic Array Swap

Generic Stack

先看int版本的stack

#include <assert.h>
#include <error.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// The number of elements to put in our test stack
const int TEST_STACK_SIZE = 10;

/* This type is a single node in our linked list of ints,
 * that stores a single integer value and where the next
 * node lives.
 */
typedef struct int_node {
    struct int_node *next;
    int data;
} int_node;

/* This type is a stack that contains where the head of
 * its linked list of values is located, and its size.
 */
typedef struct int_stack {
    int nelems;
    int_node *top; 
} int_stack;

/* This function dynamically allocates a new empty
 * stack and returns a pointer to it.
 */
int_stack *int_stack_create() {
    int_stack *s = malloc(sizeof(int_stack));
    assert(s != NULL);
    s->nelems = 0;
    s->top = NULL;
    return s;
}

/* This function adds a copy of data to the top of the stack. */
void int_stack_push(int_stack *s, int data) {
    int_node *new_node = malloc(sizeof(int_node));
    assert(new_node != NULL);
    new_node->data = data;

    new_node->next = s->top;
    s->top = new_node;
    s->nelems++;
}

/* This function removes and returns the data at the top of the stack. 
 * If the stack is empty, this function throws an error. */
int int_stack_pop(int_stack *s) {
    if (s->nelems == 0) {
        error(1, 0, "Cannot pop from empty stack"); 
    }
    int_node *n = s->top;
    int value = n->data;

    // rewire
    s->top = n->next; 

    free(n);
    s->nelems--;

    return value;
}

int main(int argc, char *argv[]) {
    int_stack *intstack = int_stack_create();
    for (int i = 0; i < TEST_STACK_SIZE; i++) {
        int_stack_push(intstack, i); 
    }

    // Pop off all elements
    while (intstack->nelems > 0) {
        printf("%d\n", int_stack_pop(intstack));
    }

    // push one more to check to see if our wiring
    // works when we removed all of the elements 
    int_stack_push(intstack, 7);
    printf("%d\n\n", int_stack_pop(intstack));

    // clean up
    free(intstack);

    return 0;
}

修改成泛型

总结

A more efficient stack

#include <assert.h>
#include <stdbool.h>
#include <error.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// The number of elements to put in our test stack
const size_t TEST_STACK_SIZE = 10;

/* This type is a stack that contains where the head of
 * its linked list of values is located, its element size, and
 * the width (in bytes) of the data type it is storing.
 */
typedef struct stack {
    size_t elem_size_bytes;
    size_t nelems;
    void *top; 
} stack;

/* This function dynamically allocates a new empty
 * stack and returns a pointer to it.
 */
stack *stack_create(size_t elem_size_bytes) {
    stack *s = malloc(sizeof(stack));
    assert(s != NULL);
    s->elem_size_bytes = elem_size_bytes;
    s->nelems = 0;
    s->top = NULL;
    return s;
}

/* This function adds a copy of data to the top of the stack. */
void stack_push(stack *s, const void *data) {
    // node looks like: (8 bytes of next node's address) (data)
    void *new_node = malloc(sizeof(void *) + s->elem_size_bytes);
    assert(new_node != NULL);

    // copy data into the new node
    memcpy((char *) new_node + sizeof(void *), data, s->elem_size_bytes);

    // set new node's next to be top of stack
    *((void **) new_node) = s->top;

    // then set top of stack to be new node
    s->top = new_node;
    s->nelems++;
}

/* This function removes and returns the data at the top of the stack.
 * If the stack is empty, this function throws an error. */
void stack_pop(stack *s, void *addr) {
    if (s->nelems == 0) {
        error(1, 0, "Cannot pop from empty stack");
    }

    void *n = s->top;
    memcpy(addr, (char *) n + sizeof(void *), s->elem_size_bytes);

    // rewire
    s->top = *(void **) n;
    free(n);
    s->nelems--;
}

void stack_delete(stack *s) {
    char temp[s->elem_size_bytes];
    while (s->nelems) {
        stack_pop(s, temp);
    }
    free(s);
}

/************************** main **************************/
int main(int argc, char *argv[]) {
    int arr[] = {1, 2, 3, 4};
    void *ptr = arr;
    int elt_1 = * (int *) ((char *) ptr + sizeof(int));
    printf("elt 1: %d\n", elt_1);

    /* int stack */
    stack *intstack = stack_create(sizeof(int));
    for (int i = 0; i < TEST_STACK_SIZE; i++) {
        stack_push(intstack, &i); 
    }

    // Pop off all elements
    int popped_int;
    while (intstack->nelems > 0) {
        stack_pop(intstack, &popped_int);
        printf("%d\n", popped_int);
    }
    printf("\n");

    // push one more to check to see if our wiring
    // works when we removed all of the elements
    int num = 7;
    stack_push(intstack, &num);
    stack_pop(intstack, &popped_int);
    printf("%d\n", popped_int);

    // clean up
    free(intstack);
    printf("\n");

    /* string stack */
    // Try a stack of the command line arguments
    stack *string_stack = stack_create(sizeof(argv[0]));
    for (int i = 1; i < argc; i++) {
        stack_push(string_stack, argv + i); 
    }

    char *next_arg;
    while (string_stack->nelems > 0) {
        stack_pop(string_stack, &next_arg);
        printf("%s\n", next_arg);
    }
    printf("\n");

    // add read only string to see if it works
    char *s = "hello";
    stack_push(string_stack ,&s);
    stack_pop(string_stack, &next_arg);
    printf("%s\n", next_arg);

    // clean up
    free(string_stack);

    return 0;
}