liquid_feedback_core
view lf_update_suggestion_order.c @ 374:fadfe4f267e2
Optional logging in "lf_update_suggestion_order"
| author | jbe |
|---|---|
| date | Sun Mar 17 20:28:43 2013 +0100 (2013-03-17) |
| parents | 88322e31107b |
| children | 3f7a89ad996d |
line source
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <libpq-fe.h>
5 #include <search.h>
7 static int logging = 0;
9 static char *escapeLiteral(PGconn *conn, const char *str, size_t len) {
10 // provides compatibility for PostgreSQL versions prior 9.0
11 // in future: return PQescapeLiteral(conn, str, len);
12 char *res;
13 size_t res_len;
14 res = malloc(2*len+3);
15 if (!res) return NULL;
16 res[0] = '\'';
17 res_len = PQescapeStringConn(conn, res+1, str, len, NULL);
18 res[res_len+1] = '\'';
19 res[res_len+2] = 0;
20 return res;
21 }
23 static void freemem(void *ptr) {
24 // to be used for "escapeLiteral" function
25 // provides compatibility for PostgreSQL versions prior 9.0
26 // in future: PQfreemem(ptr);
27 free(ptr);
28 }
30 // column numbers when querying "individual_suggestion_ranking" view in function main():
31 #define COL_MEMBER_ID 0
32 #define COL_WEIGHT 1
33 #define COL_PREFERENCE 2
34 #define COL_SUGGESTION_ID 3
36 // data structure for a candidate (in this case a suggestion) to the proportional runoff system:
37 struct candidate {
38 char *key; // identifier of the candidate, which is the "suggestion_id" string
39 double score_per_step; // added score per step
40 double score; // current score of candidate; a score of 1.0 is needed to survive a round
41 int seat; // equals 0 for unseated candidates, or contains rank number
42 };
44 // compare two integers stored as strings (invocation like strcmp):
45 static int compare_id(char *id1, char *id2) {
46 int ldiff;
47 ldiff = strlen(id1) - strlen(id2);
48 if (ldiff) return ldiff;
49 else return strcmp(id1, id2);
50 }
52 // compare two candidates by their key (invocation like strcmp):
53 static int compare_candidate(struct candidate *c1, struct candidate *c2) {
54 return compare_id(c1->key, c2->key);
55 }
57 // candidates are stored as global variables due to the constrained twalk() interface:
58 static int candidate_count;
59 static struct candidate *candidates;
61 // function to be passed to twalk() to store candidates ordered in candidates[] array:
62 static void register_candidate(char **candidate_key, VISIT visit, int level) {
63 if (visit == postorder || visit == leaf) {
64 struct candidate *candidate;
65 candidate = candidates + (candidate_count++);
66 candidate->key = *candidate_key;
67 candidate->seat = 0;
68 }
69 }
71 // performs a binary search in candidates[] array to lookup a candidate by its key (which is the suggestion_id):
72 static struct candidate *candidate_by_key(char *candidate_key) {
73 struct candidate *candidate;
74 struct candidate compare;
75 compare.key = candidate_key;
76 candidate = bsearch(&compare, candidates, candidate_count, sizeof(struct candidate), (void *)compare_candidate);
77 if (!candidate) {
78 fprintf(stderr, "Candidate not found (should not happen).\n");
79 abort();
80 }
81 return candidate;
82 }
84 // section of a ballot with equally ranked candidates:
85 struct ballot_section {
86 int count;
87 struct candidate **candidates;
88 };
90 // ballot of the proportional runoff system:
91 struct ballot {
92 int weight; // if weight is greater than 1, then the ballot is counted multiple times
93 struct ballot_section sections[4]; // 4 sections, most preferred candidates first
94 };
96 // determine candidate, which is assigned the next seat (starting with the worst rank):
97 static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) {
98 int i, j, k; // index variables for loops
99 int remaining; // remaining candidates to be seated
100 // reset scores of all candidates:
101 for (i=0; i<candidate_count; i++) {
102 candidates[i].score = 0.0;
103 }
104 // calculate remaining candidates to be seated:
105 remaining = candidate_count - round_number;
106 // repeat following loop, as long as there is more than one remaining candidate:
107 while (remaining > 1) {
108 double scale; // factor to be later multiplied with score_per_step:
109 // reset score_per_step for all candidates:
110 for (i=0; i<candidate_count; i++) {
111 candidates[i].score_per_step = 0.0;
112 }
113 // calculate score_per_step for all candidates:
114 for (i=0; i<ballot_count; i++) {
115 for (j=0; j<4; j++) {
116 int matches = 0;
117 for (k=0; k<ballots[i].sections[j].count; k++) {
118 struct candidate *candidate;
119 candidate = ballots[i].sections[j].candidates[k];
120 if (candidate->score < 1.0 && !candidate->seat) matches++;
121 }
122 if (matches) {
123 double score_inc;
124 score_inc = (double)ballots[i].weight / (double)matches;
125 for (k=0; k<ballots[i].sections[j].count; k++) {
126 struct candidate *candidate;
127 candidate = ballots[i].sections[j].candidates[k];
128 if (candidate->score < 1.0 && !candidate->seat) {
129 candidate->score_per_step += score_inc;
130 }
131 }
132 break;
133 }
134 }
135 }
136 // calculate scale factor:
137 scale = (double)0.0; // 0.0 is used to indicate that there is no value yet
138 for (i=0; i<candidate_count; i++) {
139 double max_scale;
140 if (candidates[i].score_per_step > 0.0) {
141 max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;
142 if (scale == 0.0 || max_scale <= scale) {
143 scale = max_scale;
144 }
145 }
146 }
147 // add scale*score_per_step to each candidates score:
148 for (i=0; i<candidate_count; i++) {
149 if (candidates[i].score_per_step > 0.0) {
150 double max_scale;
151 max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;
152 if (max_scale == scale) {
153 // score of 1.0 should be reached, so we set score directly to avoid floating point errors:
154 candidates[i].score = 1.0;
155 remaining--;
156 } else {
157 candidates[i].score += scale * candidates[i].score_per_step;
158 if (candidates[i].score >= 1.0) remaining--;
159 }
160 // when there is only one candidate remaining, then break inner (and thus outer) loop:
161 if (remaining <= 1) break;
162 }
163 }
164 }
165 // return remaining candidate:
166 for (i=0; i<candidate_count; i++) {
167 if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i;
168 }
169 // if there is no remaining candidate, then something went wrong:
170 fprintf(stderr, "No remaining candidate (should not happen).");
171 abort();
172 }
174 // write results to database:
175 static int write_ranks(PGconn *db, char *escaped_initiative_id, int final) {
176 PGresult *res;
177 char *cmd;
178 int i;
179 if (final) {
180 if (asprintf(&cmd, "BEGIN; UPDATE \"initiative\" SET \"final_suggestion_order_calculated\" = TRUE WHERE \"id\" = %s; UPDATE \"suggestion\" SET \"proportional_order\" = 0 WHERE \"initiative_id\" = %s", escaped_initiative_id, escaped_initiative_id) < 0) {
181 fprintf(stderr, "Could not prepare query string in memory.\n");
182 abort();
183 }
184 } else {
185 if (asprintf(&cmd, "BEGIN; UPDATE \"suggestion\" SET \"proportional_order\" = 0 WHERE \"initiative_id\" = %s", escaped_initiative_id) < 0) {
186 fprintf(stderr, "Could not prepare query string in memory.\n");
187 abort();
188 }
189 }
190 res = PQexec(db, cmd);
191 free(cmd);
192 if (!res) {
193 fprintf(stderr, "Error in pqlib while sending SQL command to initiate suggestion update.\n");
194 return 1;
195 } else if (
196 PQresultStatus(res) != PGRES_COMMAND_OK &&
197 PQresultStatus(res) != PGRES_TUPLES_OK
198 ) {
199 fprintf(stderr, "Error while executing SQL command to initiate suggestion update:\n%s", PQresultErrorMessage(res));
200 PQclear(res);
201 return 1;
202 } else {
203 PQclear(res);
204 }
205 for (i=0; i<candidate_count; i++) {
206 char *escaped_suggestion_id;
207 escaped_suggestion_id = escapeLiteral(db, candidates[i].key, strlen(candidates[i].key));
208 if (!escaped_suggestion_id) {
209 fprintf(stderr, "Could not escape literal in memory.\n");
210 abort();
211 }
212 if (asprintf(&cmd, "UPDATE \"suggestion\" SET \"proportional_order\" = %i WHERE \"id\" = %s", candidates[i].seat, escaped_suggestion_id) < 0) {
213 fprintf(stderr, "Could not prepare query string in memory.\n");
214 abort();
215 }
216 freemem(escaped_suggestion_id);
217 res = PQexec(db, cmd);
218 free(cmd);
219 if (!res) {
220 fprintf(stderr, "Error in pqlib while sending SQL command to update suggestion order.\n");
221 } else if (
222 PQresultStatus(res) != PGRES_COMMAND_OK &&
223 PQresultStatus(res) != PGRES_TUPLES_OK
224 ) {
225 fprintf(stderr, "Error while executing SQL command to update suggestion order:\n%s", PQresultErrorMessage(res));
226 PQclear(res);
227 } else {
228 PQclear(res);
229 continue;
230 }
231 res = PQexec(db, "ROLLBACK");
232 if (res) PQclear(res);
233 return 1;
234 }
235 res = PQexec(db, "COMMIT");
236 if (!res) {
237 fprintf(stderr, "Error in pqlib while sending SQL command to commit transaction.\n");
238 return 1;
239 } else if (
240 PQresultStatus(res) != PGRES_COMMAND_OK &&
241 PQresultStatus(res) != PGRES_TUPLES_OK
242 ) {
243 fprintf(stderr, "Error while executing SQL command to commit transaction:\n%s", PQresultErrorMessage(res));
244 PQclear(res);
245 return 1;
246 } else {
247 PQclear(res);
248 return 0;
249 }
250 }
252 // calculate ordering of suggestions for an initiative and call write_ranks() to write it to database:
253 static int process_initiative(PGconn *db, PGresult *res, char *escaped_initiative_id, int final) {
254 int err; // variable to store an error condition (0 = success)
255 int ballot_count = 1; // number of ballots, must be initiatized to 1, due to loop below
256 struct ballot *ballots; // data structure containing the ballots
257 int i; // index variable for loops
258 // create candidates[] and ballots[] arrays:
259 {
260 void *candidate_tree = NULL; // temporary structure to create a sorted unique list of all candidate keys
261 int tuple_count; // number of tuples returned from the database
262 char *old_member_id = NULL; // old member_id to be able to detect a new ballot in loops
263 struct ballot *ballot; // pointer to current ballot
264 int candidates_in_sections[4] = {0, }; // number of candidates that have been placed in each section
265 // reset candidate count:
266 candidate_count = 0;
267 // determine number of tuples:
268 tuple_count = PQntuples(res);
269 // trivial case, when there are no tuples:
270 if (!tuple_count) {
271 if (final) {
272 if (logging) printf("No suggestions found, but marking initiative as finally calculated.\n");
273 err = write_ranks(db, escaped_initiative_id, final);
274 if (logging) printf("Done.\n");
275 return err;
276 } else {
277 if (logging) printf("Nothing to do.\n");
278 return 0;
279 }
280 }
281 // calculate ballot_count and generate set of candidate keys (suggestion_id is used as key):
282 for (i=0; i<tuple_count; i++) {
283 char *member_id, *suggestion_id;
284 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
285 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
286 if (!candidate_tree || !tfind(suggestion_id, &candidate_tree, (void *)compare_id)) {
287 candidate_count++;
288 if (!tsearch(suggestion_id, &candidate_tree, (void *)compare_id)) {
289 fprintf(stderr, "Insufficient memory while inserting into candidate tree.\n");
290 abort();
291 }
292 }
293 if (old_member_id && strcmp(old_member_id, member_id)) ballot_count++;
294 old_member_id = member_id;
295 }
296 // print candidate count:
297 if (logging) printf("Candidate count: %i\n", candidate_count);
298 // allocate memory for candidates[] array:
299 candidates = malloc(candidate_count * sizeof(struct candidate));
300 if (!candidates) {
301 fprintf(stderr, "Insufficient memory while creating candidate list.\n");
302 abort();
303 }
304 // transform tree of candidate keys into sorted array:
305 candidate_count = 0; // needed by register_candidate()
306 twalk(candidate_tree, (void *)register_candidate);
307 // free memory of tree structure (tdestroy() is not available on all platforms):
308 while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)compare_id);
309 // print ballot count:
310 if (logging) printf("Ballot count: %i\n", ballot_count);
311 // allocate memory for ballots[] array:
312 ballots = calloc(ballot_count, sizeof(struct ballot));
313 if (!ballots) {
314 fprintf(stderr, "Insufficient memory while creating ballot list.\n");
315 abort();
316 }
317 // set ballot weights, determine ballot section sizes, and verify preference values:
318 ballot = ballots;
319 old_member_id = NULL;
320 for (i=0; i<tuple_count; i++) {
321 char *member_id;
322 int weight, preference;
323 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
324 weight = (int)strtol(PQgetvalue(res, i, COL_WEIGHT), (char **)NULL, 10);
325 if (weight <= 0) {
326 fprintf(stderr, "Unexpected weight value.\n");
327 free(ballots);
328 free(candidates);
329 return 1;
330 }
331 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
332 if (preference < 1 || preference > 4) {
333 fprintf(stderr, "Unexpected preference value.\n");
334 free(ballots);
335 free(candidates);
336 return 1;
337 }
338 preference--;
339 if (old_member_id && strcmp(old_member_id, member_id)) ballot++;
340 ballot->weight = weight;
341 ballot->sections[preference].count++;
342 old_member_id = member_id;
343 }
344 // allocate memory for ballot sections:
345 for (i=0; i<ballot_count; i++) {
346 int j;
347 for (j=0; j<4; j++) {
348 if (ballots[i].sections[j].count) {
349 ballots[i].sections[j].candidates = malloc(ballots[i].sections[j].count * sizeof(struct candidate *));
350 if (!ballots[i].sections[j].candidates) {
351 fprintf(stderr, "Insufficient memory while creating ballot section.\n");
352 abort();
353 }
354 }
355 }
356 }
357 // fill ballot sections with candidate references:
358 old_member_id = NULL;
359 ballot = ballots;
360 for (i=0; i<tuple_count; i++) {
361 char *member_id, *suggestion_id;
362 int preference;
363 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
364 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
365 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
366 preference--;
367 if (old_member_id && strcmp(old_member_id, member_id)) {
368 ballot++;
369 candidates_in_sections[0] = 0;
370 candidates_in_sections[1] = 0;
371 candidates_in_sections[2] = 0;
372 candidates_in_sections[3] = 0;
373 }
374 ballot->sections[preference].candidates[candidates_in_sections[preference]++] = candidate_by_key(suggestion_id);
375 old_member_id = member_id;
376 }
377 }
379 // calculate ranks based on constructed data structures:
380 for (i=0; i<candidate_count; i++) {
381 struct candidate *candidate = loser(i, ballots, ballot_count);
382 candidate->seat = candidate_count - i;
383 if (logging) printf("Assigning rank #%i to suggestion #%s.\n", candidate_count - i, candidate->key);
384 }
386 // free ballots[] array:
387 for (i=0; i<ballot_count; i++) {
388 int j;
389 for (j=0; j<4; j++) {
390 if (ballots[i].sections[j].count) {
391 free(ballots[i].sections[j].candidates);
392 }
393 }
394 }
395 free(ballots);
397 // write results to database:
398 if (final) {
399 if (logging) printf("Writing final ranks to database.\n");
400 } else {
401 if (logging) printf("Writing ranks to database.\n");
402 }
403 err = write_ranks(db, escaped_initiative_id, final);
404 if (logging) printf("Done.\n");
406 // free candidates[] array:
407 free(candidates);
409 // return error code of write_ranks() call
410 return err;
411 }
413 int main(int argc, char **argv) {
415 // variable declarations:
416 int err = 0;
417 int i, count;
418 char *conninfo;
419 PGconn *db;
420 PGresult *res;
422 // parse command line:
423 if (argc == 0) return 1;
424 if (argc == 1 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
425 FILE *out;
426 out = argc == 1 ? stderr : stdout;
427 fprintf(out, "\n");
428 fprintf(out, "Usage: %s [-v|--verbose] <conninfo>\n", argv[0]);
429 fprintf(out, "\n");
430 fprintf(out, "<conninfo> is specified by PostgreSQL's libpq,\n");
431 fprintf(out, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n");
432 fprintf(out, "\n");
433 fprintf(out, "Example: %s dbname=liquid_feedback\n", argv[0]);
434 fprintf(out, "\n");
435 return argc == 1 ? 1 : 0;
436 }
437 {
438 size_t len = 0;
439 int argb = 1;
440 if (
441 argc >= 2 &&
442 (!strcmp(argv[1], "-v") || !strcmp(argv[1], "--verbose"))
443 ) {
444 argb = 2;
445 logging = 1;
446 }
447 for (i=argb; i<argc; i++) len += strlen(argv[i]) + 1;
448 conninfo = malloc(len * sizeof(char));
449 if (!conninfo) {
450 fprintf(stderr, "Error: Could not allocate memory for conninfo string.\n");
451 abort();
452 }
453 conninfo[0] = 0;
454 for (i=argb; i<argc; i++) {
455 if (i>argb) strcat(conninfo, " ");
456 strcat(conninfo, argv[i]);
457 }
458 }
460 // connect to database:
461 db = PQconnectdb(conninfo);
462 if (!db) {
463 fprintf(stderr, "Error: Could not create database handle.\n");
464 return 1;
465 }
466 if (PQstatus(db) != CONNECTION_OK) {
467 fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db));
468 return 1;
469 }
471 // check initiatives:
472 res = PQexec(db, "SELECT \"initiative_id\", \"final\" FROM \"initiative_suggestion_order_calculation\"");
473 if (!res) {
474 fprintf(stderr, "Error in pqlib while sending SQL command selecting initiatives to process.\n");
475 err = 1;
476 } else if (PQresultStatus(res) != PGRES_TUPLES_OK) {
477 fprintf(stderr, "Error while executing SQL command selecting initiatives to process:\n%s", PQresultErrorMessage(res));
478 err = 1;
479 PQclear(res);
480 } else if (PQnfields(res) < 2) {
481 fprintf(stderr, "Too few columns returned by SQL command selecting initiatives to process.\n");
482 err = 1;
483 PQclear(res);
484 } else {
485 count = PQntuples(res);
486 if (logging) printf("Number of initiatives to process: %i\n", count);
487 for (i=0; i<count; i++) {
488 char *initiative_id, *escaped_initiative_id;
489 int final;
490 char *cmd;
491 PGresult *res2;
492 initiative_id = PQgetvalue(res, i, 0);
493 final = (PQgetvalue(res, i, 1)[0] == 't') ? 1 : 0;
494 if (logging) printf("Processing initiative_id: %s\n", initiative_id);
495 escaped_initiative_id = escapeLiteral(db, initiative_id, strlen(initiative_id));
496 if (!escaped_initiative_id) {
497 fprintf(stderr, "Could not escape literal in memory.\n");
498 abort();
499 }
500 if (asprintf(&cmd, "SELECT \"member_id\", \"weight\", \"preference\", \"suggestion_id\" FROM \"individual_suggestion_ranking\" WHERE \"initiative_id\" = %s ORDER BY \"member_id\", \"preference\"", escaped_initiative_id) < 0) {
501 fprintf(stderr, "Could not prepare query string in memory.\n");
502 abort();
503 }
504 res2 = PQexec(db, cmd);
505 free(cmd);
506 if (!res2) {
507 fprintf(stderr, "Error in pqlib while sending SQL command selecting individual suggestion rankings.\n");
508 err = 1;
509 } else if (PQresultStatus(res2) != PGRES_TUPLES_OK) {
510 fprintf(stderr, "Error while executing SQL command selecting individual suggestion rankings:\n%s", PQresultErrorMessage(res));
511 err = 1;
512 PQclear(res2);
513 } else if (PQnfields(res2) < 4) {
514 fprintf(stderr, "Too few columns returned by SQL command selecting individual suggestion rankings.\n");
515 err = 1;
516 PQclear(res2);
517 } else {
518 if (process_initiative(db, res2, escaped_initiative_id, final)) err = 1;
519 PQclear(res2);
520 }
521 freemem(escaped_initiative_id);
522 }
523 PQclear(res);
524 }
526 // cleanup and exit
527 PQfinish(db);
528 if (!err) {
529 if (logging) printf("Successfully terminated.\n");
530 } else {
531 fprintf(stderr, "Exiting with error code %i.\n", err);
532 }
533 return err;
535 }