* libsortnetwork - src/sn_network.h
* Copyright (C) 2008-2010 Florian octo Forster
*
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; only version 2 of the License is applicable.
+ * This library is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
*
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
+ * This library is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
+ * for more details.
*
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this library; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
* Authors:
* Florian octo Forster <ff at octo.it>
* \endverbatim
**/
-
#ifndef SN_NETWORK_H
#define SN_NETWORK_H 1
#include <stdio.h>
+#include <stdint.h>
+#include <inttypes.h>
#include "sn_comparator.h"
#include "sn_stage.h"
#define SN_NETWORK_INPUT_NUM(n) (n)->inputs_num
/**
- * Creates an empty comparator network and returns a pointer to it.
+ * Creates an empty comparator network and returns a pointer to it. The
+ * comparator network must be freed using sn_network_destroy().
*
* \param inputs_num Number of inputs the comparator network has.
- * \return Pointer to the comparator network or NULL on error.
+ * \return Pointer to the comparator network or \c NULL on error.
*/
sn_network_t *sn_network_create (int inputs_num);
* Clones an existing comparator network.
*
* \param n Comparator network to clone.
- * \return Copied sort network or NULL on error. The returned network must be
- * freed using sn_network_destroy().
+ * \return Copied sort network or \c NULL on error. The returned network must
+ * be freed using sn_network_destroy().
*/
sn_network_t *sn_network_clone (const sn_network_t *n);
/**
* Destroys a comparator network allocated with sn_network_create() or one of
- * the other methods returning a sn_network_t. This frees all allocated space.
+ * the other methods returning a \c sn_network_t. This frees all allocated
+ * space.
*
- * \param n The comparator network to destroy. May be NULL.
+ * \param n The comparator network to destroy. May be \c NULL.
*/
void sn_network_destroy (sn_network_t *n);
* Creates a new sort network using Batcher's Odd-Even-Mergesort algorithm.
*
* \param inputs_num Number of inputs / outputs of the sorting network.
- * \return A pointer to the newly allocated sorting network or NULL if an
+ * \return A pointer to the newly allocated sorting network or \c NULL if an
* invalid number of inputs was given or allocation failed.
*/
sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
/**
+ * Creates a new sort network using Batcher's Bitonic-Mergesort algorithm.
+ *
+ * \param inputs_num Number of inputs / outputs of the sorting network.
+ * \return A pointer to the newly allocated sorting network or \c NULL if an
+ * invalid number of inputs was given or allocation failed.
+ */
+sn_network_t *sn_network_create_bitonic_mergesort (int inputs_num);
+
+/**
+ * Creates a new sorting network using the Pairwise sorting algorithm published
+ * by Ian Parberry.
+ * \param inputs_num Number of inputs / outputs of the sorting network.
+ * \return A pointer to the newly allocated sorting network or \c NULL if an
+ * invalid number of inputs was given or allocation failed.
+ */
+sn_network_t *sn_network_create_pairwise (int inputs_num);
+
+/**
+ * Append another network to a given network.
+ *
+ * \param n The comparator network to which the other network is added. This
+ * network is modified.
+ * \param other The network to be added to the first network. This network is
+ * consumed by this function and the memory pointed to is freed. You cannot
+ * use that network after this call, so use sn_network_clone() if required.
+ * \return Zero on success, non-zero on failure.
+ */
+int sn_network_network_add (sn_network_t *n, sn_network_t *other);
+
+/**
* Append a new stage to a comparator network.
*
* \param n The comparator network to which to add the stage.
*
* \param n Comparator network to work with.
* \return The number of comparators contained in the network or less than zero
- * on error (n is NULL).
+ * on error (\c n is \c NULL).
*/
int sn_network_get_comparator_num (const sn_network_t *n);
* comparator network. Otherwise, segmentation faults or memory corruption
* will occur.
* \return Zero on success, non-zero on failure.
+ * \see sn_stage_sort
*/
int sn_network_sort (sn_network_t *n, int *values);
*/
int sn_network_brute_force_check (sn_network_t *n);
+/**
+ * Prints the comparator network to \c STDOUT using a human readable
+ * representation.
+ *
+ * \param n The comparator network to display.
+ * \return Zero on success, non-zero on failure.
+ */
int sn_network_show (sn_network_t *n);
+int sn_network_show_fh (sn_network_t *n, FILE *fh);
/**
* Inverts a comparator network by switching the direction of all comparators.
*/
int sn_network_normalize (sn_network_t *n);
+int sn_network_unify (sn_network_t *n);
+
+/**
+ * Removes an input and all comparators touching that input from the comparator
+ * network.
+ *
+ * \param n The network to modify.
+ * \param input The zero-based index of the input to remove.
+ * \return Zero on success, non-zero on failure.
+ */
+int sn_network_remove_input (sn_network_t *n, int input);
+
/**
* Removes an inputs from a comparator network by assuming positive or negative
* infinity to be supplied to a given input. The value will take a
* \return Zero on success, non-zero on failure.
*/
int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
-sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1,
- int is_power_of_two);
-sn_network_t *sn_network_combine_bitonic (sn_network_t *n0, sn_network_t *n1);
+
+/* FIXME: Documentation */
+int sn_network_cut (sn_network_t *n, int *mask);
+
+/**
+ * An alias for sn_network_combine_odd_even_merge().
+ */
+sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1);
/**
* Combines two comparator networks using a bitonic merger. The number of
*
* \param n0 First network.
* \param n1 Second network.
- * \return Newly allocated network with twice the number of inputs or NULL on
- * error.
+ * \return Newly allocated network with twice the number of inputs or \c NULL
+ * on error.
*/
+sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t *n1);
/**
* Combines two comparator networks using the odd-even-merger.
*
* \param n0 First network.
* \param n1 Second network.
- * \return Newly allocated network or NULL on error.
+ * \return Newly allocated network or \c NULL on error.
*/
sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t *n1);
+/**
+ * Reads a comparator network from a open file handle.
+ *
+ * \param fh The FILE pointer to read from.
+ * \return A newly allocated comparator network or \c NULL on error.
+ * \see sn_network_read_file
+ */
sn_network_t *sn_network_read (FILE *fh);
+
+/**
+ * Reads a comparator network from a file.
+ *
+ * \param file File name to read the network from.
+ * \return A newly allocated comparator network or \c NULL on error.
+ * \see sn_network_read
+ */
sn_network_t *sn_network_read_file (const char *file);
+
+/**
+ * Writes a comparator network to a file handle.
+ *
+ * \param n The comparator network to write.
+ * \param fh The file handle to write to. Must be opened in write mode.
+ * \return Zero on success, non-zero on failure.
+ * \see sn_network_write_file
+ */
int sn_network_write (sn_network_t *n, FILE *fh);
+
+/**
+ * Writes a comparator network to a file.
+ *
+ * \param n The comparator network to write.
+ * \param fh The file name to write the network to.
+ * \return Zero on success, non-zero on failure.
+ * \see sn_network_write
+ */
int sn_network_write_file (sn_network_t *n, const char *file);
+/**
+ * Creates a serialized form of the given comparator network. The serialized
+ * form is byte-order independent and can easily be sent over a computer
+ * network.
+ *
+ * \param n The comparator network to serialize.
+ * \param[out] ret_buffer Pointer to a pointer into which the location of the
+ * allocated memory will be written. It is the caller's responsibility to
+ * free this memory.
+ * \param[out] ret_buffer_size Pointer to a size_t into which the size of the
+ * allocated memory will be written.
+ * \return Zero on success, non-zero on failure.
+ * \see sn_network_unserialize
+ */
int sn_network_serialize (sn_network_t *n, char **ret_buffer,
size_t *ret_buffer_size);
+
+/**
+ * Creates a comparator network from its serialized form.
+ *
+ * \param buffer Pointer to a buffer containing the comparator network in
+ * serialized form.
+ * \param buffer_size Size of the buffer (in bytes).
+ * \return Pointer to the newly allocated comparator network or \c NULL on
+ * error.
+ * \see sn_network_serialize
+ */
sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size);
+
+/**
+ * Compares two networks and returns zero if they are equal. If they are not
+ * equal, a number greater than zero or less than zero is returned in a
+ * consistent matter, so this function can be used to sort networks and detect
+ * duplicates. It is strongly recommended that you call sn_network_unify()
+ * before comparing two networks, because they internal structure does matter
+ * for this function.
+ *
+ * \return Zero if the two networks are equal, non-zero otherwise. Return
+ * values are consistent so this function can be used to sort networks.
+ * \see sn_network_unify
+ */
+int sn_network_compare (const sn_network_t *n0, const sn_network_t *n1);
+
+uint64_t sn_network_get_hashval (const sn_network_t *n);
+
#endif /* SN_NETWORK_H */
/* vim: set shiftwidth=2 softtabstop=2 : */