Author: sandervanderburg
Date: Sun Dec 5 16:12:35 2010
New Revision: 24973
URL: https://svn.nixos.org/websvn/nix/?rev=24973&sc=1
Log:
Added initial implementation of multiway cut approximation algorithm
Added:
disnix/dydisnix/trunk/src/multiwaycut/
disnix/dydisnix/trunk/src/multiwaycut/Makefile.am
disnix/dydisnix/trunk/src/multiwaycut/main.c
disnix/dydisnix/trunk/src/multiwaycut/multiwaycut.c
disnix/dydisnix/trunk/src/multiwaycut/multiwaycut.h
disnix/dydisnix/trunk/src/multiwaycut/targetmapping.c
disnix/dydisnix/trunk/src/multiwaycut/targetmapping.h
Modified:
disnix/dydisnix/trunk/configure.ac
disnix/dydisnix/trunk/data/extfilters.nix.in
disnix/dydisnix/trunk/scripts/dydisnix-gendist.in
disnix/dydisnix/trunk/src/Makefile.am
disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.c
disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.h
Modified: disnix/dydisnix/trunk/configure.ac
==============================================================================
--- disnix/dydisnix/trunk/configure.ac Sun Dec 5 11:42:24 2010 (r24972)
+++ disnix/dydisnix/trunk/configure.ac Sun Dec 5 16:12:35 2010 (r24973)
@@ -58,6 +58,7 @@
src/Makefile
src/filter-buildable/Makefile
src/divide/Makefile
+src/multiwaycut/Makefile
src/libmapping/Makefile
src/libservices/Makefile
src/libinfproperties/Makefile
Modified: disnix/dydisnix/trunk/data/extfilters.nix.in
==============================================================================
--- disnix/dydisnix/trunk/data/extfilters.nix.in Sun Dec 5 11:42:24
2010 (r24972)
+++ disnix/dydisnix/trunk/data/extfilters.nix.in Sun Dec 5 16:12:35
2010 (r24973)
@@ -68,4 +68,14 @@
> $out
'';
})}";
+
+ multiwaycut = {distribution}:
+ import "${(pkgs.stdenv.mkDerivation {
+ name = "distribution.nix";
+ buildInputs = [ @prefix@ ];
+ buildCommand =
+ ''
+ dydisnix-multiwaycut ${generateDistributionXML distribution} > $out
+ '';
+ })}";
}
Modified: disnix/dydisnix/trunk/scripts/dydisnix-gendist.in
==============================================================================
--- disnix/dydisnix/trunk/scripts/dydisnix-gendist.in Sun Dec 5 11:42:24
2010 (r24972)
+++ disnix/dydisnix/trunk/scripts/dydisnix-gendist.in Sun Dec 5 16:12:35
2010 (r24973)
@@ -50,7 +50,7 @@
;;
-q|--qos)
qosFile=`readlink -f $2`
- qosArg="--argstr qosFile \"$(readlink -f $qosFile)\""
+ qosArg="--argstr qosFile $(readlink -f $qosFile)"
;;
--filter-buildable)
filterBuildable=1
Modified: disnix/dydisnix/trunk/src/Makefile.am
==============================================================================
--- disnix/dydisnix/trunk/src/Makefile.am Sun Dec 5 11:42:24 2010
(r24972)
+++ disnix/dydisnix/trunk/src/Makefile.am Sun Dec 5 16:12:35 2010
(r24973)
@@ -1 +1 @@
-SUBDIRS = libservices libinfproperties libmapping filter-buildable divide
+SUBDIRS = libservices libinfproperties libmapping filter-buildable divide
multiwaycut
Modified: disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.c
==============================================================================
--- disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.c Sun Dec
5 11:42:24 2010 (r24972)
+++ disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.c Sun Dec
5 16:12:35 2010 (r24973)
@@ -167,3 +167,25 @@
g_print("}\n");
}
+
+int distribution_item_index(GArray *candidate_target_array, gchar *service)
+{
+ gint left = 0;
+ gint right = candidate_target_array->len - 1;
+
+ while(left <= right)
+ {
+ gint mid = (left + right) / 2;
+ DistributionItem *mid_distribution_item =
g_array_index(candidate_target_array, DistributionItem*, mid);
+ gint status = g_strcmp0(mid_distribution_item->service, service);
+
+ if(status == 0)
+ return mid; /* Return index of the found service */
+ else if(status > 0)
+ right = mid - 1;
+ else if(status < 0)
+ left = mid + 1;
+ }
+
+ return -1; /* service not found */
+}
Modified: disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.h
==============================================================================
--- disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.h Sun Dec
5 11:42:24 2010 (r24972)
+++ disnix/dydisnix/trunk/src/libmapping/candidatetargetmapping.h Sun Dec
5 16:12:35 2010 (r24973)
@@ -22,4 +22,6 @@
void print_expr_of_candidate_target_array(GArray *candidate_target_array);
+int distribution_item_index(GArray *candidate_target_array, gchar *service);
+
#endif
Added: disnix/dydisnix/trunk/src/multiwaycut/Makefile.am
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/multiwaycut/Makefile.am Sun Dec 5 16:12:35
2010 (r24973)
@@ -0,0 +1,7 @@
+AM_CPPFLAGS = -ggdb
+
+bin_PROGRAMS = dydisnix-multiwaycut
+
+dydisnix_multiwaycut_SOURCES = targetmapping.c multiwaycut.c main.c
+dydisnix_multiwaycut_LDADD = ../libmapping/libmapping.la
+dydisnix_multiwaycut_CFLAGS = -I../libmapping $(GLIB_CFLAGS)
Added: disnix/dydisnix/trunk/src/multiwaycut/main.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/multiwaycut/main.c Sun Dec 5 16:12:35
2010 (r24973)
@@ -0,0 +1,47 @@
+#include <stdio.h>
+#include <getopt.h>
+#define _GNU_SOURCE
+#include "multiwaycut.h"
+
+static void print_usage(char *command)
+{
+ fprintf(stderr, "Usage:\n");
+ fprintf(stderr, "%s distribution.xml\n", command);
+ fprintf(stderr, "%s {-h | --help}\n", command);
+}
+
+int main(int argc, char *argv[])
+{
+ /* Declarations */
+ int c, option_index = 0;
+ struct option long_options[] =
+ {
+ {"help", no_argument, 0, 'h'},
+ {0, 0, 0, 0}
+ };
+
+ /* Parse command-line options */
+ while((c = getopt_long(argc, argv, "h", long_options, &option_index)) !=
-1)
+ {
+ switch(c)
+ {
+ case 'h':
+ print_usage(argv[0]);
+ return 0;
+ }
+ }
+
+ /* Validate options */
+
+ if(optind >= argc)
+ {
+ fprintf(stderr, "ERROR: No distribution XML specified!\n");
+ return 1;
+ }
+ else
+ {
+ /* Execute operation */
+ multiwaycut(argv[optind]);
+ return 0;
+ }
+}
Added: disnix/dydisnix/trunk/src/multiwaycut/multiwaycut.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/multiwaycut/multiwaycut.c Sun Dec 5 16:12:35
2010 (r24973)
@@ -0,0 +1,159 @@
+#include "targetmapping.h"
+#include "candidatetargetmapping.h"
+
+static GArray *filter_cuts(GArray *target_mapping_array)
+{
+ unsigned int i;
+ GArray *filtered = g_array_new(FALSE, FALSE, sizeof(TargetMappingItem*));
+
+ for(i = 0; i < target_mapping_array->len; i++)
+ {
+ unsigned int j;
+ TargetMappingItem *item = g_array_index(target_mapping_array,
TargetMappingItem*, i);
+
+ TargetMappingItem *cut_item =
(TargetMappingItem*)g_malloc(sizeof(TargetMappingItem));
+ cut_item->target = item->target;
+ cut_item->services = g_array_new(FALSE, FALSE,
sizeof(TargetMappingItem*));
+
+ for(j = 0; j < item->services->len; j++)
+ {
+ gchar *service = g_array_index(item->services, gchar*, j);
+ unsigned int k;
+
+ for(k = i + 1; k < target_mapping_array->len; k++)
+ {
+ TargetMappingItem *target_item =
g_array_index(target_mapping_array, TargetMappingItem*, k);
+
+ if(service_name_index(target_item, service) != -1)
+ {
+ g_array_append_val(cut_item->services, service);
+ break;
+ }
+ }
+ }
+
+ g_array_append_val(filtered, cut_item);
+ }
+
+ return filtered;
+}
+
+static void discard_heaviest_cut(GArray *target_mapping_array)
+{
+ unsigned int i;
+ int max_len = 0;
+ int max_index = -1;
+
+ /* For each cut determine the length */
+ for(i = 0; i < target_mapping_array->len; i++)
+ {
+ TargetMappingItem *item = g_array_index(target_mapping_array,
TargetMappingItem*, i);
+
+ if(item->services->len > max_len)
+ {
+ max_index = i;
+ max_len = item->services->len;
+ }
+ }
+
+ /* Discard the heaviest cut */
+ if(max_index >= 0)
+ {
+ TargetMappingItem *item = g_array_index(target_mapping_array,
TargetMappingItem*, max_index);
+
+ g_array_free(item->services, TRUE);
+ g_free(item);
+ g_array_remove_index(target_mapping_array, max_index);
+ }
+}
+
+static GArray *create_candidate_target_mapping_from(GArray
*target_mapping_array)
+{
+ unsigned int i;
+ GArray *result = g_array_new(FALSE, FALSE, sizeof(DistributionItem*));
+
+ for(i = 0; i < target_mapping_array->len; i++)
+ {
+ TargetMappingItem *target_mapping_item =
g_array_index(target_mapping_array, TargetMappingItem*, i);
+ unsigned int j;
+
+ for(j = 0; j < target_mapping_item->services->len; j++)
+ {
+ gchar *service = g_array_index(target_mapping_item->services,
gchar*, j);
+ int index = distribution_item_index(result, service);
+ DistributionItem *distribution_item;
+
+ if(index == -1)
+ {
+ distribution_item =
(DistributionItem*)g_malloc(sizeof(DistributionItem));
+ distribution_item->service = service;
+ distribution_item->targets = g_array_new(FALSE, FALSE,
sizeof(gchar*));
+
+ g_array_append_val(result, distribution_item);
+ }
+ else
+ distribution_item = g_array_index(target_mapping_array,
DistributionItem*, index);
+
+ g_array_append_val(distribution_item->targets,
target_mapping_item->target);
+ }
+ }
+
+ return result;
+}
+
+static void fix_unmapped_services(GArray *initial_candidate_target_array,
GArray *candidate_target_array)
+{
+ unsigned int i;
+
+ for(i = 0; i < initial_candidate_target_array->len; i++)
+ {
+ DistributionItem *item = g_array_index(initial_candidate_target_array,
DistributionItem*, i);
+
+ if(distribution_item_index(candidate_target_array, item->service) == -1)
+ {
+ DistributionItem *candidate_item =
(DistributionItem*)g_malloc(sizeof(DistributionItem));
+ candidate_item->service = item->service;
+ candidate_item->targets = g_array_new(FALSE, FALSE, sizeof(gchar*));
+
+ if(item->targets->len > 0)
+ g_array_append_val(candidate_item->targets,
g_array_index(item->targets, gchar*, 0));
+
+ g_array_append_val(candidate_target_array, candidate_item);
+ g_array_sort(candidate_target_array,
(GCompareFunc)compare_target_mapping_item);
+ }
+ }
+}
+
+void multiwaycut(gchar *distribution_xml)
+{
+ GArray *candidate_target_array =
create_candidate_target_array(distribution_xml);
+ GArray *target_mapping_array =
create_target_mapping_array(candidate_target_array);
+ GArray *filtered;
+ GArray *distmapping;
+ unsigned int i;
+
+ filtered = filter_cuts(target_mapping_array);
+
+ discard_heaviest_cut(filtered);
+
+ distmapping = create_candidate_target_mapping_from(filtered);
+
+ fix_unmapped_services(candidate_target_array, distmapping);
+
+ print_expr_of_candidate_target_array(distmapping);
+
+ /* Cleanup */
+
+ for(i = 0; i < distmapping->len; i++)
+ {
+ DistributionItem *item = g_array_index(distmapping, DistributionItem*,
i);
+ g_array_free(item->targets, TRUE);
+ g_free(item);
+ }
+
+ g_array_free(distmapping, TRUE);
+
+ delete_target_mapping_array(filtered);
+ delete_target_mapping_array(target_mapping_array);
+ delete_candidate_target_array(candidate_target_array);
+}
Added: disnix/dydisnix/trunk/src/multiwaycut/multiwaycut.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/multiwaycut/multiwaycut.h Sun Dec 5 16:12:35
2010 (r24973)
@@ -0,0 +1,7 @@
+#ifndef __MULTIWAYCUT_H
+#define __MUTLIWAYCUT_H
+#include <glib.h>
+
+void multiwaycut(gchar *distribution_xml);
+
+#endif
Added: disnix/dydisnix/trunk/src/multiwaycut/targetmapping.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/multiwaycut/targetmapping.c Sun Dec 5
16:12:35 2010 (r24973)
@@ -0,0 +1,128 @@
+#include "targetmapping.h"
+#include <candidatetargetmapping.h>
+
+gint compare_target_mapping_item(const TargetMappingItem **l, const
TargetMappingItem **r)
+{
+ const TargetMappingItem *left = *l;
+ const TargetMappingItem *right = *r;
+
+ return g_strcmp0(left->target, right->target);
+}
+
+gint target_mapping_index(GArray *target_mapping_array, gchar *target)
+{
+ gint left = 0;
+ gint right = target_mapping_array->len - 1;
+
+ TargetMappingItem compare_mapping;
+ TargetMappingItem *compare_mapping_ptr = &compare_mapping;
+
+ compare_mapping.target = target;
+
+ while(left <= right)
+ {
+ gint mid = (left + right) / 2;
+ TargetMappingItem *mid_target_mapping_item =
g_array_index(target_mapping_array, TargetMappingItem*, mid);
+ gint status = compare_target_mapping_item((const TargetMappingItem**)
&mid_target_mapping_item, (const TargetMappingItem**) &compare_mapping_ptr);
+
+ if(status == 0)
+ return mid; /* Return index of the found target mapping */
+ else if(status > 0)
+ right = mid - 1;
+ else if(status < 0)
+ left = mid + 1;
+ }
+
+ return -1; /* Target mapping not found */
+}
+
+GArray *create_target_mapping_array(GArray *candidate_target_array)
+{
+ GArray *target_mapping_array = g_array_new(FALSE, FALSE,
sizeof(TargetMappingItem*));
+ unsigned int i;
+
+ for(i = 0; i < candidate_target_array->len; i++)
+ {
+ DistributionItem *distribution_item =
g_array_index(candidate_target_array, DistributionItem*, i);
+ GArray *targets = distribution_item->targets;
+ unsigned int j;
+
+ for(j = 0; j < targets->len; j++)
+ {
+ gchar *target = g_array_index(targets, gchar*, j);
+ int target_index = target_mapping_index(target_mapping_array,
target);
+ TargetMappingItem *mapping;
+
+ if(target_index == -1)
+ {
+ mapping =
(TargetMappingItem*)g_malloc(sizeof(TargetMappingItem));
+ mapping->target = target;
+ mapping->services = g_array_new(FALSE, FALSE, sizeof(gchar*));
+
+ g_array_append_val(target_mapping_array, mapping);
+ g_array_sort(target_mapping_array,
(GCompareFunc)compare_target_mapping_item);
+ }
+ else
+ mapping = g_array_index(target_mapping_array,
TargetMappingItem*, target_index);
+
+ g_array_append_val(mapping->services, distribution_item->service);
+ }
+ }
+
+ return target_mapping_array;
+}
+
+void delete_target_mapping_array(GArray *target_mapping_array)
+{
+ unsigned int i;
+
+ for(i = 0; i < target_mapping_array->len; i++)
+ {
+ TargetMappingItem *item = g_array_index(target_mapping_array,
TargetMappingItem*, i);
+ g_array_free(item->services, TRUE);
+ g_free(item);
+ }
+
+ g_array_free(target_mapping_array, TRUE);
+}
+
+void print_target_mapping_array(GArray *target_mapping_array)
+{
+ unsigned int i;
+
+ for(i = 0; i < target_mapping_array->len; i++)
+ {
+ unsigned int j;
+ TargetMappingItem *item = g_array_index(target_mapping_array,
TargetMappingItem*, i);
+
+ g_print("target: %s\n", item->target);
+
+ for(j = 0; j < item->services->len; j++)
+ {
+ gchar *service = g_array_index(item->services, gchar*, j);
+ g_print(" service: %s\n", service);
+ }
+ }
+}
+
+int service_name_index(TargetMappingItem *item, gchar *service)
+{
+ gint left = 0;
+ gint right = item->services->len - 1;
+
+ while(left <= right)
+ {
+ gint mid = (left + right) / 2;
+ gchar *mid_service = g_array_index(item->services, gchar*, mid);
+ gint status = g_strcmp0(mid_service, service);
+
+ if(status == 0)
+ return mid; /* Return index of the found service */
+ else if(status > 0)
+ right = mid - 1;
+ else if(status < 0)
+ left = mid + 1;
+ }
+
+ return -1; /* service not found */
+}
Added: disnix/dydisnix/trunk/src/multiwaycut/targetmapping.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/multiwaycut/targetmapping.h Sun Dec 5
16:12:35 2010 (r24973)
@@ -0,0 +1,23 @@
+#ifndef __SERVICE_MAPPING_H
+#define __SERVICE_MAPPING_H
+#include <glib.h>
+
+typedef struct
+{
+ gchar *target;
+
+ GArray *services;
+}
+TargetMappingItem;
+
+GArray *create_target_mapping_array(GArray *candidate_target_array);
+
+void delete_target_mapping_array(GArray *target_mapping_array);
+
+void print_target_mapping_array(GArray *target_mapping_array);
+
+int service_name_index(TargetMappingItem *item, gchar *service);
+
+gint compare_target_mapping_item(const TargetMappingItem **l, const
TargetMappingItem **r);
+
+#endif
_______________________________________________
nix-commits mailing list
[email protected]
http://mail.cs.uu.nl/mailman/listinfo/nix-commits
