Author: sandervanderburg
Date: Mon Dec 6 14:04:20 2010
New Revision: 25002
URL: https://svn.nixos.org/websvn/nix/?rev=25002&sc=1
Log:
- Added minsetcover approximation algorithm, for cost efficient deployment
- Separated inverse mapping into a separate library (because minsetcover also
needs it)
Added:
disnix/dydisnix/trunk/src/libinvmapping/
disnix/dydisnix/trunk/src/libinvmapping/Makefile.am
disnix/dydisnix/trunk/src/libinvmapping/targetmapping.c
disnix/dydisnix/trunk/src/libinvmapping/targetmapping.h
disnix/dydisnix/trunk/src/minsetcover/
disnix/dydisnix/trunk/src/minsetcover/Makefile.am
disnix/dydisnix/trunk/src/minsetcover/main.c
disnix/dydisnix/trunk/src/minsetcover/minsetcover.c
disnix/dydisnix/trunk/src/minsetcover/minsetcover.h
Deleted:
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/src/Makefile.am
disnix/dydisnix/trunk/src/multiwaycut/Makefile.am
Modified: disnix/dydisnix/trunk/configure.ac
==============================================================================
--- disnix/dydisnix/trunk/configure.ac Mon Dec 6 13:45:07 2010 (r25001)
+++ disnix/dydisnix/trunk/configure.ac Mon Dec 6 14:04:20 2010 (r25002)
@@ -59,7 +59,9 @@
src/filter-buildable/Makefile
src/divide/Makefile
src/multiwaycut/Makefile
+src/minsetcover/Makefile
src/libmapping/Makefile
+src/libinvmapping/Makefile
src/libservices/Makefile
src/libinfproperties/Makefile
data/extfilters.nix
Modified: disnix/dydisnix/trunk/data/extfilters.nix.in
==============================================================================
--- disnix/dydisnix/trunk/data/extfilters.nix.in Mon Dec 6 13:45:07
2010 (r25001)
+++ disnix/dydisnix/trunk/data/extfilters.nix.in Mon Dec 6 14:04:20
2010 (r25002)
@@ -78,4 +78,19 @@
dydisnix-multiwaycut ${generateDistributionXML distribution} > $out
'';
})}";
+
+ minsetcover = {services, infrastructure, distribution, targetProperty}:
+ import "${(pkgs.stdenv.mkDerivation {
+ name = "distribution.nix";
+ buildInputs = [ @prefix@ ];
+ buildCommand =
+ ''
+ dydisnix-minsetcover \
+ --services-xml ${generateServicesXML services} \
+ --infrastructure-xml ${generateInfrastructureXML infrastructure} \
+ --distribution-xml ${generateDistributionXML distribution} \
+ --target-property ${targetProperty} \
+ > $out
+ '';
+ })}";
}
Modified: disnix/dydisnix/trunk/src/Makefile.am
==============================================================================
--- disnix/dydisnix/trunk/src/Makefile.am Mon Dec 6 13:45:07 2010
(r25001)
+++ disnix/dydisnix/trunk/src/Makefile.am Mon Dec 6 14:04:20 2010
(r25002)
@@ -1 +1 @@
-SUBDIRS = libservices libinfproperties libmapping filter-buildable divide
multiwaycut
+SUBDIRS = libservices libinfproperties libmapping libinvmapping
filter-buildable divide multiwaycut minsetcover
Added: disnix/dydisnix/trunk/src/libinvmapping/Makefile.am
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/libinvmapping/Makefile.am Mon Dec 6 14:04:20
2010 (r25002)
@@ -0,0 +1,8 @@
+AM_CPPFLAGS=-ggdb
+
+pkglib_LTLIBRARIES = libinvmapping.la
+pkginclude_HEADERS = targetmapping.h
+
+libinvmapping_la_SOURCES = targetmapping.c
+libinvmapping_la_CFLAGS = $(LIBXML2_CFLAGS) $(GLIB_CFLAGS) -I../libmapping
$(DISNIX_CFLAGS)
+libinvmapping_la_LIBADD = $(DISNIX_LIBS) ../libmapping/libmapping.la -lxmlutil
Added: disnix/dydisnix/trunk/src/libinvmapping/targetmapping.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/libinvmapping/targetmapping.c Mon Dec 6
14:04:20 2010 (r25002)
@@ -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/libinvmapping/targetmapping.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/libinvmapping/targetmapping.h Mon Dec 6
14:04:20 2010 (r25002)
@@ -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
Added: disnix/dydisnix/trunk/src/minsetcover/Makefile.am
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/minsetcover/Makefile.am Mon Dec 6 14:04:20
2010 (r25002)
@@ -0,0 +1,7 @@
+AM_CPPFLAGS = -ggdb
+
+bin_PROGRAMS = dydisnix-minsetcover
+
+dydisnix_minsetcover_SOURCES = minsetcover.c main.c
+dydisnix_minsetcover_LDADD = ../libservices/libservices.la
../libinfproperties/libinfproperties.la ../libmapping/libmapping.la
../libinvmapping/libinvmapping.la
+dydisnix_minsetcover_CFLAGS = -I../libservices -I../libinfproperties
-I../libmapping -I../libinvmapping $(GLIB_CFLAGS)
Added: disnix/dydisnix/trunk/src/minsetcover/main.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/minsetcover/main.c Mon Dec 6 14:04:20
2010 (r25002)
@@ -0,0 +1,84 @@
+#include "minsetcover.h"
+#include <stdio.h>
+#include <getopt.h>
+#define _GNU_SOURCE
+#include <string.h>
+
+static void print_usage(char *command)
+{
+ fprintf(stderr, "Usage:\n");
+ fprintf(stderr, "%s --services-xml services.xml --infrastructure-xml
infrastructure.xml --distribution-xml distribution.xml --target-property
targetProperty\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[] =
+ {
+ {"services-xml", required_argument, 0, 's'},
+ {"infrastructure-xml", required_argument, 0, 'i'},
+ {"distribution-xml", required_argument, 0, 'd'},
+ {"target-property", required_argument, 0, 'T'},
+ {"help", no_argument, 0, 'h'},
+ {0, 0, 0, 0}
+ };
+ char *services_xml = NULL;
+ char *infrastructure_xml = NULL;
+ char *distribution_xml = NULL;
+ char *target_property = NULL;
+
+ /* Parse command-line options */
+ while((c = getopt_long(argc, argv, "h", long_options, &option_index)) !=
-1)
+ {
+ switch(c)
+ {
+ case 's':
+ services_xml = optarg;
+ break;
+ case 'i':
+ infrastructure_xml = optarg;
+ break;
+ case 'd':
+ distribution_xml = optarg;
+ break;
+ case 'T':
+ target_property = optarg;
+ break;
+ case 'h':
+ print_usage(argv[0]);
+ return 0;
+ }
+ }
+
+ /* Validate options */
+
+ if(services_xml == NULL)
+ {
+ fprintf(stderr, "A services XML file must be specified!\n");
+ return 1;
+ }
+
+ if(infrastructure_xml == NULL)
+ {
+ fprintf(stderr, "An infrastructure XML file must be specified!\n");
+ return 1;
+ }
+
+ if(distribution_xml == NULL)
+ {
+ fprintf(stderr, "A distribution XML file must be specified!\n");
+ return 1;
+ }
+
+ if(target_property == NULL)
+ {
+ fprintf(stderr, "An target property must be specified!\n");
+ return 1;
+ }
+
+ /* Execute operation */
+ minsetcover(services_xml, infrastructure_xml, distribution_xml,
target_property);
+ return 0;
+}
Added: disnix/dydisnix/trunk/src/minsetcover/minsetcover.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/minsetcover/minsetcover.c Mon Dec 6 14:04:20
2010 (r25002)
@@ -0,0 +1,95 @@
+#include "serviceproperties.h"
+#include "infrastructureproperties.h"
+#include "candidatetargetmapping.h"
+#include "targetmapping.h"
+#include <stdlib.h>
+
+void minsetcover(gchar *services_xml, gchar *infrastructure_xml, gchar
*distribution_xml, gchar *target_property)
+{
+ GArray *service_property_array =
create_service_property_array(services_xml);
+ GArray *infrastructure_property_array =
create_infrastructure_property_array(infrastructure_xml);
+ GArray *candidate_target_array =
create_candidate_target_array(distribution_xml);
+ GHashTable *covered_services_table = g_hash_table_new(g_str_hash,
g_str_equal);
+ GArray *target_mapping_array =
create_target_mapping_array(candidate_target_array);
+ GArray *result = g_array_new(FALSE, FALSE, sizeof(DistributionItem*));
+ unsigned int i;
+
+ for(i = 0; i < candidate_target_array->len; i++)
+ {
+ DistributionItem *item = g_array_index(candidate_target_array,
DistributionItem*, i);
+
+ DistributionItem *result_item =
(DistributionItem*)g_malloc(sizeof(DistributionItem));
+ result_item->service = item->service;
+ result_item->targets = g_array_new(FALSE, FALSE, sizeof(gchar*));
+
+ g_array_append_val(result, result_item);
+ }
+
+ while(g_hash_table_size(covered_services_table) <
service_property_array->len)
+ {
+ unsigned int i;
+ double min_cost = -1;
+ int min_cost_index = -1;
+ TargetMappingItem *min_cost_target_mapping;
+
+ for(i = 0; i < target_mapping_array->len; i++)
+ {
+ TargetMappingItem *target_mapping =
g_array_index(target_mapping_array, TargetMappingItem*, i);
+ int target_index =
infrastructure_index(infrastructure_property_array, target_mapping->target);
+ Target *target = g_array_index(infrastructure_property_array,
Target*, target_index);
+ int infrastructure_prop_index =
infrastructure_property_index(target, target_property);
+ InfrastructureProperty *infrastructure_prop =
g_array_index(target->property, InfrastructureProperty*,
infrastructure_prop_index);
+ int count = 0;
+ double cost;
+ unsigned int j;
+
+ for(j = 0; j < target_mapping->services->len; j++)
+ {
+ gchar *service_name = g_array_index(target_mapping->services,
gchar*, j);
+
+ if(g_hash_table_lookup(covered_services_table, service_name) ==
NULL)
+ count++;
+ }
+
+ cost = atoi(infrastructure_prop->value) / (double)count;
+
+ if(min_cost == -1 || cost < min_cost)
+ {
+ min_cost = cost;
+ min_cost_index = i;
+ }
+ }
+
+ min_cost_target_mapping = g_array_index(target_mapping_array,
TargetMappingItem*, min_cost_index);
+
+ for(i = 0; i < min_cost_target_mapping->services->len; i++)
+ {
+ gchar *service = g_array_index(min_cost_target_mapping->services,
gchar*, i);
+ int index = distribution_item_index(result, service);
+ DistributionItem *item = g_array_index(result, DistributionItem*,
index);
+
+ g_hash_table_insert(covered_services_table, service, service);
+
+ g_array_append_val(item->targets, min_cost_target_mapping->target);
+ }
+ }
+
+ print_expr_of_candidate_target_array(result);
+
+ /* Cleanup */
+
+ for(i = 0; i < result->len; i++)
+ {
+ DistributionItem *item = g_array_index(result, DistributionItem*, i);
+ g_array_free(item->targets, TRUE);
+ g_free(item);
+ }
+
+ g_array_free(result, TRUE);
+
+ delete_target_mapping_array(target_mapping_array);
+ g_hash_table_destroy(covered_services_table);
+ delete_candidate_target_array(candidate_target_array);
+ delete_infrastructure_property_array(infrastructure_property_array);
+ delete_service_property_array(service_property_array);
+}
Added: disnix/dydisnix/trunk/src/minsetcover/minsetcover.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ disnix/dydisnix/trunk/src/minsetcover/minsetcover.h Mon Dec 6 14:04:20
2010 (r25002)
@@ -0,0 +1,7 @@
+#ifndef __MINSETCOVER_H
+#define __MINSETCOVER_H
+#include <glib.h>
+
+void minsetcover(gchar *services_xml, gchar *infrastructure_xml, gchar
*distribution_xml, gchar *target_property);
+
+#endif
Modified: disnix/dydisnix/trunk/src/multiwaycut/Makefile.am
==============================================================================
--- disnix/dydisnix/trunk/src/multiwaycut/Makefile.am Mon Dec 6 13:45:07
2010 (r25001)
+++ disnix/dydisnix/trunk/src/multiwaycut/Makefile.am Mon Dec 6 14:04:20
2010 (r25002)
@@ -2,6 +2,6 @@
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)
+dydisnix_multiwaycut_SOURCES = multiwaycut.c main.c
+dydisnix_multiwaycut_LDADD = ../libmapping/libmapping.la
../libinvmapping/libinvmapping.la
+dydisnix_multiwaycut_CFLAGS = -I../libmapping -I../libinvmapping $(GLIB_CFLAGS)
_______________________________________________
nix-commits mailing list
[email protected]
http://mail.cs.uu.nl/mailman/listinfo/nix-commits
