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 #include <stdint.h>
  33 #include <inttypes.h>
  34
  35 #include "sn_comparator.h"
  36
  37 /**
  38  * Struct representing a stage of the comparator network. Don't modify this
  39  * struct yourself, use the sn_stage_* methods instead.
  40  */
  41 struct sn_stage_s
  42 {
  43   int depth;                    /**< Depth of this stage, where zero means closest to the input. */
  44   sn_comparator_t *comparators; /**< Pointer to a list of comparators contained in this stage. */
  45   int comparators_num;          /**< Number of comparators in this stage. */
  46 };
  47 typedef struct sn_stage_s sn_stage_t;
  48
  49 /**
  50  * Direction into which to cut.
  51  *
  52  * \see sn_network_cut_at, sn_stage_cut_at
  53  */
  54 enum sn_network_cut_dir_e
  55 {
  56   DIR_MIN, /**< Assume negative infinity. */
  57   DIR_MAX  /**< Assume positive infinity. */
  58 };
  59
  60 #define SN_STAGE_DEPTH(s) (s)->depth
  61 #define SN_STAGE_COMP_NUM(s) (s)->comparators_num
  62 #define SN_STAGE_COMP_GET(s,n) ((s)->comparators + (n))
  63
  64 /**
  65  * Creates an empty stage and returns a pointer to it. The stage must be freed
  66  * using sn_stage_destroy().
  67  *
  68  * \param depth Depth of the stage within the comparator network. This will be
  69  *   re-set by sn_network_stage_add().
  70  * \return Pointer to the comparator network or \c NULL on error.
  71  */
  72 sn_stage_t *sn_stage_create (int depth);
  73
  74 /**
  75  * Clones an existing stage.
  76  *
  77  * \param s Stage to clone.
  78  * \return Copied stage or \c NULL on error. The returned stage must be freed
  79  *   using sn_stage_destroy().
  80  */
  81 sn_stage_t *sn_stage_clone (const sn_stage_t *s);
  82
  83 /**
  84  * Destroys a stage allocated with sn_stage_create() or one of the other
  85  * methods returning a \c sn_stage_t. This frees all allocated space.
  86  *
  87  * \param s The stage to destroy. May be \c NULL.
  88  */
  89 void sn_stage_destroy (sn_stage_t *s);
  90
  91 /**
  92  * Applies a stage to an array of integers.
  93  *
  94  * \param s Pointer to the stage.
  95  * \param[in,out] values Pointer to integer values to sort. The number of
  96  *   integer values pointed to must be at least the number of inputs of the
  97  *   comparator network. Otherwise, segmentation faults or memory corruption
  98  *   will occur.
  99  * \return Zero on success, non-zero on failure.
 100  * \see sn_network_sort
 101  */
 102 int sn_stage_sort (sn_stage_t *s, int *values);
 103
 104 /**
 105  * Adds a comparator to a stage. If this would return in a conflict (a
 106  * comparator using on of the line already exists in this stage) an error is
 107  * returned.
 108  *
 109  * \param s Pointer to the stage.
 110  * \param c Pointer to a comparator to add. The given comparator is copied. It
 111  *   is the caller's responsibility to free c.
 112  * \return Zero on success, non-zero on failure.
 113  * \see sn_stage_comparator_remove
 114  */
 115 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c);
 116
 117
 118 /**
 119  * Removed a comparator from a stage.
 120  *
 121  * \param s The stage from which to remove the comparator.
 122  * \param index The index of the comparator to remove.
 123  * \return Zero on success, non-zero on failure.
 124  * \see sn_stage_comparator_add
 125  */
 126 int sn_stage_comparator_remove (sn_stage_t *s, int index);
 127
 128 /**
 129  * Checks whether the given comparator can be added to a stage, i.e. if neither
 130  * line if used by another comparator.
 131  *
 132  * \param s Pointer to the stage.
 133  * \param c Pointer to the comparator.
 134  * \return Zero if there is no conflict, one if there is a conflict and two if
 135  *   the comparator is already present in the stage.
 136  */
 137 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c);
 138
 139 /**
 140  * Prints the stage to \c STDOUT using a human readable representation.
 141  *
 142  * \param s The comparator network to display.
 143  * \return Zero on success, non-zero on failure.
 144  * \see sn_network_show
 145  */
 146 int sn_stage_show (sn_stage_t *s);
 147 int sn_stage_show_fh (sn_stage_t *s, FILE *fh);
 148
 149 /**
 150  * Inverts a stage by switching the direction of all comparators.
 151  *
 152  * \param s The stage to invert.
 153  * \return Zero on success, non-zero on failure.
 154  * \see sn_network_invert
 155  */
 156 int sn_stage_invert (sn_stage_t *s);
 157
 158 /**
 159  * Shifts a stage (permutes the inputs). Each input is shifted \c sw positions,
 160  * higher inputs are "wrapped around".
 161  *
 162  * \param s The stage to shift.
 163  * \param sw The number of positions to shift.
 164  * \param inputs_num The number of inputs of the comparator network. This value
 165  *   is used to "wrap around" inputs.
 166  * \return Zero on success, non-zero on failure.
 167  */
 168 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num);
 169
 170 int sn_stage_unify (sn_stage_t *s);
 171
 172 /**
 173  * Swaps two lines. This is used by the algorithm used in
 174  * sn_network_normalize() to transform non-standard sort networks to standard
 175  * sort networks.
 176  *
 177  * \param s The stage on which to operate.
 178  * \param con0 Index of the first line.
 179  * \param con1 Index of the second line.
 180  * \return Zero on success, non-zero on failure.
 181  * \see sn_network_normalize(), sn_comparator_swap()
 182  */
 183 int sn_stage_swap (sn_stage_t *s, int con0, int con1);
 184
 185 /**
 186  * Removes an input / line by assuming positive or negative infinity is applied
 187  * to one line.
 188  *
 189  * \param s The stage to work with.
 190  * \param input The input / line on which is assumed to be positive or negative
 191  *   infinity.
 192  * \param dir Direction in which to cut; whether positive or negative infinity
 193  *   is assumed.
 194  * \return The new position of the infinite value on success or less than zero
 195  *   on failure.
 196  * \see sn_network_cut_at
 197  */
 198 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir);
 199
 200 /* FIXME: Documentation */
 201 int sn_stage_cut (sn_stage_t *s, int *mask, sn_stage_t **prev);
 202
 203 /**
 204  * Remove an input from a stage, remove all touching comparators and adapt the
 205  * input indexes of all remaining comparators.
 206  *
 207  * \param s The stage from which to remove the input.
 208  * \param input The index of the line which to remove.
 209  * \return Zero on success, non-zero on failure.
 210  */
 211 int sn_stage_remove_input (sn_stage_t *s, int input);
 212
 213 /**
 214  * Reads a stage from a \c FILE pointer and return the newly allocated stage.
 215  *
 216  * \param fh The file handle.
 217  * \return Pointer to a newly allocated stage or \c NULL on error.
 218  * \see sn_stage_write
 219  */
 220 sn_stage_t *sn_stage_read (FILE *fh);
 221
 222 /**
 223  * Writes a stage to a \c FILE pointer.
 224  *
 225  * \param s The stage to write.
 226  * \param fh The file handle to write to.
 227  * \return Zero on success, non-zero on failure.
 228  * \see sn_stage_read
 229  */
 230 int sn_stage_write (sn_stage_t *s, FILE *fh);
 231
 232 /**
 233  * Creates a serialized form of the given stage. The serialized form is
 234  * byte-order independent and can easily be sent over a computer network.
 235  *
 236  * \param s The stage to serialize.
 237  * \param[out] ret_buffer Pointer to a pointer into which the location of the
 238  *   allocated memory will be written. It is the caller's responsibility to
 239  *   free this memory.
 240  * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
 241  *   allocated memory will be written.
 242  * \return Zero on success, non-zero on failure.
 243  * \see sn_stage_unserialize(), sn_network_serialize()
 244  */
 245 int sn_stage_serialize (sn_stage_t *s,
 246     char **ret_buffer, size_t *ret_buffer_size);
 247
 248 /**
 249  * Creates a stage from its serialized form.
 250  *
 251  * \param buffer Pointer to a buffer containing the stage in serialized form.
 252  * \param buffer_size Size of the buffer (in bytes).
 253  * \return Pointer to the newly allocated stage or \c NULL on error.
 254  * \see sn_stage_serialize(), sn_network_unserialize()
 255  */
 256 sn_stage_t *sn_stage_unserialize (char **buffer, size_t *buffer_size);
 257
 258 int sn_stage_compare (const sn_stage_t *s0, const sn_stage_t *s1);
 259
 260 uint64_t sn_stage_get_hashval (const sn_stage_t *s);
 261
 262 #endif /* SN_STAGE_H */
 263
 264 /* vim: set shiftwidth=2 softtabstop=2 : */