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.
56 * \param inputs_num Number of inputs the comparator network has.
57 * \return Pointer to the comparator network or 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 NULL on error. The returned network must be
66 * 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 sn_network_t. This frees all allocated space.
74 * \param n The comparator network to destroy. May be NULL.
76 void sn_network_destroy (sn_network_t *n);
79 * Creates a new sort network using Batcher's Odd-Even-Mergesort algorithm.
81 * \param inputs_num Number of inputs / outputs of the sorting network.
82 * \return A pointer to the newly allocated sorting network or NULL if an
83 * invalid number of inputs was given or allocation failed.
85 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
88 * Append a new stage to a comparator network.
90 * \param n The comparator network to which to add the stage.
91 * \param s A pointer to a stage. The memory pointed to by this parameter is
92 * not copied and freed by sn_network_destroy. It is the caller's
93 * responsibility to call sn_stage_clone() if appropriate.
94 * \return Zero on success, non-zero on failure.
96 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s);
99 * Remove a stage from a comparator network.
101 * \param n A pointer to the comparator network to modify.
102 * \param s_num The depth of the comparator network to remove, with zero being
103 * meaning the stage closest to the inputs.
104 * \return Zero on success, non-zero on failure.
106 int sn_network_stage_remove (sn_network_t *n, int s_num);
109 * Adds a comparator to a comparator network. The code tries to add the
110 * comparator to the last stage, i.e. the stage closest to the outputs. If this
111 * is not possible, because one line is used by another comparator, a new stage
112 * is created and appended to the sorting network.
114 * \param n Pointer to the comparator netork.
115 * \param c Pointer to a comparator to add. The given comparator is copied. It
116 * is the caller's responsibility to free c.
117 * \return Zero on success, non-zero on failure.
119 int sn_network_comparator_add (sn_network_t *n, const sn_comparator_t *c);
122 * Returns the number of comparators contained in the comparator network. This
123 * will traverse all comparators in all stages, resulting in a running time of
126 * \param n Comparator network to work with.
127 * \return The number of comparators contained in the network or less than zero
128 * on error (n is NULL).
130 int sn_network_get_comparator_num (const sn_network_t *n);
133 * Applies a comparator network to an array of integers. This is implemented by
134 * calling sn_stage_sort() with every stage of the network.
136 * \param n Pointer to the comparator netork.
137 * \param[in,out] values Pointer to integer values to sort. The number of
138 * integer values pointed to must be at least the number of inputs of the
139 * comparator network. Otherwise, segmentation faults or memory corruption
141 * \return Zero on success, non-zero on failure.
143 int sn_network_sort (sn_network_t *n, int *values);
146 * Checks whether a given comparator network is a sorting network by testing
147 * all 2^n 0-1-patterns. Since this function has exponential running time,
148 * using it with comparator networks with many inputs is not advisable.
150 * \param n The comparator network to test.
151 * \return Zero if the comparator network is a sort network, one if the
152 * comparator network is \em not a sort network, or something else on error.
154 int sn_network_brute_force_check (sn_network_t *n);
156 int sn_network_show (sn_network_t *n);
157 int sn_network_invert (sn_network_t *n);
158 int sn_network_shift (sn_network_t *n, int s);
159 int sn_network_compress (sn_network_t *n);
160 int sn_network_normalize (sn_network_t *n);
162 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
163 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1,
164 int is_power_of_two);
165 sn_network_t *sn_network_combine_bitonic (sn_network_t *n0, sn_network_t *n1);
166 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t *n1);
168 sn_network_t *sn_network_read (FILE *fh);
169 sn_network_t *sn_network_read_file (const char *file);
170 int sn_network_write (sn_network_t *n, FILE *fh);
171 int sn_network_write_file (sn_network_t *n, const char *file);
173 int sn_network_serialize (sn_network_t *n, char **ret_buffer,
174 size_t *ret_buffer_size);
175 sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size);
176 #endif /* SN_NETWORK_H */
178 /* vim: set shiftwidth=2 softtabstop=2 : */