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 library is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU Lesser General Public License as published by
13 * the Free Software Foundation; either version 2.1 of the License, or (at
14 * your option) any later version.
16 * This library is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
21 * You should have received a copy of the GNU Lesser General Public License
22 * along with this library; if not, write to the Free Software Foundation,
23 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
26 * Florian octo Forster <ff at octo.it>
31 #define SN_NETWORK_H 1
37 #include "sn_comparator.h"
41 * The global struct representing a comparator or sort network.
45 int inputs_num; /**< Number of inputs of the comparator network. */
46 sn_stage_t **stages; /**< Array of pointers to the stages of a comparator network. */
47 int stages_num; /**< Number of stages in this comparator network. */
49 typedef struct sn_network_s sn_network_t;
51 #define SN_NETWORK_STAGE_NUM(n) (n)->stages_num
52 #define SN_NETWORK_STAGE_GET(n,i) ((n)->stages[i])
53 #define SN_NETWORK_INPUT_NUM(n) (n)->inputs_num
56 * Creates an empty comparator network and returns a pointer to it. The
57 * comparator network must be freed using sn_network_destroy().
59 * \param inputs_num Number of inputs the comparator network has.
60 * \return Pointer to the comparator network or \c NULL on error.
62 sn_network_t *sn_network_create (int inputs_num);
65 * Clones an existing comparator network.
67 * \param n Comparator network to clone.
68 * \return Copied sort network or \c NULL on error. The returned network must
69 * be freed using sn_network_destroy().
71 sn_network_t *sn_network_clone (const sn_network_t *n);
74 * Destroys a comparator network allocated with sn_network_create() or one of
75 * the other methods returning a \c sn_network_t. This frees all allocated
78 * \param n The comparator network to destroy. May be \c NULL.
80 void sn_network_destroy (sn_network_t *n);
83 * Creates a new sort network using Batcher's Odd-Even-Mergesort algorithm.
85 * \param inputs_num Number of inputs / outputs of the sorting network.
86 * \return A pointer to the newly allocated sorting network or \c NULL if an
87 * invalid number of inputs was given or allocation failed.
89 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
92 * Creates a new sort network using Batcher's Bitonic-Mergesort algorithm.
94 * \param inputs_num Number of inputs / outputs of the sorting network.
95 * \return A pointer to the newly allocated sorting network or \c NULL if an
96 * invalid number of inputs was given or allocation failed.
98 sn_network_t *sn_network_create_bitonic_mergesort (int inputs_num);
101 * Creates a new sorting network using the Pairwise sorting algorithm published
103 * \param inputs_num Number of inputs / outputs of the sorting network.
104 * \return A pointer to the newly allocated sorting network or \c NULL if an
105 * invalid number of inputs was given or allocation failed.
107 sn_network_t *sn_network_create_pairwise (int inputs_num);
110 * Append another network to a given network.
112 * \param n The comparator network to which the other network is added. This
113 * network is modified.
114 * \param other The network to be added to the first network. This network is
115 * consumed by this function and the memory pointed to is freed. You cannot
116 * use that network after this call, so use sn_network_clone() if required.
117 * \return Zero on success, non-zero on failure.
119 int sn_network_network_add (sn_network_t *n, sn_network_t *other);
122 * Append a new stage to a comparator network.
124 * \param n The comparator network to which to add the stage.
125 * \param s A pointer to a stage. The memory pointed to by this parameter is
126 * not copied and freed by sn_network_destroy(). It is the caller's
127 * responsibility to call sn_stage_clone() if appropriate.
128 * \return Zero on success, non-zero on failure.
130 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s);
133 * Remove a stage from a comparator network.
135 * \param n A pointer to the comparator network to modify.
136 * \param s_num The depth of the comparator network to remove, with zero being
137 * meaning the stage closest to the inputs.
138 * \return Zero on success, non-zero on failure.
140 int sn_network_stage_remove (sn_network_t *n, int s_num);
143 * Adds a comparator to a comparator network. The code tries to add the
144 * comparator to the last stage, i.e. the stage closest to the outputs. If this
145 * is not possible, because one line is used by another comparator, a new stage
146 * is created and appended to the sorting network.
148 * \param n Pointer to the comparator netork.
149 * \param c Pointer to a comparator to add. The given comparator is copied. It
150 * is the caller's responsibility to free c.
151 * \return Zero on success, non-zero on failure.
153 int sn_network_comparator_add (sn_network_t *n, const sn_comparator_t *c);
156 * Returns the number of comparators contained in the comparator network. This
157 * will traverse all comparators in all stages, resulting in a running time of
158 * \f$ \mathcal{O}(n) \f$.
160 * \param n Comparator network to work with.
161 * \return The number of comparators contained in the network or less than zero
162 * on error (\c n is \c NULL).
164 int sn_network_get_comparator_num (const sn_network_t *n);
167 * Applies a comparator network to an array of integers. This is implemented by
168 * calling sn_stage_sort() with every stage of the network.
170 * \param n Pointer to the comparator netork.
171 * \param[in,out] values Pointer to integer values to sort. The number of
172 * integer values pointed to must be at least the number of inputs of the
173 * comparator network. Otherwise, segmentation faults or memory corruption
175 * \return Zero on success, non-zero on failure.
178 int sn_network_sort (sn_network_t *n, int *values);
181 * Checks whether a given comparator network is a sorting network by testing
182 * all \f$ 2^n \f$ 0-1-patterns. Since this function has exponential running
183 * time, using it with comparator networks with many inputs is not advisable.
185 * \param n The comparator network to test.
186 * \return Zero if the comparator network is a sort network, one if the
187 * comparator network is \em not a sort network, or something else on error.
189 int sn_network_brute_force_check (sn_network_t *n);
192 * Prints the comparator network to \c STDOUT using a human readable
195 * \param n The comparator network to display.
196 * \return Zero on success, non-zero on failure.
198 int sn_network_show (sn_network_t *n);
199 int sn_network_show_fh (sn_network_t *n, FILE *fh);
202 * Inverts a comparator network by switching the direction of all comparators.
204 * \param n The network to invert.
205 * \return Zero on success, non-zero on failure.
207 int sn_network_invert (sn_network_t *n);
210 * Shifts a comparator network (permutes the inputs). Each input is shifted
211 * \f$ s \f$ positions, higher inputs are "wrapped around".
213 * \param n The comparator network to shift.
214 * \param s The number of positions to shift.
215 * \return Zero on success, non-zero on failure.
217 int sn_network_shift (sn_network_t *n, int s);
220 * Compresses a comparator network by moving all comparators to the earliest
221 * possible stage and removing all remaining empty stages.
223 * \param n The network to compress.
224 * \return Zero on success, non-zero on failure.
226 int sn_network_compress (sn_network_t *n);
229 * Converts a non-standard comparator network to a standard comparator network,
230 * i.e. a network in which all comparators point in the same direction.
232 * \param n The network to normalize.
233 * \return Zero on success, non-zero on failure.
235 int sn_network_normalize (sn_network_t *n);
237 int sn_network_unify (sn_network_t *n);
240 * Removes an input and all comparators touching that input from the comparator
243 * \param n The network to modify.
244 * \param input The zero-based index of the input to remove.
245 * \return Zero on success, non-zero on failure.
247 int sn_network_remove_input (sn_network_t *n, int input);
250 * Removes an inputs from a comparator network by assuming positive or negative
251 * infinity to be supplied to a given input. The value will take a
252 * deterministic way through the comparator network. After removing the path
253 * and all comparators it touched from the comparator network, a new comparator
254 * network with \f$ n-1 \f$ inputs remains. The remaining outputs behave
255 * identical to the original network with respect to one another.
257 * \param n The comparator network to modify.
258 * \param input The input to remove.
259 * \param dir The direction in which to cut, i.e. whether to assume positive or
261 * \return Zero on success, non-zero on failure.
263 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
265 /* FIXME: Documentation */
266 int sn_network_cut (sn_network_t *n, int *mask);
269 * An alias for sn_network_combine_odd_even_merge().
271 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1);
274 * Combines two comparator networks using a bitonic merger. The number of
275 * inputs of both comparator networks must be identical and a power of two.
277 * \param n0 First network.
278 * \param n1 Second network.
279 * \return Newly allocated network with twice the number of inputs or \c NULL
282 sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t *n1);
285 * Combines two comparator networks using the odd-even-merger.
287 * \param n0 First network.
288 * \param n1 Second network.
289 * \return Newly allocated network or \c NULL on error.
291 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t *n1);
294 * Reads a comparator network from a open file handle.
296 * \param fh The FILE pointer to read from.
297 * \return A newly allocated comparator network or \c NULL on error.
298 * \see sn_network_read_file
300 sn_network_t *sn_network_read (FILE *fh);
303 * Reads a comparator network from a file.
305 * \param file File name to read the network from.
306 * \return A newly allocated comparator network or \c NULL on error.
307 * \see sn_network_read
309 sn_network_t *sn_network_read_file (const char *file);
312 * Writes a comparator network to a file handle.
314 * \param n The comparator network to write.
315 * \param fh The file handle to write to. Must be opened in write mode.
316 * \return Zero on success, non-zero on failure.
317 * \see sn_network_write_file
319 int sn_network_write (sn_network_t *n, FILE *fh);
322 * Writes a comparator network to a file.
324 * \param n The comparator network to write.
325 * \param fh The file name to write the network to.
326 * \return Zero on success, non-zero on failure.
327 * \see sn_network_write
329 int sn_network_write_file (sn_network_t *n, const char *file);
332 * Creates a serialized form of the given comparator network. The serialized
333 * form is byte-order independent and can easily be sent over a computer
336 * \param n The comparator network to serialize.
337 * \param[out] ret_buffer Pointer to a pointer into which the location of the
338 * allocated memory will be written. It is the caller's responsibility to
340 * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
341 * allocated memory will be written.
342 * \return Zero on success, non-zero on failure.
343 * \see sn_network_unserialize
345 int sn_network_serialize (sn_network_t *n, char **ret_buffer,
346 size_t *ret_buffer_size);
349 * Creates a comparator network from its serialized form.
351 * \param buffer Pointer to a buffer containing the comparator network in
353 * \param buffer_size Size of the buffer (in bytes).
354 * \return Pointer to the newly allocated comparator network or \c NULL on
356 * \see sn_network_serialize
358 sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size);
361 * Compares two networks and returns zero if they are equal. If they are not
362 * equal, a number greater than zero or less than zero is returned in a
363 * consistent matter, so this function can be used to sort networks and detect
364 * duplicates. It is strongly recommended that you call sn_network_unify()
365 * before comparing two networks, because they internal structure does matter
368 * \return Zero if the two networks are equal, non-zero otherwise. Return
369 * values are consistent so this function can be used to sort networks.
370 * \see sn_network_unify
372 int sn_network_compare (const sn_network_t *n0, const sn_network_t *n1);
374 uint64_t sn_network_get_hashval (const sn_network_t *n);
376 #endif /* SN_NETWORK_H */
378 /* vim: set shiftwidth=2 softtabstop=2 : */