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