X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=blobdiff_plain;f=src%2Fsn_network.h;h=f94a2377cc9dc740bdf9e382238e8f26a465ac8e;hp=ee95e8ee973dda6a2ddb9f4592c01bf0d3c5fa0e;hb=785cb745f68b61aa83820a4f85a8c91a0e015228;hpb=3a18f201b43da9852a2e19941b9a60f512409877 diff --git a/src/sn_network.h b/src/sn_network.h index ee95e8e..f94a237 100644 --- a/src/sn_network.h +++ b/src/sn_network.h @@ -8,29 +8,31 @@ * 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 * \endverbatim **/ - #ifndef SN_NETWORK_H #define SN_NETWORK_H 1 #include +#include +#include #include "sn_comparator.h" #include "sn_stage.h" @@ -87,6 +89,36 @@ void sn_network_destroy (sn_network_t *n); 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. @@ -127,7 +159,7 @@ int sn_network_comparator_add (sn_network_t *n, const sn_comparator_t *c); * * \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); @@ -157,7 +189,7 @@ 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 STDOUT using a human readable + * Prints the comparator network to \c STDOUT using a human readable * representation. * * \param n The comparator network to display. @@ -201,6 +233,18 @@ int sn_network_compress (sn_network_t *n); */ 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 @@ -217,6 +261,9 @@ int sn_network_normalize (sn_network_t *n); */ int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir); +/* FIXME: Documentation */ +int sn_network_cut (sn_network_t *n, int *mask); + /** * An alias for sn_network_combine_odd_even_merge(). */ @@ -228,8 +275,8 @@ sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1); * * \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); @@ -238,7 +285,7 @@ sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t * * * \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); @@ -246,7 +293,7 @@ sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, sn_network_t * Reads a comparator network from a open file handle. * * \param fh The FILE pointer to read from. - * \return A newly allocated comparator network or NULL on error. + * \return A newly allocated comparator network or \c NULL on error. * \see sn_network_read_file */ sn_network_t *sn_network_read (FILE *fh); @@ -255,7 +302,7 @@ 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 NULL on error. + * \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); @@ -303,10 +350,28 @@ int sn_network_serialize (sn_network_t *n, char **ret_buffer, * \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 NULL on error. + * \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 : */