|
4223
|
1 #include "list.h"
|
|
|
2 #include "val.h"
|
|
|
3 #include "xmalloc.h"
|
|
|
4
|
|
|
5 #include <string.h>
|
|
|
6 #include <assert.h>
|
|
|
7
|
|
|
8 typedef struct li_whale whale;
|
|
|
9
|
|
|
10 static whale *incr(whale *wp) {
|
|
|
11 assert(wp->refs > 0);
|
|
|
12 ++wp->refs;
|
|
|
13 return wp;
|
|
|
14 }
|
|
|
15
|
|
|
16 static void decr(whale *wp) {
|
|
|
17 assert(wp->refs > 0);
|
|
|
18 if (!--wp->refs) {
|
|
|
19 while (wp->length) {
|
|
|
20 --wp->length;
|
|
|
21 v_delete(wp->field[wp->length]);
|
|
|
22 }
|
|
|
23 xfree(wp->field);
|
|
|
24 xfree(wp);
|
|
|
25 }
|
|
|
26 }
|
|
|
27
|
|
|
28 enum {MAGIC = 7};
|
|
|
29
|
|
|
30 struct list *li_new(void) {
|
|
|
31 struct list *l = xmalloc(1, sizeof *l);
|
|
|
32 l->lwp = xmalloc(1, sizeof *l->lwp);
|
|
|
33 l->lwp->field = xmalloc(l->lwp->size = MAGIC, sizeof *l->lwp->field);
|
|
|
34 l->lwp->length = 0;
|
|
|
35 l->lwp->refs = 1;
|
|
|
36 l->offset = 0;
|
|
|
37 l->length = 0;
|
|
|
38 return l;
|
|
|
39 }
|
|
|
40
|
|
|
41 struct list *li_dup(const struct list *k) {
|
|
|
42 struct list *l = xmalloc(1, sizeof *l);
|
|
|
43 l->lwp = incr(k->lwp);
|
|
|
44 l->offset = k->offset;
|
|
|
45 l->length = k->length;
|
|
|
46 return l;
|
|
|
47 }
|
|
|
48
|
|
|
49 static void decouple(struct list *l, size_t slack) {
|
|
|
50 size_t i, n;
|
|
|
51 whale *const wp = l->lwp;
|
|
|
52 struct val **const field = wp->field + l->offset, **nfield;
|
|
|
53 assert(wp->refs > 0);
|
|
|
54 if (wp->refs == 1) {
|
|
|
55 return;
|
|
|
56 }
|
|
|
57 l->lwp = xmalloc(1, sizeof *l->lwp);
|
|
|
58 n = l->length;
|
|
|
59 l->lwp->field = nfield = xmalloc(l->lwp->size = n + slack > MAGIC ? n + slack : MAGIC, sizeof *l->lwp->field);
|
|
|
60 for (i = 0; i < n; ++i) {
|
|
|
61 v_set(nfield[i] = v_undef(), field[i]);
|
|
|
62 }
|
|
|
63 l->lwp->length = n;
|
|
|
64 l->lwp->refs = 1;
|
|
|
65 l->offset = 0;
|
|
|
66 decr(wp);
|
|
|
67 }
|
|
|
68
|
|
|
69 void li_decouple(struct list *l) {
|
|
|
70 decouple(l, 1);
|
|
|
71 }
|
|
|
72
|
|
|
73 void li_delete(struct list *l) {
|
|
|
74 decr(l->lwp);
|
|
|
75 xfree(l);
|
|
|
76 }
|
|
|
77
|
|
|
78 size_t (li_length)(const struct list *l) {
|
|
|
79 return li_length(l);
|
|
|
80 }
|
|
|
81
|
|
|
82 struct val *li_at(const struct list *l, size_t i) {
|
|
|
83 return i < l->length ? l->lwp->field[l->offset + i] : NULL;
|
|
|
84 }
|
|
|
85
|
|
|
86 int li_cmp(const struct list *k, const struct list *l) {
|
|
|
87 const size_t len_k = li_length(k), len_l = li_length(l);
|
|
|
88 struct val **const field_k = k->lwp->field + k->offset, **const field_l = l->lwp->field + l->offset;
|
|
|
89 size_t i;
|
|
|
90
|
|
|
91 for (i = 0; i < len_k && i < len_l; ++i) {
|
|
|
92 const int tmp = v_cmp_ls(field_k[i], field_l[i]);
|
|
|
93 if (tmp) {
|
|
|
94 return tmp;
|
|
|
95 }
|
|
|
96 }
|
|
|
97 if (i < len_k) {
|
|
|
98 return 1;
|
|
|
99 }
|
|
|
100 if (i < len_l) {
|
|
|
101 return -1;
|
|
|
102 }
|
|
|
103 return 0;
|
|
|
104 }
|
|
|
105
|
|
|
106 void (li_zero)(struct list *l) {
|
|
|
107 li_zero(l);
|
|
|
108 }
|
|
|
109
|
|
|
110 static void vpswap(struct val **p, struct val **q) {
|
|
|
111 struct val *tmp = *p;
|
|
|
112 *p = *q;
|
|
|
113 *q = tmp;
|
|
|
114 }
|
|
|
115
|
|
|
116 void li_push(struct list *l, struct val *v) {
|
|
|
117 struct li_whale *wp = l->lwp;
|
|
|
118 const size_t off = l->offset, len = l->length, wlen = wp->length, wsiz = wp->size;
|
|
|
119 struct val **field = wp->field;
|
|
|
120 assert(wp->refs > 0);
|
|
|
121 if (wp->refs > 1) {
|
|
|
122 decouple(l, 1);
|
|
|
123 wp = l->lwp;
|
|
|
124 field = wp->field;
|
|
|
125 } else if (off + len < wlen) {
|
|
|
126 v_delete(field[off + len]);
|
|
|
127 } else if (wlen < wsiz) {
|
|
|
128 /* */
|
|
|
129 } else if (off) {
|
|
|
130 size_t i;
|
|
|
131 for (i = 0; i < len; ++i) {
|
|
|
132 vpswap(&field[i], &field[off + i]);
|
|
|
133 }
|
|
|
134 l->offset = 0;
|
|
|
135 v_delete(field[len]);
|
|
|
136 } else {
|
|
|
137 wp->field = field = xrealloc(field, wp->size *= 2);
|
|
|
138 }
|
|
|
139 field[l->offset + l->length++] = v;
|
|
|
140 if (l->offset + l->length > wlen) {
|
|
|
141 wp->length = l->offset + l->length;
|
|
|
142 }
|
|
|
143 }
|
|
|
144
|
|
|
145 void li_push_cpy(struct list *l, const struct val *v) {
|
|
|
146 struct li_whale *wp = l->lwp;
|
|
|
147 const size_t off = l->offset, len = l->length, wlen = wp->length, wsiz = wp->size;
|
|
|
148 struct val **field = wp->field;
|
|
|
149 assert(wp->refs > 0);
|
|
|
150 if (wp->refs > 1) {
|
|
|
151 decouple(l, 1);
|
|
|
152 wp = l->lwp;
|
|
|
153 field = wp->field;
|
|
|
154 field[l->offset + len] = v_undef();
|
|
|
155 } else if (off + len < wlen) {
|
|
|
156 /* */
|
|
|
157 } else if (wlen < wsiz) {
|
|
|
158 field[off + len] = v_undef();
|
|
|
159 } else if (off) {
|
|
|
160 size_t i;
|
|
|
161 for (i = 0; i < len; ++i) {
|
|
|
162 vpswap(&field[i], &field[off + i]);
|
|
|
163 }
|
|
|
164 l->offset = 0;
|
|
|
165 } else {
|
|
|
166 wp->field = field = xrealloc(field, wp->size *= 2);
|
|
|
167 field[len] = v_undef();
|
|
|
168 }
|
|
|
169 v_set(field[l->offset + l->length++], v);
|
|
|
170 if (l->offset + l->length > wlen) {
|
|
|
171 wp->length = l->offset + l->length;
|
|
|
172 }
|
|
|
173 }
|
|
|
174
|
|
|
175 void li_append(struct list *k, const struct list *l) {
|
|
|
176 struct val **const field = l->lwp->field + l->offset;
|
|
|
177 const size_t len = li_length(l);
|
|
|
178 size_t i;
|
|
|
179
|
|
|
180 for (i = 0; i < len; ++i) {
|
|
|
181 li_push_cpy(k, field[i]);
|
|
|
182 }
|
|
|
183 }
|
|
|
184
|
|
|
185 void li_reverse(struct list *l) {
|
|
|
186 struct val **field;
|
|
|
187 size_t i, len;
|
|
|
188
|
|
|
189 len = li_length(l);
|
|
|
190 if (len < 2) {
|
|
|
191 return;
|
|
|
192 }
|
|
|
193
|
|
|
194 li_decouple(l);
|
|
|
195
|
|
|
196 field = l->lwp->field + l->offset;
|
|
|
197
|
|
|
198 for (i = 0; i < len / 2; ++i) {
|
|
|
199 vpswap(&field[i], &field[len - i - 1]);
|
|
|
200 }
|
|
|
201 }
|
|
|
202
|
|
|
203 void li_trunc(struct list *l, size_t n) {
|
|
|
204 if (l->length > n) {
|
|
|
205 if (!(l->length = n)) {
|
|
|
206 l->offset = 0;
|
|
|
207 }
|
|
|
208 }
|
|
|
209 }
|
|
|
210
|
|
|
211 void li_shift(struct list *l, size_t n) {
|
|
|
212 if (n >= li_length(l)) {
|
|
|
213 li_zero(l);
|
|
|
214 return;
|
|
|
215 }
|
|
|
216
|
|
|
217 l->offset += n;
|
|
|
218 l->length -= n;
|
|
|
219 }
|
