src/sn_stage.h

   1 /**
   2  * \file sn_stage.h
   3  * \brief The sn_stage_t class and associated methods.
   4  *
   5  * \verbatim
   6  * libsortnetwork - src/sn_stage.h
   7  * Copyright (C) 2008-2010  Florian octo Forster
   8  *
   9  * This library is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU Lesser General Public License as published by
  11  * the Free Software Foundation; either version 2.1 of the License, or (at
  12  * your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful, but WITHOUT
  15  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
  17  * for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public License
  20  * along with this library; if not, write to the Free Software Foundation,
  21  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  22  *
  23  * Authors:
  24  *   Florian octo Forster <ff at octo.it>
  25  * \endverbatim
  26  **/
  27
  28 #ifndef SN_STAGE_H
  29 #define SN_STAGE_H 1
  30
  31 #include <stdio.h>
  32
  33 #include "sn_comparator.h"
  34
  35 /**
  36  * Struct representing a stage of the comparator network. Don't modify this
  37  * struct yourself, use the sn_stage_* methods instead.
  38  */
  39 struct sn_stage_s
  40 {
  41   int depth;                    /**< Depth of this stage, where zero means closest to the input. */
  42   sn_comparator_t *comparators; /**< Pointer to a list of comparators contained in this stage. */
  43   int comparators_num;          /**< Number of comparators in this stage. */
  44 };
  45 typedef struct sn_stage_s sn_stage_t;
  46
  47 /**
  48  * Direction into which to cut.
  49  *
  50  * \see sn_network_cut_at, sn_stage_cut_at
  51  */
  52 enum sn_network_cut_dir_e
  53 {
  54   DIR_MIN, /**< Assume negative infinity. */
  55   DIR_MAX  /**< Assume positive infinity. */
  56 };
  57
  58 #define SN_STAGE_DEPTH(s) (s)->depth
  59 #define SN_STAGE_COMP_NUM(s) (s)->comparators_num
  60 #define SN_STAGE_COMP_GET(s,n) ((s)->comparators + (n))
  61
  62 /**
  63  * Creates an empty stage and returns a pointer to it. The stage must be freed
  64  * using sn_stage_destroy().
  65  *
  66  * \param depth Depth of the stage within the comparator network. This will be
  67  *   re-set by sn_network_stage_add().
  68  * \return Pointer to the comparator network or \c NULL on error.
  69  */
  70 sn_stage_t *sn_stage_create (int depth);
  71
  72 /**
  73  * Clones an existing stage.
  74  *
  75  * \param s Stage to clone.
  76  * \return Copied stage or \c NULL on error. The returned stage must be freed
  77  *   using sn_stage_destroy().
  78  */
  79 sn_stage_t *sn_stage_clone (const sn_stage_t *s);
  80
  81 /**
  82  * Destroys a stage allocated with sn_stage_create() or one of the other
  83  * methods returning a \c sn_stage_t. This frees all allocated space.
  84  *
  85  * \param s The stage to destroy. May be \c NULL.
  86  */
  87 void sn_stage_destroy (sn_stage_t *s);
  88
  89 /**
  90  * Applies a stage to an array of integers.
  91  *
  92  * \param s Pointer to the stage.
  93  * \param[in,out] values Pointer to integer values to sort. The number of
  94  *   integer values pointed to must be at least the number of inputs of the
  95  *   comparator network. Otherwise, segmentation faults or memory corruption
  96  *   will occur.
  97  * \return Zero on success, non-zero on failure.
  98  * \see sn_network_sort
  99  */
 100 int sn_stage_sort (sn_stage_t *s, int *values);
 101
 102 /**
 103  * Adds a comparator to a stage. If this would return in a conflict (a
 104  * comparator using on of the line already exists in this stage) an error is
 105  * returned.
 106  *
 107  * \param s Pointer to the stage.
 108  * \param c Pointer to a comparator to add. The given comparator is copied. It
 109  *   is the caller's responsibility to free c.
 110  * \return Zero on success, non-zero on failure.
 111  * \see sn_stage_comparator_remove
 112  */
 113 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c);
 114
 115
 116 /**
 117  * Removed a comparator from a stage.
 118  *
 119  * \param s The stage from which to remove the comparator.
 120  * \param index The index of the comparator to remove.
 121  * \return Zero on success, non-zero on failure.
 122  * \see sn_stage_comparator_add
 123  */
 124 int sn_stage_comparator_remove (sn_stage_t *s, int index);
 125
 126 /**
 127  * Checks whether the given comparator can be added to a stage, i.e. if neither
 128  * line if used by another comparator.
 129  *
 130  * \param s Pointer to the stage.
 131  * \param c Pointer to the comparator.
 132  * \return Zero if there is no conflict, one if there is a conflict and two if
 133  *   the comparator is already present in the stage.
 134  */
 135 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c);
 136
 137 /**
 138  * Prints the stage to \c STDOUT using a human readable representation.
 139  *
 140  * \param s The comparator network to display.
 141  * \return Zero on success, non-zero on failure.
 142  * \see sn_network_show
 143  */
 144 int sn_stage_show (sn_stage_t *s);
 145
 146 /**
 147  * Inverts a stage by switching the direction of all comparators.
 148  *
 149  * \param s The stage to invert.
 150  * \return Zero on success, non-zero on failure.
 151  * \see sn_network_invert
 152  */
 153 int sn_stage_invert (sn_stage_t *s);
 154
 155 /**
 156  * Shifts a stage (permutes the inputs). Each input is shifted \c sw positions,
 157  * higher inputs are "wrapped around".
 158  *
 159  * \param s The stage to shift.
 160  * \param sw The number of positions to shift.
 161  * \param inputs_num The number of inputs of the comparator network. This value
 162  *   is used to "wrap around" inputs.
 163  * \return Zero on success, non-zero on failure.
 164  */
 165 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num);
 166
 167 /**
 168  * Swaps two lines. This is used by the algorithm used in
 169  * sn_network_normalize() to transform non-standard sort networks to standard
 170  * sort networks.
 171  *
 172  * \param s The stage on which to operate.
 173  * \param con0 Index of the first line.
 174  * \param con1 Index of the second line.
 175  * \return Zero on success, non-zero on failure.
 176  * \see sn_network_normalize(), sn_comparator_swap()
 177  */
 178 int sn_stage_swap (sn_stage_t *s, int con0, int con1);
 179
 180 /**
 181  * Removes an input / line by assuming positive or negative infinity is applied
 182  * to one line.
 183  *
 184  * \param s The stage to work with.
 185  * \param input The input / line on which is assumed to be positive or negative
 186  *   infinity.
 187  * \param dir Direction in which to cut; whether positive or negative infinity
 188  *   is assumed.
 189  * \return The new position of the infinite value on success or less than zero
 190  *   on failure.
 191  * \see sn_network_cut_at
 192  */
 193 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir);
 194
 195 /* FIXME: Documentation */
 196 int sn_stage_cut (sn_stage_t *s, int *mask, sn_stage_t **prev);
 197
 198 /**
 199  * Remove an input from a stage, remove all touching comparators and adapt the
 200  * input indexes of all remaining comparators.
 201  *
 202  * \param s The stage from which to remove the input.
 203  * \param input The index of the line which to remove.
 204  * \return Zero on success, non-zero on failure.
 205  */
 206 int sn_stage_remove_input (sn_stage_t *s, int input);
 207
 208 /**
 209  * Reads a stage from a \c FILE pointer and return the newly allocated stage.
 210  *
 211  * \param fh The file handle.
 212  * \return Pointer to a newly allocated stage or \c NULL on error.
 213  * \see sn_stage_write
 214  */
 215 sn_stage_t *sn_stage_read (FILE *fh);
 216
 217 /**
 218  * Writes a stage to a \c FILE pointer.
 219  *
 220  * \param s The stage to write.
 221  * \param fh The file handle to write to.
 222  * \return Zero on success, non-zero on failure.
 223  * \see sn_stage_read
 224  */
 225 int sn_stage_write (sn_stage_t *s, FILE *fh);
 226
 227 /**
 228  * Creates a serialized form of the given stage. The serialized form is
 229  * byte-order independent and can easily be sent over a computer network.
 230  *
 231  * \param s The stage to serialize.
 232  * \param[out] ret_buffer Pointer to a pointer into which the location of the
 233  *   allocated memory will be written. It is the caller's responsibility to
 234  *   free this memory.
 235  * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
 236  *   allocated memory will be written.
 237  * \return Zero on success, non-zero on failure.
 238  * \see sn_stage_unserialize(), sn_network_serialize()
 239  */
 240 int sn_stage_serialize (sn_stage_t *s,
 241     char **ret_buffer, size_t *ret_buffer_size);
 242
 243 /**
 244  * Creates a stage from its serialized form.
 245  *
 246  * \param buffer Pointer to a buffer containing the stage in serialized form.
 247  * \param buffer_size Size of the buffer (in bytes).
 248  * \return Pointer to the newly allocated stage or \c NULL on error.
 249  * \see sn_stage_serialize(), sn_network_unserialize()
 250  */
 251 sn_stage_t *sn_stage_unserialize (char **buffer, size_t *buffer_size);
 252
 253 #endif /* SN_STAGE_H */
 254
 255 /* vim: set shiftwidth=2 softtabstop=2 : */