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>
31 #define SN_NETWORK_H 1
35 #include "sn_comparator.h"
39 * The global struct representing a comparator or sort network.
43 int inputs_num; /**< Number of inputs of the comparator network. */
44 sn_stage_t **stages; /**< Array of pointers to the stages of a comparator network. */
45 int stages_num; /**< Number of stages in this comparator network. */
47 typedef struct sn_network_s sn_network_t;
49 #define SN_NETWORK_STAGE_NUM(n) (n)->stages_num
50 #define SN_NETWORK_STAGE_GET(n,i) ((n)->stages[i])
51 #define SN_NETWORK_INPUT_NUM(n) (n)->inputs_num
54 * Creates an empty comparator network and returns a pointer to it. The
55 * comparator network must be freed using sn_network_destroy().
57 * \param inputs_num Number of inputs the comparator network has.
58 * \return Pointer to the comparator network or \c NULL on error.
60 sn_network_t *sn_network_create (int inputs_num);
63 * Clones an existing comparator network.
65 * \param n Comparator network to clone.
66 * \return Copied sort network or \c NULL on error. The returned network must
67 * be freed using sn_network_destroy().
69 sn_network_t *sn_network_clone (const sn_network_t *n);
72 * Destroys a comparator network allocated with sn_network_create() or one of
73 * the other methods returning a \c sn_network_t. This frees all allocated
76 * \param n The comparator network to destroy. May be \c NULL.
78 void sn_network_destroy (sn_network_t *n);
81 * Creates a new sort network using Batcher's Odd-Even-Mergesort algorithm.
83 * \param inputs_num Number of inputs / outputs of the sorting network.
84 * \return A pointer to the newly allocated sorting network or \c NULL if an
85 * invalid number of inputs was given or allocation failed.
87 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
90 * Append a new stage to a comparator network.
92 * \param n The comparator network to which to add the stage.
93 * \param s A pointer to a stage. The memory pointed to by this parameter is
94 * not copied and freed by sn_network_destroy(). It is the caller's
95 * responsibility to call sn_stage_clone() if appropriate.
96 * \return Zero on success, non-zero on failure.
98 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s);
101 * Remove a stage from a comparator network.
103 * \param n A pointer to the comparator network to modify.
104 * \param s_num The depth of the comparator network to remove, with zero being
105 * meaning the stage closest to the inputs.
106 * \return Zero on success, non-zero on failure.
108 int sn_network_stage_remove (sn_network_t *n, int s_num);
111 * Adds a comparator to a comparator network. The code tries to add the
112 * comparator to the last stage, i.e. the stage closest to the outputs. If this
113 * is not possible, because one line is used by another comparator, a new stage
114 * is created and appended to the sorting network.
116 * \param n Pointer to the comparator netork.
117 * \param c Pointer to a comparator to add. The given comparator is copied. It
118 * is the caller's responsibility to free c.
119 * \return Zero on success, non-zero on failure.
121 int sn_network_comparator_add (sn_network_t *n, const sn_comparator_t *c);
124 * Returns the number of comparators contained in the comparator network. This
125 * will traverse all comparators in all stages, resulting in a running time of
126 * \f$ \mathcal{O}(n) \f$.
128 * \param n Comparator network to work with.
129 * \return The number of comparators contained in the network or less than zero
130 * on error (n is NULL).
132 int sn_network_get_comparator_num (const sn_network_t *n);
135 * Applies a comparator network to an array of integers. This is implemented by
136 * calling sn_stage_sort() with every stage of the network.
138 * \param n Pointer to the comparator netork.
139 * \param[in,out] values Pointer to integer values to sort. The number of
140 * integer values pointed to must be at least the number of inputs of the
141 * comparator network. Otherwise, segmentation faults or memory corruption
143 * \return Zero on success, non-zero on failure.
146 int sn_network_sort (sn_network_t *n, int *values);
149 * Checks whether a given comparator network is a sorting network by testing
150 * all \f$ 2^n \f$ 0-1-patterns. Since this function has exponential running
151 * time, using it with comparator networks with many inputs is not advisable.
153 * \param n The comparator network to test.
154 * \return Zero if the comparator network is a sort network, one if the
155 * comparator network is \em not a sort network, or something else on error.
157 int sn_network_brute_force_check (sn_network_t *n);
160 * Prints the comparator network to STDOUT using a human readable
163 * \param n The comparator network to display.
164 * \return Zero on success, non-zero on failure.
166 int sn_network_show (sn_network_t *n);
169 * Inverts a comparator network by switching the direction of all comparators.
171 * \param n The network to invert.
172 * \return Zero on success, non-zero on failure.
174 int sn_network_invert (sn_network_t *n);
177 * Shifts a comparator network (permutes the inputs). Each input is shifted
178 * \f$ s \f$ positions, higher inputs are "wrapped around".
180 * \param n The comparator network to shift.
181 * \param s The number of positions to shift.
182 * \return Zero on success, non-zero on failure.
184 int sn_network_shift (sn_network_t *n, int s);
187 * Compresses a comparator network by moving all comparators to the earliest
188 * possible stage and removing all remaining empty stages.
190 * \param n The network to compress.
191 * \return Zero on success, non-zero on failure.
193 int sn_network_compress (sn_network_t *n);
196 * Converts a non-standard comparator network to a standard comparator network,
197 * i.e. a network in which all comparators point in the same direction.
199 * \param n The network to normalize.
200 * \return Zero on success, non-zero on failure.
202 int sn_network_normalize (sn_network_t *n);
205 * Removes an inputs from a comparator network by assuming positive or negative
206 * infinity to be supplied to a given input. The value will take a
207 * deterministic way through the comparator network. After removing the path
208 * and all comparators it touched from the comparator network, a new comparator
209 * network with \f$ n-1 \f$ inputs remains. The remaining outputs behave
210 * identical to the original network with respect to one another.
212 * \param n The comparator network to modify.
213 * \param input The input to remove.
214 * \param dir The direction in which to cut, i.e. whether to assume positive or
216 * \return Zero on success, non-zero on failure.
218 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
221 * An alias for sn_network_combine_odd_even_merge().
223 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1);
226 * Combines two comparator networks using a bitonic merger. The number of
227 * inputs of both comparator networks must be identical and a power of two.
229 * \param n0 First network.
230 * \param n1 Second network.
231 * \return Newly allocated network with twice the number of inputs or NULL on
234 sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t *n1);
237 * Combines two comparator networks using the odd-even-merger.
239 * \param n0 First network.
240 * \param n1 Second network.
241 * \return Newly allocated network or NULL on error.
243 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t *n1);
246 * Reads a comparator network from a open file handle.
248 * \param fh The FILE pointer to read from.
249 * \return A newly allocated comparator network or NULL on error.
250 * \see sn_network_read_file
252 sn_network_t *sn_network_read (FILE *fh);
255 * Reads a comparator network from a file.
257 * \param file File name to read the network from.
258 * \return A newly allocated comparator network or NULL on error.
259 * \see sn_network_read
261 sn_network_t *sn_network_read_file (const char *file);
264 * Writes a comparator network to a file handle.
266 * \param n The comparator network to write.
267 * \param fh The file handle to write to. Must be opened in write mode.
268 * \return Zero on success, non-zero on failure.
269 * \see sn_network_write_file
271 int sn_network_write (sn_network_t *n, FILE *fh);
274 * Writes a comparator network to a file.
276 * \param n The comparator network to write.
277 * \param fh The file name to write the network to.
278 * \return Zero on success, non-zero on failure.
279 * \see sn_network_write
281 int sn_network_write_file (sn_network_t *n, const char *file);
284 * Creates a serialized form of the given comparator network. The serialized
285 * form is byte-order independent and can easily be sent over a computer
288 * \param n The comparator network to serialize.
289 * \param[out] ret_buffer Pointer to a pointer into which the location of the
290 * allocated memory will be written. It is the caller's responsibility to
292 * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
293 * allocated memory will be written.
294 * \return Zero on success, non-zero on failure.
295 * \see sn_network_unserialize
297 int sn_network_serialize (sn_network_t *n, char **ret_buffer,
298 size_t *ret_buffer_size);
301 * Creates a comparator network from its serialized form.
303 * \param buffer Pointer to a buffer containing the comparator network in
305 * \param buffer_size Size of the buffer (in bytes).
306 * \return Pointer to the newly allocated comparator network or NULL on error.
307 * \see sn_network_serialize
309 sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size);
310 #endif /* SN_NETWORK_H */
312 /* vim: set shiftwidth=2 softtabstop=2 : */