Specify First: Abstract Data Types

/* rqueue.c: agent-written from rqueue.h (illustrative) */
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "rqueue.h"

struct rqueue {
    struct reading *data;   /* ring buffer of cap slots */
    size_t head;            /* index of the oldest reading */
    size_t count;           /* readings currently stored */
    size_t cap;             /* slots allocated */
};

struct rqueue *rq_create(size_t initial_cap) {
    assert(initial_cap >= 1);
    struct rqueue *q = malloc(sizeof *q);
    if (q == NULL) return NULL;
    q->data = malloc(initial_cap * sizeof *q->data);
    if (q->data == NULL) { free(q); return NULL; }
    q->head = 0;
    q->count = 0;
    q->cap = initial_cap;
    return q;
}

void rq_destroy(struct rqueue *q) {
    if (q == NULL) return;
    free(q->data);
    free(q);
}

static enum rq_status grow(struct rqueue *q) {
    size_t new_cap = q->cap * 2;
    struct reading *d = malloc(new_cap * sizeof *d);
    if (d == NULL) return RQ_NOMEM;
    memcpy(d, q->data + q->head, q->count * sizeof *d);
    free(q->data);
    q->data = d;
    q->head = 0;
    q->cap = new_cap;
    return RQ_OK;
}

enum rq_status rq_push(struct rqueue *q,
                       const struct reading *r) {
    assert(q != NULL && r != NULL);
    if (q->count == q->cap) {
        enum rq_status s = grow(q);
        if (s != RQ_OK) return s;
    }
    q->data[(q->head + q->count) % q->cap] = *r;
    q->count++;
    return RQ_OK;
}

enum rq_status rq_pop(struct rqueue *q, struct reading *out) {
    assert(q != NULL && out != NULL);
    assert(q->count > 0);        /* cannot pop an empty queue */
    *out = q->data[q->head];
    q->head = (q->head + 1) % q->cap;
    q->count--;
    return RQ_OK;
}

size_t rq_size(const struct rqueue *q) {
    assert(q != NULL);
    return q->count;
}

#include "check.h"
#include "rqueue.h"

static void test_push_pop(void) {
    struct rqueue *q = rq_create(4);
    struct reading r = { 1001, 60, 21.5, 0x01 }, out;
    for (int i = 0; i < 6; i++)
        rq_push(q, &r);                  /* grows once */
    CHECK(rq_size(q) == 6);
    for (int i = 0; i < 6; i++)
        rq_pop(q, &out);
    CHECK(out.value == 21.5);
    CHECK(rq_size(q) == rq_size(q));
    rq_destroy(q);
}

int main(void) {
    test_push_pop();
    return CHECK_SUMMARY();
}

/* check.h: CHECK records a failure and keeps going. */
#ifndef CHECK_H
#define CHECK_H
#include <stdio.h>

static int checks_run = 0;
static int checks_failed = 0;

