include/shared/array_list.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#ifndef SHARED_ARRAY_LIST_H_
#define SHARED_ARRAY_LIST_H_

#include "kern/common.h"
#include "kern/mem.h"

#define ALLOC kalloc
#define FREE kfree

#define array_list_t(type) array_list_##type##_t
#define array_list_new(type) array_list_##type##_new
#define array_list_length(type) array_list_##type##_length
#define array_list_reserve(type) array_list_##type##_reserve
#define array_list_add(type) array_list_##type##_add
#define array_list_remove(type) array_list_##type##remove
#define array_list_ref(type) array_list_##type##_get
#define array_list_free(type) array_list_##type##_free

#define array_list_foreach(ar, val)            \
  typeof((ar)->elements[0]) val;               \
  if ((ar)->size > 0) val = (ar)->elements[0]; \
  for (size_t _idx_ = 0; _idx_ < (ar)->size;   \
       val = (++_idx_) >= (ar)->size ? val : (ar)->elements[_idx_])

#define ARRAY_LIST_DECL(type)                                                \
  typedef struct {                                                           \
    size_t reserved;                                                         \
    size_t size;                                                             \
    type* elements;                                                          \
  } array_list_t(type);                                                      \
  size_t array_list_length(type)(const array_list_t(type)*);                 \
  array_list_t(type) * array_list_new(type)();                               \
  bool array_list_reserve(type)(array_list_t(type)*, size_t len);            \
  bool array_list_add(type)(array_list_t(type)*, type val);                  \
  bool array_list_remove(type)(array_list_t(type)*, size_t idx, type * out); \
  type* array_list_ref(type)(array_list_t(type)*, size_t idx);               \
  void array_list_free(type)(array_list_t(type)*);

#define ARRAY_LIST_IMPL(type)                                            \
  array_list_t(type) * array_list_new(type)()                            \
  {                                                                      \
    array_list_t(type)* ret = ALLOC(sizeof(array_list_t(type)));         \
    ret->size = 0;                                                       \
    ret->reserved = 0;                                                   \
    ret->elements = NULL;                                                \
    return ret;                                                          \
  }                                                                      \
  size_t array_list_length(type)(const array_list_t(type) * lst)         \
  {                                                                      \
    return lst->size;                                                    \
  }                                                                      \
  bool array_list_reserve(type)(array_list_t(type) * lst, size_t newlen) \
  {                                                                      \
    if (lst->reserved < newlen) {                                        \
      type* new_arr = ALLOC(sizeof(type) * newlen);                      \
      if (!new_arr) {                                                    \
        return 0;                                                        \
      }                                                                  \
      for (size_t i = 0; i < lst->size; ++i) {                           \
        new_arr[i] = lst->elements[i];                                   \
      }                                                                  \
      FREE(lst->elements);                                               \
      lst->elements = new_arr;                                           \
      lst->reserved = newlen;                                            \
    }                                                                    \
    return 1;                                                            \
  }                                                                      \
  bool array_list_add(type)(array_list_t(type) * lst, type v)            \
  {                                                                      \
    if (lst->size == lst->reserved) {                                    \
      if (!array_list_reserve(type)(                                     \
              lst, lst->reserved == 0 ? 4 : lst->reserved * 2)) {        \
        return 0;                                                        \
      }                                                                  \
    }                                                                    \
    lst->elements[lst->size++] = v;                                      \
    return 1;                                                            \
  }                                                                      \
  bool array_list_remove(type)(                                          \
      array_list_t(type) * lst, size_t idx, type * out)                  \
  {                                                                      \
    if (idx >= lst->size) {                                              \
      return 0;                                                          \
    }                                                                    \
    if (out) *out = lst->elements[idx];                                  \
    for (size_t i = idx; i < lst->size - 1; ++i) {                       \
      lst->elements[i] = lst->elements[i + 1];                           \
    }                                                                    \
    lst->size--;                                                         \
    return 1;                                                            \
  }                                                                      \
  type* array_list_ref(type)(array_list_t(type) * lst, size_t idx)       \
  {                                                                      \
    if (idx >= lst->size) {                                              \
      return NULL;                                                       \
    }                                                                    \
    return &lst->elements[idx];                                          \
  }                                                                      \
  void array_list_free(type)(array_list_t(type) * lst)                   \
  {                                                                      \
    FREE(lst->elements);                                                 \
    FREE(lst);                                                           \
  }

#endif /* SHARED_ARRAY_LIST_H_ */