Vector và danh sách

#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#include "cds.h"

struct Vector {
    void  *d;         /* mang lien ke, do vector SO HUU */
    size_t n;         /* so phan tu dang co */
    size_t cap;       /* so phan tu chua duoc */
    size_t esz;       /* kich thuoc mot phan tu, biet luc CHAY */
};

/* Do doi cua phan tu thu i. Ep sang char * de so hoc theo byte. */
static void *o(const Vector *v, size_t i) {
    return (char *)v->d + i * v->esz;
}

Vector *vec_new(size_t esz) {
    if (esz == 0) return NULL;

    Vector *v = malloc(sizeof *v);
    if (v == NULL) return NULL;

    v->d = NULL;
    v->n = v->cap = 0;
    v->esz = esz;
    return v;
}

void vec_free(Vector *v, FreeFn f, void *ctx) {
    if (v == NULL) return;                 /* chap nhan NULL, nhu free */

    if (f != NULL)
        for (size_t i = 0; i < v->n; ++i) f(o(v, i), ctx);

    free(v->d);        /* vector so huu MANG */
    free(v);           /* va so huu chinh no */
}

/* Ham goi lai giai phong TAI NGUYEN BEN TRONG tung phan tu.
   Vi du voi phan tu la "struct { char *ten; int ma; }": */

static void huy_sv(void *pt, void *ctx) {
    (void)ctx;
    free(((SinhVien *)pt)->ten);     /* giai phong "ten"
                                        KHONG free(pt): pt tro vao giua mang */
}

vec_free(v, huy_sv, NULL);

/* Neu phan tu khong so huu gi thi truyen NULL: */
vec_free(v, NULL, NULL);

int vec_reserve(Vector *v, size_t n) {
    if (v == NULL) return -1;
    if (n <= v->cap) return 0;             /* da du cho */
    if (n > SIZE_MAX / v->esz) return -1;  /* chan tran, Bai 33.4 */

    void *moi = realloc(v->d, n * v->esz);
    if (moi == NULL) return -1;            /* v->d CON NGUYEN */

    v->d = moi;
    v->cap = n;
    return 0;
}

static int mo_rong(Vector *v) {
    size_t cap = v->cap ? v->cap * 2 : 8;
    if (v->cap > SIZE_MAX / 2) return -1;
    return vec_reserve(v, cap);
}

int vec_push(Vector *v, const void *pt) {
    if (v == NULL || pt == NULL) return -1;
    if (v->n == v->cap && mo_rong(v) != 0) return -1;

    memcpy(o(v, v->n), pt, v->esz);
    ++v->n;
    return 0;
}

static void doi_cho(void *a, void *b, size_t n) {
    unsigned char *x = a, *y = b;
    for (size_t i = 0; i < n; ++i) {
        unsigned char t = x[i]; x[i] = y[i]; y[i] = t;
    }
}

static void chim_xuong(Vector *v, size_t goc, size_t n,
                       CmpFn cmp, void *ctx) {
    for (;;) {
        size_t lon = goc;
        size_t t = 2 * goc + 1;      /* con trai  */
        size_t p = t + 1;            /* con phai  */

        if (t < n && cmp(o(v, t), o(v, lon), ctx) > 0) lon = t;
        if (p < n && cmp(o(v, p), o(v, lon), ctx) > 0) lon = p;
        if (lon == goc) return;      /* da dung cho */

        doi_cho(o(v, goc), o(v, lon), v->esz);
        goc = lon;
    }
}

void vec_sort(Vector *v, CmpFn cmp, void *ctx) {
    if (v == NULL || cmp == NULL || v->n < 2) return;

    /* 1. Dung heap: chim xuong tu giua ve dau */
    for (size_t i = v->n / 2; i-- > 0; ) chim_xuong(v, i, v->n, cmp, ctx);

    /* 2. Lay lan luot phan tu lon nhat ra cuoi */
    for (size_t i = v->n; i-- > 1; ) {
        doi_cho(o(v, 0), o(v, i), v->esz);
        chim_xuong(v, 0, i, cmp, ctx);
    }
}

static int ss_theo_khoa(const void *a, const void *b, void *ctx) {
    const double *khoa = ctx;
    double x = khoa[*(const int *)a];
    double y = khoa[*(const int *)b];
    return (x > y) - (x < y);
}

double khoa[] = { 3.1, 1.2, 5.9, 0.4 };

Vector *idx = vec_new(sizeof(int));
for (int i = 0; i < 4; ++i) vec_push(idx, &i);

vec_sort(idx, ss_theo_khoa, khoa);

/* idx gio la { 3, 1, 0, 2 }, tuc thu tu sap xep theo khoa.

   Voi qsort chuan thi ban phai dat "khoa" vao mot bien toan cuc,
   va do la ba van de o Bai 55.1: khong an toan da luong,
   khong long nhau duoc, khong tai su dung duoc. */

typedef struct Nut {
    struct Nut *truoc, *sau;
    /* du lieu nam NGAY SAU trong cung mot lan cap phat */
} Nut;

struct List {
    Nut    dau;          /* nut GIA, khong chua du lieu */
    size_t n;
    size_t esz;
};

static void *du_lieu(Nut *n) { return (char *)n + sizeof(Nut); }

List *list_new(size_t esz) {
    if (esz == 0) return NULL;

    List *l = malloc(sizeof *l);
    if (l == NULL) return NULL;

    l->dau.truoc = l->dau.sau = &l->dau;   /* tro vao chinh no */
    l->n = 0;
    l->esz = esz;
    return l;
}

static int go(List *l, Nut *n, void *ra) {
    if (n == &l->dau) return -1;           /* danh sach rong */

    if (ra != NULL) memcpy(ra, du_lieu(n), l->esz);

    n->truoc->sau = n->sau;
    n->sau->truoc = n->truoc;
    free(n);

    --l->n;
    return 0;
}

int list_pop_front(List *l, void *ra) {
    if (l == NULL) return -1;
    return go(l, l->dau.sau, ra);
}

int list_pop_back(List *l, void *ra) {
    if (l == NULL) return -1;
    return go(l, l->dau.truoc, ra);
}

/* Mot ham "go" dung cho ca hai dau, va cho ca viec xoa mot nut
   o giua neu ban them list_remove.

   Va cach kiem tra danh sach rong: "n == &l->dau".
   Voi danh sach rong thi dau.sau va dau.truoc deu tro vao chinh dau,
   nen ca hai ham pop deu tra ve -1 mot cach tu nhien. */

void list_foreach(List *l, ApplyFn f, void *ctx) {
    if (l == NULL || f == NULL) return;

    for (Nut *p = l->dau.sau; p != &l->dau; p = p->sau)
        f(du_lieu(p), ctx);
}

void list_free(List *l, FreeFn f, void *ctx) {
    if (l == NULL) return;

    Nut *p = l->dau.sau;
    while (p != &l->dau) {
        Nut *sau = p->sau;              /* LUU truoc khi free(p) */
        if (f != NULL) f(du_lieu(p), ctx);
        free(p);
        p = sau;
    }

    free(l);
}

/* Chu y dong "Nut *sau = p->sau;": doc p->sau SAU khi free(p)
   la dung sau khi giai phong. Bai 33.3 da do hau qua. */