#define CHECK(cond)                                            \
    do {                                                       \
        checks_run++;                                          \
        if (!(cond)) {                                         \
            checks_failed++;                                   \
            fprintf(stderr, "%s:%d: FAIL: %s\n",               \
                    __FILE__, __LINE__, #cond);                \
        }                                                      \
    } while (0)

#define CHECK_SUMMARY()                                    \
    (printf("%d checks, %d failed\n",                     \
            checks_run, checks_failed),                    \
     checks_failed == 0 ? 0 : 1)
#endif

/* rqueue.c: agent-written from rqueue.h (illustrative) */
#include <assert.h>
#include <stdlib.h>
#include "rqueue.h"

struct rqueue {
    struct reading *data;   /* ring buffer of cap slots */
    size_t head;            /* index of the oldest reading */
    size_t count;           /* readings currently stored */
    size_t cap;             /* slots allocated */
};

struct rqueue *rq_create(size_t initial_cap) {
    assert(initial_cap >= 1);
    struct rqueue *q = malloc(sizeof *q);
    if (q == NULL) return NULL;
    q->data = malloc(initial_cap * sizeof *q->data);
    if (q->data == NULL) { free(q); return NULL; }
    q->head = 0;
    q->count = 0;
    q->cap = initial_cap;
    return q;
}

void rq_destroy(struct rqueue *q) {
    if (q == NULL) return;
    free(q->data);
    free(q);
}

static enum rq_status grow(struct rqueue *q) {
    size_t new_cap = q->cap * 2;
    struct reading *d = malloc(new_cap * sizeof *d);
    if (d == NULL) return RQ_NOMEM;
    for (size_t i = 0; i < q->count; i++)  /* unwrap in order */
        d[i] = q->data[(q->head + i) % q->cap];
    free(q->data);
    q->data = d;
    q->head = 0;
    q->cap = new_cap;
    return RQ_OK;
}

enum rq_status rq_push(struct rqueue *q,
                       const struct reading *r) {
    assert(q != NULL && r != NULL);
    if (q->count == q->cap) {
        enum rq_status s = grow(q);
        if (s != RQ_OK) return s;
    }
    q->data[(q->head + q->count) % q->cap] = *r;
    q->count++;
    return RQ_OK;
}

enum rq_status rq_pop(struct rqueue *q, struct reading *out) {
    assert(q != NULL && out != NULL);
    if (q->count == 0) return RQ_EMPTY;   /* rule 6: report */
    *out = q->data[q->head];
    q->head = (q->head + 1) % q->cap;
    q->count--;
    return RQ_OK;
}

size_t rq_size(const struct rqueue *q) {
    assert(q != NULL);
    return q->count;
}

#ifndef READING_H
#define READING_H
#include <stdint.h>
struct reading {
    uint32_t sensor_id;
    int64_t  time_s;
    double   value;
    uint8_t  flags;
};
#endif

#include <stdlib.h>
#include "rqueue.h"

struct rqueue {
    struct reading **items;      /* pointers, not copies */
    size_t head, count, cap;
};

struct rqueue *rq_create(void) {
    struct rqueue *q = malloc(sizeof *q);
    if (!q) return NULL;
    q->cap = 16; q->head = 0; q->count = 0;
    q->items = malloc(q->cap * sizeof *q->items);
    if (!q->items) { free(q); return NULL; }
    return q;
}

/* Takes ownership of r: the queue frees it in rq_destroy. */
int rq_push(struct rqueue *q, struct reading *r) {
    if (q->count == q->cap) return -1;
    q->items[(q->head + q->count) % q->cap] = r;
    q->count++;
    return 0;
}

/* Returns the oldest reading or NULL. The caller frees it. */
struct reading *rq_pop(struct rqueue *q) {
    if (q->count == 0) return NULL;
    struct reading *r = q->items[q->head];
    q->head = (q->head + 1) % q->cap;
    q->count--;
    return r;
}

size_t rq_size(const struct rqueue *q) { return q->count; }

/* Frees any readings still queued, then the queue itself. */
void rq_destroy(struct rqueue *q) {
    if (!q) return;
    for (size_t i = 0; i < q->count; i++)
        free(q->items[(q->head + i) % q->cap]);
    free(q->items);
    free(q);
}

#ifndef RQUEUE_H
#define RQUEUE_H
#include <stddef.h>
#include "reading.h"
struct rqueue;
struct rqueue *rq_create(void);
int rq_push(struct rqueue *q, struct reading *r);
struct reading *rq_pop(struct rqueue *q);
size_t rq_size(const struct rqueue *q);
void rq_destroy(struct rqueue *q);
#endif

#include <stdio.h>
#include "rqueue.h"

int main(void) {
    struct reading batch[3] = { /* one minute, three sensors */
        { 1001, 60, 21.75, 0x03 },
        { 1002, 60, 64.0,  0x03 },
        { 1003, 60, 1013.2, 0x03 },
    };
    struct rqueue *q = rq_create();
    if (q == NULL) return 1;
    for (int i = 0; i < 3; i++)
        rq_push(q, &batch[i]);

    struct reading *r = rq_pop(q);       /* upload the oldest */
    if (r != NULL)
        printf("uploaded sensor %u at t=%lld: %.2f\n",
               (unsigned)r->sensor_id, (long long)r->time_s,
               r->value);

    rq_destroy(q);                       /* shut down cleanly */
    printf("queue destroyed\n");
    return 0;
}

#ifndef READING_H
#define READING_H
#include <stdint.h>
struct reading {
    uint32_t sensor_id;
    int64_t  time_s;
    double   value;
    uint8_t  flags;
};
#endif

/* rmap.h: the latest reading for each sensor ID (a map ADT).
 * OWNERSHIP: the caller owns the map; rmap_destroy it once.
 *   put and get copy readings. Keys are integers, not owned.
 * ERRORS: NULL arguments are preconditions (assert). NOTFOUND
 *   and NOMEM are reported; on either, map and *out unchanged.
 * BUDGET (k = distinct IDs): put and get O(k). A station has
 *   k <= 64, so a linear scan is within budget.
 */
#ifndef RMAP_H
#define RMAP_H
#include <stddef.h>
#include "reading.h"
enum rmap_status { RMAP_OK = 0, RMAP_NOTFOUND, RMAP_NOMEM };
struct rmap;
struct rmap *rmap_create(void);
void rmap_destroy(struct rmap *m);
/* Post OK: rmap_get(m, id) yields *r; older ones are gone. */
enum rmap_status rmap_put(struct rmap *m, uint32_t id,
                          const struct reading *r);
enum rmap_status rmap_get(const struct rmap *m, uint32_t id,
                          struct reading *out);
size_t rmap_count(const struct rmap *m);
#endif

/* rqueue.h: a first-in, first-out queue of station readings.
 *
 * OWNERSHIP AND LIFETIME (student-written; never delegated)
 * 1. rq_create returns a queue that the caller owns. The caller
 *    passes it to rq_destroy exactly once. rq_destroy(NULL) is
 *    a no-op, as free(NULL) is.
 * 2. The queue stores copies. rq_push copies *r; the caller
 *    keeps ownership of r and may reuse or free it at once.
 * 3. rq_pop copies the oldest reading into *out, which the
 *    caller owns. No function returns a pointer into the queue.
 * 4. The queue owns its internal buffer. Nothing outside
 *    rqueue.c may free it or keep a pointer to it.
 *
 * ERRORS
 * 5. A NULL q, r or out is a precondition violation (a bug in
 *    the caller), except q in rq_destroy (rule 1): checked by
 *    assert, undefined behavior under NDEBUG.
 * 6. Empty and out-of-memory are run-time conditions, reported
 *    by return value, never asserted. On any return other than
 *    RQ_OK, the queue and *out are unchanged.
 */
/* INVARIANT (true before and after every call)
 *   0 <= size <= capacity, capacity >= 1, and readings leave in
 *   the order they arrived.
 * COMPLEXITY BUDGET (n = readings in the queue)
 *   rq_push  O(1) amortized; O(n) on the call that grows
 *   rq_pop, rq_size, rq_destroy    O(1)
 *   space    O(capacity); capacity <= max(initial, 2 * peak n)
 */
#ifndef RQUEUE_H
#define RQUEUE_H
#include <stddef.h>
#include "reading.h"

enum rq_status { RQ_OK = 0, RQ_EMPTY, RQ_NOMEM };
struct rqueue;                          /* opaque (Chapter 9) */

/* Pre: initial_cap >= 1. Post: an empty queue, or NULL if out
   of memory. */
struct rqueue *rq_create(size_t initial_cap);
/* Pre: q is NULL or came from rq_create and was not destroyed.
   Post: all memory owned by q is released. */
void rq_destroy(struct rqueue *q);

/* Pre: q != NULL, r != NULL.
   Post RQ_OK:    size is one larger; *r is the newest reading.
   Post RQ_NOMEM: queue unchanged. */
enum rq_status rq_push(struct rqueue *q,
                       const struct reading *r);

/* Pre: q != NULL, out != NULL.
   Post RQ_OK:    *out is the reading that was oldest; it has
                  been removed, so size is one smaller.
   Post RQ_EMPTY: size was 0; queue and *out unchanged. */
enum rq_status rq_pop(struct rqueue *q, struct reading *out);

/* Pre: q != NULL. Post: returns the number of readings held;
   the queue is unchanged. */
size_t rq_size(const struct rqueue *q);

#endif

/* test_model.c: compare rqueue against a plain-array model. */
#include <stdlib.h>
#include "check.h"
#include "rqueue.h"

int main(void) {
    enum { STEPS = 100000 };
    static int64_t model[STEPS];    /* every time ever pushed */
    size_t front = 0, back = 0;     /* model holds [front, back) */
    struct rqueue *q = rq_create(1);
    srand(11);
    for (int64_t t = 0; t < STEPS; t++) {
        struct reading r = { 1001, t, 0.0, 0x01 }, out;
        if (rand() % 3 != 0) {          /* push 2 times in 3 */
            CHECK(rq_push(q, &r) == RQ_OK);
            model[back++] = t;
        } else if (front == back) {
            CHECK(rq_pop(q, &out) == RQ_EMPTY);
        } else {
            CHECK(rq_pop(q, &out) == RQ_OK);
            CHECK(out.time_s == model[front]);
            front++;
        }
        CHECK(rq_size(q) == back - front);
    }
    rq_destroy(q);
    return CHECK_SUMMARY();
}

/* test_rqueue.c: the spec as checks, before any code. */
#include "check.h"
#include "rqueue.h"

static struct reading mk(int64_t t) {  /* a reading at time t */
    struct reading r = {1001, t, 20.0 + (double)t / 10.0, 0x01};
    return r;
}

static void test_new_queue_is_empty(void) {
    struct rqueue *q = rq_create(4);
    CHECK(q != NULL);
    CHECK(rq_size(q) == 0);
    rq_destroy(q);
}

static void test_pop_empty_is_reported(void) {     /* rule 6 */
    struct rqueue *q = rq_create(4);
    struct reading out = mk(-1);
    CHECK(rq_pop(q, &out) == RQ_EMPTY);
    CHECK(out.time_s == -1);               /* *out unchanged */
    CHECK(rq_size(q) == 0);                /* queue unchanged */
    rq_destroy(q);
}

static void test_push_copies(void) {                /* rule 2 */
    struct rqueue *q = rq_create(4);
    struct reading r = mk(5), out;
    CHECK(rq_push(q, &r) == RQ_OK);
    r.time_s = 99;               /* caller reuses its storage */
    CHECK(rq_pop(q, &out) == RQ_OK);
    CHECK(out.time_s == 5);
    rq_destroy(q);
}

static void test_fifo_across_wrap_and_growth(void) {
    struct rqueue *q = rq_create(4);
    struct reading r, out;
    for (int64_t t = 0; t < 3; t++) {    /* holds 0 1 2     */
        r = mk(t);
        CHECK(rq_push(q, &r) == RQ_OK);
    }
    CHECK(rq_pop(q, &out) == RQ_OK && out.time_s == 0);
    CHECK(rq_pop(q, &out) == RQ_OK && out.time_s == 1);
    for (int64_t t = 3; t < 10; t++) {   /* wraps, grows    */
        r = mk(t);
        CHECK(rq_push(q, &r) == RQ_OK);
    }
    CHECK(rq_size(q) == 8);
    for (int64_t t = 2; t < 10; t++) {   /* leave in order */
        CHECK(rq_pop(q, &out) == RQ_OK);
        CHECK(out.time_s == t);
    }
    CHECK(rq_pop(q, &out) == RQ_EMPTY);
    rq_destroy(q);
}

int main(void) {
    test_new_queue_is_empty();
    test_pop_empty_is_reported();
    test_push_copies();
    test_fifo_across_wrap_and_growth();
    rq_destroy(NULL);                      /* rule 1: a no-op */
    return CHECK_SUMMARY();
}

/* time_rq.c: push n readings, pop them all; best of five runs.
   Build: gcc -std=c17 -O2 -o time_rq time_rq.c corrected/rqueue.c */
#include <stdio.h>
#include <time.h>
#include "rqueue.h"

static double now(void) {
    struct timespec ts;
    timespec_get(&ts, TIME_UTC);
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}

int main(void) {
    for (long n = 125000; n <= 4000000; n *= 2) {
        double best = 1e9;
        for (int rep = 0; rep < 5; rep++) {
            struct rqueue *q = rq_create(4);
            if (q == NULL) return 1;
            struct reading r = { 1001, 0, 1.0, 0x01 }, out;
            double t0 = now();
            for (long i = 0; i < n; i++) { r.time_s = i; rq_push(q, &r); }
            for (long i = 0; i < n; i++) rq_pop(q, &out);
            double t = now() - t0;
            if (t < best) best = t;
            rq_destroy(q);
        }
        printf("%8ld  %8.2f ms  %6.2f ns/op\n", n, best * 1e3,
               best * 1e9 / (2.0 * (double)n));
    }
    return 0;
}

/* undo.c: a stack of calibration offsets, a contract per op. */
#include <assert.h>
#include <stdio.h>

#define UNDO_MAX 4
enum st_status { ST_OK, ST_EMPTY, ST_FULL };
struct undo_stack { double items[UNDO_MAX]; size_t top; };
/* Invariant: 0 <= top <= UNDO_MAX; items[0..top-1] are held,
   items[top-1] is the newest. */

/* Pre: s != NULL. Post OK: top grew by 1, items[top-1] == x.
   Post FULL: top == UNDO_MAX; stack unchanged. */
enum st_status st_push(struct undo_stack *s, double x) {
    assert(s != NULL);
    if (s->top == UNDO_MAX) return ST_FULL;
    s->items[s->top++] = x;
    return ST_OK;
}

/* Pre: s != NULL, out != NULL. Post OK: *out was the newest
   item and is removed. Post EMPTY: top == 0; *out and the stack
   are unchanged. */
enum st_status st_pop(struct undo_stack *s, double *out) {
    assert(s != NULL && out != NULL);
    if (s->top == 0) return ST_EMPTY;
    *out = s->items[--s->top];
    return ST_OK;
}

int main(void) {
    struct undo_stack s = { .top = 0 };
    double x = 0.0;
    st_push(&s, 0.10); st_push(&s, -0.05); st_push(&s, 0.20);
    for (int i = 0; i < 4; i++) {
        enum st_status st = st_pop(&s, &x);
        printf("pop %d: status %d, x = %.2f\n", i, (int)st, x);
    }
    return 0;
}