1
2 #ifndef _GNU_SOURCE
3 #define _GNU_SOURCE 1
4 #endif
5
6 #include <R.h>
7 #include "processx-types.h"
8 #include "errors.h"
9
processx_vector_init(processx_vector_t * v,size_t size,size_t alloc_size)10 void processx_vector_init(processx_vector_t *v, size_t size, size_t alloc_size) {
11 if (alloc_size < size) alloc_size = size;
12 if (alloc_size == 0) alloc_size = 1;
13 v->stor_begin = (pid_t*) R_alloc(alloc_size, sizeof(pid_t));
14 if (v->stor_begin == 0) {
15 R_THROW_ERROR("cannot allocate processx vector, out of memory");
16 }
17 v->stor_end = v->stor_begin + alloc_size;
18 v->end = v->stor_begin + size;
19 }
20
processx_vector_size(const processx_vector_t * v)21 size_t processx_vector_size(const processx_vector_t *v) {
22 return v->end - v->stor_begin;
23 }
24
processx_vector_reserve(processx_vector_t * v,size_t size)25 void processx_vector_reserve(processx_vector_t *v, size_t size) {
26 size_t actual_size = processx_vector_size(v);
27 size_t alloc_size = v->stor_end - v->stor_begin;
28 pid_t *tmp;
29 if (size <= actual_size) return;
30
31 tmp = (pid_t*) S_realloc( (char*) v->stor_begin, size, alloc_size, sizeof(pid_t));
32 v->stor_begin = tmp;
33 v->stor_end = v->stor_begin + size;
34 v->end = v->stor_begin + actual_size;
35 }
36
processx_vector_clear(processx_vector_t * v)37 void processx_vector_clear(processx_vector_t *v) {
38 v->end = v->stor_begin;
39 }
40
processx_vector_push_back(processx_vector_t * v,pid_t e)41 void processx_vector_push_back(processx_vector_t *v, pid_t e) {
42 /* full, allocate more storage */
43 if (v->stor_end == v->end) {
44 long int new_size = processx_vector_size(v) * 2;
45 if (new_size == 0) { new_size = 1; }
46 processx_vector_reserve(v, new_size);
47 }
48
49 *(v->end) = e;
50 v->end += 1;
51 }
52
53 /**
54 * Find an element in a vector
55 *
56 * @param v The vector.
57 * @param e The element to find.
58 * @param from Start the search from this position.
59 * @param idx If not a NULL pointer, then it is set to the index of the first
60 occurence of `e`, if found. Otherwise not touched.
61 * @return Non-zero if `e` is found, zero otherwise.
62 */
63
processx_vector_find(const processx_vector_t * v,pid_t e,size_t from,size_t * idx)64 int processx_vector_find(const processx_vector_t *v, pid_t e, size_t from, size_t *idx) {
65 size_t size = processx_vector_size(v);
66
67 while (from < size) {
68 if (VECTOR(*v)[from] == e) {
69 if (idx) *idx = from;
70 return 1;
71 }
72 from++;
73 }
74
75 return 0;
76 }
77
78 /**
79 * Find a rooted tree within forest
80 *
81 * @param root The id of the root node.
82 * @param nodes The ids of all nodes.
83 * @param parents The ids of the parent nodes for each node. The length must
84 * match `nodes`.
85 * @param result The result is stored here. `root` is included here as well, as the first
86 * (zeroth) element.
87 */
88
processx_vector_rooted_tree(pid_t root,const processx_vector_t * nodes,const processx_vector_t * parents,processx_vector_t * result)89 void processx_vector_rooted_tree(pid_t root, const processx_vector_t *nodes,
90 const processx_vector_t *parents,
91 processx_vector_t *result) {
92
93 size_t len = processx_vector_size(nodes);
94 size_t done = 0, next_done = 1;
95
96 processx_vector_clear(result);
97 processx_vector_push_back(result, root);
98
99 while (done < next_done) {
100 size_t i;
101 for (i = 0; i < len; i++) {
102 pid_t parent = VECTOR(*parents)[i];
103 if (processx_vector_find(result, parent, done, 0)) {
104 processx_vector_push_back(result, VECTOR(*nodes)[i]);
105 }
106 }
107 done = next_done;
108 next_done = processx_vector_size(result);
109 }
110 }
111