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 program is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License as published by the
11 * Free Software Foundation; only version 2 of the License is applicable.
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 * Florian octo Forster <ff at octo.it>
32 #include "sn_comparator.h"
35 * Struct representing a stage of the comparator network. Don't modify this
36 * struct yourself, use the sn_stage_* methods instead.
40 int depth; /**< Depth of this stage, where zero means closest to the input. */
41 sn_comparator_t *comparators; /**< Pointer to a list of comparators contained in this stage. */
42 int comparators_num; /**< Number of comparators in this stage. */
44 typedef struct sn_stage_s sn_stage_t;
47 * Direction into which to cut.
49 * \see sn_network_cut_at, sn_stage_cut_at
51 enum sn_network_cut_dir_e
53 DIR_MIN, /**< Assume negative infinity. */
54 DIR_MAX /**< Assume positive infinity. */
57 #define SN_STAGE_DEPTH(s) (s)->depth
58 #define SN_STAGE_COMP_NUM(s) (s)->comparators_num
59 #define SN_STAGE_COMP_GET(s,n) ((s)->comparators + (n))
62 * Creates an empty stage and returns a pointer to it. The stage must be freed
63 * using sn_stage_destroy().
65 * \param depth Depth of the stage within the comparator network. This will be
66 * re-set by sn_network_stage_add().
67 * \return Pointer to the comparator network or \c NULL on error.
69 sn_stage_t *sn_stage_create (int depth);
72 * Clones an existing stage.
74 * \param s Stage to clone.
75 * \return Copied stage or \c NULL on error. The returned stage must be freed
76 * using sn_stage_destroy().
78 sn_stage_t *sn_stage_clone (const sn_stage_t *s);
81 * Destroys a stage allocated with sn_stage_create() or one of the other
82 * methods returning a \c sn_stage_t. This frees all allocated space.
84 * \param s The stage to destroy. May be \c NULL.
86 void sn_stage_destroy (sn_stage_t *s);
89 * Applies a stage to an array of integers.
91 * \param s Pointer to the stage.
92 * \param[in,out] values Pointer to integer values to sort. The number of
93 * integer values pointed to must be at least the number of inputs of the
94 * comparator network. Otherwise, segmentation faults or memory corruption
96 * \return Zero on success, non-zero on failure.
97 * \see sn_network_sort
99 int sn_stage_sort (sn_stage_t *s, int *values);
102 * Adds a comparator to a stage. If this would return in a conflict (a
103 * comparator using on of the line already exists in this stage) an error is
106 * \param s Pointer to the stage.
107 * \param c Pointer to a comparator to add. The given comparator is copied. It
108 * is the caller's responsibility to free c.
109 * \return Zero on success, non-zero on failure.
110 * \see sn_stage_comparator_remove
112 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c);
116 * Removed a comparator from a stage.
118 * \param s The stage from which to remove the comparator.
119 * \param index The index of the comparator to remove.
120 * \return Zero on success, non-zero on failure.
121 * \see sn_stage_comparator_add
123 int sn_stage_comparator_remove (sn_stage_t *s, int index);
126 * Checks whether the given comparator can be added to a stage, i.e. if neither
127 * line if used by another comparator.
129 * \param s Pointer to the stage.
130 * \param c Pointer to the comparator.
131 * \return Zero if there is no conflict, one if there is a conflict and two if
132 * the comparator is already present in the stage.
134 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c);
137 * Prints the stage to \c STDOUT using a human readable representation.
139 * \param s The comparator network to display.
140 * \return Zero on success, non-zero on failure.
141 * \see sn_network_show
143 int sn_stage_show (sn_stage_t *s);
146 * Inverts a stage by switching the direction of all comparators.
148 * \param s The stage to invert.
149 * \return Zero on success, non-zero on failure.
150 * \see sn_network_invert
152 int sn_stage_invert (sn_stage_t *s);
155 * Shifts a stage (permutes the inputs). Each input is shifted \c sw positions,
156 * higher inputs are "wrapped around".
158 * \param s The stage to shift.
159 * \param sw The number of positions to shift.
160 * \param inputs_num The number of inputs of the comparator network. This value
161 * is used to "wrap around" inputs.
162 * \return Zero on success, non-zero on failure.
164 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num);
167 * Swaps two lines. This is used by the algorithm used in
168 * sn_network_normalize() to transform non-standard sort networks to standard
171 * \param s The stage on which to operate.
172 * \param con0 Index of the first line.
173 * \param con1 Index of the second line.
174 * \return Zero on success, non-zero on failure.
175 * \see sn_network_normalize(), sn_comparator_swap()
177 int sn_stage_swap (sn_stage_t *s, int con0, int con1);
180 * Removes an input / line by assuming positive or negative infinity is applied
183 * \param s The stage to work with.
184 * \param input The input / line on which is assumed to be positive or negative
186 * \param dir Direction in which to cut; whether positive or negative infinity
188 * \return The new position of the infinite value on success or less than zero
190 * \see sn_network_cut_at
192 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir);
195 * Remove an input from a stage, remove all touching comparators and adapt the
196 * input indexes of all remaining comparators.
198 * \param s The stage from which to remove the input.
199 * \param input The index of the line which to remove.
200 * \return Zero on success, non-zero on failure.
202 int sn_stage_remove_input (sn_stage_t *s, int input);
205 * Reads a stage from a \c FILE pointer and return the newly allocated stage.
207 * \param fh The file handle.
208 * \return Pointer to a newly allocated stage or \c NULL on error.
209 * \see sn_stage_write
211 sn_stage_t *sn_stage_read (FILE *fh);
214 * Writes a stage to a \c FILE pointer.
216 * \param s The stage to write.
217 * \param fh The file handle to write to.
218 * \return Zero on success, non-zero on failure.
221 int sn_stage_write (sn_stage_t *s, FILE *fh);
224 * Creates a serialized form of the given stage. The serialized form is
225 * byte-order independent and can easily be sent over a computer network.
227 * \param s The stage to serialize.
228 * \param[out] ret_buffer Pointer to a pointer into which the location of the
229 * allocated memory will be written. It is the caller's responsibility to
231 * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
232 * allocated memory will be written.
233 * \return Zero on success, non-zero on failure.
234 * \see sn_stage_unserialize(), sn_network_serialize()
236 int sn_stage_serialize (sn_stage_t *s,
237 char **ret_buffer, size_t *ret_buffer_size);
240 * Creates a stage from its serialized form.
242 * \param buffer Pointer to a buffer containing the stage in serialized form.
243 * \param buffer_size Size of the buffer (in bytes).
244 * \return Pointer to the newly allocated stage or \c NULL on error.
245 * \see sn_stage_serialize(), sn_network_unserialize()
247 sn_stage_t *sn_stage_unserialize (char **buffer, size_t *buffer_size);
249 #endif /* SN_STAGE_H */
251 /* vim: set shiftwidth=2 softtabstop=2 : */