1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2009, 2011 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18
19 #include "data/caseproto.h"
20
21 #include "data/val-type.h"
22 #include "data/value.h"
23 #include "libpspp/array.h"
24 #include "libpspp/assertion.h"
25 #include "libpspp/pool.h"
26
27 #include "gl/minmax.h"
28
29 static struct caseproto *caseproto_unshare (struct caseproto *);
30 static bool try_init_strings (const struct caseproto *,
31 size_t first, size_t last, union value[]);
32 static void init_strings (const struct caseproto *,
33 size_t first, size_t last, union value[]);
34 static void destroy_strings (const struct caseproto *,
35 size_t first, size_t last, union value[]);
36 static size_t count_strings (const struct caseproto *,
37 size_t idx, size_t count);
38
39 /* Returns the number of bytes to allocate for a struct caseproto
40 with room for N_WIDTHS elements in its widths[] array. */
41 static inline size_t
caseproto_size(size_t n_widths)42 caseproto_size (size_t n_widths)
43 {
44 return (offsetof (struct caseproto, widths)
45 + n_widths * sizeof (((struct caseproto *) NULL)->widths[0]));
46 }
47
48 /* Creates and returns a case prototype that initially has no
49 widths. */
50 struct caseproto *
caseproto_create(void)51 caseproto_create (void)
52 {
53 enum { N_ALLOCATE = 4 };
54 struct caseproto *proto = xmalloc (caseproto_size (N_ALLOCATE));
55 proto->ref_cnt = 1;
56 proto->strings = NULL;
57 proto->n_strings = 0;
58 proto->n_widths = 0;
59 proto->allocated_widths = N_ALLOCATE;
60 return proto;
61 }
62
63 static void
do_unref(void * proto_)64 do_unref (void *proto_)
65 {
66 struct caseproto *proto = proto_;
67 caseproto_unref (proto);
68 }
69
70 /* Creates and returns a new reference to PROTO. When POOL is
71 destroyed, the new reference will be destroyed (unrefed). */
72 struct caseproto *
caseproto_ref_pool(const struct caseproto * proto_,struct pool * pool)73 caseproto_ref_pool (const struct caseproto *proto_, struct pool *pool)
74 {
75 struct caseproto *proto = caseproto_ref (proto_);
76 pool_register (pool, do_unref, proto);
77 return proto;
78 }
79
80 /* Returns a replacement for PROTO that is unshared and has
81 enough room for at least N_WIDTHS widths before additional
82 memory is needed. */
83 struct caseproto *
caseproto_reserve(struct caseproto * proto,size_t n_widths)84 caseproto_reserve (struct caseproto *proto, size_t n_widths)
85 {
86 proto = caseproto_unshare (proto);
87 if (n_widths > proto->allocated_widths)
88 {
89 proto->allocated_widths *= MAX (proto->allocated_widths * 2, n_widths);
90 proto = xrealloc (proto, caseproto_size (proto->allocated_widths));
91 }
92 return proto;
93 }
94
95 /* Returns a replacement for PROTO with WIDTH appended. */
96 struct caseproto *
caseproto_add_width(struct caseproto * proto,int width)97 caseproto_add_width (struct caseproto *proto, int width)
98 {
99 assert (width >= -1 && width <= MAX_STRING);
100
101 proto = caseproto_reserve (proto, proto->n_widths + 1);
102 proto->widths[proto->n_widths++] = width;
103 proto->n_strings += count_strings (proto, proto->n_widths - 1, 1);
104
105 return proto;
106 }
107
108 /* Returns a replacement for PROTO with the width at index IDX
109 replaced by WIDTH. IDX may be greater than the current number
110 of widths in PROTO, in which case any gap is filled in by
111 widths of -1. */
112 struct caseproto *
caseproto_set_width(struct caseproto * proto,size_t idx,int width)113 caseproto_set_width (struct caseproto *proto, size_t idx, int width)
114 {
115 assert (width >= -1 && width <= MAX_STRING);
116
117 proto = caseproto_reserve (proto, idx + 1);
118 while (idx >= proto->n_widths)
119 proto->widths[proto->n_widths++] = -1;
120 proto->n_strings -= count_strings (proto, idx, 1);
121 proto->widths[idx] = width;
122 proto->n_strings += count_strings (proto, idx, 1);
123
124 return proto;
125 }
126
127 /* Returns a replacement for PROTO with WIDTH inserted just
128 before index BEFORE, or just after the last element if BEFORE
129 is the number of widths in PROTO. */
130 struct caseproto *
caseproto_insert_width(struct caseproto * proto,size_t before,int width)131 caseproto_insert_width (struct caseproto *proto, size_t before, int width)
132 {
133 assert (before <= proto->n_widths);
134
135 proto = caseproto_reserve (proto, proto->n_widths + 1);
136 proto->n_strings += value_needs_init (width);
137 insert_element (proto->widths, proto->n_widths, sizeof *proto->widths,
138 before);
139 proto->widths[before] = width;
140 proto->n_widths++;
141
142 return proto;
143 }
144
145 /* Returns a replacement for PROTO with CNT widths removed
146 starting at index IDX. */
147 struct caseproto *
caseproto_remove_widths(struct caseproto * proto,size_t idx,size_t cnt)148 caseproto_remove_widths (struct caseproto *proto, size_t idx, size_t cnt)
149 {
150 assert (caseproto_range_is_valid (proto, idx, cnt));
151
152 proto = caseproto_unshare (proto);
153 proto->n_strings -= count_strings (proto, idx, cnt);
154 remove_range (proto->widths, proto->n_widths, sizeof *proto->widths,
155 idx, cnt);
156 proto->n_widths -= cnt;
157 return proto;
158 }
159
160 /* Returns a replacement for PROTO in which the CNT widths
161 starting at index OLD_WIDTH now start at index NEW_WIDTH, with
162 other widths shifting out of the way to make room. */
163 struct caseproto *
caseproto_move_widths(struct caseproto * proto,size_t old_start,size_t new_start,size_t cnt)164 caseproto_move_widths (struct caseproto *proto,
165 size_t old_start, size_t new_start,
166 size_t cnt)
167 {
168 assert (caseproto_range_is_valid (proto, old_start, cnt));
169 assert (caseproto_range_is_valid (proto, new_start, cnt));
170
171 proto = caseproto_unshare (proto);
172 move_range (proto->widths, proto->n_widths, sizeof *proto->widths,
173 old_start, new_start, cnt);
174 return proto;
175 }
176
177 /* Returns true if PROTO contains COUNT widths starting at index
178 OFS, false if any of those widths are out of range for
179 PROTO. */
180 bool
caseproto_range_is_valid(const struct caseproto * proto,size_t ofs,size_t count)181 caseproto_range_is_valid (const struct caseproto *proto,
182 size_t ofs, size_t count)
183 {
184 return (count <= proto->n_widths
185 && ofs <= proto->n_widths
186 && ofs + count <= proto->n_widths);
187 }
188
189 /* Returns true if A and B have the same widths along their
190 common length. (When this is so, a case with prototype A may
191 be extended or truncated to have prototype B without having to
192 change any existing values, and vice versa.) */
193 bool
caseproto_is_conformable(const struct caseproto * a,const struct caseproto * b)194 caseproto_is_conformable (const struct caseproto *a, const struct caseproto *b)
195 {
196 size_t min;
197 size_t i;
198
199 min = MIN (a->n_widths, b->n_widths);
200 for (i = 0; i < min; i++)
201 if (a->widths[i] != b->widths[i])
202 return false;
203 return true;
204 }
205
206 /* Returns true if the N widths starting at A_START in A are the
207 same as the N widths starting at B_START in B, false if any of
208 the corresponding widths differ. */
209 bool
caseproto_equal(const struct caseproto * a,size_t a_start,const struct caseproto * b,size_t b_start,size_t n)210 caseproto_equal (const struct caseproto *a, size_t a_start,
211 const struct caseproto *b, size_t b_start,
212 size_t n)
213 {
214 size_t i;
215
216 assert (caseproto_range_is_valid (a, a_start, n));
217 assert (caseproto_range_is_valid (b, b_start, n));
218 for (i = 0; i < n; i++)
219 if (a->widths[a_start + i] != b->widths[b_start + i])
220 return false;
221 return true;
222 }
223
224 /* Returns true if an array of values that is to be used for
225 data of the format specified in PROTO needs to be initialized
226 by calling caseproto_init_values, false if that step may be
227 skipped because such an initialization would be a no-op anyhow.
228
229 This optimization is useful only when a large number of
230 initializations of such arrays may be skipped as a group. */
231 bool
caseproto_needs_init_values(const struct caseproto * proto)232 caseproto_needs_init_values (const struct caseproto *proto)
233 {
234 return proto->n_strings > 0;
235 }
236
237 /* Initializes the values in VALUES as required by PROTO, by
238 calling value_init() on each value for which this is required.
239 The data in VALUES have indeterminate contents until
240 explicitly written.
241
242 VALUES must have at least caseproto_get_n_widths(PROTO)
243 elements; only that many elements of VALUES are initialized.
244
245 The caller retains ownership of PROTO. */
246 void
caseproto_init_values(const struct caseproto * proto,union value values[])247 caseproto_init_values (const struct caseproto *proto, union value values[])
248 {
249 init_strings (proto, 0, proto->n_strings, values);
250 }
251
252 /* Like caseproto_init_values, but returns false instead of
253 terminating if memory cannot be obtained. */
254 bool
caseproto_try_init_values(const struct caseproto * proto,union value values[])255 caseproto_try_init_values (const struct caseproto *proto, union value values[])
256 {
257 return try_init_strings (proto, 0, proto->n_strings, values);
258 }
259
260 /* Initializes the data in VALUES that are in NEW but not in OLD,
261 destroys the data in VALUES that are in OLD but not NEW, and
262 does not modify the data in VALUES that are in both OLD and
263 NEW. VALUES must previously have been initialized as required
264 by OLD using e.g. caseproto_init_values. The data in VALUES
265 that are in NEW but not in OLD will have indeterminate
266 contents until explicitly written.
267
268 OLD and NEW must be conformable for this operation, as
269 reported by caseproto_is_conformable.
270
271 The caller retains ownership of OLD and NEW. */
272 void
caseproto_reinit_values(const struct caseproto * old,const struct caseproto * new,union value values[])273 caseproto_reinit_values (const struct caseproto *old,
274 const struct caseproto *new, union value values[])
275 {
276 size_t old_n_long = old->n_strings;
277 size_t new_n_long = new->n_strings;
278
279 expensive_assert (caseproto_is_conformable (old, new));
280
281 if (new_n_long > old_n_long)
282 init_strings (new, old_n_long, new_n_long, values);
283 else if (new_n_long < old_n_long)
284 destroy_strings (old, new_n_long, old_n_long, values);
285 }
286
287 /* Frees the values in VALUES as required by PROTO, by calling
288 value_destroy() on each value for which this is required. The
289 values must previously have been initialized using
290 e.g. caseproto_init_values.
291
292 The caller retains ownership of PROTO. */
293 void
caseproto_destroy_values(const struct caseproto * proto,union value values[])294 caseproto_destroy_values (const struct caseproto *proto, union value values[])
295 {
296 destroy_strings (proto, 0, proto->n_strings, values);
297 }
298
299 /* Copies COUNT values, whose widths are given by widths in PROTO
300 starting with index IDX, from SRC to DST. The caller must
301 ensure that the values in SRC and DST were appropriately
302 initialized using e.g. caseproto_init_values. */
303 void
caseproto_copy(const struct caseproto * proto,size_t idx,size_t count,union value * dst,const union value * src)304 caseproto_copy (const struct caseproto *proto, size_t idx, size_t count,
305 union value *dst, const union value *src)
306 {
307 size_t i;
308
309 assert (caseproto_range_is_valid (proto, idx, count));
310 for (i = 0; i < count; i++)
311 value_copy (&dst[idx + i], &src[idx + i], proto->widths[idx + i]);
312 }
313
314 void
caseproto_free__(struct caseproto * proto)315 caseproto_free__ (struct caseproto *proto)
316 {
317 free (proto->strings);
318 free (proto);
319 }
320
321 void
caseproto_refresh_string_cache__(const struct caseproto * proto_)322 caseproto_refresh_string_cache__ (const struct caseproto *proto_)
323 {
324 struct caseproto *proto = CONST_CAST (struct caseproto *, proto_);
325 size_t n, i;
326
327 assert (proto->strings == NULL);
328 assert (proto->n_strings > 0);
329
330 proto->strings = xmalloc (proto->n_strings * sizeof *proto->strings);
331 n = 0;
332 for (i = 0; i < proto->n_widths; i++)
333 if (proto->widths[i] > 0)
334 proto->strings[n++] = i;
335 assert (n == proto->n_strings);
336 }
337
338 static struct caseproto *
caseproto_unshare(struct caseproto * old)339 caseproto_unshare (struct caseproto *old)
340 {
341 struct caseproto *new;
342 if (old->ref_cnt > 1)
343 {
344 new = xmemdup (old, caseproto_size (old->allocated_widths));
345 new->ref_cnt = 1;
346 --old->ref_cnt;
347 }
348 else
349 {
350 new = old;
351 free (new->strings);
352 }
353 new->strings = NULL;
354 return new;
355 }
356
357 static bool
try_init_strings(const struct caseproto * proto,size_t first,size_t last,union value values[])358 try_init_strings (const struct caseproto *proto,
359 size_t first, size_t last, union value values[])
360 {
361 size_t i;
362
363 if (last > 0 && proto->strings == NULL)
364 caseproto_refresh_string_cache__ (proto);
365
366 for (i = first; i < last; i++)
367 {
368 size_t idx = proto->strings[i];
369 if (!value_try_init (&values[idx], proto->widths[idx]))
370 {
371 destroy_strings (proto, first, i, values);
372 return false;
373 }
374 }
375 return true;
376 }
377
378 static void
init_strings(const struct caseproto * proto,size_t first,size_t last,union value values[])379 init_strings (const struct caseproto *proto,
380 size_t first, size_t last, union value values[])
381 {
382 if (!try_init_strings (proto, first, last, values))
383 xalloc_die ();
384 }
385
386 static void
destroy_strings(const struct caseproto * proto,size_t first,size_t last,union value values[])387 destroy_strings (const struct caseproto *proto, size_t first, size_t last,
388 union value values[])
389 {
390 size_t i;
391
392 if (last > 0 && proto->strings == NULL)
393 caseproto_refresh_string_cache__ (proto);
394
395 for (i = first; i < last; i++)
396 {
397 size_t idx = proto->strings[i];
398 value_destroy (&values[idx], proto->widths[idx]);
399 }
400 }
401
402 static size_t
count_strings(const struct caseproto * proto,size_t idx,size_t count)403 count_strings (const struct caseproto *proto, size_t idx, size_t count)
404 {
405 size_t n, i;
406
407 n = 0;
408 for (i = 0; i < count; i++)
409 n += proto->widths[idx + i] > 0;
410 return n;
411 }
412