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 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.
  15  *
  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
  19  * for more details.
  20  *
  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
  24  *
  25  * Authors:
  26  *   Florian octo Forster <ff at octo.it>
  27  * \endverbatim
  28  **/
  29
  30 #ifndef SN_NETWORK_H
  31 #define SN_NETWORK_H 1
  32
  33 #include <stdio.h>
  34 #include <stdint.h>
  35 #include <inttypes.h>
  36
  37 #include "sn_comparator.h"
  38 #include "sn_stage.h"
  39
  40 /**
  41  * The global struct representing a comparator or sort network.
  42  */
  43 struct sn_network_s
  44 {
  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. */
  48 };
  49 typedef struct sn_network_s sn_network_t;
  50
  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
  54
  55 /**
  56  * Creates an empty comparator network and returns a pointer to it. The
  57  * comparator network must be freed using sn_network_destroy().
  58  *
  59  * \param inputs_num Number of inputs the comparator network has.
  60  * \return Pointer to the comparator network or \c NULL on error.
  61  */
  62 sn_network_t *sn_network_create (int inputs_num);
  63
  64 /**
  65  * Clones an existing comparator network.
  66  *
  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().
  70  */
  71 sn_network_t *sn_network_clone (const sn_network_t *n);
  72
  73 /**
  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
  76  * space.
  77  *
  78  * \param n The comparator network to destroy. May be \c NULL.
  79  */
  80 void sn_network_destroy (sn_network_t *n);
  81
  82 /**
  83  * Creates a new sort network using Batcher's Odd-Even-Mergesort algorithm.
  84  *
  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.
  88  */
  89 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
  90
  91 /**
  92  * Creates a new sort network using Batcher's Bitonic-Mergesort algorithm.
  93  *
  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.
  97  */
  98 sn_network_t *sn_network_create_bitonic_mergesort (int inputs_num);
  99
 100 /**
 101  * Creates a new sorting network using the Pairwise sorting algorithm published
 102  * by Ian Parberry.
 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.
 106  */
 107 sn_network_t *sn_network_create_pairwise (int inputs_num);
 108
 109 /**
 110  * Append another network to a given network.
 111  *
 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.
 118  */
 119 int sn_network_network_add (sn_network_t *n, sn_network_t *other);
 120
 121 /**
 122  * Append a new stage to a comparator network.
 123  *
 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.
 129  */
 130 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s);
 131
 132 /**
 133  * Remove a stage from a comparator network.
 134  *
 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.
 139  */
 140 int sn_network_stage_remove (sn_network_t *n, int s_num);
 141
 142 /**
 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.
 147  *
 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.
 152  */
 153 int sn_network_comparator_add (sn_network_t *n, const sn_comparator_t *c);
 154
 155 /**
 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$.
 159  *
 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).
 163  */
 164 int sn_network_get_comparator_num (const sn_network_t *n);
 165
 166 /**
 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.
 169  *
 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
 174  *   will occur.
 175  * \return Zero on success, non-zero on failure.
 176  * \see sn_stage_sort
 177  */
 178 int sn_network_sort (sn_network_t *n, int *values);
 179
 180 /**
 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.
 184  *
 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.
 188  */
 189 int sn_network_brute_force_check (sn_network_t *n);
 190
 191 /**
 192  * Prints the comparator network to \c STDOUT using a human readable
 193  * representation.
 194  *
 195  * \param n The comparator network to display.
 196  * \return Zero on success, non-zero on failure.
 197  */
 198 int sn_network_show (sn_network_t *n);
 199
 200 /**
 201  * Inverts a comparator network by switching the direction of all comparators.
 202  *
 203  * \param n The network to invert.
 204  * \return Zero on success, non-zero on failure.
 205  */
 206 int sn_network_invert (sn_network_t *n);
 207
 208 /**
 209  * Shifts a comparator network (permutes the inputs). Each input is shifted
 210  * \f$ s \f$ positions, higher inputs are "wrapped around".
 211  *
 212  * \param n The comparator network to shift.
 213  * \param s The number of positions to shift.
 214  * \return Zero on success, non-zero on failure.
 215  */
 216 int sn_network_shift (sn_network_t *n, int s);
 217
 218 /**
 219  * Compresses a comparator network by moving all comparators to the earliest
 220  * possible stage and removing all remaining empty stages.
 221  *
 222  * \param n The network to compress.
 223  * \return Zero on success, non-zero on failure.
 224  */
 225 int sn_network_compress (sn_network_t *n);
 226
 227 /**
 228  * Converts a non-standard comparator network to a standard comparator network,
 229  * i.e. a network in which all comparators point in the same direction.
 230  *
 231  * \param n The network to normalize.
 232  * \return Zero on success, non-zero on failure.
 233  */
 234 int sn_network_normalize (sn_network_t *n);
 235
 236 int sn_network_unify (sn_network_t *n);
 237
 238 /**
 239  * Removes an input and all comparators touching that input from the comparator
 240  * network.
 241  *
 242  * \param n The network to modify.
 243  * \param input The zero-based index of the input to remove.
 244  * \return Zero on success, non-zero on failure.
 245  */
 246 int sn_network_remove_input (sn_network_t *n, int input);
 247
 248 /**
 249  * Removes an inputs from a comparator network by assuming positive or negative
 250  * infinity to be supplied to a given input. The value will take a
 251  * deterministic way through the comparator network. After removing the path
 252  * and all comparators it touched from the comparator network, a new comparator
 253  * network with \f$ n-1 \f$ inputs remains. The remaining outputs behave
 254  * identical to the original network with respect to one another.
 255  *
 256  * \param n The comparator network to modify.
 257  * \param input The input to remove.
 258  * \param dir The direction in which to cut, i.e. whether to assume positive or
 259  *   negative infinity.
 260  * \return Zero on success, non-zero on failure.
 261  */
 262 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
 263
 264 /* FIXME: Documentation */
 265 int sn_network_cut (sn_network_t *n, int *mask);
 266
 267 /**
 268  * An alias for sn_network_combine_odd_even_merge().
 269  */
 270 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1);
 271
 272 /**
 273  * Combines two comparator networks using a bitonic merger. The number of
 274  * inputs of both comparator networks must be identical and a power of two.
 275  *
 276  * \param n0 First network.
 277  * \param n1 Second network.
 278  * \return Newly allocated network with twice the number of inputs or \c NULL
 279  *   on error.
 280  */
 281 sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t *n1);
 282
 283 /**
 284  * Combines two comparator networks using the odd-even-merger.
 285  *
 286  * \param n0 First network.
 287  * \param n1 Second network.
 288  * \return Newly allocated network or \c NULL on error.
 289  */
 290 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t *n1);
 291
 292 /**
 293  * Reads a comparator network from a open file handle.
 294  *
 295  * \param fh The FILE pointer to read from.
 296  * \return A newly allocated comparator network or \c NULL on error.
 297  * \see sn_network_read_file
 298  */
 299 sn_network_t *sn_network_read (FILE *fh);
 300
 301 /**
 302  * Reads a comparator network from a file.
 303  *
 304  * \param file File name to read the network from.
 305  * \return A newly allocated comparator network or \c NULL on error.
 306  * \see sn_network_read
 307  */
 308 sn_network_t *sn_network_read_file (const char *file);
 309
 310 /**
 311  * Writes a comparator network to a file handle.
 312  *
 313  * \param n The comparator network to write.
 314  * \param fh The file handle to write to. Must be opened in write mode.
 315  * \return Zero on success, non-zero on failure.
 316  * \see sn_network_write_file
 317  */
 318 int sn_network_write (sn_network_t *n, FILE *fh);
 319
 320 /**
 321  * Writes a comparator network to a file.
 322  *
 323  * \param n The comparator network to write.
 324  * \param fh The file name to write the network to.
 325  * \return Zero on success, non-zero on failure.
 326  * \see sn_network_write
 327  */
 328 int sn_network_write_file (sn_network_t *n, const char *file);
 329
 330 /**
 331  * Creates a serialized form of the given comparator network. The serialized
 332  * form is byte-order independent and can easily be sent over a computer
 333  * network.
 334  *
 335  * \param n The comparator network to serialize.
 336  * \param[out] ret_buffer Pointer to a pointer into which the location of the
 337  *   allocated memory will be written. It is the caller's responsibility to
 338  *   free this memory.
 339  * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
 340  *   allocated memory will be written.
 341  * \return Zero on success, non-zero on failure.
 342  * \see sn_network_unserialize
 343  */
 344 int sn_network_serialize (sn_network_t *n, char **ret_buffer,
 345     size_t *ret_buffer_size);
 346
 347 /**
 348  * Creates a comparator network from its serialized form.
 349  *
 350  * \param buffer Pointer to a buffer containing the comparator network in
 351  *   serialized form.
 352  * \param buffer_size Size of the buffer (in bytes).
 353  * \return Pointer to the newly allocated comparator network or \c NULL on
 354  *   error.
 355  * \see sn_network_serialize
 356  */
 357 sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size);
 358
 359 /**
 360  * Compares two networks and returns zero if they are equal. If they are not
 361  * equal, a number greater than zero or less than zero is returned in a
 362  * consistent matter, so this function can be used to sort networks and detect
 363  * duplicates. It is strongly recommended that you call sn_network_unify()
 364  * before comparing two networks, because they internal structure does matter
 365  * for this function.
 366  *
 367  * \return Zero if the two networks are equal, non-zero otherwise. Return
 368  *   values are consistent so this function can be used to sort networks.
 369  * \see sn_network_unify
 370  */
 371 int sn_network_compare (const sn_network_t *n0, const sn_network_t *n1);
 372
 373 uint64_t sn_network_get_hashval (const sn_network_t *n);
 374
 375 #endif /* SN_NETWORK_H */
 376
 377 /* vim: set shiftwidth=2 softtabstop=2 : */