3 * \brief The sn_network_t class and associated methods.
5 * This is more details about what this file does.
8 * libsortnetwork - src/sn_network.h
9 * Copyright (C) 2008-2010 Florian octo Forster
11 * This program is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by the
13 * Free Software Foundation; only version 2 of the License is applicable.
15 * This program is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
20 * You should have received a copy of the GNU General Public License along
21 * with this program; if not, write to the Free Software Foundation, Inc.,
22 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25 * Florian octo Forster <ff at octo.it>
30 #define SN_NETWORK_H 1
34 #include "sn_comparator.h"
38 * The global struct representing a comparator or sort network.
42 int inputs_num; /**< Number of inputs of the comparator network. */
43 sn_stage_t **stages; /**< Array of pointers to the stages of a comparator network. */
44 int stages_num; /**< Number of stages in this comparator network. */
46 typedef struct sn_network_s sn_network_t;
48 #define SN_NETWORK_STAGE_NUM(n) (n)->stages_num
49 #define SN_NETWORK_STAGE_GET(n,i) ((n)->stages[i])
50 #define SN_NETWORK_INPUT_NUM(n) (n)->inputs_num
53 * Creates an empty comparator network and returns a pointer to it. The
54 * comparator network must be freed using sn_network_destroy().
56 * \param inputs_num Number of inputs the comparator network has.
57 * \return Pointer to the comparator network or \c NULL on error.
59 sn_network_t *sn_network_create (int inputs_num);
62 * Clones an existing comparator network.
64 * \param n Comparator network to clone.
65 * \return Copied sort network or \c NULL on error. The returned network must
66 * be freed using sn_network_destroy().
68 sn_network_t *sn_network_clone (const sn_network_t *n);
71 * Destroys a comparator network allocated with sn_network_create() or one of
72 * the other methods returning a \c sn_network_t. This frees all allocated
75 * \param n The comparator network to destroy. May be \c NULL.
77 void sn_network_destroy (sn_network_t *n);
80 * Creates a new sort network using Batcher's Odd-Even-Mergesort algorithm.
82 * \param inputs_num Number of inputs / outputs of the sorting network.
83 * \return A pointer to the newly allocated sorting network or \c NULL if an
84 * invalid number of inputs was given or allocation failed.
86 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
89 * Creates a new sorting network using the Pairwise sorting algorithm published
91 * \param inputs_num Number of inputs / outputs of the sorting network.
92 * \return A pointer to the newly allocated sorting network or \c NULL if an
93 * invalid number of inputs was given or allocation failed.
95 sn_network_t *sn_network_create_pairwise (int inputs_num);
98 * Append another network to a given network.
100 * \param n The comparator network to which the other network is added. This
101 * network is modified.
102 * \param other The network to be added to the first network. This network is
103 * consumed by this function and the memory pointed to is freed. You cannot
104 * use that network after this call, so use sn_network_clone() if required.
105 * \return Zero on success, non-zero on failure.
107 int sn_network_network_add (sn_network_t *n, sn_network_t *other);
110 * Append a new stage to a comparator network.
112 * \param n The comparator network to which to add the stage.
113 * \param s A pointer to a stage. The memory pointed to by this parameter is
114 * not copied and freed by sn_network_destroy(). It is the caller's
115 * responsibility to call sn_stage_clone() if appropriate.
116 * \return Zero on success, non-zero on failure.
118 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s);
121 * Remove a stage from a comparator network.
123 * \param n A pointer to the comparator network to modify.
124 * \param s_num The depth of the comparator network to remove, with zero being
125 * meaning the stage closest to the inputs.
126 * \return Zero on success, non-zero on failure.
128 int sn_network_stage_remove (sn_network_t *n, int s_num);
131 * Adds a comparator to a comparator network. The code tries to add the
132 * comparator to the last stage, i.e. the stage closest to the outputs. If this
133 * is not possible, because one line is used by another comparator, a new stage
134 * is created and appended to the sorting network.
136 * \param n Pointer to the comparator netork.
137 * \param c Pointer to a comparator to add. The given comparator is copied. It
138 * is the caller's responsibility to free c.
139 * \return Zero on success, non-zero on failure.
141 int sn_network_comparator_add (sn_network_t *n, const sn_comparator_t *c);
144 * Returns the number of comparators contained in the comparator network. This
145 * will traverse all comparators in all stages, resulting in a running time of
146 * \f$ \mathcal{O}(n) \f$.
148 * \param n Comparator network to work with.
149 * \return The number of comparators contained in the network or less than zero
150 * on error (\c n is \c NULL).
152 int sn_network_get_comparator_num (const sn_network_t *n);
155 * Applies a comparator network to an array of integers. This is implemented by
156 * calling sn_stage_sort() with every stage of the network.
158 * \param n Pointer to the comparator netork.
159 * \param[in,out] values Pointer to integer values to sort. The number of
160 * integer values pointed to must be at least the number of inputs of the
161 * comparator network. Otherwise, segmentation faults or memory corruption
163 * \return Zero on success, non-zero on failure.
166 int sn_network_sort (sn_network_t *n, int *values);
169 * Checks whether a given comparator network is a sorting network by testing
170 * all \f$ 2^n \f$ 0-1-patterns. Since this function has exponential running
171 * time, using it with comparator networks with many inputs is not advisable.
173 * \param n The comparator network to test.
174 * \return Zero if the comparator network is a sort network, one if the
175 * comparator network is \em not a sort network, or something else on error.
177 int sn_network_brute_force_check (sn_network_t *n);
180 * Prints the comparator network to \c STDOUT using a human readable
183 * \param n The comparator network to display.
184 * \return Zero on success, non-zero on failure.
186 int sn_network_show (sn_network_t *n);
189 * Inverts a comparator network by switching the direction of all comparators.
191 * \param n The network to invert.
192 * \return Zero on success, non-zero on failure.
194 int sn_network_invert (sn_network_t *n);
197 * Shifts a comparator network (permutes the inputs). Each input is shifted
198 * \f$ s \f$ positions, higher inputs are "wrapped around".
200 * \param n The comparator network to shift.
201 * \param s The number of positions to shift.
202 * \return Zero on success, non-zero on failure.
204 int sn_network_shift (sn_network_t *n, int s);
207 * Compresses a comparator network by moving all comparators to the earliest
208 * possible stage and removing all remaining empty stages.
210 * \param n The network to compress.
211 * \return Zero on success, non-zero on failure.
213 int sn_network_compress (sn_network_t *n);
216 * Converts a non-standard comparator network to a standard comparator network,
217 * i.e. a network in which all comparators point in the same direction.
219 * \param n The network to normalize.
220 * \return Zero on success, non-zero on failure.
222 int sn_network_normalize (sn_network_t *n);
225 * Removes an input and all comparators touching that input from the comparator
228 * \param n The network to modify.
229 * \param input The zero-based index of the input to remove.
230 * \return Zero on success, non-zero on failure.
232 int sn_network_remove_input (sn_network_t *n, int input);
235 * Removes an inputs from a comparator network by assuming positive or negative
236 * infinity to be supplied to a given input. The value will take a
237 * deterministic way through the comparator network. After removing the path
238 * and all comparators it touched from the comparator network, a new comparator
239 * network with \f$ n-1 \f$ inputs remains. The remaining outputs behave
240 * identical to the original network with respect to one another.
242 * \param n The comparator network to modify.
243 * \param input The input to remove.
244 * \param dir The direction in which to cut, i.e. whether to assume positive or
246 * \return Zero on success, non-zero on failure.
248 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
250 /* FIXME: Documentation */
251 int sn_network_cut (sn_network_t *n, int *mask);
254 * An alias for sn_network_combine_odd_even_merge().
256 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1);
259 * Combines two comparator networks using a bitonic merger. The number of
260 * inputs of both comparator networks must be identical and a power of two.
262 * \param n0 First network.
263 * \param n1 Second network.
264 * \return Newly allocated network with twice the number of inputs or \c NULL
267 sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t *n1);
270 * Combines two comparator networks using the odd-even-merger.
272 * \param n0 First network.
273 * \param n1 Second network.
274 * \return Newly allocated network or \c NULL on error.
276 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t *n1);
279 * Reads a comparator network from a open file handle.
281 * \param fh The FILE pointer to read from.
282 * \return A newly allocated comparator network or \c NULL on error.
283 * \see sn_network_read_file
285 sn_network_t *sn_network_read (FILE *fh);
288 * Reads a comparator network from a file.
290 * \param file File name to read the network from.
291 * \return A newly allocated comparator network or \c NULL on error.
292 * \see sn_network_read
294 sn_network_t *sn_network_read_file (const char *file);
297 * Writes a comparator network to a file handle.
299 * \param n The comparator network to write.
300 * \param fh The file handle to write to. Must be opened in write mode.
301 * \return Zero on success, non-zero on failure.
302 * \see sn_network_write_file
304 int sn_network_write (sn_network_t *n, FILE *fh);
307 * Writes a comparator network to a file.
309 * \param n The comparator network to write.
310 * \param fh The file name to write the network to.
311 * \return Zero on success, non-zero on failure.
312 * \see sn_network_write
314 int sn_network_write_file (sn_network_t *n, const char *file);
317 * Creates a serialized form of the given comparator network. The serialized
318 * form is byte-order independent and can easily be sent over a computer
321 * \param n The comparator network to serialize.
322 * \param[out] ret_buffer Pointer to a pointer into which the location of the
323 * allocated memory will be written. It is the caller's responsibility to
325 * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
326 * allocated memory will be written.
327 * \return Zero on success, non-zero on failure.
328 * \see sn_network_unserialize
330 int sn_network_serialize (sn_network_t *n, char **ret_buffer,
331 size_t *ret_buffer_size);
334 * Creates a comparator network from its serialized form.
336 * \param buffer Pointer to a buffer containing the comparator network in
338 * \param buffer_size Size of the buffer (in bytes).
339 * \return Pointer to the newly allocated comparator network or \c NULL on
341 * \see sn_network_serialize
343 sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size);
344 #endif /* SN_NETWORK_H */
346 /* vim: set shiftwidth=2 softtabstop=2 : */