void case_copy (struct ccase *dst, size_t dst_idx,
const struct ccase *src, size_t src_idx,
- size_t cnt);
+ size_t n_values);
void case_copy_out (const struct ccase *,
size_t start_idx, union value *, size_t n_values);
void case_copy_in (struct ccase *,
struct init_list
{
struct init_value *values;
- size_t cnt;
+ size_t n;
};
/* A bitmap of the "left" status of variables. */
init_list_create (struct init_list *list)
{
list->values = NULL;
- list->cnt = 0;
+ list->n = 0;
}
/* Initializes NEW as a copy of OLD. */
{
size_t i;
- new->values = xmemdup (old->values, old->cnt * sizeof *old->values);
- new->cnt = old->cnt;
+ new->values = xmemdup (old->values, old->n * sizeof *old->values);
+ new->n = old->n;
- for (i = 0; i < new->cnt; i++)
+ for (i = 0; i < new->n; i++)
{
struct init_value *iv = &new->values[i];
value_clone (&iv->value, &iv->value, iv->width);
{
struct init_value *iv;
- for (iv = &list->values[0]; iv < &list->values[list->cnt]; iv++)
+ for (iv = &list->values[0]; iv < &list->values[list->n]; iv++)
value_destroy (&iv->value, iv->width);
free (list->values);
}
{
struct init_value value;
value.case_index = case_index;
- return binary_search (list->values, list->cnt, sizeof *list->values,
+ return binary_search (list->values, list->n, sizeof *list->values,
&value, compare_init_values, NULL) != NULL;
}
size_t n_vars = dict_get_n_vars (d);
assert (list != exclude);
- list->values = xnrealloc (list->values, list->cnt + dict_get_n_vars (d),
+ list->values = xnrealloc (list->values, list->n + dict_get_n_vars (d),
sizeof *list->values);
for (size_t i = 0; i < n_vars; i++)
{
if (exclude != NULL && init_list_includes (exclude, case_index))
continue;
- iv = &list->values[list->cnt++];
+ iv = &list->values[list->n++];
iv->case_index = case_index;
iv->width = var_get_width (v);
value_init (&iv->value, iv->width);
}
/* Drop duplicates. */
- list->cnt = sort_unique (list->values, list->cnt, sizeof *list->values,
- compare_init_values, NULL);
+ list->n = sort_unique (list->values, list->n, sizeof *list->values,
+ compare_init_values, NULL);
}
/* Initializes data in case C to the values in the initializer
{
const struct init_value *iv;
- for (iv = &list->values[0]; iv < &list->values[list->cnt]; iv++)
+ for (iv = &list->values[0]; iv < &list->values[list->n]; iv++)
value_copy (case_data_rw_idx (c, iv->case_index), &iv->value, iv->width);
}
{
struct init_value *iv;
- for (iv = &list->values[0]; iv < &list->values[list->cnt]; iv++)
+ for (iv = &list->values[0]; iv < &list->values[list->n]; iv++)
value_copy (&iv->value, case_data_idx (c, iv->case_index), iv->width);
}
\f
return proto;
}
-/* Returns a replacement for PROTO with CNT widths removed
+/* Returns a replacement for PROTO with N widths removed
starting at index IDX. */
struct caseproto *
-caseproto_remove_widths (struct caseproto *proto, size_t idx, size_t cnt)
+caseproto_remove_widths (struct caseproto *proto, size_t idx, size_t n)
{
- assert (caseproto_range_is_valid (proto, idx, cnt));
+ assert (caseproto_range_is_valid (proto, idx, n));
proto = caseproto_unshare (proto);
- proto->n_strings -= count_strings (proto, idx, cnt);
+ proto->n_strings -= count_strings (proto, idx, n);
remove_range (proto->widths, proto->n_widths, sizeof *proto->widths,
- idx, cnt);
- proto->n_widths -= cnt;
+ idx, n);
+ proto->n_widths -= n;
return proto;
}
-/* Returns a replacement for PROTO in which the CNT widths
+/* Returns a replacement for PROTO in which the N widths
starting at index OLD_WIDTH now start at index NEW_WIDTH, with
other widths shifting out of the way to make room. */
struct caseproto *
caseproto_move_widths (struct caseproto *proto,
size_t old_start, size_t new_start,
- size_t cnt)
+ size_t n)
{
- assert (caseproto_range_is_valid (proto, old_start, cnt));
- assert (caseproto_range_is_valid (proto, new_start, cnt));
+ assert (caseproto_range_is_valid (proto, old_start, n));
+ assert (caseproto_range_is_valid (proto, new_start, n));
proto = caseproto_unshare (proto);
move_range (proto->widths, proto->n_widths, sizeof *proto->widths,
- old_start, new_start, cnt);
+ old_start, new_start, n);
return proto;
}
size_t before, int width)
WARN_UNUSED_RESULT;
struct caseproto *caseproto_remove_widths (struct caseproto *,
- size_t idx, size_t cnt)
+ size_t idx, size_t n)
WARN_UNUSED_RESULT;
struct caseproto *caseproto_move_widths (struct caseproto *,
size_t old_start, size_t new_start,
- size_t cnt)
+ size_t n)
WARN_UNUSED_RESULT;
/* Working with "union value" arrays. */
/* Mandatory.
- A call to this function tells the callee that the CNT
+ A call to this function tells the callee that the N
cases at the beginning of READER will never be read again.
The casereader implementation should free any resources
associated with those cases. After this function returns,
the IDX argument in future calls to the "read" function
will be relative to remaining cases. */
- void (*advance) (struct casereader *reader, void *aux, casenumber cnt);
+ void (*advance) (struct casereader *reader, void *aux, casenumber n);
};
struct casereader *
free (s);
}
-/* Discards CNT cases from the front of S's window. */
+/* Discards N_CASES cases from the front of S's window. */
static void
casereader_shim_advance (struct casereader *reader UNUSED, void *s_,
casenumber n_cases)
static void
casereader_stateless_translator_advance (struct casereader *reader UNUSED,
- void *cst_, casenumber cnt)
+ void *cst_, casenumber n)
{
struct casereader_stateless_translator *cst = cst_;
- cst->case_offset += casereader_advance (cst->subreader, cnt);
+ cst->case_offset += casereader_advance (cst->subreader, n);
}
/* Casereader class for stateless translating casereader. */
void *(*create) (struct taint *, const struct caseproto *);
void (*destroy) (void *aux);
void (*push_head) (void *aux, struct ccase *);
- void (*pop_tail) (void *aux, casenumber cnt);
+ void (*pop_tail) (void *aux, casenumber n);
struct ccase *(*get_case) (void *aux, casenumber ofs);
casenumber (*get_n_cases) (const void *aux);
};
case_unref (c);
}
-/* Deletes CASE_CNT cases at the tail of casewindow CW. */
+/* Deletes N_CASES cases at the tail of casewindow CW. */
void
casewindow_pop_tail (struct casewindow *cw, casenumber n_cases)
{
}
static void
-casewindow_file_pop_tail (void *cwf_, casenumber cnt)
+casewindow_file_pop_tail (void *cwf_, casenumber n)
{
struct casewindow_file *cwf = cwf_;
- assert (cnt <= cwf->head - cwf->tail);
- cwf->tail += cnt;
+ assert (n <= cwf->head - cwf->tail);
+ cwf->tail += n;
if (cwf->head == cwf->tail)
cwf->head = cwf->tail = 0;
}
bool casewindow_destroy (struct casewindow *);
void casewindow_push_head (struct casewindow *, struct ccase *);
-void casewindow_pop_tail (struct casewindow *, casenumber cnt);
+void casewindow_pop_tail (struct casewindow *, casenumber n);
struct ccase *casewindow_get_case (const struct casewindow *,
casenumber case_idx);
const struct caseproto *casewindow_get_proto (const struct casewindow *);
static void axis_insert (struct axis *,
unsigned long int log_start,
unsigned long int phy_start,
- unsigned long int cnt);
+ unsigned long int n);
static void axis_remove (struct axis *,
- unsigned long int start, unsigned long int cnt);
+ unsigned long int start, unsigned long int n);
static void axis_move (struct axis *,
unsigned long int old_start,
unsigned long int new_start,
- unsigned long int cnt);
+ unsigned long int n);
static struct source *source_create_empty (size_t n_bytes);
static struct source *source_create_casereader (struct casereader *);
return rw_case (ds, OP_WRITE, row, column, 1, (union value *) value);
}
-/* Inserts the CNT cases at C into datasheet DS just before row
+/* Inserts the N cases at C into datasheet DS just before row
BEFORE. Returns true if successful, false on I/O error. On
failure, datasheet DS is not modified.
bool
datasheet_insert_rows (struct datasheet *ds,
casenumber before, struct ccase *c[],
- casenumber cnt)
+ casenumber n)
{
casenumber added = 0;
- while (cnt > 0)
+ while (n > 0)
{
unsigned long first_phy;
unsigned long n_phys;
/* Allocate physical rows from the pool of available
rows. */
- if (!axis_allocate (ds->rows, cnt, &first_phy, &n_phys))
+ if (!axis_allocate (ds->rows, n, &first_phy, &n_phys))
{
/* No rows were available. Extend the row axis to make
some new ones available. */
- n_phys = cnt;
- first_phy = axis_extend (ds->rows, cnt);
+ n_phys = n;
+ first_phy = axis_extend (ds->rows, n);
}
/* Insert the new rows into the row mapping. */
for (i = 0; i < n_phys; i++)
if (!datasheet_put_row (ds, before + i, c[i]))
{
- while (++i < cnt)
+ while (++i < n)
case_unref (c[i]);
datasheet_delete_rows (ds, before - added, n_phys + added);
return false;
/* Advance. */
c += n_phys;
- cnt -= n_phys;
+ n -= n_phys;
before += n_phys;
added += n_phys;
}
return true;
}
-/* Deletes the CNT rows in DS starting from row FIRST. */
+/* Deletes the N rows in DS starting from row FIRST. */
void
datasheet_delete_rows (struct datasheet *ds,
- casenumber first, casenumber cnt)
+ casenumber first, casenumber n)
{
size_t lrow;
/* Free up rows for reuse.
FIXME: optimize. */
- for (lrow = first; lrow < first + cnt; lrow++)
+ for (lrow = first; lrow < first + n; lrow++)
axis_make_available (ds->rows, axis_map (ds->rows, lrow), 1);
/* Remove rows from logical-to-physical mapping. */
- axis_remove (ds->rows, first, cnt);
+ axis_remove (ds->rows, first, n);
}
-/* Moves the CNT rows in DS starting at position OLD_START so
+/* Moves the N rows in DS starting at position OLD_START so
that they then start at position NEW_START. Equivalent to
deleting the given rows, then inserting them at what becomes
position NEW_START after the deletion. */
void
datasheet_move_rows (struct datasheet *ds,
size_t old_start, size_t new_start,
- size_t cnt)
+ size_t n)
{
- axis_move (ds->rows, old_start, new_start, cnt);
+ axis_move (ds->rows, old_start, new_start, n);
}
\f
static const struct casereader_random_class datasheet_reader_class;
return tower_height (&axis->log_to_phy);
}
-/* Inserts the CNT contiguous physical ordinates starting at
+/* Inserts the N contiguous physical ordinates starting at
PHY_START into AXIS's logical-to-physical mapping, starting at
logical position LOG_START. */
static void
axis_insert (struct axis *axis,
unsigned long int log_start, unsigned long int phy_start,
- unsigned long int cnt)
+ unsigned long int n)
{
struct tower_node *before = split_axis (axis, log_start);
struct tower_node *new = make_axis_group (phy_start);
- tower_insert (&axis->log_to_phy, cnt, new, before);
+ tower_insert (&axis->log_to_phy, n, new, before);
merge_axis_nodes (axis, new, NULL);
check_axis_merged (axis);
}
-/* Removes CNT ordinates from AXIS's logical-to-physical mapping
+/* Removes N ordinates from AXIS's logical-to-physical mapping
starting at logical position START. */
static void
axis_remove (struct axis *axis,
- unsigned long int start, unsigned long int cnt)
+ unsigned long int start, unsigned long int n)
{
- if (cnt > 0)
+ if (n > 0)
{
- struct tower_node *last = split_axis (axis, start + cnt);
+ struct tower_node *last = split_axis (axis, start + n);
struct tower_node *cur, *next;
for (cur = split_axis (axis, start); cur != last; cur = next)
{
}
}
-/* Moves the CNT ordinates in AXIS's logical-to-mapping starting
+/* Moves the N ordinates in AXIS's logical-to-mapping starting
at logical position OLD_START so that they then start at
position NEW_START. */
static void
axis_move (struct axis *axis,
unsigned long int old_start, unsigned long int new_start,
- unsigned long int cnt)
+ unsigned long int n)
{
- if (cnt > 0 && old_start != new_start)
+ if (n > 0 && old_start != new_start)
{
struct tower_node *old_first, *old_last, *new_first;
struct tower_node *merge1, *merge2;
struct tower tmp_array;
- /* Move ordinates OLD_START...(OLD_START + CNT) into new,
+ /* Move ordinates OLD_START...(OLD_START + N) into new,
separate TMP_ARRAY. */
old_first = split_axis (axis, old_start);
- old_last = split_axis (axis, old_start + cnt);
+ old_last = split_axis (axis, old_start + n);
tower_init (&tmp_array);
tower_splice (&tmp_array, NULL,
&axis->log_to_phy, old_first, old_last);
return true;
}
-/* Within SOURCE, which must not have a backing casereader,
- writes the VALUE_CNT values in VALUES_CNT to the VALUE_CNT
- columns starting from START_COLUMN, in every row, even in rows
- not yet otherwise initialized. Returns true if successful,
- false if an I/O error occurs.
-
- We don't support backing != NULL because (1) it's harder and
- (2) this function is only called by
- datasheet_insert_column, which doesn't reuse columns from
- sources that are backed by casereaders. */
static bool
source_write_column (struct column *column, const union value *value)
{
size_t datasheet_get_n_columns (const struct datasheet *);
bool datasheet_insert_column (struct datasheet *,
const union value *, int width, size_t before);
-void datasheet_delete_columns (struct datasheet *, size_t start, size_t cnt);
+void datasheet_delete_columns (struct datasheet *, size_t start, size_t n);
void datasheet_move_columns (struct datasheet *,
size_t old_start, size_t new_start,
- size_t cnt);
+ size_t n);
bool datasheet_resize_column (struct datasheet *, size_t column, int new_width,
void (*resize_cb) (const union value *,
union value *, const void *aux),
casenumber datasheet_get_n_rows (const struct datasheet *);
bool datasheet_insert_rows (struct datasheet *,
casenumber before, struct ccase *[],
- casenumber cnt);
+ casenumber n);
void datasheet_delete_rows (struct datasheet *,
- casenumber first, casenumber cnt);
+ casenumber first, casenumber n);
void datasheet_move_rows (struct datasheet *,
size_t old_start, size_t new_start,
- size_t cnt);
+ size_t n);
/* Data. */
struct ccase *datasheet_get_row (const struct datasheet *, casenumber);
: empty_string);
}
-absorb_miss string function SUBSTR (string s, integer ofs, integer cnt)
+absorb_miss string function SUBSTR (string s, integer ofs, integer len)
{
- return (ofs >= 1 && cnt >= 1
- ? ss_substr (s, ofs - 1, cnt)
+ return (ofs >= 1 && len >= 1
+ ? ss_substr (s, ofs - 1, len)
: empty_string);
}
/* Parses a set of variables from dictionary D given options
OPTS. Resulting list of variables stored in *VAR and the
- number of variables into *CNT. Returns true only if
+ number of variables into *N. Returns true only if
successful. The dictionary D must contain at least one
variable. */
bool
parse_variables (struct lexer *lexer, const struct dictionary *d,
- struct variable ***var,
- size_t *cnt, int opts)
+ struct variable ***var,
+ size_t *n, int opts)
{
struct var_set *vs;
int success;
assert (d != NULL);
assert (var != NULL);
- assert (cnt != NULL);
+ assert (n != NULL);
vs = var_set_create_from_dict (d);
if (var_set_get_n (vs) == 0)
{
- *cnt = 0;
+ *n = 0;
var_set_destroy (vs);
return false;
}
- success = parse_var_set_vars (lexer, vs, var, cnt, opts);
+ success = parse_var_set_vars (lexer, vs, var, n, opts);
var_set_destroy (vs);
return success;
}
char *parse_DATA_LIST_var (struct lexer *, const struct dictionary *);
bool parse_DATA_LIST_vars (struct lexer *, const struct dictionary *,
- char ***names, size_t *cnt, int opts);
+ char ***names, size_t *n, int opts);
bool parse_DATA_LIST_vars_pool (struct lexer *, const struct dictionary *,
struct pool *,
- char ***names, size_t *cnt, int opts);
+ char ***names, size_t *n, int opts);
bool parse_mixed_vars (struct lexer *, const struct dictionary *dict,
- char ***names, size_t *cnt, int opts);
+ char ***names, size_t *n, int opts);
bool parse_mixed_vars_pool (struct lexer *, const struct dictionary *dict,
struct pool *,
- char ***names, size_t *cnt, int opts);
+ char ***names, size_t *n, int opts);
\f
/* This variable parser supports the unusual situation where set of variables
has to be parsed before the associated dictionary is available. Thus,
setup_z_trns (struct dsc_proc *dsc, struct dataset *ds)
{
struct dsc_trns *t;
- size_t cnt, i;
+ size_t n, i;
- for (cnt = i = 0; i < dsc->n_vars; i++)
+ for (n = i = 0; i < dsc->n_vars; i++)
if (dsc->vars[i].z_name != NULL)
- cnt++;
+ n++;
t = xmalloc (sizeof *t);
- t->z_scores = xnmalloc (cnt, sizeof *t->z_scores);
- t->n_z_scores = cnt;
+ t->z_scores = xnmalloc (n, sizeof *t->z_scores);
+ t->n_z_scores = n;
t->missing_type = dsc->missing_type;
t->exclude = dsc->exclude;
if (t->missing_type == DSC_LISTWISE)
t->ok = true;
dsc->z_writer = NULL;
- for (cnt = i = 0; i < dsc->n_vars; i++)
+ for (n = i = 0; i < dsc->n_vars; i++)
{
struct dsc_var *dv = &dsc->vars[i];
if (dv->z_name != NULL)
var_set_label (dst_var, label);
free (label);
- z = &t->z_scores[cnt++];
+ z = &t->z_scores[n++];
z->src_var = dv->v;
z->z_var = dst_var;
}
#define _(msgid) gettext (msgid)
static bool
-read_values (struct lexer *lexer, double **values, double **weights, size_t *cnt)
+read_values (struct lexer *lexer, double **values, double **weights, size_t *n)
{
size_t cap = 0;
*values = NULL;
*weights = NULL;
- *cnt = 0;
+ *n = 0;
while (lex_is_number (lexer))
{
double value = lex_tokval (lexer);
lex_get (lexer);
}
- if (*cnt >= cap)
+ if (*n >= cap)
{
cap = 2 * (cap + 8);
*values = xnrealloc (*values, cap, sizeof **values);
*weights = xnrealloc (*weights, cap, sizeof **weights);
}
- (*values)[*cnt] = value;
- (*weights)[*cnt] = weight;
- (*cnt)++;
+ (*values)[*n] = value;
+ (*weights)[*n] = weight;
+ (*n)++;
}
return true;
double *weights = NULL;
double weight, M[4];
int two_pass = 1;
- size_t cnt;
+ size_t n;
size_t i;
if (lex_match_id (lexer, "ONEPASS"))
struct moments *m = NULL;
m = moments_create (MOMENT_KURTOSIS);
- if (!read_values (lexer, &values, &weights, &cnt))
+ if (!read_values (lexer, &values, &weights, &n))
{
moments_destroy (m);
goto done;
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
moments_pass_one (m, values[i], weights[i]);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
moments_pass_two (m, values[i], weights[i]);
moments_calculate (m, &weight, &M[0], &M[1], &M[2], &M[3]);
moments_destroy (m);
struct moments1 *m = NULL;
m = moments1_create (MOMENT_KURTOSIS);
- if (!read_values (lexer, &values, &weights, &cnt))
+ if (!read_values (lexer, &values, &weights, &n))
{
moments1_destroy (m);
goto done;
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
moments1_add (m, values[i], weights[i]);
moments1_calculate (m, &weight, &M[0], &M[1], &M[2], &M[3]);
moments1_destroy (m);
return x;
}
\f
-/* Returns CNT bits in X starting from the given bit OFS. */
+/* Returns N bits in X starting from the given bit OFS. */
static inline uint64_t
-get_bits (uint64_t x, int ofs, int cnt)
+get_bits (uint64_t x, int ofs, int n)
{
assert (ofs >= 0 && ofs < 64);
- assert (cnt > 0 && cnt < 64);
- assert (ofs + cnt <= 64);
- return (x >> ofs) & ((UINT64_C(1) << cnt) - 1);
+ assert (n > 0 && n < 64);
+ assert (ofs + n <= 64);
+ return (x >> ofs) & ((UINT64_C(1) << n) - 1);
}
/* Returns NATIVE converted to a form that, when stored in
const void *aux;
/* Contents. */
- struct heap_node **nodes; /* Element 0 unused, 1...CNT are the heap. */
- size_t cnt; /* Number of elements in heap. */
- size_t cap; /* Max CNT without allocating more memory. */
+ struct heap_node **nodes; /* Element 0 unused, 1...N are the heap. */
+ size_t n; /* Number of elements in heap. */
+ size_t allocated; /* Max N without allocating more memory. */
};
static inline void set_node (struct heap *, size_t idx, struct heap_node *);
h->compare = compare;
h->aux = aux;
h->nodes = NULL;
- h->cap = 0;
- h->cnt = 0;
+ h->allocated = 0;
+ h->n = 0;
return h;
}
bool
heap_is_empty (const struct heap *h)
{
- return h->cnt == 0;
+ return h->n == 0;
}
/* Returns the number of elements in H. */
size_t
heap_count (const struct heap *h)
{
- return h->cnt;
+ return h->n;
}
/* Heap nodes may be moved around in memory as necessary, e.g. as
void
heap_moved (struct heap *h, struct heap_node *node)
{
- assert (node->idx <= h->cnt);
+ assert (node->idx <= h->n);
h->nodes[node->idx] = node;
}
void
heap_insert (struct heap *h, struct heap_node *node)
{
- if (h->cnt >= h->cap)
+ if (h->n >= h->allocated)
{
- h->cap = 2 * (h->cap + 8);
- h->nodes = xnrealloc (h->nodes, h->cap + 1, sizeof *h->nodes);
+ h->allocated = 2 * (h->allocated + 8);
+ h->nodes = xnrealloc (h->nodes, h->allocated + 1, sizeof *h->nodes);
}
- h->cnt++;
- set_node (h, h->cnt, node);
- propagate_up (h, h->cnt);
+ h->n++;
+ set_node (h, h->n, node);
+ propagate_up (h, h->n);
expensive_assert (is_heap (h));
}
void
heap_delete (struct heap *h, struct heap_node *node)
{
- assert (node->idx <= h->cnt);
+ assert (node->idx <= h->n);
assert (h->nodes[node->idx] == node);
- if (node->idx < h->cnt)
+ if (node->idx < h->n)
{
- set_node (h, node->idx, h->nodes[h->cnt--]);
+ set_node (h, node->idx, h->nodes[h->n--]);
heap_changed (h, h->nodes[node->idx]);
}
else
- h->cnt--;
+ h->n--;
}
/* After client code changes the value represented by a heap
void
heap_changed (struct heap *h, struct heap_node *node)
{
- assert (node->idx <= h->cnt);
+ assert (node->idx <= h->n);
assert (h->nodes[node->idx] == node);
if (!propagate_up (h, node->idx))
static size_t
lesser_node (const struct heap *h, size_t a, size_t b)
{
- assert (a <= h->cnt);
- return b > h->cnt || less (h, a, b) ? a : b;
+ assert (a <= h->n);
+ return b > h->n || less (h, a, b) ? a : b;
}
/* Swaps, in H, the nodes with indexes A and B. */
{
struct heap_node *t;
- assert (a <= h->cnt);
- assert (b <= h->cnt);
+ assert (a <= h->n);
+ assert (b <= h->n);
t = h->nodes[a];
set_node (h, a, h->nodes[b]);
{
size_t i;
- for (i = 2; i <= h->cnt; i++)
+ for (i = 2; i <= h->n; i++)
if (less (h, i, i / 2))
return false;
- for (i = 1; i <= h->cnt; i++)
+ for (i = 1; i <= h->n; i++)
if (h->nodes[i]->idx != i)
return false;
|| format == INTEGER_VAX);
}
-/* Converts the CNT bytes in INTEGER from SRC integer_format to DST
+/* Converts the N bytes in INTEGER from SRC integer_format to DST
integer_format. */
void
integer_convert (enum integer_format src, const void *from,
enum integer_format dst, void *to,
- size_t cnt)
+ size_t n)
{
if (src != dst)
- integer_put (integer_get (src, from, cnt), dst, to, cnt);
+ integer_put (integer_get (src, from, n), dst, to, n);
else if (from != to)
- memcpy (to, from, cnt);
+ memcpy (to, from, n);
}
-/* Returns the value of the CNT-byte integer at FROM, which is in
+/* Returns the value of the N-byte integer at FROM, which is in
the given FORMAT. */
uint64_t
-integer_get (enum integer_format format, const void *from_, size_t cnt)
+integer_get (enum integer_format format, const void *from_, size_t n)
{
const uint8_t *from = from_;
uint64_t value = 0;
size_t i;
assert (is_integer_format (format));
- assert (cnt <= 8);
+ assert (n <= 8);
switch (format)
{
case INTEGER_MSB_FIRST:
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
value = (value << 8) | from[i];
break;
case INTEGER_LSB_FIRST:
- for (i = 0; i < cnt; i++)
- value = (value << 8) | from[cnt - i - 1];
+ for (i = 0; i < n; i++)
+ value = (value << 8) | from[n - i - 1];
break;
case INTEGER_VAX:
- for (i = 0; i < (cnt & ~1); i++)
+ for (i = 0; i < (n & ~1); i++)
value = (value << 8) | from[i ^ 1];
- if (cnt & 1)
- value = (value << 8) | from[cnt - 1];
+ if (n & 1)
+ value = (value << 8) | from[n - 1];
break;
}
return value;
}
-/* Stores VALUE as a CNT-byte integer at TO, in the given
+/* Stores VALUE as a N-byte integer at TO, in the given
FORMAT. */
void
-integer_put (uint64_t value, enum integer_format format, void *to_, size_t cnt)
+integer_put (uint64_t value, enum integer_format format, void *to_, size_t n)
{
uint8_t *to = to_;
size_t i;
assert (is_integer_format (format));
- assert (cnt <= 8);
+ assert (n <= 8);
- value <<= 8 * (8 - cnt);
+ value <<= 8 * (8 - n);
switch (format)
{
case INTEGER_MSB_FIRST:
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
to[i] = value >> 56;
value <<= 8;
}
break;
case INTEGER_LSB_FIRST:
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- to[cnt - i - 1] = value >> 56;
+ to[n - i - 1] = value >> 56;
value <<= 8;
}
break;
case INTEGER_VAX:
- for (i = 0; i < (cnt & ~1); i++)
+ for (i = 0; i < (n & ~1); i++)
{
to[i ^ 1] = value >> 56;
value <<= 8;
}
- if (cnt & 1)
- to[cnt - 1] = value >> 56;
+ if (n & 1)
+ to[n - 1] = value >> 56;
break;
}
}
\f
/* Substrings. */
-/* Returns a substring whose contents are the CNT bytes
+/* Returns a substring whose contents are the N bytes
starting at the (0-based) position START in SS. */
struct substring
-ss_substr (struct substring ss, size_t start, size_t cnt)
+ss_substr (struct substring ss, size_t start, size_t n)
{
if (start < ss.length)
- return ss_buffer (ss.string + start, MIN (cnt, ss.length - start));
+ return ss_buffer (ss.string + start, MIN (n, ss.length - start));
else
return ss_buffer (ss.string + ss.length, 0);
}
-/* Returns a substring whose contents are the first CNT
+/* Returns a substring whose contents are the first N
bytes in SS. */
struct substring
-ss_head (struct substring ss, size_t cnt)
+ss_head (struct substring ss, size_t n)
{
- return ss_buffer (ss.string, MIN (cnt, ss.length));
+ return ss_buffer (ss.string, MIN (n, ss.length));
}
-/* Returns a substring whose contents are the last CNT bytes
+/* Returns a substring whose contents are the last N bytes
in SS. */
struct substring
-ss_tail (struct substring ss, size_t cnt)
+ss_tail (struct substring ss, size_t n)
{
- if (cnt < ss.length)
- return ss_buffer (ss.string + (ss.length - cnt), cnt);
+ if (n < ss.length)
+ return ss_buffer (ss.string + (ss.length - n), n);
else
return ss;
}
new->length = old.length;
}
-/* Allocates room for a CNT-byte string in NEW. */
+/* Allocates room for a N-byte string in NEW. */
void
-ss_alloc_uninit (struct substring *new, size_t cnt)
+ss_alloc_uninit (struct substring *new, size_t n)
{
- new->string = xmalloc (cnt);
- new->length = cnt;
+ new->string = xmalloc (n);
+ new->length = n;
}
void
new->string[old.length] = '\0';
}
-/* Allocates room for a CNT-byte string in NEW in POOL. */
+/* Allocates room for a N-byte string in NEW in POOL. */
void
-ss_alloc_uninit_pool (struct substring *new, size_t cnt, struct pool *pool)
+ss_alloc_uninit_pool (struct substring *new, size_t n, struct pool *pool)
{
- new->string = pool_alloc_unaligned (pool, cnt);
- new->length = cnt;
+ new->string = pool_alloc_unaligned (pool, n);
+ new->length = n;
}
/* Frees the string that SS points to. */
*b = tmp;
}
-/* Truncates SS to at most CNT bytes in length. */
+/* Truncates SS to at most N bytes in length. */
void
-ss_truncate (struct substring *ss, size_t cnt)
+ss_truncate (struct substring *ss, size_t n)
{
- if (ss->length > cnt)
- ss->length = cnt;
+ if (ss->length > n)
+ ss->length = n;
}
/* Removes trailing bytes in TRIM_SET from SS.
size_t
ss_rtrim (struct substring *ss, struct substring trim_set)
{
- size_t cnt = 0;
- while (cnt < ss->length
+ size_t n = 0;
+ while (n < ss->length
&& ss_find_byte (trim_set,
- ss->string[ss->length - cnt - 1]) != SIZE_MAX)
- cnt++;
- ss->length -= cnt;
- return cnt;
+ ss->string[ss->length - n - 1]) != SIZE_MAX)
+ n++;
+ ss->length -= n;
+ return n;
}
/* Removes leading bytes in TRIM_SET from SS.
size_t
ss_ltrim (struct substring *ss, struct substring trim_set)
{
- size_t cnt = ss_span (*ss, trim_set);
- ss_advance (ss, cnt);
- return cnt;
+ size_t n = ss_span (*ss, trim_set);
+ ss_advance (ss, n);
+ return n;
}
/* Trims leading and trailing bytes in TRIM_SET from SS. */
return found_token;
}
-/* Removes the first CNT bytes from SS. */
+/* Removes the first N bytes from SS. */
void
-ss_advance (struct substring *ss, size_t cnt)
+ss_advance (struct substring *ss, size_t n)
{
- if (cnt > ss->length)
- cnt = ss->length;
- ss->string += cnt;
- ss->length -= cnt;
+ if (n > ss->length)
+ n = ss->length;
+ ss->string += n;
+ ss->length -= n;
}
/* If the first byte in SS is C, removes it and returns true.
return ss_match_byte (ss, delimiter);
}
-/* Stores the first CNT bytes in SS in OUT (or fewer, if SS
- is shorter than CNT bytes). Trims the same bytes
- from the beginning of SS. Returns CNT. */
+/* Stores the first N bytes in SS in OUT (or fewer, if SS
+ is shorter than N bytes). Trims the same bytes
+ from the beginning of SS. Returns N. */
size_t
-ss_get_bytes (struct substring *ss, size_t cnt, struct substring *out)
+ss_get_bytes (struct substring *ss, size_t n, struct substring *out)
{
- *out = ss_head (*ss, cnt);
- ss_advance (ss, cnt);
- return cnt;
+ *out = ss_head (*ss, n);
+ ss_advance (ss, n);
+ return n;
}
/* Parses and removes an optionally signed decimal integer from
return st->ss;
}
-/* Returns a substring that contains CNT bytes from ST
+/* Returns a substring that contains N bytes from ST
starting at position START.
If START is greater than or equal to the length of ST, then
- the substring will be the empty string. If START + CNT
+ the substring will be the empty string. If START + N
exceeds the length of ST, then the substring will only be
ds_length(ST) - START bytes long. */
struct substring
-ds_substr (const struct string *st, size_t start, size_t cnt)
+ds_substr (const struct string *st, size_t start, size_t n)
{
- return ss_substr (ds_ss (st), start, cnt);
+ return ss_substr (ds_ss (st), start, n);
}
-/* Returns a substring that contains the first CNT bytes in
- ST. If CNT exceeds the length of ST, then the substring will
+/* Returns a substring that contains the first N bytes in
+ ST. If N exceeds the length of ST, then the substring will
contain all of ST. */
struct substring
-ds_head (const struct string *st, size_t cnt)
+ds_head (const struct string *st, size_t n)
{
- return ss_head (ds_ss (st), cnt);
+ return ss_head (ds_ss (st), n);
}
-/* Returns a substring that contains the last CNT bytes in
- ST. If CNT exceeds the length of ST, then the substring will
+/* Returns a substring that contains the last N bytes in
+ ST. If N exceeds the length of ST, then the substring will
contain all of ST. */
struct substring
-ds_tail (const struct string *st, size_t cnt)
+ds_tail (const struct string *st, size_t n)
{
- return ss_tail (ds_ss (st), cnt);
+ return ss_tail (ds_ss (st), n);
}
/* Ensures that ST can hold at least MIN_CAPACITY bytes plus a null
size_t
ds_ltrim (struct string *st, struct substring trim_set)
{
- size_t cnt = ds_span (st, trim_set);
- if (cnt > 0)
- ds_assign_substring (st, ds_substr (st, cnt, SIZE_MAX));
- return cnt;
+ size_t n = ds_span (st, trim_set);
+ if (n > 0)
+ ds_assign_substring (st, ds_substr (st, n, SIZE_MAX));
+ return n;
}
/* Trims leading and trailing bytes in TRIM_SET from ST.
size_t
ds_trim (struct string *st, struct substring trim_set)
{
- size_t cnt = ds_rtrim (st, trim_set);
- return cnt + ds_ltrim (st, trim_set);
+ size_t n = ds_rtrim (st, trim_set);
+ return n + ds_ltrim (st, trim_set);
}
/* If the last byte in ST is C, removes it and returns true.
return true;
}
-/* Attempts to read SIZE * CNT bytes from STREAM and append them
+/* Attempts to read SIZE * N bytes from STREAM and append them
to ST.
Returns true if all the requested data was read, false otherwise. */
bool
-ds_read_stream (struct string *st, size_t size, size_t cnt, FILE *stream)
+ds_read_stream (struct string *st, size_t size, size_t n, FILE *stream)
{
if (size != 0)
{
- size_t try_bytes = xtimes (cnt, size);
+ size_t try_bytes = xtimes (n, size);
if (size_in_bounds_p (xsum (ds_length (st), try_bytes)))
{
char *buffer = ds_put_uninit (st, try_bytes);
ds_put_uninit (st, 1)[0] = ch;
}
-/* Appends CNT copies of byte CH to ST. */
+/* Appends N copies of byte CH to ST. */
void
-ds_put_byte_multiple (struct string *st, int ch, size_t cnt)
+ds_put_byte_multiple (struct string *st, int ch, size_t n)
{
- memset (ds_put_uninit (st, cnt), ch, cnt);
+ memset (ds_put_uninit (st, n), ch, n);
}
/* Appends Unicode code point UC to ST in UTF-8 encoding. */
int ss_match_byte_in (struct substring *, struct substring);
bool ss_match_string (struct substring *, const struct substring);
int ss_get_byte (struct substring *);
-size_t ss_get_bytes (struct substring *, size_t cnt, struct substring *);
+size_t ss_get_bytes (struct substring *, size_t n, struct substring *);
bool ss_get_until (struct substring *, char delimiter, struct substring *);
size_t ss_get_long (struct substring *, long *);
/* File input. */
bool ds_read_line (struct string *, FILE *, size_t max_length);
bool ds_read_config_line (struct string *, int *line_number, FILE *);
-bool ds_read_stream (struct string *, size_t size, size_t cnt, FILE *stream);
+bool ds_read_stream (struct string *, size_t size, size_t n, FILE *stream);
/* Append. */
void ds_put_byte (struct string *, int ch);
return ss_buffer (cstr, strlen (cstr));
}
-/* Returns a substring whose contents are the CNT characters in
+/* Returns a substring whose contents are the N characters in
BUFFER. */
static inline struct substring
-ss_buffer (const char *buffer, size_t cnt)
+ss_buffer (const char *buffer, size_t n)
{
struct substring ss;
ss.string = (char *) buffer;
- ss.length = cnt;
+ ss.length = n;
return ss;
}
/* A list of pointers to taint structures. */
struct taint_list
{
- size_t cnt;
+ size_t n;
struct taint **taints;
};
{
size_t i, j;
- for (i = 0; i < taint->predecessors.cnt; i++)
- for (j = 0; j < taint->successors.cnt; j++)
+ for (i = 0; i < taint->predecessors.n; i++)
+ for (j = 0; j < taint->successors.n; j++)
taint_propagate (taint->predecessors.taints[i],
taint->successors.taints[j]);
- for (i = 0; i < taint->predecessors.cnt; i++)
+ for (i = 0; i < taint->predecessors.n; i++)
taint_list_remove (&taint->predecessors.taints[i]->successors, taint);
- for (i = 0; i < taint->successors.cnt; i++)
+ for (i = 0; i < taint->successors.n; i++)
taint_list_remove (&taint->successors.taints[i]->predecessors, taint);
taint_list_destroy (&taint->successors);
{
size_t i;
- for (i = 0; i < taint->successors.cnt; i++)
+ for (i = 0; i < taint->successors.n; i++)
if (taint->successors.taints[i]->tainted_successor)
return;
static void
taint_list_init (struct taint_list *list)
{
- list->cnt = 0;
+ list->n = 0;
list->taints = NULL;
}
{
size_t i;
- for (i = 0; i < list->cnt; i++)
+ for (i = 0; i < list->n; i++)
if (list->taints[i] == taint)
return true;
list capacity is always zero or a power of 2. Thus, if
the list count is one of these threshold values, we need
to allocate more memory. */
- if (is_zero_or_power_of_2 (list->cnt))
+ if (is_zero_or_power_of_2 (list->n))
list->taints = xnrealloc (list->taints,
- list->cnt == 0 ? 1 : 2 * list->cnt,
+ list->n == 0 ? 1 : 2 * list->n,
sizeof *list->taints);
- list->taints[list->cnt++] = taint;
+ list->taints[list->n++] = taint;
}
}
{
size_t i;
- for (i = 0; i < list->cnt; i++)
+ for (i = 0; i < list->n; i++)
if (list->taints[i] == taint)
{
- remove_element (list->taints, list->cnt, sizeof *list->taints, i);
- list->cnt--;
+ remove_element (list->taints, list->n, sizeof *list->taints, i);
+ list->n--;
return;
}
size_t i;
taint->tainted = taint->tainted_successor = true;
- for (i = 0; i < taint->successors.cnt; i++)
+ for (i = 0; i < taint->successors.n; i++)
{
struct taint *s = taint->successors.taints[i];
if (!s->tainted)
recursively_set_taint (s);
}
- for (i = 0; i < taint->predecessors.cnt; i++)
+ for (i = 0; i < taint->predecessors.n; i++)
{
struct taint *p = taint->predecessors.taints[i];
if (!p->tainted_successor)
size_t i;
taint->tainted_successor = true;
- for (i = 0; i < taint->predecessors.cnt; i++)
+ for (i = 0; i < taint->predecessors.n; i++)
{
struct taint *p = taint->predecessors.taints[i];
if (!p->tainted_successor)
free (m);
}
-/* Calculates the requested moments on the CNT values in ARRAY.
+/* Calculates the requested moments on the N values in ARRAY.
Each value is given a weight of 1. The total weight is stored
into *WEIGHT (trivially) and the mean, variance, skewness, and
kurtosis are stored into *MEAN, *VARIANCE, *SKEWNESS, and
*KURTOSIS, respectively. Any of the result pointers may be
null, in which case no value is stored. */
void
-moments_of_doubles (const double *array, size_t cnt,
+moments_of_doubles (const double *array, size_t n,
double *weight,
double *mean, double *variance,
double *skewness, double *kurtosis)
max_moment = MOMENT_MEAN;
init_moments (&m, max_moment);
- for (idx = 0; idx < cnt; idx++)
+ for (idx = 0; idx < n; idx++)
moments_pass_one (&m, array[idx], 1.);
- for (idx = 0; idx < cnt; idx++)
+ for (idx = 0; idx < n; idx++)
moments_pass_two (&m, array[idx], 1.);
moments_calculate (&m, weight, mean, variance, skewness, kurtosis);
}
-/* Calculates the requested moments on the CNT numeric values in
+/* Calculates the requested moments on the N numeric values in
ARRAY. Each value is given a weight of 1. The total weight
is stored into *WEIGHT (trivially) and the mean, variance,
skewness, and kurtosis are stored into *MEAN, *VARIANCE,
*SKEWNESS, and *KURTOSIS, respectively. Any of the result
pointers may be null, in which case no value is stored. */
void
-moments_of_values (const union value *array, size_t cnt,
+moments_of_values (const union value *array, size_t n,
double *weight,
double *mean, double *variance,
double *skewness, double *kurtosis)
max_moment = MOMENT_MEAN;
init_moments (&m, max_moment);
- for (idx = 0; idx < cnt; idx++)
+ for (idx = 0; idx < n; idx++)
moments_pass_one (&m, array[idx].f, 1.);
- for (idx = 0; idx < cnt; idx++)
+ for (idx = 0; idx < n; idx++)
moments_pass_two (&m, array[idx].f, 1.);
moments_calculate (&m, weight, mean, variance, skewness, kurtosis);
}
void moments_destroy (struct moments *);
/* Convenience functions for two-pass moments. */
-void moments_of_doubles (const double *array, size_t cnt,
+void moments_of_doubles (const double *array, size_t n,
double *weight,
double *mean, double *variance,
double *skewness, double *kurtosis);
-void moments_of_values (const union value *array, size_t cnt,
+void moments_of_values (const union value *array, size_t n,
double *weight,
double *mean, double *variance,
double *skewness, double *kurtosis);
gboolean valid;
GtkTreeIter iter;
- struct hmap count_map[SEPARATOR_CNT];
- for (int j = 0; j < SEPARATOR_CNT; ++j)
+ struct hmap count_map[N_SEPARATORS];
+ for (int j = 0; j < N_SEPARATORS; ++j)
hmap_init (count_map + j);
GtkTreePath *p = gtk_tree_path_new_from_indices (first_line, -1);
gchar *line_text = NULL;
gtk_tree_model_get (GTK_TREE_MODEL (ia->text_file), &iter, 1, &line_text, -1);
- gint *counts = XCALLOC (SEPARATOR_CNT, gint);
+ gint *counts = XCALLOC (N_SEPARATORS, gint);
struct substring cs = ss_cstr (line_text);
for (;
ucs4_t character = ss_first_mb (cs);
int s;
- for (s = 0; s < SEPARATOR_CNT; ++s)
+ for (s = 0; s < N_SEPARATORS; ++s)
{
if (character == separators[s].c)
counts[s]++;
}
int j;
- for (j = 0; j < SEPARATOR_CNT; ++j)
+ for (j = 0; j < N_SEPARATORS; ++j)
{
if (counts[j] > 0)
{
{
int most_frequent = -1;
int largest = 0;
- for (int j = 0; j < SEPARATOR_CNT; ++j)
+ for (int j = 0; j < N_SEPARATORS; ++j)
{
struct separator_count_node *cn;
struct separator_count_node *next;
{
int i;
GSList *delimiters = NULL;
- for (i = 0; i < SEPARATOR_CNT; i++)
+ for (i = 0; i < N_SEPARATORS; i++)
{
const struct separator *s = &separators[i];
GtkWidget *button = get_widget_assert (ia->text_builder, s->name);
gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (ia->quote_cb), FALSE);
gtk_entry_set_text (GTK_ENTRY (ia->custom_entry), "");
- for (gint i = 0; i < SEPARATOR_CNT; i++)
+ for (gint i = 0; i < N_SEPARATORS; i++)
{
const struct separator *s = &separators[i];
GtkWidget *button = get_widget_assert (ia->text_builder, s->name);
G_CALLBACK (on_separators_custom_entry_notify), ia);
g_signal_connect (ia->custom_cb, "toggled",
G_CALLBACK (on_separators_custom_cb_toggle), ia);
- for (i = 0; i < SEPARATOR_CNT; i++)
+ for (i = 0; i < N_SEPARATORS; i++)
g_signal_connect (get_widget_assert (builder, separators[i].name),
"toggled", G_CALLBACK (on_separator_toggle), ia);
}
static void
-my_advance (struct casereader *reader, void *aux, casenumber cnt)
+my_advance (struct casereader *reader, void *aux, casenumber n)
{
g_print ("%s:%d\n", __FILE__, __LINE__);
}
if (gtk_toggle_button_get_active (GTK_TOGGLE_BUTTON (get_widget_assert (ia->text_builder, "tab"))))
ds_put_cstr (s, "\\t");
- for (i = 0; i < SEPARATOR_CNT; i++)
+ for (i = 0; i < N_SEPARATORS; i++)
{
const struct separator *seps = &separators[i];
GtkWidget *button = get_widget_assert (ia->text_builder, seps->name);
{"slash", '/'},
};
-#define SEPARATOR_CNT (sizeof separators / sizeof *separators)
+#define N_SEPARATORS (sizeof separators / sizeof *separators)
/* Initializes IA's intro substructure. */
void intro_page_create (PsppireImportAssistant *ia);
const struct caseproto *oproto = datasheet_get_proto (ods);
size_t n_columns = datasheet_get_n_columns (ods);
size_t n_rows = datasheet_get_n_rows (ods);
- size_t pos, new_pos, cnt, width_idx;
+ size_t pos, new_pos, n, width_idx;
extract_data (ods, odata);
/* Delete all possible numbers of columns from all possible
positions. */
for (pos = 0; pos < n_columns; pos++)
- for (cnt = 1; cnt < n_columns - pos; cnt++)
+ for (n = 1; n < n_columns - pos; n++)
if (mc_include_state (mc))
{
struct caseproto *proto;
mc_name_operation (mc, "delete %zu columns at %zu "
"(from %zu to %zu columns)",
- cnt, pos, n_columns, n_columns - cnt);
+ n, pos, n_columns, n_columns - n);
clone_model (ods, odata, &ds, data);
- datasheet_delete_columns (ds, pos, cnt);
- proto = caseproto_remove_widths (caseproto_ref (oproto), pos, cnt);
+ datasheet_delete_columns (ds, pos, n);
+ proto = caseproto_remove_widths (caseproto_ref (oproto), pos, n);
for (i = 0; i < n_rows; i++)
{
- for (j = pos; j < pos + cnt; j++)
+ for (j = pos; j < pos + n; j++)
value_destroy (&data[i][j], caseproto_get_width (oproto, j));
- remove_range (&data[i], n_columns, sizeof *data[i], pos, cnt);
+ remove_range (&data[i], n_columns, sizeof *data[i], pos, n);
}
check_datasheet (mc, ds, data, n_rows, proto);
/* Move all possible numbers of columns from all possible
existing positions to all possible new positions. */
for (pos = 0; pos < n_columns; pos++)
- for (cnt = 1; cnt < n_columns - pos; cnt++)
- for (new_pos = 0; new_pos < n_columns - cnt; new_pos++)
+ for (n = 1; n < n_columns - pos; n++)
+ for (new_pos = 0; new_pos < n_columns - n; new_pos++)
if (mc_include_state (mc))
{
struct caseproto *proto;
clone_model (ods, odata, &ds, data);
mc_name_operation (mc, "move %zu columns (of %zu) from %zu to %zu",
- cnt, n_columns, pos, new_pos);
+ n, n_columns, pos, new_pos);
- datasheet_move_columns (ds, pos, new_pos, cnt);
+ datasheet_move_columns (ds, pos, new_pos, n);
for (i = 0; i < n_rows; i++)
move_range (&data[i], n_columns, sizeof data[i][0],
- pos, new_pos, cnt);
+ pos, new_pos, n);
proto = caseproto_move_widths (caseproto_ref (oproto),
- pos, new_pos, cnt);
+ pos, new_pos, n);
check_datasheet (mc, ds, data, n_rows, proto);
release_data (n_rows, proto, data);
/* Insert all possible numbers of rows in all possible
positions. */
for (pos = 0; pos <= n_rows; pos++)
- for (cnt = 1; cnt <= params->max_rows - n_rows; cnt++)
+ for (n = 1; n <= params->max_rows - n_rows; n++)
if (mc_include_state (mc))
{
struct datasheet *ds;
clone_model (ods, odata, &ds, data);
mc_name_operation (mc, "insert %zu rows at %zu "
"(from %zu to %zu rows)",
- cnt, pos, n_rows, n_rows + cnt);
+ n, pos, n_rows, n_rows + n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
c[i] = case_create (oproto);
for (j = 0; j < n_columns; j++)
params->next_value++);
}
- insert_range (data, n_rows, sizeof data[pos], pos, cnt);
- for (i = 0; i < cnt; i++)
+ insert_range (data, n_rows, sizeof data[pos], pos, n);
+ for (i = 0; i < n; i++)
for (j = 0; j < n_columns; j++)
{
int width = caseproto_get_width (oproto, j);
value_copy (&data[i + pos][j], case_data_idx (c[i], j), width);
}
- if (!datasheet_insert_rows (ds, pos, c, cnt))
+ if (!datasheet_insert_rows (ds, pos, c, n))
mc_error (mc, "datasheet_insert_rows failed");
- check_datasheet (mc, ds, data, n_rows + cnt, oproto);
- release_data (n_rows + cnt, oproto, data);
+ check_datasheet (mc, ds, data, n_rows + n, oproto);
+ release_data (n_rows + n, oproto, data);
}
/* Delete all possible numbers of rows from all possible
positions. */
for (pos = 0; pos < n_rows; pos++)
- for (cnt = 1; cnt < n_rows - pos; cnt++)
+ for (n = 1; n < n_rows - pos; n++)
if (mc_include_state (mc))
{
struct datasheet *ds;
clone_model (ods, odata, &ds, data);
mc_name_operation (mc, "delete %zu rows at %zu "
"(from %zu to %zu rows)",
- cnt, pos, n_rows, n_rows - cnt);
+ n, pos, n_rows, n_rows - n);
- datasheet_delete_rows (ds, pos, cnt);
+ datasheet_delete_rows (ds, pos, n);
- release_data (cnt, oproto, &data[pos]);
- remove_range (&data[0], n_rows, sizeof data[0], pos, cnt);
+ release_data (n, oproto, &data[pos]);
+ remove_range (&data[0], n_rows, sizeof data[0], pos, n);
- check_datasheet (mc, ds, data, n_rows - cnt, oproto);
- release_data (n_rows - cnt, oproto, data);
+ check_datasheet (mc, ds, data, n_rows - n, oproto);
+ release_data (n_rows - n, oproto, data);
}
/* Move all possible numbers of rows from all possible existing
positions to all possible new positions. */
for (pos = 0; pos < n_rows; pos++)
- for (cnt = 1; cnt < n_rows - pos; cnt++)
- for (new_pos = 0; new_pos < n_rows - cnt; new_pos++)
+ for (n = 1; n < n_rows - pos; n++)
+ for (new_pos = 0; new_pos < n_rows - n; new_pos++)
if (mc_include_state (mc))
{
struct datasheet *ds;
clone_model (ods, odata, &ds, data);
mc_name_operation (mc, "move %zu rows (of %zu) from %zu to %zu",
- cnt, n_rows, pos, new_pos);
+ n, n_rows, pos, new_pos);
- datasheet_move_rows (ds, pos, new_pos, cnt);
+ datasheet_move_rows (ds, pos, new_pos, n);
move_range (&data[0], n_rows, sizeof data[0],
- pos, new_pos, cnt);
+ pos, new_pos, n);
check_datasheet (mc, ds, data, n_rows, oproto);
release_data (n_rows, oproto, data);
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
}
}
-/* Checks that ABT contains the CNT ints in DATA, that its
+/* Checks that ABT contains the N ints in DATA, that its
structure is correct, and that certain operations on ABT
produce the expected results. */
static void
-check_abt (struct abt *abt, const int data[], size_t cnt)
+check_abt (struct abt *abt, const int data[], size_t n)
{
struct element e;
size_t i;
int *order;
- order = xmemdup (data, cnt * sizeof *data);
- qsort (order, cnt, sizeof *order, compare_ints_noaux);
+ order = xmemdup (data, n * sizeof *data);
+ qsort (order, n, sizeof *order, compare_ints_noaux);
if (abt->compare != NULL)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
struct abt_node *p;
check_levels (abt->root);
check_augmentations (abt->root);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
check (find_by_position (abt, i)->data == order[i]);
- if (cnt == 0)
+ if (n == 0)
{
check (abt_first (abt) == NULL);
check (abt_last (abt) == NULL);
{
struct abt_node *p;
- for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
+ for (p = abt_first (abt), i = 0; i < n; p = abt_next (abt, p), i++)
check (abt_node_to_element (p)->data == order[i]);
check (p == NULL);
- for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
- check (abt_node_to_element (p)->data == order[cnt - i - 1]);
+ for (p = abt_last (abt), i = 0; i < n; p = abt_prev (abt, p), i++)
+ check (abt_node_to_element (p)->data == order[n - i - 1]);
check (p == NULL);
}
- check (abt_is_empty (abt) == (cnt == 0));
+ check (abt_is_empty (abt) == (n == 0));
free (order);
}
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an
ABT in the order specified by INSERTIONS using the given
METHOD, then deletes them in the order specified by DELETIONS,
checking the ABT's contents for correctness after each
do_test_insert_delete (enum insertion_method method,
const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct element *elements;
struct abt abt;
size_t i;
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
elements[i].data = i;
abt_init (&abt, method == INSERT ? compare_elements : NULL,
reaugment_elements, &aux_data);
check_abt (&abt, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
insert_node (&abt, &elements[insertions[i]], method);
check_abt (&abt, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
abt_delete (&abt, &elements[deletions[i]].node);
- check_abt (&abt, deletions + i + 1, cnt - i - 1);
+ check_abt (&abt, deletions + i + 1, n - i - 1);
}
free (elements);
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an
ABT in the order specified by INSERTIONS, then deletes them in
the order specified by DELETIONS, checking the ABT's contents
for correctness after each operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
- do_test_insert_delete (INSERT, insertions, deletions, cnt);
- do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
- do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
+ do_test_insert_delete (INSERT, insertions, deletions, n);
+ do_test_insert_delete (INSERT_AFTER, insertions, deletions, n);
+ do_test_insert_delete (INSERT_BEFORE, insertions, deletions, n);
}
\f
/* Inserts values into an ABT in each possible order, then
test_insert_any_remove_any (void)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
{
const int max_elems = 128;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
test_changed (void)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values, *changed_values;
struct element *elements;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- changed_values = xnmalloc (cnt, sizeof *changed_values);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ changed_values = xnmalloc (n, sizeof *changed_values);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int j, k;
- for (j = 0; j <= cnt; j++)
+ for (j = 0; j <= n; j++)
{
struct abt abt;
struct abt_node *changed_retval;
&aux_data);
/* Add to ABT in order. */
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
{
int n = values[k];
elements[n].data = n;
check (abt_insert (&abt, &elements[n].node) == NULL);
}
- check_abt (&abt, values, cnt);
+ check_abt (&abt, values, n);
/* Change value i to j. */
elements[i].data = j;
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
changed_values[k] = k;
changed_retval = abt_changed (&abt, &elements[i].node);
- if (i != j && j < cnt)
+ if (i != j && j < n)
{
/* Will cause duplicate. */
check (changed_retval == &elements[j].node);
- changed_values[i] = changed_values[cnt - 1];
- check_abt (&abt, changed_values, cnt - 1);
+ changed_values[i] = changed_values[n - 1];
+ check_abt (&abt, changed_values, n - 1);
}
else
{
/* Succeeds. */
check (changed_retval == NULL);
changed_values[i] = j;
- check_abt (&abt, changed_values, cnt);
+ check_abt (&abt, changed_values, n);
}
}
}
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (values);
free (changed_values);
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
check (height <= max_height);
}
-/* Checks that BT contains the CNT ints in DATA, that its
+/* Checks that BT contains the N ints in DATA, that its
structure is correct, and that certain operations on BT
produce the expected results. */
static void
-check_bt (struct bt *bt, const int data[], size_t cnt)
+check_bt (struct bt *bt, const int data[], size_t n)
{
struct element e;
size_t i;
int *order;
- order = xmemdup (data, cnt * sizeof *data);
- qsort (order, cnt, sizeof *order, compare_ints_noaux);
+ order = xmemdup (data, n * sizeof *data);
+ qsort (order, n, sizeof *order, compare_ints_noaux);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
struct bt_node *p;
check_balance (bt);
- if (cnt == 0)
+ if (n == 0)
{
check (bt_first (bt) == NULL);
check (bt_last (bt) == NULL);
{
struct bt_node *p;
- for (p = bt_first (bt), i = 0; i < cnt; p = bt_next (bt, p), i++)
+ for (p = bt_first (bt), i = 0; i < n; p = bt_next (bt, p), i++)
check (bt_node_to_element (p)->data == order[i]);
check (p == NULL);
- for (p = bt_last (bt), i = 0; i < cnt; p = bt_prev (bt, p), i++)
- check (bt_node_to_element (p)->data == order[cnt - i - 1]);
+ for (p = bt_last (bt), i = 0; i < n; p = bt_prev (bt, p), i++)
+ check (bt_node_to_element (p)->data == order[n - i - 1]);
check (p == NULL);
}
free (order);
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an
BT in the order specified by INSERTIONS, then deletes them in
the order specified by DELETIONS, checking the BT's contents
for correctness after each operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct element *elements;
struct bt bt;
size_t i;
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
elements[i].data = i;
bt_init (&bt, compare_elements, &aux_data);
check_bt (&bt, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (bt_insert (&bt, &elements[insertions[i]].node) == NULL);
check_bt (&bt, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
bt_delete (&bt, &elements[deletions[i]].node);
- check_bt (&bt, deletions + i + 1, cnt - i - 1);
+ check_bt (&bt, deletions + i + 1, n - i - 1);
}
free (elements);
test_insert_any_remove_any (void)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
{
const int max_elems = 128;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
test_changed (void)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values, *changed_values;
struct element *elements;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- changed_values = xnmalloc (cnt, sizeof *changed_values);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ changed_values = xnmalloc (n, sizeof *changed_values);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int j, k;
- for (j = 0; j <= cnt; j++)
+ for (j = 0; j <= n; j++)
{
struct bt bt;
struct bt_node *changed_retval;
bt_init (&bt, compare_elements, &aux_data);
/* Add to BT in order. */
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
{
int n = values[k];
elements[n].data = n;
check (bt_insert (&bt, &elements[n].node) == NULL);
}
- check_bt (&bt, values, cnt);
+ check_bt (&bt, values, n);
/* Change value i to j. */
elements[i].data = j;
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
changed_values[k] = k;
changed_retval = bt_changed (&bt, &elements[i].node);
- if (i != j && j < cnt)
+ if (i != j && j < n)
{
/* Will cause duplicate. */
check (changed_retval == &elements[j].node);
- changed_values[i] = changed_values[cnt - 1];
- check_bt (&bt, changed_values, cnt - 1);
+ changed_values[i] = changed_values[n - 1];
+ check_bt (&bt, changed_values, n - 1);
}
else
{
/* Succeeds. */
check (changed_retval == NULL);
changed_values[i] = j;
- check_bt (&bt, changed_values, cnt);
+ check_bt (&bt, changed_values, n);
}
}
}
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (values);
free (changed_values);
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Returns the number of permutations of the CNT values in
+/* Returns the number of permutations of the N values in
VALUES. If VALUES contains duplicates, they must be
adjacent. */
static unsigned int
-expected_perms (int *values, size_t cnt)
+expected_perms (int *values, size_t n)
{
size_t i, j;
unsigned int n_perms;
- n_perms = factorial (cnt);
- for (i = 0; i < cnt; i = j)
+ n_perms = factorial (n);
+ for (i = 0; i < n; i = j)
{
- for (j = i + 1; j < cnt; j++)
+ for (j = i + 1; j < n; j++)
if (values[i] != values[j])
break;
n_perms /= factorial (j - i);
test_insert_no_dups_delete_min (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct heap *h;
struct element *elements;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
values[i] = i;
h = heap_create (compare_elements, &aux_data);
n_permutations = 0;
- while (n_permutations == 0 || next_permutation (values, cnt))
+ while (n_permutations == 0 || next_permutation (values, n))
{
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
elements[i].x = values[i];
check (heap_is_empty (h));
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
heap_insert (h, &elements[i].node);
check (heap_node_to_element (heap_minimum (h))->x
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (heap_node_to_element (heap_minimum (h))->x == i);
heap_delete (h, heap_minimum (h));
check (heap_is_empty (h));
n_permutations++;
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
heap_destroy (h);
free (values);
free (elements);
test_insert_with_dups_delete_min (void)
{
const int max_elems = 7;
- int cnt;
-
- for (cnt = 1; cnt <= max_elems; cnt++)
+ for (int n_elems = 1; n_elems <= max_elems; n_elems++)
{
unsigned int n_compositions;
int *dups;
struct element *elements;
int n = 0;
- dups = xnmalloc (cnt, sizeof *dups);
- values = xnmalloc (cnt, sizeof *values);
- sorted_values = xnmalloc (cnt, sizeof *sorted_values);
- elements = xnmalloc (cnt, sizeof *elements);
+ dups = xnmalloc (n_elems, sizeof *dups);
+ values = xnmalloc (n_elems, sizeof *values);
+ sorted_values = xnmalloc (n_elems, sizeof *sorted_values);
+ elements = xnmalloc (n_elems, sizeof *elements);
n_uniques = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_uniques, dups))
+ while (next_composition (n_elems, &n_uniques, dups))
{
struct heap *h;
int i, j, k;
sorted_values[k] = i;
k++;
}
- check (k == cnt);
+ check (k == n_elems);
h = heap_create (compare_elements, &aux_data);
n_permutations = 0;
- while (n_permutations == 0 || next_permutation (values, cnt))
+ while (n_permutations == 0 || next_permutation (values, n_elems))
{
int min = INT_MAX;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n_elems; i++)
elements[i].x = values[i];
n++;
check (heap_is_empty (h));
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n_elems; i++)
{
heap_insert (h, &elements[i].node);
if (values[i] < min)
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n_elems; i++)
{
struct element *min = heap_node_to_element (heap_minimum (h));
check (min->x == sorted_values[i]);
check (heap_is_empty (h));
n_permutations++;
}
- check (n_permutations == expected_perms (values, cnt));
+ check (n_permutations == expected_perms (values, n_elems));
heap_destroy (h);
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n_elems - 1));
free (dups);
free (values);
test_insert_no_dups_delete_random (void)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct heap *h;
struct element *elements;
unsigned int insert_n_perms;
int i;
- insert = xnmalloc (cnt, sizeof *insert);
- delete = xnmalloc (cnt, sizeof *delete);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ insert = xnmalloc (n, sizeof *insert);
+ delete = xnmalloc (n, sizeof *delete);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
{
insert[i] = i;
delete[i] = i;
h = heap_create (compare_elements, &aux_data);
insert_n_perms = 0;
- while (insert_n_perms == 0 || next_permutation (insert, cnt))
+ while (insert_n_perms == 0 || next_permutation (insert, n))
{
unsigned int delete_n_perms = 0;
- while (delete_n_perms == 0 || next_permutation (delete, cnt))
+ while (delete_n_perms == 0 || next_permutation (delete, n))
{
int min;
int i;
check (heap_is_empty (h));
min = INT_MAX;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
heap_insert (h, &elements[insert[i]].node);
if (insert[i] < min)
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- int new_min = min_int (delete + i + 1, cnt - i - 1);
+ int new_min = min_int (delete + i + 1, n - i - 1);
heap_delete (h, &elements[delete[i]].node);
- check (heap_count (h) == cnt - i - 1);
+ check (heap_count (h) == n - i - 1);
if (!heap_is_empty (h))
check (heap_node_to_element (heap_minimum (h))->x == new_min);
}
check (heap_is_empty (h));
delete_n_perms++;
}
- check (delete_n_perms == factorial (cnt));
+ check (delete_n_perms == factorial (n));
insert_n_perms++;
}
- check (insert_n_perms == factorial (cnt));
+ check (insert_n_perms == factorial (n));
heap_destroy (h);
free (insert);
free (delete);
test_inc_dec (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct heap *h;
struct element *elements;
unsigned int insert_n_perms;
int i;
- insert = xnmalloc (cnt, sizeof *insert);
- delete = xnmalloc (cnt, sizeof *delete);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ insert = xnmalloc (n, sizeof *insert);
+ delete = xnmalloc (n, sizeof *delete);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
insert[i] = i;
h = heap_create (compare_elements, &aux_data);
insert_n_perms = 0;
- while (insert_n_perms == 0 || next_permutation (insert, cnt))
+ while (insert_n_perms == 0 || next_permutation (insert, n))
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
elements[i].x = insert[i];
check (heap_is_empty (h));
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int new_min = min_int (insert, i + 1);
heap_insert (h, &elements[i].node);
check (heap_count (h) == i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
delete[i] = insert[i];
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
+ elements[i].x = delete[i] = rand () % (n + 2) - 1;
heap_changed (h, &elements[i].node);
check (heap_node_to_element (heap_minimum (h))->x
- == min_int (delete, cnt));
+ == min_int (delete, n));
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- int new_min = min_int (delete + i + 1, cnt - i - 1);
+ int new_min = min_int (delete + i + 1, n - i - 1);
heap_delete (h, &elements[i].node);
- check (heap_count (h) == cnt - i - 1);
+ check (heap_count (h) == n - i - 1);
if (!heap_is_empty (h))
check (heap_node_to_element (heap_minimum (h))->x == new_min);
}
check (heap_is_empty (h));
insert_n_perms++;
}
- check (insert_n_perms == factorial (cnt));
+ check (insert_n_perms == factorial (n));
heap_destroy (h);
free (insert);
free (delete);
struct heap *h;
int *values;
struct element *elements;
- int cnt;
+ int n;
int insert_chance;
int i;
values = xnmalloc (max_elems, sizeof *values);
elements = xnmalloc (max_elems, sizeof *elements);
- cnt = 0;
+ n = 0;
insert_chance = 5;
h = heap_create (compare_elements, &aux_data);
{
enum { INSERT, DELETE } action;
- if (cnt == 0)
+ if (n == 0)
{
action = INSERT;
if (insert_chance < 9)
insert_chance++;
}
- else if (cnt == max_elems)
+ else if (n == max_elems)
{
action = DELETE;
if (insert_chance > 0)
int new_value;
new_value = rand () % max_elems;
- values[cnt] = new_value;
- elements[cnt].x = new_value;
+ values[n] = new_value;
+ elements[n].x = new_value;
- heap_insert (h, &elements[cnt].node);
+ heap_insert (h, &elements[n].node);
- cnt++;
+ n++;
}
else if (action == DELETE)
{
int del_idx;
- del_idx = rand () % cnt;
+ del_idx = rand () % n;
heap_delete (h, &elements[del_idx].node);
- cnt--;
- if (del_idx != cnt)
+ n--;
+ if (del_idx != n)
{
- values[del_idx] = values[cnt];
- elements[del_idx] = elements[cnt];
+ values[del_idx] = values[n];
+ elements[del_idx] = elements[n];
heap_moved (h, &elements[del_idx].node);
}
}
else
abort ();
- check (heap_count (h) == cnt);
- check (heap_is_empty (h) == (cnt == 0));
- if (cnt > 0)
+ check (heap_count (h) == n);
+ check (heap_is_empty (h) == (n == 0));
+ if (n > 0)
check (heap_node_to_element (heap_minimum (h))->x
- == min_int (values, cnt));
+ == min_int (values, n));
}
heap_destroy (h);
free (elements);
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
return &e->node;
}
-/* Checks that HMAP contains the CNT ints in DATA, that its
+/* Checks that HMAP contains the N ints in DATA, that its
structure is correct, and that certain operations on HMAP
produce the expected results. */
static void
-check_hmap (struct hmap *hmap, const int data[], size_t cnt,
+check_hmap (struct hmap *hmap, const int data[], size_t n,
hash_function *hash)
{
size_t i, j;
int *order;
- check (hmap_is_empty (hmap) == (cnt == 0));
- check (hmap_count (hmap) == cnt);
- check (cnt <= hmap_capacity (hmap));
+ check (hmap_is_empty (hmap) == (n == 0));
+ check (hmap_count (hmap) == n);
+ check (n <= hmap_capacity (hmap));
- order = xmemdup (data, cnt * sizeof *data);
- qsort (order, cnt, sizeof *order, compare_ints);
+ order = xmemdup (data, n * sizeof *data);
+ qsort (order, n, sizeof *order, compare_ints);
- for (i = 0; i < cnt; i = j)
+ for (i = 0; i < n; i = j)
{
struct element *e;
int count;
- for (j = i + 1; j < cnt; j++)
+ for (j = i + 1; j < n; j++)
if (order[i] != order[j])
break;
check (find_element (hmap, -1, hash) == NULL);
- if (cnt == 0)
+ if (n == 0)
check (hmap_first (hmap) == NULL);
else
{
struct hmap_node *p;
int left;
- left = cnt;
- for (p = hmap_first (hmap), i = 0; i < cnt; p = hmap_next (hmap, p), i++)
+ left = n;
+ for (p = hmap_first (hmap), i = 0; i < n; p = hmap_next (hmap, p), i++)
{
struct element *e = hmap_node_to_element (p);
free (order);
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an
HMAP in the order specified by INSERTIONS, then deletes them in
the order specified by DELETIONS, checking the HMAP's contents
for correctness after each operation. Uses HASH as the hash
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt,
+ size_t n,
hash_function *hash)
{
struct element *elements;
struct hmap hmap;
size_t i;
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
elements[i].data = i;
hmap_init (&hmap);
hmap_reserve (&hmap, 1);
check_hmap (&hmap, NULL, 0, hash);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
size_t capacity;
hmap_insert (&hmap, &elements[insertions[i]].node, hash (insertions[i]));
hmap_shrink (&hmap);
check (capacity == hmap_capacity (&hmap));
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
hmap_delete (&hmap, &elements[deletions[i]].node);
- check_hmap (&hmap, deletions + i + 1, cnt - i - 1, hash);
+ check_hmap (&hmap, deletions + i + 1, n - i - 1, hash);
}
hmap_destroy (&hmap);
test_insert_any_remove_any (hash_function *hash)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt, hash);
+ test_insert_delete (insertions, deletions, n, hash);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (hash_function *hash)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt, hash);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n, hash);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (hash_function *hash)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt, hash);
+ test_insert_delete (insertions, deletions, n, hash);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
test_random_sequence (int max_elems, hash_function *hash)
{
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt, hash);
+ test_insert_delete (insertions, deletions, n, hash);
}
free (insertions);
test_changed (hash_function *hash)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values, *changed_values;
struct element *elements;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- changed_values = xnmalloc (cnt, sizeof *changed_values);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ changed_values = xnmalloc (n, sizeof *changed_values);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int j, k;
- for (j = 0; j <= cnt; j++)
+ for (j = 0; j <= n; j++)
{
struct hmap hmap;
hmap_init (&hmap);
/* Add to HMAP in order. */
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
{
int n = values[k];
elements[n].data = n;
hmap_insert (&hmap, &elements[n].node,
hash (elements[n].data));
}
- check_hmap (&hmap, values, cnt, hash);
+ check_hmap (&hmap, values, n, hash);
/* Change value i to j. */
elements[i].data = j;
hmap_changed (&hmap, &elements[i].node,
hash (elements[i].data));
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
changed_values[k] = k;
changed_values[i] = j;
- check_hmap (&hmap, changed_values, cnt, hash);
+ check_hmap (&hmap, changed_values, n, hash);
hmap_destroy (&hmap);
}
}
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (values);
free (changed_values);
struct element *elements;
int *values;
struct hmap hmap;
- int cnt;
+ int n;
#if __GNUC__ == 4 && __GNUC_MINOR__ == 3
/* This tells the Autotest framework that the test was skipped. */
elements = xnmalloc (max_elems, sizeof *elements);
values = xnmalloc (max_elems, sizeof *values);
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int i;
hmap_init (&hmap);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
values[i] = elements[i].data = i;
hmap_insert (&hmap, &elements[i].node,
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
return node;
}
-/* Checks that HMAPX contains the CNT ints in DATA, that its
+/* Checks that HMAPX contains the N ints in DATA, that its
structure is correct, and that certain operations on HMAPX
produce the expected results. */
static void
-check_hmapx (struct hmapx *hmapx, const int data[], size_t cnt,
+check_hmapx (struct hmapx *hmapx, const int data[], size_t n,
hash_function *hash)
{
size_t i, j;
int *order;
- check (hmapx_is_empty (hmapx) == (cnt == 0));
- check (hmapx_count (hmapx) == cnt);
- check (cnt <= hmapx_capacity (hmapx));
+ check (hmapx_is_empty (hmapx) == (n == 0));
+ check (hmapx_count (hmapx) == n);
+ check (n <= hmapx_capacity (hmapx));
- order = xmemdup (data, cnt * sizeof *data);
- qsort (order, cnt, sizeof *order, compare_ints);
+ order = xmemdup (data, n * sizeof *data);
+ qsort (order, n, sizeof *order, compare_ints);
- for (i = 0; i < cnt; i = j)
+ for (i = 0; i < n; i = j)
{
struct hmapx_node *node;
struct element *e;
int count;
- for (j = i + 1; j < cnt; j++)
+ for (j = i + 1; j < n; j++)
if (order[i] != order[j])
break;
check (find_element (hmapx, -1, hash) == NULL);
- if (cnt == 0)
+ if (n == 0)
check (hmapx_first (hmapx) == NULL);
else
{
struct hmapx_node *p;
int left;
- left = cnt;
- for (p = hmapx_first (hmapx), i = 0; i < cnt;
+ left = n;
+ for (p = hmapx_first (hmapx), i = 0; i < n;
p = hmapx_next (hmapx, p), i++)
{
struct element *e = hmapx_node_data (p);
free (order);
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an
HMAPX in the order specified by INSERTIONS, then deletes them in
the order specified by DELETIONS, checking the HMAPX's contents
for correctness after each operation. Uses HASH as the hash
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt,
+ size_t n,
hash_function *hash,
size_t reserve)
{
struct hmapx hmapx;
size_t i;
- elements = xnmalloc (cnt, sizeof *elements);
- nodes = xnmalloc (cnt, sizeof *nodes);
- for (i = 0; i < cnt; i++)
+ elements = xnmalloc (n, sizeof *elements);
+ nodes = xnmalloc (n, sizeof *nodes);
+ for (i = 0; i < n; i++)
elements[i].data = i;
hmapx_init (&hmapx);
hmapx_reserve (&hmapx, reserve);
check_hmapx (&hmapx, NULL, 0, hash);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
struct hmapx_node *(*insert) (struct hmapx *, void *, size_t hash);
size_t capacity;
check (capacity == hmapx_capacity (&hmapx));
}
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
hmapx_delete (&hmapx, nodes[deletions[i]]);
- check_hmapx (&hmapx, deletions + i + 1, cnt - i - 1, hash);
+ check_hmapx (&hmapx, deletions + i + 1, n - i - 1, hash);
}
hmapx_destroy (&hmapx);
test_insert_any_remove_any (hash_function *hash)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt, hash, 1);
+ test_insert_delete (insertions, deletions, n, hash, 1);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (hash_function *hash)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt, hash, cnt / 2);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n, hash, n / 2);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (hash_function *hash)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt, hash, cnt);
+ test_insert_delete (insertions, deletions, n, hash, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
test_random_sequence (int max_elems, hash_function *hash)
{
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt, hash, 0);
+ test_insert_delete (insertions, deletions, n, hash, 0);
}
free (insertions);
test_changed (hash_function *hash)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values, *changed_values;
struct hmapx_node **nodes;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- changed_values = xnmalloc (cnt, sizeof *changed_values);
- elements = xnmalloc (cnt, sizeof *elements);
- nodes = xnmalloc (cnt, sizeof *nodes);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ changed_values = xnmalloc (n, sizeof *changed_values);
+ elements = xnmalloc (n, sizeof *elements);
+ nodes = xnmalloc (n, sizeof *nodes);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int j, k;
- for (j = 0; j <= cnt; j++)
+ for (j = 0; j <= n; j++)
{
struct hmapx hmapx;
hmapx_init (&hmapx);
/* Add to HMAPX in order. */
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
{
int n = values[k];
elements[n].data = n;
nodes[n] = hmapx_insert (&hmapx, &elements[n],
hash (elements[n].data));
}
- check_hmapx (&hmapx, values, cnt, hash);
+ check_hmapx (&hmapx, values, n, hash);
/* Change value i to j. */
elements[i].data = j;
hmapx_changed (&hmapx, nodes[i],
hash (elements[i].data));
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
changed_values[k] = k;
changed_values[i] = j;
- check_hmapx (&hmapx, changed_values, cnt, hash);
+ check_hmapx (&hmapx, changed_values, n, hash);
hmapx_destroy (&hmapx);
}
}
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (values);
free (changed_values);
test_change (hash_function *hash)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values, *changed_values;
struct hmapx_node **nodes;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- changed_values = xnmalloc (cnt, sizeof *changed_values);
- elements = xnmalloc (cnt, sizeof *elements);
- nodes = xnmalloc (cnt, sizeof *nodes);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ changed_values = xnmalloc (n, sizeof *changed_values);
+ elements = xnmalloc (n, sizeof *elements);
+ nodes = xnmalloc (n, sizeof *nodes);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int j, k;
- for (j = 0; j <= cnt; j++)
+ for (j = 0; j <= n; j++)
{
struct hmapx hmapx;
hmapx_init (&hmapx);
/* Add to HMAPX in order. */
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
{
int n = values[k];
elements[n].data = n;
nodes[n] = hmapx_insert (&hmapx, &elements[n],
hash (elements[n].data));
}
- check_hmapx (&hmapx, values, cnt, hash);
+ check_hmapx (&hmapx, values, n, hash);
/* Change value i to j. */
replacement.data = j;
hmapx_change (&hmapx, nodes[i], &replacement, hash (j));
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
changed_values[k] = k;
changed_values[i] = j;
- check_hmapx (&hmapx, changed_values, cnt, hash);
+ check_hmapx (&hmapx, changed_values, n, hash);
hmapx_destroy (&hmapx);
}
}
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (values);
free (changed_values);
struct hmapx_node **nodes;
int *values;
struct hmapx hmapx;
- int cnt;
+ int n;
elements = xnmalloc (max_elems, sizeof *elements);
nodes = xnmalloc (max_elems, sizeof *nodes);
values = xnmalloc (max_elems, sizeof *values);
hmapx_init (&hmapx);
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
values[i] = elements[i].data = i;
nodes[i] = hmapx_insert (&hmapx, &elements[i],
printf ("\n");
}
-/* Prints the CNT numbers in VALUES. */
+/* Prints the N numbers in VALUES. */
static void UNUSED
-print_array (int values[], size_t cnt)
+print_array (int values[], size_t n)
{
size_t i;
printf ("arry:");
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
printf (" %d", values[i]);
printf ("\n");
}
*values = xnmalloc (n, sizeof *values);
}
-/* Copies the CNT values of `x' from LIST into VALUES[]. */
+/* Copies the N values of `x' from LIST into VALUES[]. */
static void
-extract_values (struct ll_list *list, int values[], size_t cnt)
+extract_values (struct ll_list *list, int values[], size_t n)
{
struct ll *x;
- check (ll_count (list) == cnt);
+ check (ll_count (list) == n);
for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
{
struct element *e = ll_to_element (x);
extract_values (list, *values, n);
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
return *a < *b ? -1 : *a > *b;
}
-/* Checks that LIST contains the CNT values in ELEMENTS. */
+/* Checks that LIST contains the N values in ELEMENTS. */
static void
-check_list_contents (struct ll_list *list, int elements[], size_t cnt)
+check_list_contents (struct ll_list *list, int elements[], size_t n)
{
struct ll *ll;
size_t i;
- check ((cnt == 0) == ll_is_empty (list));
+ check ((n == 0) == ll_is_empty (list));
/* Iterate in forward order. */
- for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++)
+ for (ll = ll_head (list), i = 0; i < n; ll = ll_next (ll), i++)
{
struct element *e = ll_to_element (ll);
check (elements[i] == e->x);
check (ll == ll_null (list));
/* Iterate in reverse order. */
- for (ll = ll_tail (list), i = 0; i < cnt; ll = ll_prev (ll), i++)
+ for (ll = ll_tail (list), i = 0; i < n; ll = ll_prev (ll), i++)
{
struct element *e = ll_to_element (ll);
- check (elements[cnt - i - 1] == e->x);
+ check (elements[n - i - 1] == e->x);
check (ll != ll_null (list));
}
check (ll == ll_null (list));
- check (ll_count (list) == cnt);
+ check (ll_count (list) == n);
}
/* Lexicographically compares ARRAY1, which contains COUNT1
test_insert_remove (void)
{
const int max_elems = 16;
- int cnt;
+ int n;
- for (cnt = 0; cnt < max_elems; cnt++)
+ for (n = 0; n < max_elems; n++)
{
struct element **elems;
struct ll **elemp;
- int *values = xnmalloc (cnt + 1, sizeof *values);
+ int *values = xnmalloc (n + 1, sizeof *values);
struct ll_list list;
struct element extra;
int pos;
- allocate_ascending (cnt, &list, &elems, &elemp, NULL);
+ allocate_ascending (n, &list, &elems, &elemp, NULL);
extra.x = -1;
- for (pos = 0; pos <= cnt; pos++)
+ for (pos = 0; pos <= n; pos++)
{
int i, j;
for (i = 0; i < pos; i++)
values[j++] = i;
values[j++] = -1;
- for (; i < cnt; i++)
+ for (; i < n; i++)
values[j++] = i;
- check_list_contents (&list, values, cnt + 1);
+ check_list_contents (&list, values, n + 1);
ll_remove (&extra.ll);
}
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
test_swap (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct ll_list list;
struct element **elems;
int i, j, k;
- allocate_ascending (cnt, &list, &elems, NULL, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, NULL, &values);
+ check_list_contents (&list, values, n);
- for (i = 0; i < cnt; i++)
- for (j = 0; j < cnt; j++)
+ for (i = 0; i < n; i++)
+ for (j = 0; j < n; j++)
for (k = 0; k < 2; k++)
{
int t;
t = values[i];
values[i] = values[j];
values[j] = t;
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
}
- free_elements (cnt, elems, NULL, values);
+ free_elements (n, elems, NULL, values);
}
}
test_swap_range (void)
{
const int max_elems = 8;
- int cnt, a0, a1, b0, b1, r;
+ int n, a0, a1, b0, b1, r;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (a0 = 0; a0 <= cnt; a0++)
- for (a1 = a0; a1 <= cnt; a1++)
- for (b0 = a1; b0 <= cnt; b0++)
- for (b1 = b0; b1 <= cnt; b1++)
+ for (n = 0; n <= max_elems; n++)
+ for (a0 = 0; a0 <= n; a0++)
+ for (a1 = a0; a1 <= n; a1++)
+ for (b0 = a1; b0 <= n; b0++)
+ for (b1 = b0; b1 <= n; b1++)
for (r = 0; r < 2; r++)
{
struct ll_list list;
int i, j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
j = 0;
for (i = 0; i < a0; i++)
values[j++] = i;
for (i = a0; i < a1; i++)
values[j++] = i;
- for (i = b1; i < cnt; i++)
+ for (i = b1; i < n; i++)
values[j++] = i;
- check (j == cnt);
+ check (j == n);
if (r == 0)
ll_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
else
ll_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1;
+ int n, r0, r1;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct ll_list list;
struct element **elems;
int i, j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
j = 0;
for (i = 0; i < r0; i++)
values[j++] = i;
- for (i = r1; i < cnt; i++)
+ for (i = r1; i < n; i++)
values[j++] = i;
ll_remove_range (elemp[r0], elemp[r1]);
check_list_contents (&list, values, j);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, eq_pat;
+ int n, r0, r1, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct ll_list list;
struct element **elems;
int remaining;
int i;
- allocate_elements (cnt, &list, &elems, &elemp, &values);
+ allocate_elements (n, &list, &elems, &elemp, &values);
remaining = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int x = eq_pat & (1 << i) ? -1 : i;
bool delete = x == -1 && r0 <= i && i < r1;
to_remove.x = -1;
check ((int) ll_remove_equal (elemp[r0], elemp[r1], &to_remove.ll,
compare_elements, &aux_data)
- == cnt - remaining);
+ == n - remaining);
check_list_contents (&list, values, remaining);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, pattern;
+ int n, r0, r1, pattern;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
- for (pattern = 0; pattern <= 1 << cnt; pattern++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
+ for (pattern = 0; pattern <= 1 << n; pattern++)
{
struct ll_list list;
struct element **elems;
int remaining;
int i;
- allocate_elements (cnt, &list, &elems, &elemp, &values);
+ allocate_elements (n, &list, &elems, &elemp, &values);
remaining = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
elems[i]->x = i;
check ((int) ll_remove_if (elemp[r0], elemp[r1],
pattern_pred, &pattern)
- == cnt - remaining);
+ == n - remaining);
check_list_contents (&list, values, remaining);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct ll_list list;
struct element **elems;
int i;
- allocate_ascending (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &new_elems, NULL, NULL);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &new_elems, NULL, NULL);
+ check_list_contents (&list, values, n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
*new_elems[i] = *elems[i];
ll_moved (&new_elems[i]->ll);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
}
- free_elements (cnt, elems, NULL, values);
- free_elements (cnt, new_elems, NULL, NULL);
+ free_elements (n, elems, NULL, values);
+ free_elements (n, new_elems, NULL, NULL);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, eq_pat;
+ int n, r0, r1, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct ll_list list;
struct element **elems;
int i;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
if (eq_pat & (1 << i))
values[i] = elems[i]->x = -1;
to_find.x = -1;
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
helper (r0, r1, eq_pat, &to_find.ll, elemp);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, eq_pat;
+ int n, r0, r1, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct ll_list list;
struct element **elems;
struct ll **elemp;
int *values;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
helper (r0, r1, eq_pat, elemp);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, eq_pat;
+ int n, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct ll_list list;
struct element **elems;
int i;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
match = -1;
- for (i = 0; i < cnt - 1; i++)
+ for (i = 0; i < n - 1; i++)
{
elems[i]->y = i;
if (eq_pat & (1 << i))
match--;
}
- for (i = 0; i <= cnt; i++)
+ for (i = 0; i <= n; i++)
{
struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list),
compare_elements,
int j;
ll2 = ll_null (&list);
- for (j = i; j < cnt - 1; j++)
+ for (j = i; j < n - 1; j++)
if (eq_pat & (1 << j))
{
ll2 = elemp[j];
}
check (ll1 == ll2);
}
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
return value;
}
-/* Returns the number of permutations of the CNT values in
+/* Returns the number of permutations of the N values in
VALUES. If VALUES contains duplicates, they must be
adjacent. */
static unsigned int
-expected_perms (int *values, size_t cnt)
+expected_perms (int *values, size_t n)
{
size_t i, j;
unsigned int n_perms;
- n_perms = factorial (cnt);
- for (i = 0; i < cnt; i = j)
+ n_perms = factorial (n);
+ for (i = 0; i < n; i = j)
{
- for (j = i + 1; j < cnt; j++)
+ for (j = i + 1; j < n; j++)
if (values[i] != values[j])
break;
n_perms /= factorial (j - i);
test_min_max (void)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct ll_list list;
struct element **elems;
struct ll **elemp;
int *values;
- int *new_values = xnmalloc (cnt, sizeof *values);
+ int *new_values = xnmalloc (n, sizeof *values);
size_t n_perms;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
n_perms = 1;
while (ll_next_permutation (ll_head (&list), ll_null (&list),
elemp[i] = x;
new_values[i] = e->x;
}
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct ll *min = ll_min (elemp[r0], elemp[r1],
compare_elements, &aux_data);
}
n_perms++;
}
- check (n_perms == factorial (cnt));
- check_list_contents (&list, values, cnt);
+ check (n_perms == factorial (n));
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
free (new_values);
}
}
{
const int max_elems = 4;
- int cnt_a, pat_a, cnt_b, pat_b;
+ int n_a, pat_a, n_b, pat_b;
- for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
- for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
- for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
- for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
+ for (n_a = 0; n_a <= max_elems; n_a++)
+ for (pat_a = 0; pat_a <= 1 << n_a; pat_a++)
+ for (n_b = 0; n_b <= max_elems; n_b++)
+ for (pat_b = 0; pat_b <= 1 << n_b; pat_b++)
{
struct ll_list list_a, list_b;
struct element **elems_a, **elems_b;
int a0, a1, b0, b1;
- allocate_pattern (cnt_a, pat_a,
+ allocate_pattern (n_a, pat_a,
&list_a, &elems_a, &elemp_a, &values_a);
- allocate_pattern (cnt_b, pat_b,
+ allocate_pattern (n_b, pat_b,
&list_b, &elems_b, &elemp_b, &values_b);
- for (a0 = 0; a0 <= cnt_a; a0++)
- for (a1 = a0; a1 <= cnt_a; a1++)
- for (b0 = 0; b0 <= cnt_b; b0++)
- for (b1 = b0; b1 <= cnt_b; b1++)
+ for (a0 = 0; a0 <= n_a; a0++)
+ for (a1 = a0; a1 <= n_a; a1++)
+ for (b0 = 0; b0 <= n_b; b0++)
+ for (b1 = b0; b1 <= n_b; b1++)
{
int a_ordering = lexicographical_compare_3way (
values_a + a0, a1 - a0,
check (a_ordering == b_ordering);
}
- free_elements (cnt_a, elems_a, elemp_a, values_a);
- free_elements (cnt_b, elems_b, elemp_b, values_b);
+ free_elements (n_a, elems_a, elemp_a, values_a);
+ free_elements (n_b, elems_b, elemp_b, values_b);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1;
+ int n, r0, r1;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct ll_list list;
struct element **elems;
int i;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
- output = next_output = xnmalloc (cnt, sizeof *output);
+ output = next_output = xnmalloc (n, sizeof *output);
ll_apply (elemp[r0], elemp[r1], apply_func, &next_output);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
check (r1 - r0 == next_output - output);
for (i = 0; i < r1 - r0; i++)
check (output[i] == r0 + i);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
free (output);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1;
+ int n, r0, r1;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct ll_list list;
struct element **elems;
int i, j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
j = 0;
for (i = 0; i < r0; i++)
values[j++] = i;
for (i = r1 - 1; i >= r0; i--)
values[j++] = i;
- for (i = r1; i < cnt; i++)
+ for (i = r1; i < n; i++)
values[j++] = i;
ll_reverse (elemp[r0], elemp[r1]);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
test_permutations_no_dups (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct ll_list list;
struct element **elems;
int *values;
- int *old_values = xnmalloc (cnt, sizeof *values);
- int *new_values = xnmalloc (cnt, sizeof *values);
+ int *old_values = xnmalloc (n, sizeof *values);
+ int *new_values = xnmalloc (n, sizeof *values);
size_t n_perms;
- allocate_ascending (cnt, &list, &elems, NULL, &values);
+ allocate_ascending (n, &list, &elems, NULL, &values);
n_perms = 1;
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n);
while (ll_next_permutation (ll_head (&list), ll_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n);
+ check (lexicographical_compare_3way (new_values, n,
+ old_values, n,
sizeof *new_values,
compare_ints, NULL) > 0);
- memcpy (old_values, new_values, (cnt) * sizeof *old_values);
+ memcpy (old_values, new_values, (n) * sizeof *old_values);
n_perms++;
}
- check (n_perms == factorial (cnt));
- check_list_contents (&list, values, cnt);
+ check (n_perms == factorial (n));
+ check_list_contents (&list, values, n);
n_perms = 1;
ll_reverse (ll_head (&list), ll_null (&list));
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n);
while (ll_prev_permutation (ll_head (&list), ll_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n);
+ check (lexicographical_compare_3way (new_values, n,
+ old_values, n,
sizeof *new_values,
compare_ints, NULL) < 0);
- memcpy (old_values, new_values, (cnt) * sizeof *old_values);
+ memcpy (old_values, new_values, (n) * sizeof *old_values);
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
ll_reverse (ll_head (&list), ll_null (&list));
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, NULL, values);
+ free_elements (n, elems, NULL, values);
free (old_values);
free (new_values);
}
const int max_dup = 3;
const int repetitions = 1024;
- int cnt, repeat;
-
- for (repeat = 0; repeat < repetitions; repeat++)
- for (cnt = 0; cnt < max_elems; cnt++)
+ for (int repeat = 0; repeat < repetitions; repeat++)
+ for (int n_elems = 0; n_elems < max_elems; n_elems++)
{
struct ll_list list;
struct element **elems;
int *new_values = xnmalloc (max_elems, sizeof *values);
unsigned int n_permutations;
- int left = cnt;
+ int left = n_elems;
int value = 0;
- allocate_elements (cnt, &list, &elems, NULL, &values);
+ allocate_elements (n_elems, &list, &elems, NULL, &values);
value = 0;
while (left > 0)
int n = rand () % max + 1;
while (n-- > 0)
{
- int idx = cnt - left--;
+ int idx = n_elems - left--;
values[idx] = elems[idx]->x = value;
}
value++;
}
n_permutations = 1;
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n_elems);
while (ll_next_permutation (ll_head (&list), ll_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n_elems);
+ check (lexicographical_compare_3way (new_values, n_elems,
+ old_values, n_elems,
sizeof *new_values,
compare_ints, NULL) > 0);
- memcpy (old_values, new_values, cnt * sizeof *old_values);
+ memcpy (old_values, new_values, n_elems * sizeof *old_values);
n_permutations++;
}
- check (n_permutations == expected_perms (values, cnt));
- check_list_contents (&list, values, cnt);
+ check (n_permutations == expected_perms (values, n_elems));
+ check_list_contents (&list, values, n_elems);
n_permutations = 1;
ll_reverse (ll_head (&list), ll_null (&list));
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n_elems);
while (ll_prev_permutation (ll_head (&list), ll_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n_elems);
+ check (lexicographical_compare_3way (new_values, n_elems,
+ old_values, n_elems,
sizeof *new_values,
compare_ints, NULL) < 0);
n_permutations++;
}
ll_reverse (ll_head (&list), ll_null (&list));
- check (n_permutations == expected_perms (values, cnt));
- check_list_contents (&list, values, cnt);
+ check (n_permutations == expected_perms (values, n_elems));
+ check_list_contents (&list, values, n_elems);
- free_elements (cnt, elems, NULL, values);
+ free_elements (n_elems, elems, NULL, values);
free (old_values);
free (new_values);
}
{
const int max_elems = 8;
- int cnt, merge_pat, inc_pat, order;
+ int n, merge_pat, inc_pat, order;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
- for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (merge_pat = 0; merge_pat <= (1 << n); merge_pat++)
+ for (inc_pat = 0; inc_pat <= (1 << n); inc_pat++)
for (order = 0; order < 2; order++)
{
struct ll_list list;
int mid;
int i, j, k;
- allocate_elements (cnt, &list, &elems, &elemp, &values);
+ allocate_elements (n, &list, &elems, &elemp, &values);
j = 0;
- for (i = k = 0; i < cnt; i++)
+ for (i = k = 0; i < n; i++)
{
if (merge_pat & (1u << i))
elems[j++]->x = k;
k++;
}
mid = j;
- for (i = k = 0; i < cnt; i++)
+ for (i = k = 0; i < n; i++)
{
if (!(merge_pat & (1u << i)))
elems[j++]->x = k;
if (inc_pat & (1u << i))
k++;
}
- check (cnt == j);
+ check (n == j);
if (order == 0)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
elems[i]->y = i;
}
else
{
for (i = 0; i < mid; i++)
elems[i]->y = 100 + i;
- for (i = mid; i < cnt; i++)
+ for (i = mid; i < n; i++)
elems[i]->y = i;
}
j = 0;
- for (i = k = 0; i < cnt; i++)
+ for (i = k = 0; i < n; i++)
{
values[j++] = k;
if (inc_pat & (1u << i))
k++;
}
- check (cnt == j);
+ check (n == j);
if (order == 0)
- ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
+ ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[n],
compare_elements, &aux_data);
else
- ll_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
+ ll_merge (elemp[mid], elemp[n], elemp[0], elemp[mid],
compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
check (ll_is_sorted (ll_head (&list), ll_null (&list),
compare_elements_x_y, &aux_data));
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
test_sort_exhaustive (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct ll_list list;
struct element **elems;
size_t n_perms;
- allocate_ascending (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_ascending (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
n_perms = 1;
while (ll_next_permutation (ll_head (&list), ll_null (&list),
struct ll_list perm_list;
int j;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
ll_init (&perm_list);
- for (j = 0; j < cnt; j++)
+ for (j = 0; j < n; j++)
{
perm_elems[j]->x = perm_values[j];
ll_push_tail (&perm_list, &perm_elems[j]->ll);
}
ll_sort (ll_head (&perm_list), ll_null (&perm_list),
compare_elements, &aux_data);
- check_list_contents (&perm_list, values, cnt);
+ check_list_contents (&perm_list, values, n);
check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
compare_elements, &aux_data));
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
- free_elements (cnt, elems, NULL, values);
- free_elements (cnt, perm_elems, NULL, perm_values);
+ free_elements (n, elems, NULL, values);
+ free_elements (n, perm_elems, NULL, perm_values);
}
}
test_sort_stable (void)
{
const int max_elems = 6;
- int cnt, inc_pat;
+ int n, inc_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (inc_pat = 0; inc_pat <= 1 << n; inc_pat++)
{
struct ll_list list;
struct element **elems;
size_t n_perms;
int i, j;
- allocate_elements (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_elements (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
j = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
elems[i]->x = values[i] = j;
if (inc_pat & (1 << i))
{
struct ll_list perm_list;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
ll_init (&perm_list);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
}
ll_sort (ll_head (&perm_list), ll_null (&perm_list),
compare_elements, &aux_data);
- check_list_contents (&perm_list, values, cnt);
+ check_list_contents (&perm_list, values, n);
check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
compare_elements_x_y, &aux_data));
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
- free_elements (cnt, elems, NULL, values);
- free_elements (cnt, perm_elems, NULL, perm_values);
+ free_elements (n, elems, NULL, values);
+ free_elements (n, perm_elems, NULL, perm_values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, repeat;
+ int n, r0, r1, repeat;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
for (repeat = 0; repeat < 100; repeat++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct ll_list list;
struct element **elems;
struct ll **elemp;
int *values;
- allocate_random (cnt, &list, &elems, &elemp, &values);
+ allocate_random (n, &list, &elems, &elemp, &values);
qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
ll_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
{
const int max_elems = 1024;
- int cnt;
+ int n;
- for (cnt = 0; cnt < max_elems; cnt++)
+ for (n = 0; n < max_elems; n++)
{
struct ll_list list;
struct element **elems;
int *values;
- allocate_random (cnt, &list, &elems, NULL, &values);
+ allocate_random (n, &list, &elems, NULL, &values);
- qsort (values, cnt, sizeof *values, compare_ints_noaux);
+ qsort (values, n, sizeof *values, compare_ints_noaux);
ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, NULL, values);
+ free_elements (n, elems, NULL, values);
}
}
int *ascending = xnmalloc (max_elems, sizeof *ascending);
- int cnt, inc_pat, i, j, unique_values;
+ int n, inc_pat, i, j, unique_values;
for (i = 0; i < max_elems; i++)
ascending[i] = i;
- for (cnt = 0; cnt < max_elems; cnt++)
- for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
+ for (n = 0; n < max_elems; n++)
+ for (inc_pat = 0; inc_pat < (1 << n); inc_pat++)
{
struct ll_list list, dups;
struct element **elems;
int *values;
- allocate_elements (cnt, &list, &elems, NULL, &values);
+ allocate_elements (n, &list, &elems, NULL, &values);
j = unique_values = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
unique_values = j + 1;
elems[i]->x = values[i] = j;
if (inc_pat & (1 << i))
j++;
}
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
ll_init (&dups);
check (ll_unique (ll_head (&list), ll_null (&list), ll_null (&dups),
ll_splice (ll_null (&list), ll_head (&dups), ll_null (&dups));
ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, elems, NULL, values);
+ free_elements (n, elems, NULL, values);
}
free (ascending);
test_sort_unique (void)
{
const int max_elems = 7;
- int cnt, inc_pat;
+ int n, inc_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (inc_pat = 0; inc_pat <= 1 << n; inc_pat++)
{
struct ll_list list;
struct element **elems;
size_t n_perms;
int i, j;
- allocate_elements (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_elements (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
j = n_uniques = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
elems[i]->x = values[i] = j;
n_uniques = j + 1;
{
struct ll_list perm_list;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
ll_init (&perm_list);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
compare_elements_x_y, &aux_data));
n_perms++;
}
- check (n_perms == expected_perms (values, cnt));
+ check (n_perms == expected_perms (values, n));
- free_elements (cnt, elems, NULL, values);
- free_elements (cnt, perm_elems, NULL, perm_values);
+ free_elements (n, elems, NULL, values);
+ free_elements (n, perm_elems, NULL, perm_values);
free (unique_values);
}
}
test_insert_ordered (void)
{
const int max_elems = 6;
- int cnt, inc_pat;
+ int n, inc_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (inc_pat = 0; inc_pat <= 1 << n; inc_pat++)
{
struct ll_list list;
struct element **elems;
size_t n_perms;
int i, j;
- allocate_elements (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_elements (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
j = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
elems[i]->x = values[i] = j;
if (inc_pat & (1 << i))
{
struct ll_list perm_list;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
ll_init (&perm_list);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
compare_elements_x_y, &aux_data));
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
- free_elements (cnt, elems, NULL, values);
- free_elements (cnt, perm_elems, NULL, perm_values);
+ free_elements (n, elems, NULL, values);
+ free_elements (n, perm_elems, NULL, perm_values);
}
}
{
const int max_elems = 10;
- int cnt;
+ int n;
unsigned int pbase;
int r0, r1;
- for (cnt = 0; cnt < max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n < max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
{
struct ll_list list;
int first_false;
struct ll *part_ll;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
/* Check that ll_find_partition works okay in every
case. We use it after partitioning, too, but that
}
if (first_false == -1)
first_false = r1;
- for (i = r1; i < cnt; i++)
+ for (i = r1; i < n; i++)
values[j++] = i;
- check (j == cnt);
+ check (j == n);
/* Partition and check for expected results. */
check (ll_partition (elemp[r0], elemp[r1],
check (ll_find_partition (elemp[r0], elemp[r1],
pattern_pred, &pattern)
== elemp[first_false]);
- check_list_contents (&list, values, cnt);
- check ((int) ll_count (&list) == cnt);
+ check_list_contents (&list, values, n);
+ check ((int) ll_count (&list) == n);
- free_elements (cnt, elems, elemp, values);
+ free_elements (n, elems, elemp, values);
}
}
\f
printf ("\n");
}
-/* Prints the CNT numbers in VALUES. */
+/* Prints the N numbers in VALUES. */
static void UNUSED
-print_array (int values[], size_t cnt)
+print_array (int values[], size_t n)
{
size_t i;
printf ("arry:");
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
printf (" %d", values[i]);
printf ("\n");
}
*values = xnmalloc (n, sizeof *values);
}
-/* Copies the CNT values of `x' from LIST into VALUES[]. */
+/* Copies the N values of `x' from LIST into VALUES[]. */
static void
-extract_values (struct llx_list *list, int values[], size_t cnt)
+extract_values (struct llx_list *list, int values[], size_t n)
{
struct llx *x;
- check (llx_count (list) == cnt);
+ check (llx_count (list) == n);
for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
{
struct element *e = llx_data (x);
extract_values (list, *values, n);
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
return *a < *b ? -1 : *a > *b;
}
-/* Checks that LIST contains the CNT values in ELEMENTS. */
+/* Checks that LIST contains the N values in ELEMENTS. */
static void
-check_list_contents (struct llx_list *list, int elements[], size_t cnt)
+check_list_contents (struct llx_list *list, int elements[], size_t n)
{
struct llx *llx;
size_t i;
- check ((cnt == 0) == llx_is_empty (list));
+ check ((n == 0) == llx_is_empty (list));
/* Iterate in forward order. */
- for (llx = llx_head (list), i = 0; i < cnt; llx = llx_next (llx), i++)
+ for (llx = llx_head (list), i = 0; i < n; llx = llx_next (llx), i++)
{
struct element *e = llx_data (llx);
check (elements[i] == e->x);
check (llx == llx_null (list));
/* Iterate in reverse order. */
- for (llx = llx_tail (list), i = 0; i < cnt; llx = llx_prev (llx), i++)
+ for (llx = llx_tail (list), i = 0; i < n; llx = llx_prev (llx), i++)
{
struct element *e = llx_data (llx);
- check (elements[cnt - i - 1] == e->x);
+ check (elements[n - i - 1] == e->x);
check (llx != llx_null (list));
}
check (llx == llx_null (list));
- check (llx_count (list) == cnt);
+ check (llx_count (list) == n);
}
/* Lexicographicallxy compares ARRAY1, which contains COUNT1
test_insert_remove (void)
{
const int max_elems = 16;
- int cnt;
+ int n;
- for (cnt = 0; cnt < max_elems; cnt++)
+ for (n = 0; n < max_elems; n++)
{
struct element **elems;
struct llx **elemp;
- int *values = xnmalloc (cnt + 1, sizeof *values);
+ int *values = xnmalloc (n + 1, sizeof *values);
struct llx_list list;
struct element extra;
struct llx *extra_llx;
int pos;
- allocate_ascending (cnt, &list, &elems, &elemp, NULL);
+ allocate_ascending (n, &list, &elems, &elemp, NULL);
extra.x = -1;
- for (pos = 0; pos <= cnt; pos++)
+ for (pos = 0; pos <= n; pos++)
{
int i, j;
for (i = 0; i < pos; i++)
values[j++] = i;
values[j++] = -1;
- for (; i < cnt; i++)
+ for (; i < n; i++)
values[j++] = i;
- check_list_contents (&list, values, cnt + 1);
+ check_list_contents (&list, values, n + 1);
llx_remove (extra_llx, &llx_malloc_mgr);
}
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
test_swap (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct llx_list list;
struct element **elems;
int i, j, k;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
- for (i = 0; i < cnt; i++)
- for (j = 0; j < cnt; j++)
+ for (i = 0; i < n; i++)
+ for (j = 0; j < n; j++)
for (k = 0; k < 2; k++)
{
int t;
t = values[i];
values[i] = values[j];
values[j] = t;
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
}
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
test_swap_range (void)
{
const int max_elems = 8;
- int cnt, a0, a1, b0, b1, r;
+ int n, a0, a1, b0, b1, r;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (a0 = 0; a0 <= cnt; a0++)
- for (a1 = a0; a1 <= cnt; a1++)
- for (b0 = a1; b0 <= cnt; b0++)
- for (b1 = b0; b1 <= cnt; b1++)
+ for (n = 0; n <= max_elems; n++)
+ for (a0 = 0; a0 <= n; a0++)
+ for (a1 = a0; a1 <= n; a1++)
+ for (b0 = a1; b0 <= n; b0++)
+ for (b1 = b0; b1 <= n; b1++)
for (r = 0; r < 2; r++)
{
struct llx_list list;
int i, j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
j = 0;
for (i = 0; i < a0; i++)
values[j++] = i;
for (i = a0; i < a1; i++)
values[j++] = i;
- for (i = b1; i < cnt; i++)
+ for (i = b1; i < n; i++)
values[j++] = i;
- check (j == cnt);
+ check (j == n);
if (r == 0)
llx_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
else
llx_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1;
+ int n, r0, r1;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct llx_list list;
struct element **elems;
int i, j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
j = 0;
for (i = 0; i < r0; i++)
values[j++] = i;
- for (i = r1; i < cnt; i++)
+ for (i = r1; i < n; i++)
values[j++] = i;
llx_remove_range (elemp[r0], elemp[r1], &llx_malloc_mgr);
check_list_contents (&list, values, j);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, eq_pat;
+ int n, r0, r1, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct llx_list list;
struct element **elems;
int remaining;
int i;
- allocate_elements (cnt, &list, &elems, &elemp, &values);
+ allocate_elements (n, &list, &elems, &elemp, &values);
remaining = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int x = eq_pat & (1 << i) ? -1 : i;
bool delete = x == -1 && r0 <= i && i < r1;
check ((int) llx_remove_equal (elemp[r0], elemp[r1], &to_remove,
compare_elements, &aux_data,
&llx_malloc_mgr)
- == cnt - remaining);
+ == n - remaining);
check_list_contents (&list, values, remaining);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, pattern;
+ int n, r0, r1, pattern;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
- for (pattern = 0; pattern <= 1 << cnt; pattern++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
+ for (pattern = 0; pattern <= 1 << n; pattern++)
{
struct llx_list list;
struct element **elems;
int remaining;
int i;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
remaining = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
if (!delete)
check ((int) llx_remove_if (elemp[r0], elemp[r1],
pattern_pred, &pattern,
&llx_malloc_mgr)
- == cnt - remaining);
+ == n - remaining);
check_list_contents (&list, values, remaining);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, eq_pat;
+ int n, r0, r1, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct llx_list list;
struct element **elems;
int i;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
if (eq_pat & (1 << i))
values[i] = elems[i]->x = -1;
to_find.x = -1;
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
helper (r0, r1, eq_pat, &to_find, elemp);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, eq_pat;
+ int n, r0, r1, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct llx_list list;
struct element **elems;
struct llx **elemp;
int *values;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
helper (r0, r1, eq_pat, elemp);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct llx_list list;
struct element **elems;
int i;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
check (llx_find (llx_head (&list), llx_null (&list), elems[i])
== elemp[i]);
check (llx_find (llx_head (&list), llx_null (&list), NULL) == NULL);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 8;
- int cnt, eq_pat;
+ int n, eq_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (eq_pat = 0; eq_pat <= 1 << n; eq_pat++)
{
struct llx_list list;
struct element **elems;
int i;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
match = -1;
- for (i = 0; i < cnt - 1; i++)
+ for (i = 0; i < n - 1; i++)
{
elems[i]->y = i;
if (eq_pat & (1 << i))
match--;
}
- for (i = 0; i <= cnt; i++)
+ for (i = 0; i <= n; i++)
{
struct llx *llx1 = llx_find_adjacent_equal (elemp[i], llx_null (&list),
compare_elements,
int j;
llx2 = llx_null (&list);
- for (j = i; j < cnt - 1; j++)
+ for (j = i; j < n - 1; j++)
if (eq_pat & (1 << j))
{
llx2 = elemp[j];
}
check (llx1 == llx2);
}
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
return value;
}
-/* Returns the number of permutations of the CNT values in
+/* Returns the number of permutations of the N values in
VALUES. If VALUES contains duplicates, they must be
adjacent. */
static unsigned int
-expected_perms (int *values, size_t cnt)
+expected_perms (int *values, size_t n)
{
size_t i, j;
unsigned int n_perms;
- n_perms = factorial (cnt);
- for (i = 0; i < cnt; i = j)
+ n_perms = factorial (n);
+ for (i = 0; i < n; i = j)
{
- for (j = i + 1; j < cnt; j++)
+ for (j = i + 1; j < n; j++)
if (values[i] != values[j])
break;
n_perms /= factorial (j - i);
test_min_max (void)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct llx_list list;
struct element **elems;
struct llx **elemp;
int *values;
- int *new_values = xnmalloc (cnt, sizeof *values);
+ int *new_values = xnmalloc (n, sizeof *values);
size_t n_perms;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
n_perms = 1;
while (llx_next_permutation (llx_head (&list), llx_null (&list),
elemp[i] = x;
new_values[i] = e->x;
}
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct llx *min = llx_min (elemp[r0], elemp[r1],
compare_elements, &aux_data);
}
n_perms++;
}
- check (n_perms == factorial (cnt));
- check_list_contents (&list, values, cnt);
+ check (n_perms == factorial (n));
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
free (new_values);
}
}
{
const int max_elems = 4;
- int cnt_a, pat_a, cnt_b, pat_b;
+ int n_a, pat_a, n_b, pat_b;
- for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
- for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
- for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
- for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
+ for (n_a = 0; n_a <= max_elems; n_a++)
+ for (pat_a = 0; pat_a <= 1 << n_a; pat_a++)
+ for (n_b = 0; n_b <= max_elems; n_b++)
+ for (pat_b = 0; pat_b <= 1 << n_b; pat_b++)
{
struct llx_list list_a, list_b;
struct element **elems_a, **elems_b;
int a0, a1, b0, b1;
- allocate_pattern (cnt_a, pat_a,
+ allocate_pattern (n_a, pat_a,
&list_a, &elems_a, &elemp_a, &values_a);
- allocate_pattern (cnt_b, pat_b,
+ allocate_pattern (n_b, pat_b,
&list_b, &elems_b, &elemp_b, &values_b);
- for (a0 = 0; a0 <= cnt_a; a0++)
- for (a1 = a0; a1 <= cnt_a; a1++)
- for (b0 = 0; b0 <= cnt_b; b0++)
- for (b1 = b0; b1 <= cnt_b; b1++)
+ for (a0 = 0; a0 <= n_a; a0++)
+ for (a1 = a0; a1 <= n_a; a1++)
+ for (b0 = 0; b0 <= n_b; b0++)
+ for (b1 = b0; b1 <= n_b; b1++)
{
int a_ordering = lexicographical_compare_3way (
values_a + a0, a1 - a0,
check (a_ordering == b_ordering);
}
- free_elements (cnt_a, &list_a, elems_a, elemp_a, values_a);
- free_elements (cnt_b, &list_b, elems_b, elemp_b, values_b);
+ free_elements (n_a, &list_a, elems_a, elemp_a, values_a);
+ free_elements (n_b, &list_b, elems_b, elemp_b, values_b);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1;
+ int n, r0, r1;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct llx_list list;
struct element **elems;
int *next_output;
int j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
- output = next_output = xnmalloc (cnt, sizeof *output);
+ output = next_output = xnmalloc (n, sizeof *output);
llx_apply (elemp[r0], elemp[r1], apply_func, &next_output);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
llx_destroy (&list, NULL, NULL, &llx_malloc_mgr);
check (r1 - r0 == next_output - output);
for (j = 0; j < r1 - r0; j++)
check (output[j] == r0 + j);
- free_elements (cnt, NULL, elems, elemp, values);
+ free_elements (n, NULL, elems, elemp, values);
free (output);
}
}
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct llx_list list;
struct element **elems;
int *next_output;
int j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
- output = next_output = xnmalloc (cnt, sizeof *output);
+ output = next_output = xnmalloc (n, sizeof *output);
llx_destroy (&list, apply_func, &next_output, &llx_malloc_mgr);
- check (cnt == next_output - output);
- for (j = 0; j < cnt; j++)
+ check (n == next_output - output);
+ for (j = 0; j < n; j++)
check (output[j] == j);
- free_elements (cnt, NULL, elems, elemp, values);
+ free_elements (n, NULL, elems, elemp, values);
free (output);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1;
+ int n, r0, r1;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n <= max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct llx_list list;
struct element **elems;
int i, j;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
- check_list_contents (&list, values, cnt);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
+ check_list_contents (&list, values, n);
j = 0;
for (i = 0; i < r0; i++)
values[j++] = i;
for (i = r1 - 1; i >= r0; i--)
values[j++] = i;
- for (i = r1; i < cnt; i++)
+ for (i = r1; i < n; i++)
values[j++] = i;
llx_reverse (elemp[r0], elemp[r1]);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
test_permutations_no_dups (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct llx_list list;
struct element **elems;
int *values;
- int *old_values = xnmalloc (cnt, sizeof *values);
- int *new_values = xnmalloc (cnt, sizeof *values);
+ int *old_values = xnmalloc (n, sizeof *values);
+ int *new_values = xnmalloc (n, sizeof *values);
size_t n_perms;
- allocate_ascending (cnt, &list, &elems, NULL, &values);
+ allocate_ascending (n, &list, &elems, NULL, &values);
n_perms = 1;
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n);
while (llx_next_permutation (llx_head (&list), llx_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n);
+ check (lexicographical_compare_3way (new_values, n,
+ old_values, n,
sizeof *new_values,
compare_ints, NULL) > 0);
- memcpy (old_values, new_values, (cnt) * sizeof *old_values);
+ memcpy (old_values, new_values, (n) * sizeof *old_values);
n_perms++;
}
- check (n_perms == factorial (cnt));
- check_list_contents (&list, values, cnt);
+ check (n_perms == factorial (n));
+ check_list_contents (&list, values, n);
n_perms = 1;
llx_reverse (llx_head (&list), llx_null (&list));
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n);
while (llx_prev_permutation (llx_head (&list), llx_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n);
+ check (lexicographical_compare_3way (new_values, n,
+ old_values, n,
sizeof *new_values,
compare_ints, NULL) < 0);
- memcpy (old_values, new_values, (cnt) * sizeof *old_values);
+ memcpy (old_values, new_values, (n) * sizeof *old_values);
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
llx_reverse (llx_head (&list), llx_null (&list));
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, NULL, values);
+ free_elements (n, &list, elems, NULL, values);
free (old_values);
free (new_values);
}
const int max_dup = 3;
const int repetitions = 1024;
- int cnt, repeat;
-
- for (repeat = 0; repeat < repetitions; repeat++)
- for (cnt = 0; cnt < max_elems; cnt++)
+ for (int repeat = 0; repeat < repetitions; repeat++)
+ for (int n_elems = 0; n_elems < max_elems; n_elems++)
{
struct llx_list list;
struct element **elems;
int *new_values = xnmalloc (max_elems, sizeof *values);
unsigned int n_permutations;
- int left = cnt;
+ int left = n_elems;
int value = 0;
- allocate_elements (cnt, &list, &elems, &elemp, &values);
+ allocate_elements (n_elems, &list, &elems, &elemp, &values);
value = 0;
while (left > 0)
int n = rand () % max + 1;
while (n-- > 0)
{
- int idx = cnt - left--;
+ int idx = n_elems - left--;
values[idx] = elems[idx]->x = value;
}
value++;
}
n_permutations = 1;
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n_elems);
while (llx_next_permutation (llx_head (&list), llx_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n_elems);
+ check (lexicographical_compare_3way (new_values, n_elems,
+ old_values, n_elems,
sizeof *new_values,
compare_ints, NULL) > 0);
- memcpy (old_values, new_values, cnt * sizeof *old_values);
+ memcpy (old_values, new_values, n_elems * sizeof *old_values);
n_permutations++;
}
- check (n_permutations == expected_perms (values, cnt));
- check_list_contents (&list, values, cnt);
+ check (n_permutations == expected_perms (values, n_elems));
+ check_list_contents (&list, values, n_elems);
n_permutations = 1;
llx_reverse (llx_head (&list), llx_null (&list));
- extract_values (&list, old_values, cnt);
+ extract_values (&list, old_values, n_elems);
while (llx_prev_permutation (llx_head (&list), llx_null (&list),
compare_elements, &aux_data))
{
- extract_values (&list, new_values, cnt);
- check (lexicographical_compare_3way (new_values, cnt,
- old_values, cnt,
+ extract_values (&list, new_values, n_elems);
+ check (lexicographical_compare_3way (new_values, n_elems,
+ old_values, n_elems,
sizeof *new_values,
compare_ints, NULL) < 0);
n_permutations++;
}
llx_reverse (llx_head (&list), llx_null (&list));
- check (n_permutations == expected_perms (values, cnt));
- check_list_contents (&list, values, cnt);
+ check (n_permutations == expected_perms (values, n_elems));
+ check_list_contents (&list, values, n_elems);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n_elems, &list, elems, elemp, values);
free (old_values);
free (new_values);
}
{
const int max_elems = 8;
- int cnt, merge_pat, inc_pat, order;
+ int n, merge_pat, inc_pat, order;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
- for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (merge_pat = 0; merge_pat <= (1 << n); merge_pat++)
+ for (inc_pat = 0; inc_pat <= (1 << n); inc_pat++)
for (order = 0; order < 2; order++)
{
struct llx_list list;
int mid;
int i, j, k;
- allocate_elements (cnt, &list, &elems, &elemp, &values);
+ allocate_elements (n, &list, &elems, &elemp, &values);
j = 0;
- for (i = k = 0; i < cnt; i++)
+ for (i = k = 0; i < n; i++)
{
if (merge_pat & (1u << i))
elems[j++]->x = k;
k++;
}
mid = j;
- for (i = k = 0; i < cnt; i++)
+ for (i = k = 0; i < n; i++)
{
if (!(merge_pat & (1u << i)))
elems[j++]->x = k;
if (inc_pat & (1u << i))
k++;
}
- check (cnt == j);
+ check (n == j);
if (order == 0)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
elems[i]->y = i;
}
else
{
for (i = 0; i < mid; i++)
elems[i]->y = 100 + i;
- for (i = mid; i < cnt; i++)
+ for (i = mid; i < n; i++)
elems[i]->y = i;
}
j = 0;
- for (i = k = 0; i < cnt; i++)
+ for (i = k = 0; i < n; i++)
{
values[j++] = k;
if (inc_pat & (1u << i))
k++;
}
- check (cnt == j);
+ check (n == j);
if (order == 0)
- llx_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
+ llx_merge (elemp[0], elemp[mid], elemp[mid], elemp[n],
compare_elements, &aux_data);
else
- llx_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
+ llx_merge (elemp[mid], elemp[n], elemp[0], elemp[mid],
compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
check (llx_is_sorted (llx_head (&list), llx_null (&list),
compare_elements_x_y, &aux_data));
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
test_sort_exhaustive (void)
{
const int max_elems = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
struct llx_list list;
struct element **elems;
size_t n_perms;
- allocate_ascending (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_ascending (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
n_perms = 1;
while (llx_next_permutation (llx_head (&list), llx_null (&list),
struct llx_list perm_list;
int j;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
llx_init (&perm_list);
- for (j = 0; j < cnt; j++)
+ for (j = 0; j < n; j++)
{
perm_elems[j]->x = perm_values[j];
llx_push_tail (&perm_list, perm_elems[j], &llx_malloc_mgr);
}
llx_sort (llx_head (&perm_list), llx_null (&perm_list),
compare_elements, &aux_data);
- check_list_contents (&perm_list, values, cnt);
+ check_list_contents (&perm_list, values, n);
check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
compare_elements, &aux_data));
llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
- free_elements (cnt, &list, elems, NULL, values);
- free_elements (cnt, NULL, perm_elems, NULL, perm_values);
+ free_elements (n, &list, elems, NULL, values);
+ free_elements (n, NULL, perm_elems, NULL, perm_values);
}
}
test_sort_stable (void)
{
const int max_elems = 6;
- int cnt, inc_pat;
+ int n, inc_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (inc_pat = 0; inc_pat <= 1 << n; inc_pat++)
{
struct llx_list list;
struct element **elems;
size_t n_perms;
int i, j;
- allocate_elements (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_elements (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
j = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
elems[i]->x = values[i] = j;
if (inc_pat & (1 << i))
{
struct llx_list perm_list;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
llx_init (&perm_list);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
}
llx_sort (llx_head (&perm_list), llx_null (&perm_list),
compare_elements, &aux_data);
- check_list_contents (&perm_list, values, cnt);
+ check_list_contents (&perm_list, values, n);
check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
compare_elements_x_y, &aux_data));
llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
- free_elements (cnt, &list, elems, NULL, values);
- free_elements (cnt, NULL, perm_elems, NULL, perm_values);
+ free_elements (n, &list, elems, NULL, values);
+ free_elements (n, NULL, perm_elems, NULL, perm_values);
}
}
{
const int max_elems = 8;
- int cnt, r0, r1, repeat;
+ int n, r0, r1, repeat;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
for (repeat = 0; repeat < 100; repeat++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
{
struct llx_list list;
struct element **elems;
struct llx **elemp;
int *values;
- allocate_random (cnt, &list, &elems, &elemp, &values);
+ allocate_random (n, &list, &elems, &elemp, &values);
qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
llx_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
{
const int max_elems = 1024;
- int cnt;
+ int n;
- for (cnt = 0; cnt < max_elems; cnt++)
+ for (n = 0; n < max_elems; n++)
{
struct llx_list list;
struct element **elems;
int *values;
- allocate_random (cnt, &list, &elems, NULL, &values);
+ allocate_random (n, &list, &elems, NULL, &values);
- qsort (values, cnt, sizeof *values, compare_ints_noaux);
+ qsort (values, n, sizeof *values, compare_ints_noaux);
llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
- free_elements (cnt, &list, elems, NULL, values);
+ free_elements (n, &list, elems, NULL, values);
}
}
int *ascending = xnmalloc (max_elems, sizeof *ascending);
- int cnt, inc_pat, i, j, unique_values;
+ int n, inc_pat, i, j, unique_values;
for (i = 0; i < max_elems; i++)
ascending[i] = i;
- for (cnt = 0; cnt < max_elems; cnt++)
- for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
+ for (n = 0; n < max_elems; n++)
+ for (inc_pat = 0; inc_pat < (1 << n); inc_pat++)
{
struct llx_list list, dups;
struct element **elems;
int *values;
- allocate_elements (cnt, &list, &elems, NULL, &values);
+ allocate_elements (n, &list, &elems, NULL, &values);
j = unique_values = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
unique_values = j + 1;
elems[i]->x = values[i] = j;
if (inc_pat & (1 << i))
j++;
}
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
llx_init (&dups);
check (llx_unique (llx_head (&list), llx_null (&list),
llx_splice (llx_null (&list), llx_head (&dups), llx_null (&dups));
llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
- check_list_contents (&list, values, cnt);
+ check_list_contents (&list, values, n);
llx_destroy (&dups, NULL, NULL, &llx_malloc_mgr);
- free_elements (cnt, &list, elems, NULL, values);
+ free_elements (n, &list, elems, NULL, values);
}
free (ascending);
test_sort_unique (void)
{
const int max_elems = 7;
- int cnt, inc_pat;
+ int n, inc_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (inc_pat = 0; inc_pat <= 1 << n; inc_pat++)
{
struct llx_list list;
struct element **elems;
size_t n_perms;
int i, j;
- allocate_elements (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_elements (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
j = n_uniques = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
elems[i]->x = values[i] = j;
n_uniques = j + 1;
{
struct llx_list perm_list;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
llx_init (&perm_list);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
n_perms++;
}
- check (n_perms == expected_perms (values, cnt));
+ check (n_perms == expected_perms (values, n));
- free_elements (cnt, &list, elems, NULL, values);
- free_elements (cnt, NULL, perm_elems, NULL, perm_values);
+ free_elements (n, &list, elems, NULL, values);
+ free_elements (n, NULL, perm_elems, NULL, perm_values);
free (unique_values);
}
}
test_insert_ordered (void)
{
const int max_elems = 6;
- int cnt, inc_pat;
+ int n, inc_pat;
- for (cnt = 0; cnt <= max_elems; cnt++)
- for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
+ for (n = 0; n <= max_elems; n++)
+ for (inc_pat = 0; inc_pat <= 1 << n; inc_pat++)
{
struct llx_list list;
struct element **elems;
size_t n_perms;
int i, j;
- allocate_elements (cnt, &list, &elems, NULL, &values);
- allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
+ allocate_elements (n, &list, &elems, NULL, &values);
+ allocate_elements (n, NULL, &perm_elems, NULL, &perm_values);
j = 0;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
elems[i]->x = values[i] = j;
if (inc_pat & (1 << i))
{
struct llx_list perm_list;
- extract_values (&list, perm_values, cnt);
+ extract_values (&list, perm_values, n);
llx_init (&perm_list);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
n_perms++;
}
- check (n_perms == factorial (cnt));
+ check (n_perms == factorial (n));
- free_elements (cnt, &list, elems, NULL, values);
- free_elements (cnt, NULL, perm_elems, NULL, perm_values);
+ free_elements (n, &list, elems, NULL, values);
+ free_elements (n, NULL, perm_elems, NULL, perm_values);
}
}
{
const int max_elems = 10;
- int cnt;
+ int n;
unsigned int pbase;
int r0, r1;
- for (cnt = 0; cnt < max_elems; cnt++)
- for (r0 = 0; r0 <= cnt; r0++)
- for (r1 = r0; r1 <= cnt; r1++)
+ for (n = 0; n < max_elems; n++)
+ for (r0 = 0; r0 <= n; r0++)
+ for (r1 = r0; r1 <= n; r1++)
for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
{
struct llx_list list;
int first_false;
struct llx *part_llx;
- allocate_ascending (cnt, &list, &elems, &elemp, &values);
+ allocate_ascending (n, &list, &elems, &elemp, &values);
/* Check that llx_find_partition works okay in every
case. We use it after partitioning, too, but that
}
if (first_false == -1)
first_false = r1;
- for (i = r1; i < cnt; i++)
+ for (i = r1; i < n; i++)
values[j++] = i;
- check (j == cnt);
+ check (j == n);
/* Partition and check for expected results. */
check (llx_partition (elemp[r0], elemp[r1],
check (llx_find_partition (elemp[r0], elemp[r1],
pattern_pred, &pattern)
== elemp[first_false]);
- check_list_contents (&list, values, cnt);
- check ((int) llx_count (&list) == cnt);
+ check_list_contents (&list, values, n);
+ check ((int) llx_count (&list) == n);
- free_elements (cnt, &list, elems, elemp, values);
+ free_elements (n, &list, elems, elemp, values);
}
}
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT blocks in VALUES into the lexicographically
+/* Arranges the N blocks in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its blocks (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return a->start < b->start ? -1 : a->start > b->start;
}
-/* Checks that RM contains the ELEM_CNT elements described by
+/* Checks that RM contains the ELEM_N elements described by
ELEMENTS[]. */
static void
check_range_map (struct range_map *rm,
test_insert (void)
{
const int max_range = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_range; cnt++)
+ for (n = 1; n <= max_range; n++)
{
unsigned int n_compositions;
struct expected_element *expected;
int *order;
struct element *elements;
- expected = xnmalloc (cnt, sizeof *expected);
- widths = xnmalloc (cnt, sizeof *widths);
- order = xnmalloc (cnt, sizeof *order);
- elements = xnmalloc (cnt, sizeof *elements);
+ expected = xnmalloc (n, sizeof *expected);
+ widths = xnmalloc (n, sizeof *widths);
+ order = xnmalloc (n, sizeof *order);
+ elements = xnmalloc (n, sizeof *elements);
n_elems = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_elems, widths))
+ while (next_composition (n, &n_elems, widths))
{
int i, j;
unsigned int n_permutations;
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (widths);
test_delete (int gap)
{
const int max_range = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_range; cnt++)
+ for (n = 1; n <= max_range; n++)
{
unsigned int n_compositions;
struct expected_element *expected;
int *order;
struct element *elements;
- expected = xnmalloc (cnt, sizeof *expected);
- widths = xnmalloc (cnt, sizeof *widths);
- order = xnmalloc (cnt, sizeof *order);
- elements = xnmalloc (cnt, sizeof *elements);
+ expected = xnmalloc (n, sizeof *expected);
+ widths = xnmalloc (n, sizeof *widths);
+ order = xnmalloc (n, sizeof *order);
+ elements = xnmalloc (n, sizeof *elements);
n_elems = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_elems, widths))
+ while (next_composition (n, &n_elems, widths))
{
int i, j;
unsigned int n_permutations;
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (widths);
return rs;
}
-/* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
+/* Returns an unsigned int with bits OFS...OFS+N (exclusive)
set to 1, other bits set to 0. */
static unsigned int
-bit_range (unsigned int ofs, unsigned int cnt)
+bit_range (unsigned int ofs, unsigned int n)
{
assert (ofs < UINT_BIT);
- assert (cnt <= UINT_BIT);
- assert (ofs + cnt <= UINT_BIT);
+ assert (n <= UINT_BIT);
+ assert (ofs + n <= UINT_BIT);
- return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
+ return n < UINT_BIT ? ((1u << n) - 1) << ofs : UINT_MAX;
}
\f
/* Tests inserting all possible patterns into all possible range
return rt;
}
-/* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
+/* Returns an unsigned int with bits OFS...OFS+N (exclusive)
tower to 1, other bits tower to 0. */
static unsigned int
-bit_range (unsigned int ofs, unsigned int cnt)
+bit_range (unsigned int ofs, unsigned int n)
{
assert (ofs < UINT_BIT);
- assert (cnt <= UINT_BIT);
- assert (ofs + cnt <= UINT_BIT);
+ assert (n <= UINT_BIT);
+ assert (ofs + n <= UINT_BIT);
- return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
+ return n < UINT_BIT ? ((1u << n) - 1) << ofs : UINT_MAX;
}
\f
/* Tests setting all possible ranges of 1s into all possible range sets (up to
return *a < *b ? -1 : *a > *b;
}
-/* Checks that SPAR contains the CNT ints in DATA, that its
+/* Checks that SPAR contains the N ints in DATA, that its
structure is correct, and that certain operations on SPAR
produce the expected results. */
static void
check_sparse_array (struct sparse_array *spar,
- const unsigned long data[], size_t cnt)
+ const unsigned long data[], size_t n)
{
unsigned long idx;
unsigned long *order;
unsigned long *p;
size_t i;
- check (sparse_array_count (spar) == cnt);
+ check (sparse_array_count (spar) == n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
p = sparse_array_get (spar, data[i]);
check (p != NULL);
check (*p == data[i]);
}
- order = xmemdup (data, cnt * sizeof *data);
- qsort (order, cnt, sizeof *order, compare_unsigned_longs_noaux);
+ order = xmemdup (data, n * sizeof *data);
+ qsort (order, n, sizeof *order, compare_unsigned_longs_noaux);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
p = sparse_array_get (spar, order[i]);
check (p != NULL);
check (*p == order[i]);
}
- if (cnt > 0 && order[0] - 1 != order[cnt - 1])
+ if (n > 0 && order[0] - 1 != order[n - 1])
{
check (sparse_array_get (spar, order[0] - 1) == NULL);
check (!sparse_array_remove (spar, order[0] - 1));
}
- if (cnt > 0 && order[0] != order[cnt - 1] + 1)
+ if (n > 0 && order[0] != order[n - 1] + 1)
{
- check (sparse_array_get (spar, order[cnt - 1] + 1) == NULL);
- check (!sparse_array_remove (spar, order[cnt - 1] + 1));
+ check (sparse_array_get (spar, order[n - 1] + 1) == NULL);
+ check (!sparse_array_remove (spar, order[n - 1] + 1));
}
- for (i = 0, p = sparse_array_first (spar, &idx); i < cnt;
+ for (i = 0, p = sparse_array_first (spar, &idx); i < n;
i++, p = sparse_array_next (spar, idx, &idx))
{
check (p != NULL);
}
check (p == NULL);
- for (i = 0, p = sparse_array_last (spar, &idx); i < cnt;
+ for (i = 0, p = sparse_array_last (spar, &idx); i < n;
i++, p = sparse_array_prev (spar, idx, &idx))
{
check (p != NULL);
- check (idx == order[cnt - i - 1]);
- check (*p == order[cnt - i - 1]);
+ check (idx == order[n - i - 1]);
+ check (*p == order[n - i - 1]);
}
check (p == NULL);
free (order);
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
+/* Inserts the N values from 0 to N - 1 (inclusive) into a
sparse array in the order specified by INSERTIONS, then
deletes them in the order specified by DELETIONS, checking the
array's contents for correctness after each operation. */
static void
test_insert_delete (const unsigned long insertions[],
const unsigned long deletions[],
- size_t cnt)
+ size_t n)
{
struct sparse_array *spar;
size_t i;
spar = sparse_array_create (sizeof *insertions);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
unsigned long *p = sparse_array_insert (spar, insertions[i]);
*p = insertions[i];
check_sparse_array (spar, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
bool deleted = sparse_array_remove (spar, deletions[i]);
check (deleted);
- check_sparse_array (spar, deletions + i + 1, cnt - (i + 1));
+ check_sparse_array (spar, deletions + i + 1, n - (i + 1));
}
check_sparse_array (spar, NULL, 0);
sparse_array_destroy (spar);
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
+/* Inserts the N values from 0 to N - 1 (inclusive) into a
sparse array in the order specified by INSERTIONS, then
destroys the sparse array, to check that sparse_cases_destroy
properly frees all the nodes. */
static void
-test_destroy (const unsigned long insertions[], size_t cnt)
+test_destroy (const unsigned long insertions[], size_t n)
{
struct sparse_array *spar;
size_t i;
spar = sparse_array_create (sizeof *insertions);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
unsigned long *p = sparse_array_insert (spar, insertions[i]);
*p = insertions[i];
sparse_array_destroy (spar);
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
};
const size_t n_offsets = sizeof offsets / sizeof *offsets;
- int cnt = 100;
+ int n = 100;
unsigned long *insertions, *deletions;
const unsigned long *stride, *offset;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
for (stride = strides; stride < strides + n_strides; stride++)
{
printf ("%lu\n", *stride);
{
int k;
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
insertions[k] = *stride * k + *offset;
- test_insert_delete (insertions, insertions, cnt);
- test_destroy (insertions, cnt);
+ test_insert_delete (insertions, insertions, n);
+ test_destroy (insertions, n);
- for (k = 0; k < cnt; k++)
- deletions[k] = insertions[cnt - k - 1];
- test_insert_delete (insertions, deletions, cnt);
+ for (k = 0; k < n; k++)
+ deletions[k] = insertions[n - k - 1];
+ test_insert_delete (insertions, deletions, n);
- random_shuffle (insertions, cnt, sizeof *insertions);
- test_insert_delete (insertions, insertions, cnt);
- test_insert_delete (insertions, deletions, cnt);
+ random_shuffle (insertions, n, sizeof *insertions);
+ test_insert_delete (insertions, insertions, n);
+ test_insert_delete (insertions, deletions, n);
}
}
free (insertions);
free (deletions);
}
-/* Returns the index in ARRAY of the (CNT+1)th element that has
+/* Returns the index in ARRAY of the (N+1)th element that has
the TARGET value. */
static int
-scan_bools (bool target, bool array[], size_t cnt)
+scan_bools (bool target, bool array[], size_t n)
{
size_t i;
for (i = 0; ; i++)
- if (array[i] == target && cnt-- == 0)
+ if (array[i] == target && n-- == 0)
return i;
}
const int num_actions = 250000;
struct sparse_array *spar;
bool *has_values;
- int cnt;
+ int n;
int insert_chance;
int i;
has_values = xnmalloc (max_values, sizeof *has_values);
memset (has_values, 0, max_values * sizeof *has_values);
- cnt = 0;
+ n = 0;
insert_chance = 5;
spar = sparse_array_create (sizeof *values);
unsigned long *p;
int j;
- if (cnt == 0)
+ if (n == 0)
{
action = INSERT;
if (insert_chance < 9)
insert_chance++;
}
- else if (cnt == max_values)
+ else if (n == max_values)
{
action = DELETE;
if (insert_chance > 0)
int ins_index;
ins_index = scan_bools (false, has_values,
- rand () % (max_values - cnt));
+ rand () % (max_values - n));
assert (has_values[ins_index] == false);
has_values[ins_index] = true;
check (p != NULL);
*p = values[ins_index];
- cnt++;
+ n++;
}
else if (action == DELETE)
{
int del_index;
- del_index = scan_bools (true, has_values, rand () % cnt);
+ del_index = scan_bools (true, has_values, rand () % n);
assert (has_values[del_index] == true);
has_values[del_index] = false;
check (sparse_array_remove (spar, values[del_index]));
- cnt--;
+ n--;
}
else
abort ();
- check (sparse_array_count (spar) == cnt);
+ check (sparse_array_count (spar) == n);
for (j = 0; j < max_values; j++)
{
p = sparse_array_get (spar, values[j]);
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically next greater
+/* Arranges the N elements in VALUES into the lexicographically next greater
permutation. Returns true if successful. If VALUES is already the
lexicographically greatest permutation of its elements (i.e. ordered from
greatest to smallest), arranges them into the lexicographically least
Comparisons among elements of VALUES consider only the bits in KEY_MASK. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if ((values[i] & KEY_MASK) < (values[i + 1] & KEY_MASK))
{
size_t j;
- for (j = cnt - 1;
+ for (j = n - 1;
(values[i] & KEY_MASK) >= (values[j] & KEY_MASK);
j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
free (tmp);
}
-/* Checks that MAP contains the CNT strings in DATA, that its structure is
+/* Checks that MAP contains the N strings in DATA, that its structure is
correct, and that certain operations on MAP produce the expected results. */
static void
-check_string_map (struct string_map *map, const int data[], size_t cnt)
+check_string_map (struct string_map *map, const int data[], size_t n)
{
size_t i;
- check (string_map_is_empty (map) == (cnt == 0));
- check (string_map_count (map) == cnt);
+ check (string_map_is_empty (map) == (n == 0));
+ check (string_map_count (map) == n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
struct string_map_node *node;
const char *key = make_key (data[i]);
check (string_map_find_node (map, "") == NULL);
check (!string_map_delete (map, "xyz"));
- if (cnt == 0)
+ if (n == 0)
check (string_map_first (map) == NULL);
else
{
int *data_copy;
int left;
- data_copy = xmemdup (data, cnt * sizeof *data);
- left = cnt;
- for (node = string_map_first (map), i = 0; i < cnt;
+ data_copy = xmemdup (data, n * sizeof *data);
+ left = n;
+ for (node = string_map_first (map), i = 0; i < n;
node = string_map_next (map, node), i++)
{
const char *key = string_map_node_get_key (node);
}
}
-/* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
+/* Inserts the N strings from 0 to N - 1 (inclusive) into a map in the
order specified by INSERTIONS, then deletes them in the order specified by
DELETIONS, checking the map's contents for correctness after each
operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct string_map map;
size_t i;
string_map_init (&map);
check_string_map (&map, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (string_map_insert (&map, make_key (insertions[i]),
make_value (insertions[i])));
check_string_map (&map, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (string_map_delete (&map, make_key (deletions[i])));
- check_string_map (&map, deletions + i + 1, cnt - i - 1);
+ check_string_map (&map, deletions + i + 1, n - i - 1);
}
string_map_destroy (&map);
}
{
const int basis = 0;
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, basis);
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i | random_value (i, basis);
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i | random_value (i, 1);
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, 2);
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
const int basis = 3;
const int max_elems = 64;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, basis);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i | random_value (i, basis);
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
const int basis = 15;
enum { MAX_ELEMS = 16 };
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
+ for (n = 0; n <= MAX_ELEMS; n++)
{
int insertions[MAX_ELEMS];
int trial;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
insertions[i] = (i / 2) | random_value (i, basis);
for (trial = 0; trial < max_trials; trial++)
/* Insert with replacement in random order. */
n_data = 0;
string_map_init (&map);
- random_shuffle (insertions, cnt, sizeof *insertions);
- for (i = 0; i < cnt; i++)
+ random_shuffle (insertions, n, sizeof *insertions);
+ for (i = 0; i < n; i++)
{
const char *key = make_key (insertions[i]);
const char *value = make_value (insertions[i]);
}
/* Delete in original order. */
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
const char *expected_value;
char *value;
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
free (tmp);
}
-/* Checks that SET contains the CNT strings in DATA, that its structure is
+/* Checks that SET contains the N strings in DATA, that its structure is
correct, and that certain operations on SET produce the expected results. */
static void
-check_string_set (struct string_set *set, const int data[], size_t cnt)
+check_string_set (struct string_set *set, const int data[], size_t n)
{
size_t i;
- check (string_set_is_empty (set) == (cnt == 0));
- check (string_set_count (set) == cnt);
+ check (string_set_is_empty (set) == (n == 0));
+ check (string_set_count (set) == n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
struct string_set_node *node;
const char *s = make_string (data[i]);
check (!string_set_contains (set, "xxx"));
check (string_set_find_node (set, "") == NULL);
- if (cnt == 0)
+ if (n == 0)
check (string_set_first (set) == NULL);
else
{
int *data_copy;
int left;
- data_copy = xmemdup (data, cnt * sizeof *data);
- left = cnt;
- for (node = string_set_first (set), i = 0; i < cnt;
+ data_copy = xmemdup (data, n * sizeof *data);
+ left = n;
+ for (node = string_set_first (set), i = 0; i < n;
node = string_set_next (set, node), i++)
{
const char *s = string_set_node_get_string (node);
}
}
-/* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
+/* Inserts the N strings from 0 to N - 1 (inclusive) into a set in the
order specified by INSERTIONS, then deletes them in the order specified by
DELETIONS, checking the set's contents for correctness after each
operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct string_set set;
size_t i;
string_set_init (&set);
check_string_set (&set, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (string_set_insert (&set, make_string (insertions[i])));
check_string_set (&set, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (string_set_delete (&set, make_string (deletions[i])));
- check_string_set (&set, deletions + i + 1, cnt - i - 1);
+ check_string_set (&set, deletions + i + 1, n - i - 1);
}
string_set_destroy (&set);
}
test_insert_any_remove_any (void)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
{
const int max_elems = 64;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically next greater
+/* Arranges the N elements in VALUES into the lexicographically next greater
permutation. Returns true if successful. If VALUES is already the
lexicographically greatest permutation of its elements (i.e. ordered from
greatest to smallest), arranges them into the lexicographically least
Comparisons among elements of VALUES consider only the bits in KEY_MASK. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if ((values[i] & KEY_MASK) < (values[i + 1] & KEY_MASK))
{
size_t j;
- for (j = cnt - 1;
+ for (j = n - 1;
(values[i] & KEY_MASK) >= (values[j] & KEY_MASK);
j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
check (!strcmp (found_value, value));
}
-/* Checks that MAP contains the CNT strings in DATA, that its structure is
+/* Checks that MAP contains the N strings in DATA, that its structure is
correct, and that certain operations on MAP produce the expected results. */
static void
-check_stringi_map (struct stringi_map *map, const int data[], size_t cnt)
+check_stringi_map (struct stringi_map *map, const int data[], size_t n)
{
size_t i;
- check (stringi_map_is_empty (map) == (cnt == 0));
- check (stringi_map_count (map) == cnt);
+ check (stringi_map_is_empty (map) == (n == 0));
+ check (stringi_map_count (map) == n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
const char *key = make_key (data[i]);
const char *value = make_value (data[i]);
check (stringi_map_find_node (map, "", 0) == NULL);
check (!stringi_map_delete (map, "xyz"));
- if (cnt == 0)
+ if (n == 0)
check (stringi_map_first (map) == NULL);
else
{
int *data_copy;
int left;
- data_copy = xmemdup (data, cnt * sizeof *data);
- left = cnt;
- for (node = stringi_map_first (map), i = 0; i < cnt;
+ data_copy = xmemdup (data, n * sizeof *data);
+ left = n;
+ for (node = stringi_map_first (map), i = 0; i < n;
node = stringi_map_next (map, node), i++)
{
const char *key = stringi_map_node_get_key (node);
}
}
-/* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
+/* Inserts the N strings from 0 to N - 1 (inclusive) into a map in the
order specified by INSERTIONS, then deletes them in the order specified by
DELETIONS, checking the map's contents for correctness after each
operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct stringi_map map;
size_t i;
stringi_map_init (&map);
check_stringi_map (&map, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (stringi_map_insert (&map, make_key (insertions[i]),
make_value (insertions[i])));
check_stringi_map (&map, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (stringi_map_delete (&map, make_key (deletions[i])));
- check_stringi_map (&map, deletions + i + 1, cnt - i - 1);
+ check_stringi_map (&map, deletions + i + 1, n - i - 1);
}
stringi_map_destroy (&map);
}
{
const int basis = 0;
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, basis);
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i | random_value (i, basis);
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i | random_value (i, 1);
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, 2);
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
const int basis = 3;
const int max_elems = 64;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, basis);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i | random_value (i, basis);
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
const int basis = 15;
enum { MAX_ELEMS = 16 };
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
+ for (n = 0; n <= MAX_ELEMS; n++)
{
int insertions[MAX_ELEMS];
int trial;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
insertions[i] = (i / 2) | random_value (i, basis);
for (trial = 0; trial < max_trials; trial++)
/* Insert with replacement in random order. */
n_data = 0;
stringi_map_init (&map);
- random_shuffle (insertions, cnt, sizeof *insertions);
- for (i = 0; i < cnt; i++)
+ random_shuffle (insertions, n, sizeof *insertions);
+ for (i = 0; i < n; i++)
{
const char *key = make_key (insertions[i]);
const char *value = make_value (insertions[i]);
}
/* Delete in original order. */
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
const char *expected_value;
char *value;
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
check (!utf8_strcasecmp (string, stringi_set_node_get_string (node)));
}
-/* Checks that SET contains the CNT strings in DATA, that its structure is
+/* Checks that SET contains the N strings in DATA, that its structure is
correct, and that certain operations on SET produce the expected results. */
static void
-check_stringi_set (struct stringi_set *set, const int data[], size_t cnt)
+check_stringi_set (struct stringi_set *set, const int data[], size_t n)
{
size_t i;
- check (stringi_set_is_empty (set) == (cnt == 0));
- check (stringi_set_count (set) == cnt);
+ check (stringi_set_is_empty (set) == (n == 0));
+ check (stringi_set_count (set) == n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
const char *s;
char copy[16];
check (!stringi_set_contains (set, "xxx"));
check (stringi_set_find_node (set, "") == NULL);
- if (cnt == 0)
+ if (n == 0)
{
check (stringi_set_first (set) == NULL);
free (stringi_set_get_array (set));
int left;
array = stringi_set_get_array (set);
- data_copy = xmemdup (data, cnt * sizeof *data);
- left = cnt;
- for (node = stringi_set_first (set), i = 0; i < cnt;
+ data_copy = xmemdup (data, n * sizeof *data);
+ left = n;
+ for (node = stringi_set_first (set), i = 0; i < n;
node = stringi_set_next (set, node), i++)
{
const char *s = stringi_set_node_get_string (node);
free (array);
array = stringi_set_get_sorted_array (set);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
if (i > 0)
check (utf8_strcasecmp (array[i - 1], array[i]) < 0);
}
}
-/* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
+/* Inserts the N strings from 0 to N - 1 (inclusive) into a set in the
order specified by INSERTIONS, then deletes them in the order specified by
DELETIONS, checking the set's contents for correctness after each
operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct stringi_set set;
size_t i;
stringi_set_init (&set);
check_stringi_set (&set, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (stringi_set_insert (&set, make_string (insertions[i])));
check_stringi_set (&set, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (stringi_set_delete (&set, make_string (deletions[i])));
- check_stringi_set (&set, deletions + i + 1, cnt - i - 1);
+ check_stringi_set (&set, deletions + i + 1, n - i - 1);
}
stringi_set_destroy (&set);
}
test_insert_any_remove_any (void)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
{
const int max_elems = 64;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT blocks in VALUES into the lexicographically
+/* Arranges the N blocks in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its blocks (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
int x; /* Expected value for `x' member. */
};
-/* Checks that tower T contains the BLOCK_CNT blocks described by
+/* Checks that tower T contains the BLOCK_N blocks described by
BLOCKS[]. */
static void
check_tower (struct tower *t,
test_insert (void)
{
const int max_height = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
unsigned int n_compositions;
struct expected_block *expected;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
n_blocks = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_blocks, sizes))
+ while (next_composition (n, &n_blocks, sizes))
{
int i, j;
unsigned int n_permutations;
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (sizes);
test_delete (void)
{
const int max_height = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
unsigned int n_compositions;
struct expected_block *expected;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
n_blocks = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_blocks, sizes))
+ while (next_composition (n, &n_blocks, sizes))
{
int i;
unsigned int n_permutations;
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (sizes);
test_resize (void)
{
const int max_height = 9;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
unsigned int n_compositions;
struct expected_block *expected;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- new_sizes = xnmalloc (cnt, sizeof *new_sizes);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ new_sizes = xnmalloc (n, sizeof *new_sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
n_blocks = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_blocks, sizes))
+ while (next_composition (n, &n_blocks, sizes))
{
int i;
unsigned int resizes = 0;
- for (resizes = 0, first_k_composition (cnt, n_blocks, new_sizes);
+ for (resizes = 0, first_k_composition (n, n_blocks, new_sizes);
(resizes == 0
- || next_k_composition (cnt, n_blocks, new_sizes));
+ || next_k_composition (n, n_blocks, new_sizes));
resizes++)
{
struct tower t;
}
check_tower (&t, expected, n_blocks);
}
- check (resizes == binomial_cofficient (cnt - 1, n_blocks - 1));
+ check (resizes == binomial_cofficient (n - 1, n_blocks - 1));
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (new_sizes);
test_splice_out (void)
{
const int max_height = 9;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
unsigned int n_compositions;
struct expected_block *expected;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- new_sizes = xnmalloc (cnt, sizeof *new_sizes);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ new_sizes = xnmalloc (n, sizeof *new_sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
n_blocks = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_blocks, sizes))
+ while (next_composition (n, &n_blocks, sizes))
{
int i, j;
}
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (new_sizes);
test_splice_in (void)
{
const int max_height = 9;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
unsigned int n_compositions;
struct expected_block *expected;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- new_sizes = xnmalloc (cnt, sizeof *new_sizes);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ new_sizes = xnmalloc (n, sizeof *new_sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
n_blocks = 0;
n_compositions = 0;
- while (next_composition (cnt, &n_blocks, sizes))
+ while (next_composition (n, &n_blocks, sizes))
{
int i, j;
}
n_compositions++;
}
- check (n_compositions == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (new_sizes);
projects / pspp / commitdiff