Mercurial > repo
view src/ploki/list.c @ 4335:c3083517f99c
<int-e> revert
author | HackBot |
---|---|
date | Thu, 16 Jan 2014 23:12:02 +0000 |
parents | ac0403686959 |
children |
line wrap: on
line source
#include "list.h" #include "val.h" #include "xmalloc.h" #include <string.h> #include <assert.h> typedef struct li_whale whale; static whale *incr(whale *wp) { assert(wp->refs > 0); ++wp->refs; return wp; } static void decr(whale *wp) { assert(wp->refs > 0); if (!--wp->refs) { while (wp->length) { --wp->length; v_delete(wp->field[wp->length]); } xfree(wp->field); xfree(wp); } } enum {MAGIC = 7}; struct list *li_new(void) { struct list *l = xmalloc(1, sizeof *l); l->lwp = xmalloc(1, sizeof *l->lwp); l->lwp->field = xmalloc(l->lwp->size = MAGIC, sizeof *l->lwp->field); l->lwp->length = 0; l->lwp->refs = 1; l->offset = 0; l->length = 0; return l; } struct list *li_dup(const struct list *k) { struct list *l = xmalloc(1, sizeof *l); l->lwp = incr(k->lwp); l->offset = k->offset; l->length = k->length; return l; } static void decouple(struct list *l, size_t slack) { size_t i, n; whale *const wp = l->lwp; struct val **const field = wp->field + l->offset, **nfield; assert(wp->refs > 0); if (wp->refs == 1) { return; } l->lwp = xmalloc(1, sizeof *l->lwp); n = l->length; l->lwp->field = nfield = xmalloc(l->lwp->size = n + slack > MAGIC ? n + slack : MAGIC, sizeof *l->lwp->field); for (i = 0; i < n; ++i) { v_set(nfield[i] = v_undef(), field[i]); } l->lwp->length = n; l->lwp->refs = 1; l->offset = 0; decr(wp); } void li_decouple(struct list *l) { decouple(l, 1); } void li_delete(struct list *l) { decr(l->lwp); xfree(l); } size_t (li_length)(const struct list *l) { return li_length(l); } struct val *li_at(const struct list *l, size_t i) { return i < l->length ? l->lwp->field[l->offset + i] : NULL; } int li_cmp(const struct list *k, const struct list *l) { const size_t len_k = li_length(k), len_l = li_length(l); struct val **const field_k = k->lwp->field + k->offset, **const field_l = l->lwp->field + l->offset; size_t i; for (i = 0; i < len_k && i < len_l; ++i) { const int tmp = v_cmp_ls(field_k[i], field_l[i]); if (tmp) { return tmp; } } if (i < len_k) { return 1; } if (i < len_l) { return -1; } return 0; } void (li_zero)(struct list *l) { li_zero(l); } static void vpswap(struct val **p, struct val **q) { struct val *tmp = *p; *p = *q; *q = tmp; } void li_push(struct list *l, struct val *v) { struct li_whale *wp = l->lwp; const size_t off = l->offset, len = l->length, wlen = wp->length, wsiz = wp->size; struct val **field = wp->field; assert(wp->refs > 0); if (wp->refs > 1) { decouple(l, 1); wp = l->lwp; field = wp->field; } else if (off + len < wlen) { v_delete(field[off + len]); } else if (wlen < wsiz) { /* */ } else if (off) { size_t i; for (i = 0; i < len; ++i) { vpswap(&field[i], &field[off + i]); } l->offset = 0; v_delete(field[len]); } else { wp->field = field = xrealloc(field, wp->size *= 2); } field[l->offset + l->length++] = v; if (l->offset + l->length > wlen) { wp->length = l->offset + l->length; } } void li_push_cpy(struct list *l, const struct val *v) { struct li_whale *wp = l->lwp; const size_t off = l->offset, len = l->length, wlen = wp->length, wsiz = wp->size; struct val **field = wp->field; assert(wp->refs > 0); if (wp->refs > 1) { decouple(l, 1); wp = l->lwp; field = wp->field; field[l->offset + len] = v_undef(); } else if (off + len < wlen) { /* */ } else if (wlen < wsiz) { field[off + len] = v_undef(); } else if (off) { size_t i; for (i = 0; i < len; ++i) { vpswap(&field[i], &field[off + i]); } l->offset = 0; } else { wp->field = field = xrealloc(field, wp->size *= 2); field[len] = v_undef(); } v_set(field[l->offset + l->length++], v); if (l->offset + l->length > wlen) { wp->length = l->offset + l->length; } } void li_append(struct list *k, const struct list *l) { struct val **const field = l->lwp->field + l->offset; const size_t len = li_length(l); size_t i; for (i = 0; i < len; ++i) { li_push_cpy(k, field[i]); } } void li_reverse(struct list *l) { struct val **field; size_t i, len; len = li_length(l); if (len < 2) { return; } li_decouple(l); field = l->lwp->field + l->offset; for (i = 0; i < len / 2; ++i) { vpswap(&field[i], &field[len - i - 1]); } } void li_trunc(struct list *l, size_t n) { if (l->length > n) { if (!(l->length = n)) { l->offset = 0; } } } void li_shift(struct list *l, size_t n) { if (n >= li_length(l)) { li_zero(l); return; } l->offset += n; l->length -= n; }