3 * \brief The sn_stage_t class and associated methods.
6 * libsortnetwork - src/sn_stage.h
7 * Copyright (C) 2008-2010 Florian octo Forster
9 * This library is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU Lesser General Public License as published by
11 * the Free Software Foundation; either version 2.1 of the License, or (at
12 * your option) any later version.
14 * This library is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
19 * You should have received a copy of the GNU Lesser General Public License
20 * along with this library; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 * Florian octo Forster <ff at octo.it>
35 #include "sn_comparator.h"
38 * Struct representing a stage of the comparator network. Don't modify this
39 * struct yourself, use the sn_stage_* methods instead.
43 int depth; /**< Depth of this stage, where zero means closest to the input. */
44 sn_comparator_t *comparators; /**< Pointer to a list of comparators contained in this stage. */
45 int comparators_num; /**< Number of comparators in this stage. */
47 typedef struct sn_stage_s sn_stage_t;
50 * Direction into which to cut.
52 * \see sn_network_cut_at, sn_stage_cut_at
54 enum sn_network_cut_dir_e
56 DIR_MIN, /**< Assume negative infinity. */
57 DIR_MAX /**< Assume positive infinity. */
60 #define SN_STAGE_DEPTH(s) (s)->depth
61 #define SN_STAGE_COMP_NUM(s) (s)->comparators_num
62 #define SN_STAGE_COMP_GET(s,n) ((s)->comparators + (n))
65 * Creates an empty stage and returns a pointer to it. The stage must be freed
66 * using sn_stage_destroy().
68 * \param depth Depth of the stage within the comparator network. This will be
69 * re-set by sn_network_stage_add().
70 * \return Pointer to the comparator network or \c NULL on error.
72 sn_stage_t *sn_stage_create (int depth);
75 * Clones an existing stage.
77 * \param s Stage to clone.
78 * \return Copied stage or \c NULL on error. The returned stage must be freed
79 * using sn_stage_destroy().
81 sn_stage_t *sn_stage_clone (const sn_stage_t *s);
84 * Destroys a stage allocated with sn_stage_create() or one of the other
85 * methods returning a \c sn_stage_t. This frees all allocated space.
87 * \param s The stage to destroy. May be \c NULL.
89 void sn_stage_destroy (sn_stage_t *s);
92 * Applies a stage to an array of integers.
94 * \param s Pointer to the stage.
95 * \param[in,out] values Pointer to integer values to sort. The number of
96 * integer values pointed to must be at least the number of inputs of the
97 * comparator network. Otherwise, segmentation faults or memory corruption
99 * \return Zero on success, non-zero on failure.
100 * \see sn_network_sort
102 int sn_stage_sort (sn_stage_t *s, int *values);
105 * Adds a comparator to a stage. If this would return in a conflict (a
106 * comparator using on of the line already exists in this stage) an error is
109 * \param s Pointer to the stage.
110 * \param c Pointer to a comparator to add. The given comparator is copied. It
111 * is the caller's responsibility to free c.
112 * \return Zero on success, non-zero on failure.
113 * \see sn_stage_comparator_remove
115 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c);
119 * Removed a comparator from a stage.
121 * \param s The stage from which to remove the comparator.
122 * \param index The index of the comparator to remove.
123 * \return Zero on success, non-zero on failure.
124 * \see sn_stage_comparator_add
126 int sn_stage_comparator_remove (sn_stage_t *s, int index);
129 * Checks whether the given comparator can be added to a stage, i.e. if neither
130 * line if used by another comparator.
132 * \param s Pointer to the stage.
133 * \param c Pointer to the comparator.
134 * \return Zero if there is no conflict, one if there is a conflict and two if
135 * the comparator is already present in the stage.
137 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c);
140 * Prints the stage to \c STDOUT using a human readable representation.
142 * \param s The comparator network to display.
143 * \return Zero on success, non-zero on failure.
144 * \see sn_network_show
146 int sn_stage_show (sn_stage_t *s);
149 * Inverts a stage by switching the direction of all comparators.
151 * \param s The stage to invert.
152 * \return Zero on success, non-zero on failure.
153 * \see sn_network_invert
155 int sn_stage_invert (sn_stage_t *s);
158 * Shifts a stage (permutes the inputs). Each input is shifted \c sw positions,
159 * higher inputs are "wrapped around".
161 * \param s The stage to shift.
162 * \param sw The number of positions to shift.
163 * \param inputs_num The number of inputs of the comparator network. This value
164 * is used to "wrap around" inputs.
165 * \return Zero on success, non-zero on failure.
167 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num);
169 int sn_stage_unify (sn_stage_t *s);
172 * Swaps two lines. This is used by the algorithm used in
173 * sn_network_normalize() to transform non-standard sort networks to standard
176 * \param s The stage on which to operate.
177 * \param con0 Index of the first line.
178 * \param con1 Index of the second line.
179 * \return Zero on success, non-zero on failure.
180 * \see sn_network_normalize(), sn_comparator_swap()
182 int sn_stage_swap (sn_stage_t *s, int con0, int con1);
185 * Removes an input / line by assuming positive or negative infinity is applied
188 * \param s The stage to work with.
189 * \param input The input / line on which is assumed to be positive or negative
191 * \param dir Direction in which to cut; whether positive or negative infinity
193 * \return The new position of the infinite value on success or less than zero
195 * \see sn_network_cut_at
197 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir);
199 /* FIXME: Documentation */
200 int sn_stage_cut (sn_stage_t *s, int *mask, sn_stage_t **prev);
203 * Remove an input from a stage, remove all touching comparators and adapt the
204 * input indexes of all remaining comparators.
206 * \param s The stage from which to remove the input.
207 * \param input The index of the line which to remove.
208 * \return Zero on success, non-zero on failure.
210 int sn_stage_remove_input (sn_stage_t *s, int input);
213 * Reads a stage from a \c FILE pointer and return the newly allocated stage.
215 * \param fh The file handle.
216 * \return Pointer to a newly allocated stage or \c NULL on error.
217 * \see sn_stage_write
219 sn_stage_t *sn_stage_read (FILE *fh);
222 * Writes a stage to a \c FILE pointer.
224 * \param s The stage to write.
225 * \param fh The file handle to write to.
226 * \return Zero on success, non-zero on failure.
229 int sn_stage_write (sn_stage_t *s, FILE *fh);
232 * Creates a serialized form of the given stage. The serialized form is
233 * byte-order independent and can easily be sent over a computer network.
235 * \param s The stage to serialize.
236 * \param[out] ret_buffer Pointer to a pointer into which the location of the
237 * allocated memory will be written. It is the caller's responsibility to
239 * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
240 * allocated memory will be written.
241 * \return Zero on success, non-zero on failure.
242 * \see sn_stage_unserialize(), sn_network_serialize()
244 int sn_stage_serialize (sn_stage_t *s,
245 char **ret_buffer, size_t *ret_buffer_size);
248 * Creates a stage from its serialized form.
250 * \param buffer Pointer to a buffer containing the stage in serialized form.
251 * \param buffer_size Size of the buffer (in bytes).
252 * \return Pointer to the newly allocated stage or \c NULL on error.
253 * \see sn_stage_serialize(), sn_network_unserialize()
255 sn_stage_t *sn_stage_unserialize (char **buffer, size_t *buffer_size);
257 uint64_t sn_stage_get_hashval (const sn_stage_t *s);
259 #endif /* SN_STAGE_H */
261 /* vim: set shiftwidth=2 softtabstop=2 : */