Mercurial > repo

comparison src/ploki/list.c @ 4223:ac0403686959

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<oerjan> rm -rf src/ploki; mv ploki src
author HackBot
date Fri, 20 Dec 2013 22:18:50 +0000
parents
children
comparison
equal deleted inserted replaced
4222:b0f3e267bb1e 4223:ac0403686959
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 }