ARGOBOTS  2202510f2bd4ba732a2ba2215171c0820320f58d
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 
8 /* If the value is too big, the input should be wrong. */
9 #define MAX_NUM_ELEMS (1024 * 1024)
10 
11 typedef struct alloc_header {
14 } alloc_header;
15 #define ALLOC_HEADER_SIZE \
16  ((sizeof(alloc_header) + ABTU_MAX_ALIGNMENT - 1) / ABTU_MAX_ALIGNMENT * \
17  ABTU_MAX_ALIGNMENT)
18 
19 typedef struct {
22 } alloc_list;
23 
24 /* Since it is extremely cumbersome to handle memory leaks on memory allocation
25  * failure, the following implementation uses a linked list. */
26 ABTU_ret_err static int list_calloc(alloc_list *p_alloc_list, size_t size,
27  void **p_ptr)
28 {
29  alloc_header *p_header;
30  int ret = ABTU_calloc(1, size + ALLOC_HEADER_SIZE, (void **)&p_header);
31  ABTI_CHECK_ERROR(ret);
32  /* Allocation succeeded. */
33  *p_ptr = (void *)(((char *)p_header) + ALLOC_HEADER_SIZE);
34  /* Append this header to alloc_list */
35  p_header->p_next = NULL;
36  p_header->p_prev = p_alloc_list->p_tail;
37  if (p_alloc_list->p_tail) {
38  p_alloc_list->p_tail->p_next = p_header;
39  p_alloc_list->p_tail = p_header;
40  } else {
41  p_alloc_list->p_head = p_header;
42  p_alloc_list->p_tail = p_header;
43  }
44  return ABT_SUCCESS;
45 }
46 
47 ABTU_ret_err static int list_realloc(alloc_list *p_alloc_list, size_t old_size,
48  size_t new_size, void **p_ptr)
49 {
50  /* Read header information before realloc() */
51  if (old_size == 0) {
52  return list_calloc(p_alloc_list, new_size, p_ptr);
53  } else {
54  alloc_header *p_old_header =
55  (alloc_header *)(((char *)*p_ptr) - ALLOC_HEADER_SIZE);
56  alloc_header *p_old_prev_header = p_old_header->p_prev;
57  alloc_header *p_old_next_header = p_old_header->p_next;
58  alloc_header *p_new_header = p_old_header;
59  int ret =
61  new_size + ALLOC_HEADER_SIZE, (void **)&p_new_header);
62  ABTI_CHECK_ERROR(ret);
63  /* Allocation succeeded. */
64  *p_ptr = (void *)(((char *)p_new_header) + ALLOC_HEADER_SIZE);
65  /* Replace p_old_header with p_new_header */
66  if (p_alloc_list->p_head == p_old_header)
67  p_alloc_list->p_head = p_new_header;
68  if (p_alloc_list->p_tail == p_old_header)
69  p_alloc_list->p_tail = p_new_header;
70  p_new_header->p_prev = p_old_prev_header;
71  if (p_old_prev_header)
72  p_old_prev_header->p_next = p_new_header;
73  p_new_header->p_next = p_old_next_header;
74  if (p_old_next_header)
75  p_old_next_header->p_prev = p_new_header;
76  return ABT_SUCCESS;
77  }
78 }
79 
80 static void list_free_all(void *p_head)
81 {
82  alloc_header *p_cur = (alloc_header *)p_head;
83  while (p_cur) {
84  alloc_header *p_next = p_cur->p_next;
85  ABTU_free(p_cur);
86  p_cur = p_next;
87  }
88 }
89 
90 ABTU_ret_err static int id_list_create(alloc_list *p_alloc_list,
91  ABTD_affinity_id_list **pp_id_list)
92 {
93  return list_calloc(p_alloc_list, sizeof(ABTD_affinity_id_list),
94  (void **)pp_id_list);
95 }
96 
97 ABTU_ret_err static int id_list_add(alloc_list *p_alloc_list,
98  ABTD_affinity_id_list *p_id_list, int id,
99  uint32_t num, int stride)
100 {
101  /* Needs to add num ids. */
102  uint32_t i;
103  int ret = list_realloc(p_alloc_list, sizeof(int) * p_id_list->num,
104  sizeof(int) * (p_id_list->num + num),
105  (void **)&p_id_list->ids);
106  ABTI_CHECK_ERROR(ret);
107  for (i = 0; i < num; i++) {
108  p_id_list->ids[p_id_list->num + i] = id + stride * i;
109  }
110  p_id_list->num += num;
111  return ABT_SUCCESS;
112 }
113 
114 ABTU_ret_err static int list_create(alloc_list *p_alloc_list,
115  ABTD_affinity_list **pp_affinity_list)
116 {
117  return list_calloc(p_alloc_list, sizeof(ABTD_affinity_list),
118  (void **)pp_affinity_list);
119 }
120 
121 ABTU_ret_err static int list_add(alloc_list *p_alloc_list,
122  ABTD_affinity_list *p_list,
123  ABTD_affinity_id_list *p_base, uint32_t num,
124  int stride)
125 {
126  /* Needs to add num id-lists. */
127  uint32_t i, j;
128  int ret;
129 
130  ret = list_realloc(p_alloc_list,
131  sizeof(ABTD_affinity_id_list *) * p_list->num,
132  sizeof(ABTD_affinity_id_list *) * (p_list->num + num),
133  (void **)&p_list->p_id_lists);
134  ABTI_CHECK_ERROR(ret);
135  for (i = 1; i < num; i++) {
136  ABTD_affinity_id_list *p_id_list;
137  ret = id_list_create(p_alloc_list, &p_id_list);
138  ABTI_CHECK_ERROR(ret);
139  p_id_list->num = p_base->num;
140  ret = list_calloc(p_alloc_list, sizeof(int) * p_id_list->num,
141  (void **)&p_id_list->ids);
142  ABTI_CHECK_ERROR(ret);
143  for (j = 0; j < p_id_list->num; j++)
144  p_id_list->ids[j] = p_base->ids[j] + stride * i;
145  p_list->p_id_lists[p_list->num + i] = p_id_list;
146  }
147  p_list->p_id_lists[p_list->num] = p_base;
148  p_list->num += num;
149  return ABT_SUCCESS;
150 }
151 
152 static inline int is_whitespace(char c)
153 {
154  return c == ' ' || c == '\t' || c == '\r' || c == '\n';
155 }
156 
157 /* Integer. */
158 static int consume_int(const char *str, uint32_t *p_index, int *p_val)
159 {
160  uint32_t index = *p_index;
161  int val = 0, val_sign = 1;
162  char flag = 'n';
163  while (1) {
164  char c = *(str + index);
165  if (flag != 'v' && c == '-') {
166  /* Negative sign. */
167  flag = 's';
168  val_sign = -val_sign;
169  } else if (flag != 'v' && c == '+') {
170  /* Positive sign. */
171  flag = 's';
172  } else if (flag == 'n' && is_whitespace(c)) {
173  /* Skip a whitespace. */
174  } else if ('0' <= c && c <= '9') {
175  /* Value. */
176  flag = 'v';
177  val = val * 10 + (int)(c - '0');
178  } else {
179  /* Encounters a symbol. */
180  if (flag == 'v') {
181  /* Succeeded. */
182  *p_val = val * val_sign;
183  *p_index = index;
184  return 1;
185  } else {
186  /* Failed. The parser could not consume a value. */
187  return 0;
188  }
189  }
190  index++;
191  }
192 }
193 
194 /* Positive integer */
195 static int consume_pint(const char *str, uint32_t *p_index, int *p_val)
196 {
197  uint32_t index = *p_index;
198  int val;
199  /* The value must be positive. */
200  if (consume_int(str, &index, &val) && val > 0) {
201  *p_index = index;
202  *p_val = val;
203  return 1;
204  }
205  return 0;
206 }
207 
208 /* Symbol. If succeeded, it returns a consumed characters. */
209 static int consume_symbol(const char *str, uint32_t *p_index, char symbol)
210 {
211  uint32_t index = *p_index;
212  while (1) {
213  char c = *(str + index);
214  if (c == symbol) {
215  *p_index = index + 1;
216  return 1;
217  } else if (is_whitespace(c)) {
218  /* Skip a whitespace. */
219  } else {
220  /* Failed. The parser could not consume a symbol. */
221  return 0;
222  }
223  index++;
224  }
225 }
226 
227 ABTU_ret_err static int
228 parse_es_id_list(alloc_list *p_alloc_list, const char *affinity_str,
229  uint32_t *p_index, ABTD_affinity_id_list **pp_affinity_id_list)
230 {
231  int ret, val;
232  ABTD_affinity_id_list *p_affinity_id_list;
233  ret = id_list_create(p_alloc_list, &p_affinity_id_list);
234  ABTI_CHECK_ERROR(ret);
235  /* Expect either <id> or { <id-list> } */
236  if (consume_int(affinity_str, p_index, &val)) {
237  /* If the first token is an integer, it is <id> */
238  ret = id_list_add(p_alloc_list, p_affinity_id_list, val, 1, 1);
239  ABTI_CHECK_ERROR(ret);
240  *pp_affinity_id_list = p_affinity_id_list;
241  return ABT_SUCCESS;
242  } else if (consume_symbol(affinity_str, p_index, '{')) {
243  /* It should be "{" <id-list> "}". Parse <id-list> and "}" */
244  while (1) {
245  int id, num = 1, stride = 1;
246  /* Parse <id-interval>. First, expect <id> */
247  if (!consume_int(affinity_str, p_index, &id))
248  return ABT_ERR_OTHER;
249  /* Optional: ":" <num> */
250  if (consume_symbol(affinity_str, p_index, ':')) {
251  /* Expect <num> */
252  if (!consume_pint(affinity_str, p_index, &num))
253  return ABT_ERR_OTHER;
254  /* Optional: ":" <stride> */
255  if (consume_symbol(affinity_str, p_index, ':')) {
256  /* Expect <stride> */
257  if (!consume_int(affinity_str, p_index, &stride))
258  return ABT_ERR_OTHER;
259  }
260  }
261  if (num >= MAX_NUM_ELEMS)
262  return ABT_ERR_OTHER;
263  /* Add ids based on <id-interval> */
264  ret =
265  id_list_add(p_alloc_list, p_affinity_id_list, id, num, stride);
266  ABTI_CHECK_ERROR(ret);
267  /* After <id-interval>, we expect either "," (in <id-list>) or "}"
268  * (in <es-id-list>) */
269  if (consume_symbol(affinity_str, p_index, ',')) {
270  /* Parse <id-interval> again. */
271  continue;
272  }
273  /* Expect "}" */
274  if (!consume_symbol(affinity_str, p_index, '}'))
275  return ABT_ERR_OTHER;
276  /* Succeeded. */
277  *pp_affinity_id_list = p_affinity_id_list;
278  return ABT_SUCCESS;
279  }
280  }
281  return ABT_ERR_OTHER;
282 }
283 
284 ABTU_ret_err static int parse_list(alloc_list *p_alloc_list,
285  const char *affinity_str,
286  ABTD_affinity_list **pp_affinity_list)
287 {
288  if (!affinity_str)
289  return ABT_ERR_OTHER;
290  int ret;
291  uint32_t index = 0;
292  ABTD_affinity_list *p_affinity_list;
293  ret = list_create(p_alloc_list, &p_affinity_list);
294  ABTI_CHECK_ERROR(ret);
295 
296  ABTD_affinity_id_list *p_id_list = NULL;
297  while (1) {
298  int num = 1, stride = 1;
299  /* Parse <interval> */
300  /* Expect <es-id-list> */
301  ret = parse_es_id_list(p_alloc_list, affinity_str, &index, &p_id_list);
302  ABTI_CHECK_ERROR(ret);
303  /* Optional: ":" <num> */
304  if (consume_symbol(affinity_str, &index, ':')) {
305  /* Expect <num> */
306  if (!consume_pint(affinity_str, &index, &num))
307  return ABT_ERR_OTHER;
308  /* Optional: ":" <stride> */
309  if (consume_symbol(affinity_str, &index, ':')) {
310  /* Expect <stride> */
311  if (!consume_int(affinity_str, &index, &stride))
312  return ABT_ERR_OTHER;
313  }
314  }
315  if (num >= MAX_NUM_ELEMS)
316  return ABT_ERR_OTHER;
317  /* Add <es-id-list> based on <interval> */
318  ret = list_add(p_alloc_list, p_affinity_list, p_id_list, num, stride);
319  ABTI_CHECK_ERROR(ret);
320  p_id_list = NULL;
321  /* After <interval>, expect either "," (in <list>) or "\0" */
322  if (consume_symbol(affinity_str, &index, ',')) {
323  /* Parse <interval> again. */
324  continue;
325  }
326  /* Expect "\0" */
327  if (!consume_symbol(affinity_str, &index, '\0'))
328  return ABT_ERR_OTHER;
329  /* Succeeded. */
330  *pp_affinity_list = p_affinity_list;
331  return ABT_SUCCESS;
332  }
333  /* Unreachable. */
334 }
335 
336 ABTU_ret_err int
337 ABTD_affinity_list_create(const char *affinity_str,
338  ABTD_affinity_list **pp_affinity_list)
339 {
340  ABTD_affinity_list *p_affinity_list;
341  alloc_list tmp_alloc_list = { NULL, NULL };
342  int ret = parse_list(&tmp_alloc_list, affinity_str, &p_affinity_list);
343  if (ret != ABT_SUCCESS) {
344  /* Free all the allocated memory. */
345  list_free_all((void *)tmp_alloc_list.p_head);
346  return ret;
347  } else {
348  /* Save p_head in p_affinity_list to free it in
349  * ABTD_affinity_list_free(). */
350  p_affinity_list->p_mem_head = (void *)tmp_alloc_list.p_head;
351  *pp_affinity_list = p_affinity_list;
352  return ABT_SUCCESS;
353  }
354 }
355 
356 void ABTD_affinity_list_free(ABTD_affinity_list *p_affinity_list)
357 {
358  if (p_affinity_list) {
359  list_free_all(p_affinity_list->p_mem_head);
360  }
361 }
362 
363 #if 0
364 
365 static int is_equal(const ABTD_affinity_list *a, const ABTD_affinity_list *b)
366 {
367  int i, j;
368  if (a->num != b->num)
369  return 0;
370  for (i = 0; i < a->num; i++) {
371  const ABTD_affinity_id_list *a_id = a->p_id_lists[i];
372  const ABTD_affinity_id_list *b_id = b->p_id_lists[i];
373  if (a_id->num != b_id->num)
374  return 0;
375  for (j = 0; j < a_id->num; j++) {
376  if (a_id->ids[j] != b_id->ids[j])
377  return 0;
378  }
379  }
380  return 1;
381 }
382 
383 static int is_equal_str(const char *a_str, const char *b_str)
384 {
385  int ret = 1;
386  ABTD_affinity_list *a, *b;
387  alloc_list tmp_alloc_list1 = { NULL, NULL };
388  alloc_list tmp_alloc_list2 = { NULL, NULL };
389  int ret1 = parse_list(&tmp_alloc_list1, a_str, &a);
390  int ret2 = parse_list(&tmp_alloc_list2, b_str, &b);
391  ret = ret1 == ABT_SUCCESS && ret2 == ABT_SUCCESS && a && b && is_equal(a, b);
392  list_free_all((void *)tmp_alloc_list1.p_head);
393  list_free_all((void *)tmp_alloc_list2.p_head);
394  return ret;
395 }
396 
397 static int is_err_str(const char *str)
398 {
399  alloc_list tmp_alloc_list = { NULL, NULL };
400  ABTD_affinity_list *a;
401  int ret = parse_list(&tmp_alloc_list, str, &a);
402  list_free_all((void *)tmp_alloc_list.p_head);
403  if (ret == ABT_SUCCESS) {
404  return 0;
405  }
406  return 1;
407 }
408 
409 static void test_parse(void)
410 {
411  /* Legal strings */
412  assert(!is_err_str("++1"));
413  assert(!is_err_str("+-1"));
414  assert(!is_err_str("+-+-1"));
415  assert(!is_err_str("+0"));
416  assert(!is_err_str("-0"));
417  assert(!is_err_str("-9:1:-9"));
418  assert(!is_err_str("-9:1:0"));
419  assert(!is_err_str("-9:1:9"));
420  assert(!is_err_str("0:1:-9"));
421  assert(!is_err_str("0:1:0"));
422  assert(!is_err_str("0:1:9"));
423  assert(!is_err_str("9:1:-9"));
424  assert(!is_err_str("9:1:0"));
425  assert(!is_err_str("9:1:9"));
426  assert(!is_err_str("{-9:1:-9}"));
427  assert(!is_err_str("{-9:1:0}"));
428  assert(!is_err_str("{-9:1:9}"));
429  assert(!is_err_str("{0:1:-9}"));
430  assert(!is_err_str("{0:1:0}"));
431  assert(!is_err_str("{0:1:9}"));
432  assert(!is_err_str("{9:1:-9}"));
433  assert(!is_err_str("{9:1:0}"));
434  assert(!is_err_str("{9:1:9}"));
435  assert(!is_err_str("1,2,3"));
436  assert(!is_err_str("1,2,{1,2}"));
437  assert(!is_err_str("1,2,{1:2}"));
438  assert(!is_err_str("1:2,{1:2}"));
439  assert(!is_err_str("1:2:1,2"));
440  assert(!is_err_str(" 1 : +2 , { -1 : \r 2\n:2}\n"));
441  /* Illegal strings */
442  assert(is_err_str(""));
443  assert(is_err_str("{}"));
444  assert(is_err_str("+ 1"));
445  assert(is_err_str("+ +1"));
446  assert(is_err_str("+ -1"));
447  assert(is_err_str("1:"));
448  assert(is_err_str("1:2:"));
449  assert(is_err_str("1:2,"));
450  assert(is_err_str("1:-2"));
451  assert(is_err_str("1:0"));
452  assert(is_err_str("1:-2:4"));
453  assert(is_err_str("1:0:4"));
454  assert(is_err_str("1:1:1:"));
455  assert(is_err_str("1:1:1:1"));
456  assert(is_err_str("1:1:1:1,1"));
457  assert(is_err_str("{1:2:3},"));
458  assert(is_err_str("{1:2:3}:"));
459  assert(is_err_str("{1:2:3}:2:"));
460  assert(is_err_str("{:2:3}"));
461  assert(is_err_str("{{2:3}}"));
462  assert(is_err_str("{2:3}}"));
463  assert(is_err_str("2:3}"));
464  assert(is_err_str("{1:2:3"));
465  assert(is_err_str("{1,2,}"));
466  assert(is_err_str("{1:-2}"));
467  assert(is_err_str("{1:0}"));
468  assert(is_err_str("{1:-2:4}"));
469  assert(is_err_str("{1:0:4}"));
470  /* Comparison */
471  assert(is_equal_str("{1},{2},{3},{4}", "1,2,3,4"));
472  assert(is_equal_str("{1:4:1}", "{1,2,3,4}"));
473  assert(is_equal_str("{1:4}", "{1,2,3,4}"));
474  assert(is_equal_str("1:2,3:2", "1,2,3,4"));
475  assert(is_equal_str("{1:2},3:2", "{1,2},3,4"));
476  assert(is_equal_str("{1:1:4},{2:1:-4},{3:1:0},{4:1}", "1,2,3,4"));
477  assert(is_equal_str("{3:4:-1}", "{3,2,1,0}"));
478  assert(is_equal_str("3:4:-1,-1", "3,2,1,0,-1"));
479  assert(is_equal_str("{1:2:3}:1", "{1,4}"));
480  assert(is_equal_str("{1:2:3}:3", "{1,4},{2,5},{3,6}"));
481  assert(is_equal_str("{1:2:3}:3:2", "{1,4},{3,6},{5,8}"));
482  assert(is_equal_str("{1:2:3}:3:-2", "{1,4},{-1,2},{-3,0}"));
483  assert(is_equal_str("{1:2:3}:3:-2,1", "{1,4},{-1,2},{-3,0},1"));
484  assert(is_equal_str("{-2:3:-2}:2:-4", "{-2,-4,-6},{-6,-8,-10}"));
485 }
486 
487 #endif
parse_list
static ABTU_ret_err int parse_list(alloc_list *p_alloc_list, const char *affinity_str, ABTD_affinity_list **pp_affinity_list)
Definition: abtd_affinity_parser.c:284
ABTU_realloc
static ABTU_ret_err int ABTU_realloc(size_t old_size, size_t new_size, void **p_ptr)
Definition: abtu.h:257
ALLOC_HEADER_SIZE
#define ALLOC_HEADER_SIZE
Definition: abtd_affinity_parser.c:15
alloc_header
Definition: abtd_affinity_parser.c:11
MAX_NUM_ELEMS
#define MAX_NUM_ELEMS
Definition: abtd_affinity_parser.c:9
alloc_list::p_head
alloc_header * p_head
Definition: abtd_affinity_parser.c:20
alloc_header
struct alloc_header alloc_header
abti.h
alloc_header::p_next
struct alloc_header * p_next
Definition: abtd_affinity_parser.c:13
ABTU_calloc
static ABTU_ret_err int ABTU_calloc(size_t num, size_t size, void **p_ptr)
Definition: abtu.h:244
ABT_SUCCESS
#define ABT_SUCCESS
Error code: the routine returns successfully.
Definition: abt.h:92
ABTU_ret_err
#define ABTU_ret_err
Definition: abtu.h:155
consume_symbol
static int consume_symbol(const char *str, uint32_t *p_index, char symbol)
Definition: abtd_affinity_parser.c:209
id_list_create
static ABTU_ret_err int id_list_create(alloc_list *p_alloc_list, ABTD_affinity_id_list **pp_id_list)
Definition: abtd_affinity_parser.c:90
list_free_all
static void list_free_all(void *p_head)
Definition: abtd_affinity_parser.c:80
alloc_list::p_tail
alloc_header * p_tail
Definition: abtd_affinity_parser.c:21
list_realloc
static ABTU_ret_err int list_realloc(alloc_list *p_alloc_list, size_t old_size, size_t new_size, void **p_ptr)
Definition: abtd_affinity_parser.c:47
is_whitespace
static int is_whitespace(char c)
Definition: abtd_affinity_parser.c:152
ABTU_free
static void ABTU_free(void *ptr)
Definition: abtu.h:228
list_add
static ABTU_ret_err int list_add(alloc_list *p_alloc_list, ABTD_affinity_list *p_list, ABTD_affinity_id_list *p_base, uint32_t num, int stride)
Definition: abtd_affinity_parser.c:121
consume_int
static int consume_int(const char *str, uint32_t *p_index, int *p_val)
Definition: abtd_affinity_parser.c:158
ABT_ERR_OTHER
#define ABT_ERR_OTHER
Error code: other error.
Definition: abt.h:109
alloc_header::p_prev
struct alloc_header * p_prev
Definition: abtd_affinity_parser.c:12
alloc_list
Definition: abtd_affinity_parser.c:19
id_list_add
static ABTU_ret_err int id_list_add(alloc_list *p_alloc_list, ABTD_affinity_id_list *p_id_list, int id, uint32_t num, int stride)
Definition: abtd_affinity_parser.c:97
list_calloc
static ABTU_ret_err int list_calloc(alloc_list *p_alloc_list, size_t size, void **p_ptr)
Definition: abtd_affinity_parser.c:26
parse_es_id_list
static ABTU_ret_err int parse_es_id_list(alloc_list *p_alloc_list, const char *affinity_str, uint32_t *p_index, ABTD_affinity_id_list **pp_affinity_id_list)
Definition: abtd_affinity_parser.c:228
list_create
static ABTU_ret_err int list_create(alloc_list *p_alloc_list, ABTD_affinity_list **pp_affinity_list)
Definition: abtd_affinity_parser.c:114
consume_pint
static int consume_pint(const char *str, uint32_t *p_index, int *p_val)
Definition: abtd_affinity_parser.c:195