src/sn_network.h

   1 /**
   2  * \file sn_network.h
   3  * \brief The sn_network_t class and associated methods.
   4  *
   5  * This is more details about what this file does.
   6  *
   7  * \verbatim
   8  * libsortnetwork - src/sn_network.h
   9  * Copyright (C) 2008-2010  Florian octo Forster
  10  *
  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.
  14  *
  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.
  19  *
  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
  23  *
  24  * Authors:
  25  *   Florian octo Forster <ff at octo.it>
  26  * \endverbatim
  27  **/
  28
  29 #ifndef SN_NETWORK_H
  30 #define SN_NETWORK_H 1
  31
  32 #include <stdio.h>
  33
  34 #include "sn_comparator.h"
  35 #include "sn_stage.h"
  36
  37 /**
  38  * The global struct representing a comparator or sort network.
  39  */
  40 struct sn_network_s
  41 {
  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. */
  45 };
  46 typedef struct sn_network_s sn_network_t;
  47
  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
  51
  52 /**
  53  * Creates an empty comparator network and returns a pointer to it. The
  54  * comparator network must be freed using sn_network_destroy().
  55  *
  56  * \param inputs_num Number of inputs the comparator network has.
  57  * \return Pointer to the comparator network or \c NULL on error.
  58  */
  59 sn_network_t *sn_network_create (int inputs_num);
  60
  61 /**
  62  * Clones an existing comparator network.
  63  *
  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().
  67  */
  68 sn_network_t *sn_network_clone (const sn_network_t *n);
  69
  70 /**
  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
  73  * space.
  74  *
  75  * \param n The comparator network to destroy. May be \c NULL.
  76  */
  77 void sn_network_destroy (sn_network_t *n);
  78
  79 /**
  80  * Creates a new sort network using Batcher's Odd-Even-Mergesort algorithm.
  81  *
  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.
  85  */
  86 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
  87
  88 /**
  89  * Creates a new sorting network using the Pairwise sorting algorithm published
  90  * by Ian Parberry.
  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.
  94  */
  95 sn_network_t *sn_network_create_pairwise (int inputs_num);
  96
  97 /**
  98  * Append a new stage to a comparator network.
  99  *
 100  * \param n The comparator network to which to add the stage.
 101  * \param s A pointer to a stage. The memory pointed to by this parameter is
 102  *   not copied and freed by sn_network_destroy(). It is the caller's
 103  *   responsibility to call sn_stage_clone() if appropriate.
 104  * \return Zero on success, non-zero on failure.
 105  */
 106 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s);
 107
 108 /**
 109  * Remove a stage from a comparator network.
 110  *
 111  * \param n A pointer to the comparator network to modify.
 112  * \param s_num The depth of the comparator network to remove, with zero being
 113  *   meaning the stage closest to the inputs.
 114  * \return Zero on success, non-zero on failure.
 115  */
 116 int sn_network_stage_remove (sn_network_t *n, int s_num);
 117
 118 /**
 119  * Adds a comparator to a comparator network. The code tries to add the
 120  * comparator to the last stage, i.e. the stage closest to the outputs. If this
 121  * is not possible, because one line is used by another comparator, a new stage
 122  * is created and appended to the sorting network.
 123  *
 124  * \param n Pointer to the comparator netork.
 125  * \param c Pointer to a comparator to add. The given comparator is copied. It
 126  *   is the caller's responsibility to free c.
 127  * \return Zero on success, non-zero on failure.
 128  */
 129 int sn_network_comparator_add (sn_network_t *n, const sn_comparator_t *c);
 130
 131 /**
 132  * Returns the number of comparators contained in the comparator network. This
 133  * will traverse all comparators in all stages, resulting in a running time of
 134  * \f$ \mathcal{O}(n) \f$.
 135  *
 136  * \param n Comparator network to work with.
 137  * \return The number of comparators contained in the network or less than zero
 138  *  on error (\c n is \c NULL).
 139  */
 140 int sn_network_get_comparator_num (const sn_network_t *n);
 141
 142 /**
 143  * Applies a comparator network to an array of integers. This is implemented by
 144  * calling sn_stage_sort() with every stage of the network.
 145  *
 146  * \param n Pointer to the comparator netork.
 147  * \param[in,out] values Pointer to integer values to sort. The number of
 148  *   integer values pointed to must be at least the number of inputs of the
 149  *   comparator network. Otherwise, segmentation faults or memory corruption
 150  *   will occur.
 151  * \return Zero on success, non-zero on failure.
 152  * \see sn_stage_sort
 153  */
 154 int sn_network_sort (sn_network_t *n, int *values);
 155
 156 /**
 157  * Checks whether a given comparator network is a sorting network by testing
 158  * all \f$ 2^n \f$ 0-1-patterns. Since this function has exponential running
 159  * time, using it with comparator networks with many inputs is not advisable.
 160  *
 161  * \param n The comparator network to test.
 162  * \return Zero if the comparator network is a sort network, one if the
 163  *   comparator network is \em not a sort network, or something else on error.
 164  */
 165 int sn_network_brute_force_check (sn_network_t *n);
 166
 167 /**
 168  * Prints the comparator network to \c STDOUT using a human readable
 169  * representation.
 170  *
 171  * \param n The comparator network to display.
 172  * \return Zero on success, non-zero on failure.
 173  */
 174 int sn_network_show (sn_network_t *n);
 175
 176 /**
 177  * Inverts a comparator network by switching the direction of all comparators.
 178  *
 179  * \param n The network to invert.
 180  * \return Zero on success, non-zero on failure.
 181  */
 182 int sn_network_invert (sn_network_t *n);
 183
 184 /**
 185  * Shifts a comparator network (permutes the inputs). Each input is shifted
 186  * \f$ s \f$ positions, higher inputs are "wrapped around".
 187  *
 188  * \param n The comparator network to shift.
 189  * \param s The number of positions to shift.
 190  * \return Zero on success, non-zero on failure.
 191  */
 192 int sn_network_shift (sn_network_t *n, int s);
 193
 194 /**
 195  * Compresses a comparator network by moving all comparators to the earliest
 196  * possible stage and removing all remaining empty stages.
 197  *
 198  * \param n The network to compress.
 199  * \return Zero on success, non-zero on failure.
 200  */
 201 int sn_network_compress (sn_network_t *n);
 202
 203 /**
 204  * Converts a non-standard comparator network to a standard comparator network,
 205  * i.e. a network in which all comparators point in the same direction.
 206  *
 207  * \param n The network to normalize.
 208  * \return Zero on success, non-zero on failure.
 209  */
 210 int sn_network_normalize (sn_network_t *n);
 211
 212 /**
 213  * Removes an input and all comparators touching that input from the comparator
 214  * network.
 215  *
 216  * \param n The network to modify.
 217  * \param input The zero-based index of the input to remove.
 218  * \return Zero on success, non-zero on failure.
 219  */
 220 int sn_network_remove_input (sn_network_t *n, int input);
 221
 222 /**
 223  * Removes an inputs from a comparator network by assuming positive or negative
 224  * infinity to be supplied to a given input. The value will take a
 225  * deterministic way through the comparator network. After removing the path
 226  * and all comparators it touched from the comparator network, a new comparator
 227  * network with \f$ n-1 \f$ inputs remains. The remaining outputs behave
 228  * identical to the original network with respect to one another.
 229  *
 230  * \param n The comparator network to modify.
 231  * \param input The input to remove.
 232  * \param dir The direction in which to cut, i.e. whether to assume positive or
 233  *   negative infinity.
 234  * \return Zero on success, non-zero on failure.
 235  */
 236 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
 237
 238 /* FIXME: Documentation */
 239 int sn_network_cut (sn_network_t *n, int *mask);
 240
 241 /**
 242  * An alias for sn_network_combine_odd_even_merge().
 243  */
 244 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1);
 245
 246 /**
 247  * Combines two comparator networks using a bitonic merger. The number of
 248  * inputs of both comparator networks must be identical and a power of two.
 249  *
 250  * \param n0 First network.
 251  * \param n1 Second network.
 252  * \return Newly allocated network with twice the number of inputs or \c NULL
 253  *   on error.
 254  */
 255 sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t *n1);
 256
 257 /**
 258  * Combines two comparator networks using the odd-even-merger.
 259  *
 260  * \param n0 First network.
 261  * \param n1 Second network.
 262  * \return Newly allocated network or \c NULL on error.
 263  */
 264 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t *n1);
 265
 266 /**
 267  * Reads a comparator network from a open file handle.
 268  *
 269  * \param fh The FILE pointer to read from.
 270  * \return A newly allocated comparator network or \c NULL on error.
 271  * \see sn_network_read_file
 272  */
 273 sn_network_t *sn_network_read (FILE *fh);
 274
 275 /**
 276  * Reads a comparator network from a file.
 277  *
 278  * \param file File name to read the network from.
 279  * \return A newly allocated comparator network or \c NULL on error.
 280  * \see sn_network_read
 281  */
 282 sn_network_t *sn_network_read_file (const char *file);
 283
 284 /**
 285  * Writes a comparator network to a file handle.
 286  *
 287  * \param n The comparator network to write.
 288  * \param fh The file handle to write to. Must be opened in write mode.
 289  * \return Zero on success, non-zero on failure.
 290  * \see sn_network_write_file
 291  */
 292 int sn_network_write (sn_network_t *n, FILE *fh);
 293
 294 /**
 295  * Writes a comparator network to a file.
 296  *
 297  * \param n The comparator network to write.
 298  * \param fh The file name to write the network to.
 299  * \return Zero on success, non-zero on failure.
 300  * \see sn_network_write
 301  */
 302 int sn_network_write_file (sn_network_t *n, const char *file);
 303
 304 /**
 305  * Creates a serialized form of the given comparator network. The serialized
 306  * form is byte-order independent and can easily be sent over a computer
 307  * network.
 308  *
 309  * \param n The comparator network to serialize.
 310  * \param[out] ret_buffer Pointer to a pointer into which the location of the
 311  *   allocated memory will be written. It is the caller's responsibility to
 312  *   free this memory.
 313  * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
 314  *   allocated memory will be written.
 315  * \return Zero on success, non-zero on failure.
 316  * \see sn_network_unserialize
 317  */
 318 int sn_network_serialize (sn_network_t *n, char **ret_buffer,
 319     size_t *ret_buffer_size);
 320
 321 /**
 322  * Creates a comparator network from its serialized form.
 323  *
 324  * \param buffer Pointer to a buffer containing the comparator network in
 325  *   serialized form.
 326  * \param buffer_size Size of the buffer (in bytes).
 327  * \return Pointer to the newly allocated comparator network or \c NULL on
 328  *   error.
 329  * \see sn_network_serialize
 330  */
 331 sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size);
 332 #endif /* SN_NETWORK_H */
 333
 334 /* vim: set shiftwidth=2 softtabstop=2 : */