ARGOBOTS  66b1c39742507d8df30e8d28c54839b961a14814
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
abtd_affinity_parser.c
Go to the documentation of this file.
1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil ; -*- */
2 /*
3  * See COPYRIGHT in top-level directory.
4  */
5 
6 #include "abti.h"
7 
9 {
10  ABTD_affinity_id_list *p_id_list;
11  int ret =
12  ABTU_calloc(1, sizeof(ABTD_affinity_id_list), (void **)&p_id_list);
13  ABTI_ASSERT(ret == ABT_SUCCESS);
14  return p_id_list;
15 }
16 
17 static void id_list_free(ABTD_affinity_id_list *p_id_list)
18 {
19  if (p_id_list)
20  ABTU_free(p_id_list->ids);
21  ABTU_free(p_id_list);
22 }
23 
24 static void id_list_add(ABTD_affinity_id_list *p_id_list, int id, int num,
25  int stride)
26 {
27  /* Needs to add num ids. */
28  int i, ret;
29  ret = ABTU_realloc(sizeof(int) * p_id_list->num,
30  sizeof(int) * (p_id_list->num + num),
31  (void **)&p_id_list->ids);
32  ABTI_ASSERT(ret == ABT_SUCCESS);
33  for (i = 0; i < num; i++) {
34  p_id_list->ids[p_id_list->num + i] = id + stride * i;
35  }
36  p_id_list->num += num;
37 }
38 
40 {
41 
42  ABTD_affinity_list *p_list;
43  int ret = ABTU_calloc(1, sizeof(ABTD_affinity_list), (void **)&p_list);
44  ABTI_ASSERT(ret == ABT_SUCCESS);
45  return p_list;
46 }
47 
48 static void list_free(ABTD_affinity_list *p_list)
49 {
50  if (p_list) {
51  int i;
52  for (i = 0; i < p_list->num; i++)
53  id_list_free(p_list->p_id_lists[i]);
54  free(p_list->p_id_lists);
55  }
56  free(p_list);
57 }
58 
59 static void list_add(ABTD_affinity_list *p_list, ABTD_affinity_id_list *p_base,
60  int num, int stride)
61 {
62  /* Needs to add num id-lists. */
63  int i, j, ret;
64 
65  ret = ABTU_realloc(sizeof(ABTD_affinity_id_list *) * p_list->num,
66  sizeof(ABTD_affinity_id_list *) * (p_list->num + num),
67  (void **)&p_list->p_id_lists);
68  ABTI_ASSERT(ret == ABT_SUCCESS);
69  for (i = 1; i < num; i++) {
71  p_id_list->num = p_base->num;
72  ret =
73  ABTU_malloc(sizeof(int) * p_id_list->num, (void **)&p_id_list->ids);
74  ABTI_ASSERT(ret == ABT_SUCCESS);
75  for (j = 0; j < p_id_list->num; j++)
76  p_id_list->ids[j] = p_base->ids[j] + stride * i;
77  p_list->p_id_lists[p_list->num + i] = p_id_list;
78  }
79  p_list->p_id_lists[p_list->num] = p_base;
80  p_list->num += num;
81 }
82 
83 static inline int is_whitespace(char c)
84 {
85  return c == ' ' || c == '\t' || c == '\r' || c == '\n';
86 }
87 
88 /* Integer. */
89 static int consume_int(const char *str, int *p_index, int *p_val)
90 {
91  int index = *p_index, val = 0, val_sign = 1;
92  char flag = 'n';
93  while (1) {
94  char c = *(str + index);
95  if (flag != 'v' && c == '-') {
96  /* Negative sign. */
97  flag = 's';
98  val_sign = -val_sign;
99  } else if (flag != 'v' && c == '+') {
100  /* Positive sign. */
101  flag = 's';
102  } else if (flag == 'n' && is_whitespace(c)) {
103  /* Skip a whitespace. */
104  } else if ('0' <= c && c <= '9') {
105  /* Value. */
106  flag = 'v';
107  val = val * 10 + (int)(c - '0');
108  } else {
109  /* Encounters a symbol. */
110  if (flag == 'v') {
111  /* Succeeded. */
112  *p_val = val * val_sign;
113  *p_index = index;
114  return 1;
115  } else {
116  /* Failed. The parser could not consume a value. */
117  return 0;
118  }
119  }
120  index++;
121  }
122 }
123 
124 /* Positive integer */
125 static int consume_pint(const char *str, int *p_index, int *p_val)
126 {
127  int index = *p_index, val;
128  /* The value must be positive. */
129  if (consume_int(str, &index, &val) && val > 0) {
130  *p_index = index;
131  *p_val = val;
132  return 1;
133  }
134  return 0;
135 }
136 
137 /* Symbol. If succeeded, it returns a consumed characters. */
138 static int consume_symbol(const char *str, int *p_index, char symbol)
139 {
140  int index = *p_index;
141  while (1) {
142  char c = *(str + index);
143  if (c == symbol) {
144  *p_index = index + 1;
145  return 1;
146  } else if (is_whitespace(c)) {
147  /* Skip a whitespace. */
148  } else {
149  /* Failed. The parser could not consume a symbol. */
150  return 0;
151  }
152  index++;
153  }
154 }
155 
156 static ABTD_affinity_id_list *parse_es_id_list(const char *affinity_str,
157  int *p_index)
158 {
159  ABTD_affinity_id_list *p_id_list = id_list_create();
160  int val;
161  /* Expect either <id> or { <id-list> } */
162  if (consume_int(affinity_str, p_index, &val)) {
163  /* If the first token is an integer, it is <id> */
164  id_list_add(p_id_list, val, 1, 1);
165  return p_id_list;
166  } else if (consume_symbol(affinity_str, p_index, '{')) {
167  /* It should be "{" <id-list> "}". Parse <id-list> and "}" */
168  while (1) {
169  int id, num = 1, stride = 1;
170  /* Parse <id-interval>. First, expect <id> */
171  if (!consume_int(affinity_str, p_index, &id))
172  goto FAILED;
173  /* Optional: ":" <num> */
174  if (consume_symbol(affinity_str, p_index, ':')) {
175  /* Expect <num> */
176  if (!consume_pint(affinity_str, p_index, &num))
177  goto FAILED;
178  /* Optional: ":" <stride> */
179  if (consume_symbol(affinity_str, p_index, ':')) {
180  /* Expect <stride> */
181  if (!consume_int(affinity_str, p_index, &stride))
182  goto FAILED;
183  }
184  }
185  /* Add ids based on <id-interval> */
186  id_list_add(p_id_list, id, num, stride);
187  /* After <id-interval>, we expect either "," (in <id-list>) or "}"
188  * (in <es-id-list>) */
189  if (consume_symbol(affinity_str, p_index, ',')) {
190  /* Parse <id-interval> again. */
191  continue;
192  }
193  /* Expect "}" */
194  if (!consume_symbol(affinity_str, p_index, '}'))
195  goto FAILED;
196  /* Succeeded. */
197  return p_id_list;
198  }
199  }
200 FAILED:
201  id_list_free(p_id_list);
202  return NULL; /* Failed. */
203 }
204 
205 static ABTD_affinity_list *parse_list(const char *affinity_str)
206 {
207  if (!affinity_str)
208  return NULL;
209  int index = 0;
210  ABTD_affinity_list *p_list = list_create();
211  ABTD_affinity_id_list *p_id_list = NULL;
212  while (1) {
213  int num = 1, stride = 1;
214  /* Parse <interval> */
215  /* Expect <es-id-list> */
216  p_id_list = parse_es_id_list(affinity_str, &index);
217  if (!p_id_list)
218  goto FAILED;
219  /* Optional: ":" <num> */
220  if (consume_symbol(affinity_str, &index, ':')) {
221  /* Expect <num> */
222  if (!consume_pint(affinity_str, &index, &num))
223  goto FAILED;
224  /* Optional: ":" <stride> */
225  if (consume_symbol(affinity_str, &index, ':')) {
226  /* Expect <stride> */
227  if (!consume_int(affinity_str, &index, &stride))
228  goto FAILED;
229  }
230  }
231  /* Add <es-id-list> based on <interval> */
232  list_add(p_list, p_id_list, num, stride);
233  p_id_list = NULL;
234  /* After <interval>, expect either "," (in <list>) or "\0" */
235  if (consume_symbol(affinity_str, &index, ',')) {
236  /* Parse <interval> again. */
237  continue;
238  }
239  /* Expect "\0" */
240  if (!consume_symbol(affinity_str, &index, '\0'))
241  goto FAILED;
242  /* Succeeded. */
243  return p_list;
244  }
245 FAILED:
246  list_free(p_list);
247  id_list_free(p_id_list);
248  return NULL; /* Failed. */
249 }
250 
252 {
253  return parse_list(affinity_str);
254 }
255 
257 {
258  list_free(p_list);
259 }
260 
261 #if 0
262 
263 static int is_equal(const ABTD_affinity_list *a, const ABTD_affinity_list *b)
264 {
265  int i, j;
266  if (a->num != b->num)
267  return 0;
268  for (i = 0; i < a->num; i++) {
269  const ABTD_affinity_id_list *a_id = a->p_id_lists[i];
270  const ABTD_affinity_id_list *b_id = b->p_id_lists[i];
271  if (a_id->num != b_id->num)
272  return 0;
273  for (j = 0; j < a_id->num; j++) {
274  if (a_id->ids[j] != b_id->ids[j])
275  return 0;
276  }
277  }
278  return 1;
279 }
280 
281 static int is_equal_str(const char *a_str, const char *b_str)
282 {
283  int ret = 1;
284  ABTD_affinity_list *a = parse_list(a_str);
285  ABTD_affinity_list *b = parse_list(b_str);
286  ret = a && b && is_equal(a, b);
287  list_free(a);
288  list_free(b);
289  return ret;
290 }
291 
292 static int is_err_str(const char *str)
293 {
294  ABTD_affinity_list *a = parse_list(str);
295  if (a) {
296  list_free(a);
297  return 0;
298  }
299  return 1;
300 }
301 
302 static void test_parse(void)
303 {
304  /* Legal strings */
305  assert(!is_err_str("++1"));
306  assert(!is_err_str("+-1"));
307  assert(!is_err_str("+-+-1"));
308  assert(!is_err_str("+0"));
309  assert(!is_err_str("-0"));
310  assert(!is_err_str("-9:1:-9"));
311  assert(!is_err_str("-9:1:0"));
312  assert(!is_err_str("-9:1:9"));
313  assert(!is_err_str("0:1:-9"));
314  assert(!is_err_str("0:1:0"));
315  assert(!is_err_str("0:1:9"));
316  assert(!is_err_str("9:1:-9"));
317  assert(!is_err_str("9:1:0"));
318  assert(!is_err_str("9:1:9"));
319  assert(!is_err_str("{-9:1:-9}"));
320  assert(!is_err_str("{-9:1:0}"));
321  assert(!is_err_str("{-9:1:9}"));
322  assert(!is_err_str("{0:1:-9}"));
323  assert(!is_err_str("{0:1:0}"));
324  assert(!is_err_str("{0:1:9}"));
325  assert(!is_err_str("{9:1:-9}"));
326  assert(!is_err_str("{9:1:0}"));
327  assert(!is_err_str("{9:1:9}"));
328  assert(!is_err_str("1,2,3"));
329  assert(!is_err_str("1,2,{1,2}"));
330  assert(!is_err_str("1,2,{1:2}"));
331  assert(!is_err_str("1:2,{1:2}"));
332  assert(!is_err_str("1:2:1,2"));
333  assert(!is_err_str(" 1 : +2 , { -1 : \r 2\n:2}\n"));
334  /* Illegal strings */
335  assert(is_err_str(""));
336  assert(is_err_str("{}"));
337  assert(is_err_str("+ 1"));
338  assert(is_err_str("+ +1"));
339  assert(is_err_str("+ -1"));
340  assert(is_err_str("1:"));
341  assert(is_err_str("1:2:"));
342  assert(is_err_str("1:2,"));
343  assert(is_err_str("1:-2"));
344  assert(is_err_str("1:0"));
345  assert(is_err_str("1:-2:4"));
346  assert(is_err_str("1:0:4"));
347  assert(is_err_str("1:1:1:"));
348  assert(is_err_str("1:1:1:1"));
349  assert(is_err_str("1:1:1:1,1"));
350  assert(is_err_str("{1:2:3},"));
351  assert(is_err_str("{1:2:3}:"));
352  assert(is_err_str("{1:2:3}:2:"));
353  assert(is_err_str("{:2:3}"));
354  assert(is_err_str("{{2:3}}"));
355  assert(is_err_str("{2:3}}"));
356  assert(is_err_str("2:3}"));
357  assert(is_err_str("{1:2:3"));
358  assert(is_err_str("{1,2,}"));
359  assert(is_err_str("{1:-2}"));
360  assert(is_err_str("{1:0}"));
361  assert(is_err_str("{1:-2:4}"));
362  assert(is_err_str("{1:0:4}"));
363  /* Comparison */
364  assert(is_equal_str("{1},{2},{3},{4}", "1,2,3,4"));
365  assert(is_equal_str("{1:4:1}", "{1,2,3,4}"));
366  assert(is_equal_str("{1:4}", "{1,2,3,4}"));
367  assert(is_equal_str("1:2,3:2", "1,2,3,4"));
368  assert(is_equal_str("{1:2},3:2", "{1,2},3,4"));
369  assert(is_equal_str("{1:1:4},{2:1:-4},{3:1:0},{4:1}", "1,2,3,4"));
370  assert(is_equal_str("{3:4:-1}", "{3,2,1,0}"));
371  assert(is_equal_str("3:4:-1,-1", "3,2,1,0,-1"));
372  assert(is_equal_str("{1:2:3}:1", "{1,4}"));
373  assert(is_equal_str("{1:2:3}:3", "{1,4},{2,5},{3,6}"));
374  assert(is_equal_str("{1:2:3}:3:2", "{1,4},{3,6},{5,8}"));
375  assert(is_equal_str("{1:2:3}:3:-2", "{1,4},{-1,2},{-3,0}"));
376  assert(is_equal_str("{1:2:3}:3:-2,1", "{1,4},{-1,2},{-3,0},1"));
377  assert(is_equal_str("{-2:3:-2}:2:-4", "{-2,-4,-6},{-6,-8,-10}"));
378 }
379 
380 #endif
static ABTD_affinity_id_list * parse_es_id_list(const char *affinity_str, int *p_index)
ABTD_affinity_list * ABTD_affinity_list_create(const char *affinity_str)
static int consume_pint(const char *str, int *p_index, int *p_val)
static int consume_int(const char *str, int *p_index, int *p_val)
static ABTU_ret_err int ABTU_malloc(size_t size, void **p_ptr)
Definition: abtu.h:142
static ABTD_affinity_list * parse_list(const char *affinity_str)
static ABTU_ret_err int ABTU_realloc(size_t old_size, size_t new_size, void **p_ptr)
Definition: abtu.h:165
static void id_list_add(ABTD_affinity_id_list *p_id_list, int id, int num, int stride)
static void id_list_free(ABTD_affinity_id_list *p_id_list)
ABTD_affinity_id_list ** p_id_lists
Definition: abtd.h:73
#define ABT_SUCCESS
Definition: abt.h:64
void ABTD_affinity_list_free(ABTD_affinity_list *p_list)
static void list_add(ABTD_affinity_list *p_list, ABTD_affinity_id_list *p_base, int num, int stride)
static void list_free(ABTD_affinity_list *p_list)
static ABTD_affinity_id_list * id_list_create(void)
#define ABTI_ASSERT(cond)
Definition: abti_error.h:12
static int consume_symbol(const char *str, int *p_index, char symbol)
static ABTD_affinity_list * list_create(void)
static int is_whitespace(char c)
static ABTU_ret_err int ABTU_calloc(size_t num, size_t size, void **p_ptr)
Definition: abtu.h:152
static void ABTU_free(void *ptr)
Definition: abtu.h:135