1 #ifdef _WIN32
2 # include <malloc.h>
3 #else
4 #include <stdlib.h>
5 #endif
6 #include <stdlib.h>
7 #include <assert.h>
8 
9 #include "initial.h"
10 #include "lib.h"
11 
12 /* generate a random initial schedule where all predecessor
13  * dependencies are fulfilled. we do this by storing a set with all
14  * jobs, their dependency count and how many dependecies are already
15  * scheduled in a linked list sorted by the number of unfillfiled
16  * dependencies. we can then in turn choose one of the jobs where that
17  * number is 0, and then update the list
18  * */
19 
20 struct initial_job {
21 	int job_number;
22 	int left_deps;
23 	struct initial_job **successors;
24 	struct initial_job *next;
25 	struct initial_job *prev;
26 };
27 
28 /* XXX this could be sped up by not regenrating the structure every single
29  * time this is run */
random_schedule(struct rcps_problem * problem)30 int *random_schedule(struct rcps_problem *problem) {
31 	int *result;
32 	int cproblem;
33 	int i, j, c;
34 	int zcount;
35 	struct initial_job *njob;
36 	struct initial_job *cjob;
37 	struct initial_job *ojob;
38 	struct initial_job *job_list;
39 
40 	struct initial_job *A;
41 	struct initial_job *B;
42 	struct initial_job *C;
43 
44 	/* empty result set */
45 	result = (int*)malloc(sizeof(int) * problem->job_count);
46 	cproblem = 0;
47 
48 	/* init the list */
49 	job_list = NULL;
50 	for (i = 0; i < problem->job_count; i++) {
51 		/* create new job */
52 		njob = (struct initial_job*)malloc(sizeof(struct initial_job));
53 		njob->job_number = i;
54 		njob->left_deps = problem->jobs[i]->predeccessor_count;
55 		njob->next = NULL;
56 		njob->prev = NULL;
57 		if (problem->jobs[i]->successor_count > 0) {
58 			njob->successors = (struct initial_job**)malloc(sizeof(struct initial_job *) *
59 				problem->jobs[i]->successor_count);
60 		}
61 		else {
62 			njob->successors = NULL;
63 		}
64 		/* insert into the list */
65 		if (job_list == NULL) {
66 			job_list = njob;
67 		}
68 		else {
69 			/* go through the list */
70 			ojob = NULL;
71 			cjob = job_list;
72 			while ((cjob != NULL) && (cjob->left_deps < njob->left_deps)) {
73 				ojob = cjob;
74 				cjob = cjob->next;
75 			}
76 			/* insert */
77 			if (cjob == NULL) {
78 				ojob->next = njob;
79 				njob->prev = ojob;
80 			}
81 			else if (ojob == NULL) {
82 				njob->next = job_list;
83 				job_list = njob;
84 			}
85 			else {
86 				njob->next = cjob;
87 				njob->prev = ojob;
88 				ojob->next = njob;
89 				cjob->prev = njob;
90 			}
91 		}
92 	}
93 	/* fix the successors */
94 	cjob = job_list;
95 	while (cjob) {
96 		for (i = 0; i < problem->jobs[cjob->job_number]->successor_count; i++) {
97 			for (j = 0; j < problem->job_count; j++) {
98 				if (problem->jobs[j] ==
99 						problem->jobs[cjob->job_number]->successors[i]) {
100 					/* update with successor j */
101 					ojob = job_list;
102 					while ((ojob) && (ojob->job_number != j)) {
103 						ojob = ojob->next;
104 					}
105 					cjob->successors[i] = ojob;
106 					break;
107 				}
108 			}
109 		}
110 		cjob = cjob->next;
111 	}
112 	/* get the zero count */
113 	cjob = job_list;
114 	zcount = 0;
115 	while ((cjob) && (cjob->left_deps == 0)) {
116 		zcount++;
117 		cjob = cjob->next;
118 	}
119 	/* work your way through the list */
120 	c = 0;
121 	while (zcount != 0) {
122 		/* choose the proper job */
123 		/* XXX randomly for now, insert heuristics here */
124 		i = irand(zcount);
125 		cjob = job_list;
126 		while (i > 0) {
127 			cjob = cjob->next;
128 			i--;
129 		}
130 		/* remove from list */
131 		if (cjob == job_list) {
132 			job_list = cjob->next;
133 			if (job_list != NULL) {
134 				job_list->prev = NULL;
135 			}
136 		}
137 		else {
138 			if (cjob->next != NULL) {
139 				cjob->next->prev = cjob->prev;
140 			}
141 			if (cjob->prev != NULL) {
142 				cjob->prev->next = cjob->next;
143 			}
144 		}
145 		zcount--;
146 		/* add to result */
147 		result[c] = cjob->job_number;
148 		c++;
149 		/* update the list */
150 		for (i = 0; i < problem->jobs[cjob->job_number]->successor_count; i++) {
151 			ojob = cjob->successors[i];
152 			ojob->left_deps--;
153 			/* resort */
154 			while ((ojob->prev != NULL) && (ojob->prev->left_deps > ojob->left_deps)) {
155 				/* shift down */
156 				C = ojob->next;
157 				B = ojob->prev;
158 				A = B->prev;
159 				if (C) {
160 					C->prev = B;
161 				}
162 				B->prev = ojob;
163 				B->next = C;
164 				ojob->next = B;
165 				ojob->prev = A;
166 				if (A) {
167 					A->next = ojob;
168 				}
169 				else {
170 					job_list = ojob;
171 				}
172 			}
173 			/* update zcount */
174 			if (ojob->left_deps == 0) {
175 				zcount++;
176 			}
177 		}
178 		/* clean up */
179 		free(cjob->successors);
180 		free(cjob);
181 	}
182 	return result;
183 }
184 
initial(struct rcps_problem * problem,struct rcps_genome * genome)185 void initial(struct rcps_problem *problem, struct rcps_genome *genome) {
186 	int i;
187 	/* XXX assert that he structs in the genome are not yet mallocd */
188 	/* the schedule */
189 	genome->schedule = random_schedule(problem);
190 	/* the modes */
191 	genome->modes = (int*)malloc(problem->genome_modes * sizeof(int));
192 	for (i = 0; i < problem->genome_modes; i++) {
193 		if (problem->modes_max[i] == 0) {
194 			/* XXX this should never happen, assert it and remove later */
195 			assert(0 == 1);
196 		}
197 		else {
198 			genome->modes[i] = irand(problem->modes_max[i]);
199 		}
200 	}
201 	/* the alternatives */
202 	genome->alternatives = (int*)malloc(problem->genome_alternatives *
203 			sizeof(int));
204 	for (i = 0; i < problem->genome_alternatives; i++) {
205 		if (problem->alternatives_max[i] == 0) {
206 			/* XXX this should never happen, assert it and remove later */
207 			assert(0 == 1);
208 		}
209 		else {
210 			genome->alternatives[i] = irand(problem->alternatives_max[i]);
211 		}
212 	}
213 }
214