computing-systems-212 / Lab 2: Heap Allocation + Management / task1 / crazylist.c
crazylist.c
Raw
#include <inttypes.h>
#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include "crazylist.h"

// The macro for offsetof can be used to replace it
// #define OFFSETOF(TYPE, ELEMENT) ((size_t)&(((TYPE *)0)->ELEMENT))
crazycons_t *enclosing_struct(uint64_t *car) {
    return (crazycons_t *) ((void *) car - ((size_t)&(((crazycons_t *)0)->car)));
}

uint64_t *cons(uint64_t car, uint64_t *cdr) {
    crazycons_t *cons = (crazycons_t *) malloc(sizeof(crazycons_t));
    assert(cons);
    cons->car = car;
    cons->cdr = cdr;
    assert(cons);
    return (uint64_t *) &cons->car;
}

uint64_t first(uint64_t *list) {

    return *list;
}

uint64_t *rest(uint64_t *list) {

    return &(*(list+1));
}

// (gdb) x/24g list-20 helped recognize the necessary list-5 recursive call
uint64_t *find(uint64_t *list, uint64_t query) {

    uint64_t val = first(list);
    if(val == query) {
        return (uint64_t *) enclosing_struct(list);
    }
    else {
        if (val) {
            return find(rest(list-5), query);
        }
        else
            return NULL;
    }
}

uint64_t *insert_sorted(uint64_t *list, uint64_t n) {

    uint64_t val = first(list);
    if(n <= val) {
        return cons(n, rest(list-5));
    }
    else {
        if (val) {
            return insert_sorted(rest(list-5), n);
        }
    }
}

void print_list(uint64_t *list) {
    
    uint64_t val = first(list);
    if(val) {
        printf("%lu ", val);
        print_list(rest(list-5));
    }
    else {
        printf("\n");
        return;
    }
}