gam-resource-manager: fix a few warnings.
[profile/ivi/murphy.git] / src / plugins / gam-resource-manager / c5-decision-tree.c
1 /*
2  * Copyright (c) 2014, Intel Corporation
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are
6  * met:
7  *
8  *  * Redistributions of source code must retain the above copyright notice,
9  *    this list of conditions and the following disclaimer.
10  *  * Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *  * Neither the name of Intel Corporation nor the names of its contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <ctype.h>
33 #include <errno.h>
34
35 #include <murphy/common.h>
36
37 #include "c5-decision-tree.h"
38
39
40 #define ATTRIBUTE_MAX  32
41 #define ENUM_MAX       16384
42 #define ENUM_BUCKETS   16
43
44
45
46 typedef enum   state_e              state_t;
47 typedef struct conf_iter_s          conf_iter_t;
48 typedef struct attr_value_iter_s    attr_value_iter_t;
49 typedef struct value_list_item_s    value_list_item_t;
50 typedef struct value_list_s         value_list_t;
51
52 enum state_e {
53     START = 0,
54     NAME,
55     VALUE,
56     END
57 };
58
59
60 struct conf_iter_s {
61     mrp_decision_conf_t *conf;
62     int nattr;
63     mrp_decision_attr_t *attrs[0];
64 };
65
66
67 struct attr_value_iter_s {
68     mrp_decision_attr_t *attr;
69     int ndesc;
70     mrp_decision_attr_value_desc_t descs[0];
71 };
72
73 struct value_list_item_s {
74     const char *name;
75     int32_t value;
76 };
77
78 struct value_list_s {
79     int size;
80     value_list_item_t *items;
81 };
82
83 static bool conf_finish(mrp_decision_conf_t *, const char *);
84 static conf_iter_t *conf_iterator(mrp_decision_conf_t *);
85
86 static mrp_decision_attr_t *attr_create(mrp_decision_conf_t*,const char*,int);
87 static void attr_destroy(void *, void *);
88 static void attr_add_value(mrp_decision_attr_t *, const char *);
89 static attr_value_iter_t *attr_value_iterator(mrp_decision_attr_t *);
90 static size_t attr_print(mrp_decision_attr_t *, bool, char *, size_t);
91
92 static void value_destroy(void *, void *);
93
94 static bool tree_parse(mrp_decision_conf_t *, FILE *, size_t *, char *,
95                        mrp_decision_node_t **, int);
96 static bool tree_parse_terminal_node(mrp_decision_conf_t *, FILE *, size_t *,
97                                      char *, bool, mrp_decision_node_t **, int);
98 static bool tree_parse_test_node(mrp_decision_conf_t *, FILE *, size_t *,
99                                  char *, int, mrp_decision_node_t **, int);
100
101
102
103 static bool property(char **, char **, char **);
104 static bool list_item(char **, char **);
105 static bool identifier(char **, char **, char *);
106 static bool whitespace(char **);
107 static bool quoted(char **, char **);
108
109 static size_t print_node(mrp_decision_conf_t *, mrp_decision_node_t *,
110                          conf_iter_t *, char *, size_t, char *);
111 static size_t print_bitmask(mrp_decision_attr_t *, mrp_decision_bitmask_t,
112                             char *, size_t);
113
114
115
116 mrp_decision_conf_t *mrp_decision_conf_create_from_file(const char *stem)
117 {
118     FILE *f;
119     char filnam[1024];
120     char *buf, *p;
121     size_t n;
122     ssize_t linlen;
123     state_t state;
124     char decision[256];
125     char *name;
126     char *value;
127     char sep;
128     size_t lineno;
129     mrp_decision_conf_t *conf;
130     mrp_decision_attr_t *attr;
131     mrp_htbl_config_t aconf;
132     int id;
133
134     if (!stem || !stem[0])
135         return false;
136
137     snprintf(filnam, sizeof(filnam), "%s.names", stem);
138     if (!(f = fopen(filnam, "r"))) {
139         mrp_log_error("gam-resource-manager: failed to open file '%s': %s",
140                       filnam, strerror(errno));
141         return NULL;
142     }
143
144     if (!(conf = mrp_allocz(sizeof(mrp_decision_conf_t)))) {
145         mrp_log_error("gam-resource-manager: can't allocate memory for "
146                       "'%s' decision configuration", stem);
147         return NULL;
148     }
149     else {
150         aconf.nentry  = ATTRIBUTE_MAX;
151         aconf.comp    = mrp_string_comp;
152         aconf.hash    = mrp_string_hash;
153         aconf.free    = attr_destroy;
154         aconf.nbucket = ATTRIBUTE_MAX;
155
156         conf->stem  = mrp_strdup(stem);
157         conf->nattr = 0;
158         conf->attrs = mrp_htbl_create(&aconf);
159
160         if (!conf->attrs) {
161             mrp_log_error("gam-resource-manager: failed to create attribute "
162                           "hash for '%s' decision configuration", stem);
163             mrp_decision_conf_destroy(conf);
164             return NULL;
165         }
166     }
167
168     state = START;
169     buf = NULL;
170     lineno = 0;
171     attr = NULL;
172     id = 0;
173     decision[0] = 0;
174
175     while ((linlen = getline(&buf, &n, f)) >= 0) {
176         lineno++;
177         p = buf;
178
179         whitespace(&p);
180
181         while (*p) {
182             switch (state) {
183
184             case START:
185                 if (!identifier(&p, &name, &sep) || sep != '.')
186                     goto failed;
187                 mrp_debug("decision = '%s'", name);
188                 snprintf(decision, sizeof(decision), "%s", name);
189                 state = NAME;
190                 whitespace(&p);
191                 break;
192
193             case NAME:
194                 if (!identifier(&p, &name, &sep) || sep != ':')
195                     goto failed;
196                 mrp_debug("name = '%s'", name);
197                 if (!(attr = attr_create(conf, name, id++)))
198                     goto failed;
199                 state = VALUE;
200                 whitespace(&p);
201                 break;
202
203             case VALUE:
204                 if (!identifier(&p, &value, &sep) ||
205                     (sep != ',' && sep != '.' && sep != 0))
206                     goto failed;
207                 mrp_debug("value = '%s'", value);
208                 if (!strcmp(name, "continuous") && sep != '.')
209                     goto failed;
210                 attr_add_value(attr, value);
211                 if (sep == '.') {
212                     state = NAME;
213                     attr = NULL;
214                 }
215                 whitespace(&p);
216                 break;
217
218             default:
219                 break;
220             }
221         }
222
223         free(buf);
224         buf = NULL;
225     } /* while getline */
226
227     if (linlen < 0 && !feof(f)) {
228         mrp_log_error("gam-resource-manager: error during reading "
229                       "'%s' file: %s", filnam, strerror(errno));
230         mrp_decision_conf_destroy(conf);
231         return NULL;
232     }
233
234     fclose(f);
235
236     if (!conf_finish(conf, decision)) {
237         mrp_decision_conf_destroy(conf);
238         return NULL;
239     }
240
241     mrp_log_info("mrp-resource-manager: successfully loaded "
242                  "decision configuration from file '%s'", filnam);
243
244     return conf;
245
246   failed:
247     mrp_log_error("gam-resource-manager: error in file '%s' line %zu",
248                   filnam, lineno);
249     free(buf);
250     fclose(f);
251     mrp_decision_conf_destroy(conf);
252     return NULL;
253 }
254
255 void mrp_decision_conf_destroy(mrp_decision_conf_t *conf)
256 {
257     if (conf) {
258         mrp_log_info("mrp-resource-manager: going to unload "
259                      "decision configuration '%s'", conf->stem);
260
261         if (conf->decision_attr && conf->decision_names)
262             mrp_free(conf->decision_names);
263
264         mrp_htbl_destroy(conf->attrs, TRUE);
265
266         mrp_free((void *)conf->stem);
267         mrp_free((void *)conf);
268     }
269 }
270
271 bool mrp_decision_set_attr_offset(mrp_decision_conf_t *conf,
272                                   const char *attr_name,
273                                   size_t offset)
274 {
275     mrp_decision_attr_t *attr;
276
277     if (!conf || !attr_name)
278         return false;
279
280     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
281         return false;
282
283     attr->offset = offset;
284
285     return true;
286 }
287
288 ssize_t mrp_decision_attr_list(mrp_decision_conf_t *conf,
289                                const char **buf, size_t len)
290 {
291     conf_iter_t *it;
292     int i,j,n;
293
294     if (!conf || !buf || len < 1)
295         return -1;
296
297     if ((int)len < conf->nattr)
298         return -1;
299
300     if (!(it = conf_iterator(conf)))
301         return -1;
302
303     for (i = j = 0, n = it->nattr;  i < n;  i++) {
304         if (conf->decision_attr != it->attrs[i])
305             buf[j++] = it->attrs[i]->name;
306     }
307     buf[j] = NULL;
308
309     mrp_free(it);
310
311     return j;
312 }
313
314 ssize_t mrp_decision_attr_value_list(mrp_decision_conf_t *conf,
315                                      const char *attr_name,
316                                      mrp_decision_attr_value_desc_t *buf,
317                                      size_t len)
318 {
319     mrp_decision_attr_t *attr;
320     attr_value_iter_t *it;
321     int buf_len;
322     int actual_len;
323     size_t size;
324
325     if (!conf || !attr_name || !buf || (buf_len = len) < 1)
326         return -1;
327
328     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
329         return -1;
330
331     if (buf_len < attr->nvalue)
332         return -1;
333
334     if (!(it = attr_value_iterator(attr)))
335         return -1;
336
337     actual_len = it->ndesc;
338
339     size = sizeof(mrp_decision_attr_value_desc_t) * actual_len;
340     memcpy(buf, it->descs, size);
341
342     if (buf_len > actual_len) {
343         size = sizeof(mrp_decision_attr_value_desc_t) * (buf_len - it->ndesc);
344         memset(buf + it->ndesc, 0, size);
345     }
346
347     mrp_free(it);
348
349     return actual_len;
350 }
351
352
353
354 const char *mrp_decision_name(mrp_decision_conf_t *conf, int32_t decision)
355 {
356     if (!conf || decision < 0 || decision > conf->decision_attr->nvalue)
357         return "<invalid>";
358
359     return conf->decision_names[decision];
360 }
361
362
363 int32_t mrp_decision_value_max(mrp_decision_conf_t *conf)
364 {
365     if (!conf || !conf->decision_attr)
366         return 0;
367
368     return conf->decision_attr->nvalue;
369 }
370
371 int32_t mrp_decision_get_integer_attr_value(mrp_decision_conf_t *conf,
372                                             const char *attr_name,
373                                             const char *value_name,
374                                             bool *error)
375 {
376     mrp_decision_attr_t *attr;
377     mrp_decision_value_t *value;
378
379     if (error)
380         *error = true;
381
382     if (!conf || !attr_name || !value_name)
383         return 0;
384
385     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
386         return -1;
387
388     if (attr->value_type != MRP_DECISION_VALUE_INTEGER)
389         return -1;
390
391     if (!(value = mrp_htbl_lookup(attr->values, (void *)value_name)))
392         return -1;
393
394     if (error)
395         *error = false;
396
397     return value->integer;
398 }
399
400
401 const char *mrp_decision_get_integer_attr_name(mrp_decision_conf_t *conf,
402                                                const char *attr_name,
403                                                int32_t value,
404                                                bool *error)
405 {
406     mrp_decision_attr_t *attr;
407     attr_value_iter_t *it;
408     const char *value_name;
409     int i;
410
411     if (error)
412         *error = true;
413
414     if (!conf || !attr_name)
415         return "<error>";
416
417     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
418         return "<unknown attribute>";
419
420     if (attr->value_type != MRP_DECISION_VALUE_INTEGER)
421         return "<not integer attribute>";
422
423     if (!(it = attr_value_iterator(attr)))
424         return "<error>";
425
426     for (i = 0, value_name = "<unknown value>";   i < it->ndesc;   i++) {
427         if (it->descs[i].value == value) {
428             value_name = it->descs[i].name;
429             break;
430         }
431     }
432
433     if (i < it->ndesc && error)
434         *error = false;
435
436     return value_name;
437 }
438
439
440 size_t mrp_decision_conf_print(mrp_decision_conf_t *conf, char *buf,size_t len)
441 {
442     conf_iter_t *it;
443     mrp_decision_attr_t *attr;
444     int i;
445     char *p, *e;
446
447     e = (p = buf) + len;
448
449     if (buf) {
450         if (!(it = conf_iterator(conf)))
451             p += snprintf(p, e-p, "<error>");
452         else {
453             p += snprintf(p, e-p, "attributes for '%s'\n", conf->stem);
454
455             for (i = 0;  i < it->nattr;  i++) {
456                 attr = it->attrs[i];
457                 p += attr_print(attr, (attr == conf->decision_attr), p, e-p);
458             }
459
460             mrp_free(it);
461         }
462     }
463
464     return p - buf;
465 }
466
467
468 static bool conf_finish(mrp_decision_conf_t *conf,
469                         const char *decision_attr_name)
470 {
471     mrp_decision_attr_t *attr;
472     attr_value_iter_t *it;
473     mrp_decision_attr_value_desc_t *dsc;
474     size_t size;
475     const char **tbl;
476     int i, n;
477
478     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)decision_attr_name))) {
479         mrp_log_error("gam-resoure-manager: can't find decision attribute "
480                       "'%s' for '%s'", decision_attr_name, conf->stem);
481         return false;
482     }
483
484     if (attr->nvalue < 1) {
485         mrp_log_error("gam-resource-manager: attribute '%s' in '%s' is "
486                       "not suitable for decisions", attr->name, conf->stem);
487         return false;
488     }
489
490     n = attr->nvalue;
491     size = sizeof(const char *) * n;
492
493     if (!(it = attr_value_iterator(attr)) || !(tbl = mrp_allocz(size))) {
494         mrp_free(it);
495         mrp_log_error("gam-resource-manager: can't allocate memory to "
496                       "finalize '%s' decision", conf->stem);
497         return false;
498     }
499
500     for (i = 0;  i < n;  i++) {
501         dsc = it->descs + i;
502
503         if (i != dsc->value) {
504             mrp_log_error("gam-resource-manager: internal error: decision "
505                           "values of '%s' are non-continous for '%s' decisions",
506                           attr->name, conf->stem);
507             mrp_free(it);
508             mrp_free(tbl);
509             return false;
510         }
511
512         tbl[i] = dsc->name;
513     };
514
515     mrp_free(it);
516
517     conf->decision_attr = attr;
518     conf->decision_names = tbl;
519
520     return true;
521 }
522
523
524 static int conf_iter_cb(void *key, void *object, void *user_data)
525 {
526     conf_iter_t *it = (conf_iter_t *)user_data;
527     mrp_decision_attr_t *attr = (mrp_decision_attr_t *)object;
528
529     MRP_UNUSED(key);
530
531     if (it->nattr >= it->conf->nattr) {
532         mrp_log_error("gam-resource-manager: detected inconsitency while "
533                       "iterating configuration of '%s'", it->conf->stem);
534     }
535     else {
536         it->attrs[it->nattr++] = attr;
537     }
538
539     return MRP_HTBL_ITER_MORE;
540 }
541
542 static conf_iter_t *conf_iterator(mrp_decision_conf_t *conf)
543 {
544     conf_iter_t *it;
545     size_t size;
546     mrp_decision_attr_t *tmp;
547     int i,j;
548
549     if (!conf)
550         it = NULL;
551     else {
552         size = sizeof(conf_iter_t) + (sizeof(void *) * conf->nattr);
553
554         if ((it = mrp_allocz(size))) {
555             it->conf = conf;
556
557             mrp_htbl_foreach(conf->attrs, conf_iter_cb, it);
558
559             for (i = 0;   i < it->nattr - 1;   i++) {
560                 for (j = i + 1;   j < it->nattr;   j++) {
561                     if (it->attrs[i]->id > it->attrs[j]->id) {
562                         tmp = it->attrs[i];
563                         it->attrs[i] = it->attrs[j];
564                         it->attrs[j] = tmp;
565                     }
566                 }
567             }
568         }
569     }
570
571     return it;
572 }
573
574
575 static mrp_decision_attr_t *attr_create(mrp_decision_conf_t *conf,
576                                         const char *name, int id)
577 {
578     mrp_decision_attr_t *attr;
579
580     if (!conf || !name)
581         attr = NULL;
582     else {
583         if ((attr = mrp_allocz(sizeof(mrp_decision_attr_t)))) {
584             attr->name       = mrp_strdup(name);
585             attr->id         = id;
586             attr->attr_type  = MRP_DECISION_ATTR_CONTINUOUS;
587             attr->value_type = MRP_DECISION_VALUE_INTEGER;
588             attr->nvalue     = 0;
589             attr->values     = NULL;
590         }
591
592         if (!mrp_htbl_insert(conf->attrs, (void *)attr->name, attr)) {
593             attr_destroy((void *)attr->name, (void *)attr);
594             attr = NULL;
595         }
596
597         conf->nattr++;
598     }
599
600     return attr;
601 }
602
603 static void attr_destroy(void *key, void *object)
604 {
605     mrp_decision_attr_t *attr = (mrp_decision_attr_t *)object;
606
607     MRP_UNUSED(key);
608
609     if (attr->values)
610         mrp_htbl_destroy(attr->values, TRUE);
611
612     mrp_free((void *)attr->name);
613     mrp_free(object);
614 }
615
616 static void attr_add_value(mrp_decision_attr_t *attr, const char *name)
617 {
618     mrp_htbl_config_t vconf;
619     mrp_decision_value_t *value;
620     char *key = NULL;
621
622     if (attr && name) {
623         if (attr->attr_type == MRP_DECISION_ATTR_CONTINUOUS) {
624             vconf.nentry  = ENUM_MAX;
625             vconf.comp    = mrp_string_comp;
626             vconf.hash    = mrp_string_hash;
627             vconf.free    = value_destroy;
628             vconf.nbucket = ENUM_BUCKETS;
629
630             attr->attr_type = MRP_DECISION_ATTR_ENUM;
631             attr->nvalue    = 0;
632             attr->values    = mrp_htbl_create(&vconf);
633         }
634
635         if (!(key = mrp_strdup(name)) || !(value = mrp_allocz(sizeof(*value))))
636             mrp_free((void *)key);
637         else {
638             value->integer = attr->nvalue++;
639             mrp_htbl_insert(attr->values, key, value);
640         }
641     }
642 }
643
644 static int attr_value_iter_cb(void *key, void *object, void *user_data)
645 {
646     attr_value_iter_t *it = (attr_value_iter_t *)user_data;
647     const char *name = (const char *)key;
648     mrp_decision_value_t *value = (mrp_decision_value_t *)object;
649     mrp_decision_attr_value_desc_t *desc;
650
651     if (it->ndesc >= it->attr->nvalue) {
652         mrp_log_error("gam-resource-manager: detected inconsitency while "
653                       "iterating decision attribute '%s' for '%s'",
654                       name, it->attr->name);
655     }
656     else {
657         desc = it->descs + it->ndesc++;
658         desc->name = name;
659         desc->value = value->integer;
660     }
661
662     return MRP_HTBL_ITER_MORE;
663 }
664
665 static attr_value_iter_t *attr_value_iterator(mrp_decision_attr_t *attr)
666 {
667     attr_value_iter_t *it;
668     mrp_decision_attr_value_desc_t tmp;
669     size_t size;
670     int i,j;
671
672     if (!attr)
673         it = NULL;
674     else {
675         size = sizeof(*it) +
676                (sizeof(mrp_decision_attr_value_desc_t) * attr->nvalue);
677
678         if ((it = mrp_allocz(size))) {
679             it->attr = attr;
680             it->ndesc = 0;
681             mrp_htbl_foreach(attr->values, attr_value_iter_cb, it);
682
683             for (i = 0;   i < it->ndesc - 1;   i++) {
684                 for (j = i + 1;  j < it->ndesc;   j++) {
685                     if (it->descs[i].value > it->descs[j].value) {
686                         tmp = it->descs[i];
687                         it->descs[i] = it->descs[j];
688                         it->descs[j] = tmp;
689                     }
690                 }
691             }
692         }
693     }
694
695     return it;
696 }
697
698 static size_t attr_print(mrp_decision_attr_t *attr, bool decision,
699                          char *buf, size_t len)
700 {
701 #define PRINT(args...) \
702     do { if (p < e) p += snprintf(p, e-p, args); } while (0)
703
704     attr_value_iter_t *it;
705     mrp_decision_attr_value_desc_t *dsc;
706     char *p, *e;
707     const char *sep;
708     char nambuf[256];
709     int i;
710
711     e = (p = buf) + len;
712
713     if (attr && p < e) {
714         snprintf(nambuf, sizeof(nambuf), "%2d %s:", attr->id, attr->name);
715         PRINT(" %c %-24s @%03zu  ", decision ? '*':' ', nambuf, attr->offset);
716
717         switch (attr->attr_type) {
718
719         case MRP_DECISION_ATTR_ENUM:
720             if (!(it = attr_value_iterator(attr)))
721                 PRINT("<error>\n");
722             else {
723                 PRINT("{");
724                 for (i = 0;   i < it->ndesc;   i++) {
725                     dsc = it->descs + i;
726                     sep = (i == 0) ?  ""   : ((i % 10) ?
727                                       ", " :
728                                       ",\n                                  ");
729                     PRINT("%s[%d (%s)]", sep, dsc->value, dsc->name);
730                 }
731                 PRINT("}\n");
732
733                 mrp_free(it);
734             }
735             break;
736
737         case MRP_DECISION_ATTR_CONTINUOUS:
738             PRINT("continuous\n");
739             break;
740
741         default:
742             PRINT("<unsupported attribute type %d>\n", attr->attr_type);
743             break;
744         }
745     }
746
747     return p - buf;
748
749 #undef PRINT
750 }
751
752 static void value_destroy(void *key, void *object)
753 {
754     mrp_free(key);
755     mrp_free(object);
756 }
757
758
759 mrp_decision_node_t *mrp_decision_tree_create_from_file(
760                                              mrp_decision_conf_t *conf,
761                                              const char *stem)
762 {
763     FILE *f;
764     char filnam[1024];
765     char *buf, *p;
766     size_t n;
767     ssize_t linlen;
768     size_t lineno;
769     mrp_decision_node_t *root, *node;
770     mrp_decision_value_type_t vtype;
771     char *name, *value;
772
773     if (!stem)
774         stem = conf->stem;
775
776     snprintf(filnam, sizeof(filnam), "%s.tree", stem);
777     if (!(f = fopen(filnam, "r"))) {
778         printf("failed to open file '%s': %s\n", filnam, strerror(errno));
779         return NULL;
780     }
781
782     vtype = conf->decision_attr->value_type;
783
784     if (!(root = mrp_decision_tree_create(stem, vtype))) {
785         mrp_log_error("gam-resource-manager: failed to create "
786                       "decision tree for '%s'", stem);
787         return NULL;
788     }
789
790     lineno = 0;
791     buf = NULL;
792     node = NULL;
793
794     while ((linlen = getline(&buf, &n, f)) >= 0) {
795         lineno++;
796         p = buf;
797
798         whitespace(&p);
799
800         if (!strncmp(p, "type", 4)) {
801             if (!(tree_parse(conf, f, &lineno, buf, &node, 0)))
802                 goto failed;
803             if (!(mrp_decision_add_node_to_root(root, node)))
804                 goto failed;
805             node = NULL;
806         }
807         else if (property(&p, &name, &value)) {
808             if (!strcmp(name, "id")) {
809                 mrp_debug("id: %s", value);
810             }
811             else if (!strcmp(name, "entries")) {
812                 mrp_debug("entries: %s", value);
813             }
814             else {
815                 goto parse_error;
816             }
817         }
818
819         free(buf);
820         buf = NULL;
821     }
822
823     if (linlen < 0 && !feof(f)) {
824         mrp_log_error("gam-resource-manager: error during reading "
825                       "'%s' file: %s", filnam, strerror(errno));
826         goto failed;
827     }
828
829     fclose(f);
830
831     mrp_log_info("mrp-resource-manager: successfully loaded "
832                  "decision tree from file '%s'", filnam);
833
834     return root;
835
836  parse_error:
837     mrp_log_error("gam-resource-manager: error in file '%s' line %zu",
838                   filnam, lineno);
839  failed:
840     mrp_log_error("gam-resource-manager: failed to parse '%s' file",
841                   filnam);
842     free(buf);
843     fclose(f);
844     mrp_decision_tree_destroy(root);
845     mrp_decision_tree_destroy(node);
846     return NULL;
847 }
848
849 static const char *indent(int depth)
850 {
851     static char buf[1024];
852     size_t l = depth * 3;
853     memset(buf, ' ', l);
854     buf[l] = 0;
855     return buf;
856 }
857
858 static bool tree_parse(mrp_decision_conf_t *conf,
859                        FILE *f, size_t *lineno,
860                        char *buf,
861                        mrp_decision_node_t **node,
862                        int depth)
863 {
864     char *p = buf;
865     char *name, *value, *e;
866     int type;
867
868     if (!property(&p, &name, &value) || strcmp(name, "type"))
869         return false;
870
871     type = strtol(value, &e, 10);
872
873     if (e == value || *e)
874         return false;
875
876     switch (type) {
877     case 0:
878         return tree_parse_terminal_node(conf, f, lineno, p, false, node, depth);
879
880     case 1:
881     case 2:
882     case 3:
883         return tree_parse_test_node(conf, f, lineno, p, type, node, depth);
884
885     default:
886         return false;
887     }
888
889     return true;
890 }
891
892 static bool tree_parse_terminal_node(mrp_decision_conf_t *conf,
893                                      FILE *f, size_t *lineno,
894                                      char *buf,
895                                      bool need_empty,
896                                      mrp_decision_node_t **node,
897                                      int depth)
898 {
899     char *p = buf;
900     char *name, *value;
901     mrp_decision_value_t *vptr;
902     char *decision_name;
903     int32_t decision;
904     bool has_decision;
905     bool has_cases;
906
907     MRP_UNUSED(f);
908     MRP_UNUSED(lineno);
909     MRP_UNUSED(depth);
910
911     has_decision = false;
912     has_cases = false;
913
914     while (*p) {
915         if (!property(&p, &name, &value))
916             break;
917
918         if (!strcmp(name, "class")) {
919             if (!(vptr = mrp_htbl_lookup(conf->decision_attr->values, value)))
920                 return false;
921             else {
922                 decision_name = value;
923                 decision = vptr->integer;
924                 has_decision = true;
925             }
926         }
927         if (!strcmp(name, "freq")) {
928             has_cases = true;
929         }
930
931         whitespace(&p);
932     }
933
934     if (has_decision) {
935         if (!need_empty && node) {
936             mrp_debug("%sterminal: %d/%s", indent(depth),
937                   decision, decision_name);
938             if (!(*node = mrp_decision_create_terminal_node(vptr)))
939                 return false;
940             return true;
941         }
942         if (need_empty && !has_cases)
943             return true;
944     }
945
946     return false;
947 }
948
949 static bool tree_parse_test_node(mrp_decision_conf_t *conf,
950                                  FILE *f, size_t *lineno,
951                                  char *buf,
952                                  int type,
953                                  mrp_decision_node_t **node,
954                                  int depth)
955 {
956     mrp_decision_node_t *child;
957     char *p;
958     char *name, *value;
959     mrp_decision_attr_t *attr;
960     int nbr;
961     char *e;
962     size_t n;
963     char *buf2;
964     int listidx;
965     value_list_t *lists, *l;
966     value_list_item_t *iv;
967     mrp_decision_value_t *av;
968     mrp_decision_value_type_t testval_type;
969     mrp_decision_value_t testval;
970     mrp_decision_condition_t testcond;
971     int i,j,k;
972     attr_value_iter_t *ait;
973     char valbuf[4096], *q;
974     size_t size;
975     bool ok, success;
976     char dbgbuf[256];
977
978     p = buf;
979     child = NULL;
980     attr = NULL;
981     nbr  = -1;
982     listidx = 0;
983     lists = NULL;
984     buf2 = NULL;
985     ait = NULL;
986     success = false;
987
988     testcond = MRP_DECISION_EQ;
989     testval_type = MRP_DECISION_VALUE_UNKNOWN;
990     memset(&testval, 0, sizeof(testval));
991
992     while (*p) {
993         if (!property(&p, &name, &value))
994             break;
995
996         if (!strcmp(name, "att")) {
997             if (attr)
998                 goto finish_parsing;
999
1000             if (!(attr = mrp_htbl_lookup(conf->attrs, value)))
1001                 goto finish_parsing;
1002         }
1003         else if (!strcmp(name, "forks")) {
1004             if (nbr >= 0)
1005                 goto finish_parsing;
1006
1007             nbr = strtol(value, &e, 10);
1008
1009             if (*e || e == value || nbr <= 0 || nbr > 100)
1010                 goto finish_parsing;
1011
1012             if (type == 3)
1013                 lists = mrp_allocz(sizeof(*lists) * nbr);
1014         }
1015         else if (!strcmp(name, "elts")) {
1016             if (!attr || !lists || listidx >= nbr)
1017                 goto finish_parsing;
1018
1019             l = lists + listidx++;
1020             l->items = mrp_allocz(sizeof(l->items[0]) * attr->nvalue);
1021
1022             do {
1023                 if (l->size >= attr->nvalue)
1024                     goto finish_parsing;
1025                 if (!(av = mrp_htbl_lookup(attr->values, value)))
1026                     goto finish_parsing;
1027
1028                 iv = l->items + l->size++;
1029                 iv->name = value;
1030                 iv->value = av->integer;
1031
1032             } while (list_item(&p, &value));
1033         }
1034
1035         whitespace(&p);
1036
1037     } /* while property */
1038
1039     if (attr && nbr > 0) {
1040         if (type == 1) {
1041             if (getline(&buf2, &n, f) < 0)
1042                 goto finish_parsing;
1043
1044             if (!tree_parse_terminal_node(conf, f,lineno,buf2, true, NULL, 0))
1045                 goto finish_parsing;
1046
1047             free(buf2);
1048             buf2 = NULL;
1049             nbr--;
1050             if (!(ait = attr_value_iterator(attr)))
1051                 goto finish_parsing;
1052         }
1053
1054         mrp_debug("%stest/%d: '%s'", indent(depth), nbr, attr->name);
1055
1056         if (!(*node = mrp_decision_create_test_node()))
1057             goto finish_parsing;
1058
1059         for (i=0, buf2=NULL;  i < nbr && getline(&buf2,&n,f) >= 0;   i++) {
1060             (*lineno)++;
1061
1062             switch (type) {
1063
1064             case 1:
1065                 testval_type = MRP_DECISION_VALUE_INTEGER;
1066                 testval.integer = ait->descs[i].value;
1067                 testcond = MRP_DECISION_EQ;
1068                 snprintf(valbuf, sizeof(valbuf), "%s", ait->descs[i].name);
1069                 break;
1070
1071             case 2:
1072                 break;
1073
1074             case 3:
1075                 testval_type = MRP_DECISION_VALUE_UNKNOWN;
1076                 l = lists + i;
1077                 if (l->size == 1) {
1078                     testcond = MRP_DECISION_EQ;
1079                     testval_type = MRP_DECISION_VALUE_INTEGER;
1080                     testval.integer = l->items[0].value;
1081                     snprintf(valbuf, sizeof(valbuf), "%s", l->items[0].name);
1082                 }
1083                 else {
1084                     testcond = MRP_DECISION_IN;
1085                     if (l->size <= (int)MRP_DECISION_BITMASK_WIDTH) {
1086                         testval_type = MRP_DECISION_VALUE_BITMASK;
1087                         testval.bitmask = 0;
1088                     }
1089                     else {
1090                         testval_type = MRP_DECISION_ARRAY |
1091                             MRP_DECISION_VALUE_INTEGER;
1092                         testval.array.size = l->size;
1093                         size = sizeof(mrp_decision_value_t) * testval.array.size;
1094                         testval.array.values = mrp_allocz(size);
1095                     }
1096                     e = (q = valbuf) + sizeof(valbuf);
1097                     for (j = 0;   j < l->size;   j++) {
1098                         if (q < e) {
1099                             q += snprintf(q, e-q, "%s%s",
1100                                           j?",":"", l->items[j].name);
1101                         }
1102                         k = l->items[j].value;
1103                         if (testval_type == MRP_DECISION_VALUE_BITMASK)
1104                             testval.bitmask |= MRP_DECISION_BIT(k);
1105                         else
1106                             testval.array.values[j].integer = k;
1107                     }
1108                 }
1109                 break;
1110
1111             default:
1112                 goto finish_parsing;
1113             }
1114
1115             switch (testval_type) {
1116             case MRP_DECISION_VALUE_BITMASK:
1117                 snprintf(dbgbuf, sizeof(dbgbuf), " 0x%x", testval.bitmask);
1118                 break;
1119             case MRP_DECISION_VALUE_INTEGER:
1120                 snprintf(dbgbuf, sizeof(dbgbuf), " %d", testval.integer);
1121                 break;
1122             default:
1123                 dbgbuf[0] = 0;
1124             }
1125             mrp_debug("%s%s %s '%s'%s", indent(depth+1),
1126                       mrp_decision_condition_str(testcond),
1127                       mrp_decision_value_type_str(testval_type),
1128                       valbuf, dbgbuf);
1129
1130             if (!tree_parse(conf, f, lineno, buf2, &child, depth+2))
1131                 goto finish_parsing;
1132
1133             ok = mrp_decision_add_branch_to_test_node(*node, testcond, attr->id,
1134                                                       testval_type, &testval,
1135                                                       attr->offset, child);
1136             if (!ok)
1137                 goto finish_parsing;
1138
1139             child = NULL;
1140             if ((testval_type & MRP_DECISION_ARRAY))
1141                 mrp_free(testval.array.values);
1142             testval_type = MRP_DECISION_VALUE_UNKNOWN;
1143
1144             free(buf2);
1145             buf2 = NULL;
1146         }
1147
1148         success = true;
1149     }
1150
1151  finish_parsing:
1152     if (lists) {
1153         for (i = 0; i < nbr; i++)
1154             free(lists[i].items);
1155         mrp_free(lists);
1156     }
1157     if ((testval_type & MRP_DECISION_ARRAY))
1158         mrp_free(testval.array.values);
1159     mrp_decision_tree_destroy(child);
1160     mrp_free(ait);
1161     free(buf2);
1162
1163     return success;
1164 }
1165
1166
1167
1168 static bool property(char **buf, char **name, char **value)
1169 {
1170     char *p = *buf;
1171     char term;
1172
1173     if (identifier(&p, name, &term) &&
1174         term == '=' &&
1175         quoted(&p, value))
1176     {
1177         whitespace(&p);
1178         *buf = p;
1179         return true;
1180     }
1181
1182     return false;
1183 }
1184
1185 static bool list_item(char **buf, char **name)
1186 {
1187     char *p = *buf;
1188
1189     whitespace(&p);
1190
1191     if (*p++ != ',')
1192         return false;
1193
1194     if (quoted(&p, name)) {
1195         *buf = p;
1196         return true;
1197     }
1198
1199     return false;
1200 }
1201
1202
1203 static bool identifier(char **buf, char **id, char *term)
1204 {
1205     char *p, *q, c;
1206
1207     q = *buf;
1208
1209     whitespace(&q);
1210
1211     for (p = q;  (c = *p);  p++) {
1212         if (!isalnum(c))
1213             break;
1214     }
1215
1216     if (p == q)
1217         return false;
1218
1219     whitespace(&p);
1220     if ((*term = *p))
1221         *p++ = 0;
1222
1223     *buf = p;
1224     *id = q;
1225     return true;
1226 }
1227
1228
1229 static bool whitespace(char **buf)
1230 {
1231     char *p, c;
1232
1233     for (p = *buf;  (c = *p);  p++) {
1234         if (c != ' ' && c != '\t' && c != '\n')
1235             break;
1236     }
1237
1238     *buf = p;
1239     return true;
1240 }
1241
1242 static bool quoted(char **buf, char **string)
1243 {
1244     char *p, *q, c;
1245
1246     q = *buf;
1247
1248     whitespace(&q);
1249
1250     if (*q++ != '"')
1251         return false;
1252
1253     for (p = q; (c = *p);  p++) {
1254         if (c < 0x20)
1255             return -1;
1256         if (c == '"' && p[-1] != '\\') {
1257             *p++ = 0;
1258             *buf = p;
1259             *string = q;
1260             return true;
1261         }
1262     }
1263
1264     return false;
1265 }
1266
1267 size_t mrp_decision_tree_print(mrp_decision_conf_t *conf,
1268                                mrp_decision_node_t *node,
1269                                char *buf, size_t len)
1270 {
1271     conf_iter_t *cit;
1272     char *p, *e;
1273
1274     e = (p = buf) + len;
1275
1276     if (conf && node && buf && len > 0) {
1277         if (!(cit = conf_iterator(conf)))
1278             p += snprintf(p, e-p, "<error>\n");
1279         else {
1280             p += print_node(conf, node, cit, p, e-p, NULL);
1281             p += snprintf(p, e-p, "\n");
1282             mrp_free(cit);
1283         }
1284     }
1285
1286     return p - buf;
1287 }
1288
1289
1290 static size_t print_node(mrp_decision_conf_t *conf,
1291                          mrp_decision_node_t *node,
1292                          conf_iter_t *cit,
1293                          char *buf, size_t len,
1294                          char *indent)
1295 {
1296 #define PRINT(_args...)      \
1297     do {if (p < e) p += snprintf(p,e-p, _args);} while(0)
1298 #define PRINT_VALUE(_t,_v)   \
1299     do {if (p < e) p += mrp_decision_value_print(_t, _v, p,e-p);} while(0)
1300 #define PRINT_BITMASK(_a,_m) \
1301     do {if (p < e) p += print_bitmask(_a, _m, p, e-p);} while(0)
1302 #define PRINT_NODE(_p,_i)    \
1303     do {if (p < e) p += print_node(conf, (_p)->node, cit, p,e-p, _i);} while(0)
1304
1305     static char indent_buf[4096];
1306     static char *indent_end = indent_buf + sizeof(indent_buf);
1307
1308     mrp_decision_root_node_t *root;
1309     mrp_decision_test_node_t *test;
1310     mrp_decision_terminal_node_t *term;
1311     mrp_decision_branch_t *branch;
1312     mrp_decision_attr_t *attr;
1313     const char *attr_name;
1314     int32_t value_idx;
1315     attr_value_iter_t *ait;
1316     char *p, *e, *new_indent;
1317     int32_t decision;
1318     size_t i;
1319
1320     if (!node || !buf)
1321         return 0;
1322
1323     if (!indent) {
1324         indent_buf[0] = 0;
1325         indent = indent_buf;
1326     }
1327
1328     e = (p = buf) + len;
1329
1330     switch (node->type) {
1331
1332     case MRP_DECISION_ROOT_NODE:
1333         root = &node->root;
1334         PRINT("root of %s (decision type: %s)", root->name,
1335               mrp_decision_value_type_str(root->decision_value_type));
1336         new_indent  = indent;
1337         new_indent += snprintf(indent, indent_end-indent, "\n");
1338         PRINT_NODE(root, new_indent);
1339         *indent = 0;
1340         break;
1341
1342     case MRP_DECISION_TEST_NODE:
1343         test = &node->test;
1344
1345         for (i = 0;  i < test->nbranch;  i++) {
1346             branch = test->branches + i;
1347             if (branch->value_id < 0 || branch->value_id >= cit->nattr)
1348                 PRINT("%s:...<invalid attribute>", indent_buf);
1349             else {
1350                 attr = cit->attrs[branch->value_id];
1351                 attr_name = attr ? attr->name : "<invalid attribute>";
1352                 PRINT("%s:...%s %s ", indent_buf, attr_name,
1353                       mrp_decision_condition_str(branch->condition));
1354
1355                 if (branch->value_type != MRP_DECISION_VALUE_INTEGER) {
1356                     PRINT_VALUE(branch->value_type, &branch->value);
1357                     if (branch->value_type == MRP_DECISION_VALUE_BITMASK) {
1358                         PRINT(" (");
1359                         PRINT_BITMASK(attr, branch->value.bitmask);
1360                         PRINT(")");
1361                     }
1362                 }
1363                 else {
1364                     value_idx = branch->value.integer;
1365                     if (value_idx < 0 || value_idx >= attr->nvalue ||
1366                         !(ait = attr_value_iterator(attr)))
1367                         PRINT("<invalid attribute value>");
1368                     else {
1369                         PRINT("%d (%s)", value_idx, ait->descs[value_idx].name);
1370                         mrp_free(ait);
1371                     }
1372                 }
1373             }
1374             new_indent  = indent;
1375             new_indent += snprintf(new_indent, indent_end-indent, "%c   ",
1376                                    i == test->nbranch-1 ? ' ':':');
1377             PRINT_NODE(branch, new_indent);
1378             *indent = 0;
1379         }
1380
1381         break;
1382
1383     case MRP_DECISION_TERMINAL_NODE:
1384         term = &node->terminal;
1385         decision = term->decision.integer;
1386         if (decision < 0 || decision >= conf->decision_attr->nvalue)
1387             PRINT(" => decision <invalid value>");
1388         else
1389             PRINT(" => %s", conf->decision_names[decision]);
1390         break;
1391
1392     default:
1393         PRINT("%s<unknown node type %d>\n", indent_buf, node->type);
1394         break;
1395     }
1396
1397     return p - buf;
1398
1399 #undef PRINT_VALUE
1400 #undef PRINT
1401 }
1402
1403
1404 static size_t print_bitmask(mrp_decision_attr_t *attr,
1405                             mrp_decision_bitmask_t bitmask,
1406                             char *buf, size_t len)
1407 {
1408     attr_value_iter_t *it;
1409     mrp_decision_bitmask_t m;
1410     char *p, *e;
1411     int i,j;
1412     char *sep;
1413
1414     if (!attr || !buf || len < 1)
1415         return 0;
1416
1417     if (!(it = attr_value_iterator(attr)))
1418         return 0;
1419
1420     e = (p = buf) + len;
1421
1422     if (!(m = bitmask))
1423         p += snprintf(p, e-p, "<empty>");
1424     else {
1425         for (i = 0, sep = "";   m && i < it->ndesc && p < e;  i++, m >>= 1) {
1426             if ((m & 1)) {
1427                 if (it->descs[i].value == i)
1428                     j = i;
1429                 else {
1430                     for (j = 0;  j < it->ndesc;  j++) {
1431                         if (it->descs[j].value == i)
1432                             break;
1433                     }
1434                 }
1435                 if (j < 0 || j >= it->ndesc)
1436                     p += snprintf(p, e-p, "%s<unknown value %d>", sep, j);
1437                 else
1438                     p += snprintf(p, e-p, "%s%s", sep, it->descs[j].name);
1439                 sep = ",";
1440             }
1441         }
1442     }
1443
1444     mrp_free(it);
1445
1446     return p - buf;
1447 }