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 program is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by the
  11  * Free Software Foundation; only version 2 of the License is applicable.
  12  *
  13  * This program is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with this program; if not, write to the Free Software Foundation, Inc.,
  20  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  21  *
  22  * Authors:
  23  *   Florian octo Forster <ff at octo.it>
  24  * \endverbatim
  25  **/
  26
  27 #ifndef SN_STAGE_H
  28 #define SN_STAGE_H 1
  29
  30 #include <stdio.h>
  31
  32 #include "sn_comparator.h"
  33
  34 /**
  35  * Struct representing a stage of the comparator network. Don't modify this
  36  * struct yourself, use the sn_stage_* methods instead.
  37  */
  38 struct sn_stage_s
  39 {
  40   int depth;                    /**< Depth of this stage, where zero means closest to the input. */
  41   sn_comparator_t *comparators; /**< Pointer to a list of comparators contained in this stage. */
  42   int comparators_num;          /**< Number of comparators in this stage. */
  43 };
  44 typedef struct sn_stage_s sn_stage_t;
  45
  46 /**
  47  * Direction into which to cut.
  48  *
  49  * \see sn_network_cut_at, sn_stage_cut_at
  50  */
  51 enum sn_network_cut_dir_e
  52 {
  53   DIR_MIN, /**< Assume negative infinity. */
  54   DIR_MAX  /**< Assume positive infinity. */
  55 };
  56
  57 #define SN_STAGE_DEPTH(s) (s)->depth
  58 #define SN_STAGE_COMP_NUM(s) (s)->comparators_num
  59 #define SN_STAGE_COMP_GET(s,n) ((s)->comparators + (n))
  60
  61 /**
  62  * Creates an empty stage and returns a pointer to it. The stage must be freed
  63  * using sn_stage_destroy().
  64  *
  65  * \param depth Depth of the stage within the comparator network. This will be
  66  *   re-set by sn_network_stage_add().
  67  * \return Pointer to the comparator network or \c NULL on error.
  68  */
  69 sn_stage_t *sn_stage_create (int depth);
  70
  71 /**
  72  * Clones an existing stage.
  73  *
  74  * \param s Stage to clone.
  75  * \return Copied stage or \c NULL on error. The returned stage must be freed
  76  *   using sn_stage_destroy().
  77  */
  78 sn_stage_t *sn_stage_clone (const sn_stage_t *s);
  79
  80 /**
  81  * Destroys a stage allocated with sn_stage_create() or one of the other
  82  * methods returning a \c sn_stage_t. This frees all allocated space.
  83  *
  84  * \param s The stage to destroy. May be \c NULL.
  85  */
  86 void sn_stage_destroy (sn_stage_t *s);
  87
  88 /**
  89  * Applies a stage to an array of integers.
  90  *
  91  * \param s Pointer to the stage.
  92  * \param[in,out] values Pointer to integer values to sort. The number of
  93  *   integer values pointed to must be at least the number of inputs of the
  94  *   comparator network. Otherwise, segmentation faults or memory corruption
  95  *   will occur.
  96  * \return Zero on success, non-zero on failure.
  97  * \see sn_network_sort
  98  */
  99 int sn_stage_sort (sn_stage_t *s, int *values);
 100
 101 /**
 102  * Adds a comparator to a stage. If this would return in a conflict (a
 103  * comparator using on of the line already exists in this stage) an error is
 104  * returned.
 105  *
 106  * \param s Pointer to the stage.
 107  * \param c Pointer to a comparator to add. The given comparator is copied. It
 108  *   is the caller's responsibility to free c.
 109  * \return Zero on success, non-zero on failure.
 110  * \see sn_stage_comparator_remove
 111  */
 112 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c);
 113
 114
 115 /**
 116  * Removed a comparator from a stage.
 117  *
 118  * \param s The stage from which to remove the comparator.
 119  * \param index The index of the comparator to remove.
 120  * \return Zero on success, non-zero on failure.
 121  * \see sn_stage_comparator_add
 122  */
 123 int sn_stage_comparator_remove (sn_stage_t *s, int index);
 124
 125 /**
 126  * Checks whether the given comparator can be added to a stage, i.e. if neither
 127  * line if used by another comparator.
 128  *
 129  * \param s Pointer to the stage.
 130  * \param c Pointer to the comparator.
 131  * \return Zero if there is no conflict, one if there is a conflict and two if
 132  *   the comparator is already present in the stage.
 133  */
 134 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c);
 135
 136 int sn_stage_show (sn_stage_t *s);
 137 int sn_stage_invert (sn_stage_t *s);
 138 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num);
 139 int sn_stage_swap (sn_stage_t *s, int con0, int con1);
 140
 141 /**
 142  * Removes an input / line by assuming positive or negative infinity is applied
 143  * to one line.
 144  *
 145  * \param s The stage to work with.
 146  * \param input The input / line on which is assumed to be positive or negative
 147  *   infinity.
 148  * \param dir Direction in which to cut; whether positive or negative infinity
 149  *   is assumed.
 150  * \return The new position of the infinite value on success or less than zero
 151  *   on failure.
 152  * \see sn_network_cut_at
 153  */
 154 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir);
 155
 156 int sn_stage_remove_input (sn_stage_t *s, int input);
 157
 158 sn_stage_t *sn_stage_read (FILE *fh);
 159 int sn_stage_write (sn_stage_t *s, FILE *fh);
 160
 161 int sn_stage_serialize (sn_stage_t *s,
 162     char **ret_buffer, size_t *ret_buffer_size);
 163 sn_stage_t *sn_stage_unserialize (char **buffer, size_t *buffer_size);
 164
 165 #endif /* SN_STAGE_H */
 166
 167 /* vim: set shiftwidth=2 softtabstop=2 : */