Changeset 03daabd in mainline
- Timestamp:
- 2019-10-06T19:47:36Z (5 years ago)
- Children:
- 5be6361
- Parents:
- 9559cf8
- git-author:
- Matthieu Riolo <matthieu.riolo@…> (2019-09-17 07:50:03)
- git-committer:
- Matthieu Riolo <matthieu.riolo@…> (2019-10-06 19:47:36)
- Location:
- uspace
- Files:
-
- 1 added
- 1 deleted
- 9 edited
- 2 moved
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/Makefile
r9559cf8 r03daabd 145 145 generic/loader.c \ 146 146 generic/getopt.c \ 147 generic/adt/array.c \ 147 148 generic/adt/checksum.c \ 148 149 generic/adt/circ_buf.c \ 149 generic/adt/dyn_array.c \150 150 generic/adt/list.c \ 151 151 generic/adt/hash_table.c \ … … 193 193 194 194 TEST_SOURCES = \ 195 test/adt/array.c \ 195 196 test/adt/circ_buf.c \ 196 test/adt/dyn_array.c \197 197 test/adt/odict.c \ 198 198 test/cap.c \ -
uspace/lib/c/generic/adt/array.c
r9559cf8 r03daabd 34 34 * Implementation of dynamic array that grows or shrinks based upon no. of 35 35 * items it contains. Non-negligible part of implementation is in @ref 36 * dyn_array.h because of type genericity.36 * array.h because of type genericity. 37 37 */ 38 38 39 39 #include <assert.h> 40 40 #include <errno.h> 41 #include <adt/ dyn_array.h>41 #include <adt/array.h> 42 42 #include <macros.h> 43 43 #include <mem.h> 44 44 #include <stdlib.h> 45 45 46 static errno_t dyn_array_realloc(dyn_array_t *da, size_t capacity)46 static errno_t array_realloc(array_t *da, size_t capacity) 47 47 { 48 48 if (capacity == da->capacity) { … … 58 58 } 59 59 60 void dyn_array_destroy(dyn_array_t *da)60 void array_destroy(array_t *da) 61 61 { 62 dyn_array_clear(da);62 array_clear(da); 63 63 free(da->_data); 64 64 da->capacity = 0; … … 66 66 67 67 /** Remove item at given position, shift rest of array */ 68 void dyn_array_remove(dyn_array_t *da, size_t index)68 void array_remove(array_t *da, size_t index) 69 69 { 70 70 assert(index < da->size); 71 _ dyn_array_unshift(da, index, 1);72 errno_t rc = dyn_array_reserve(da, da->size);71 _array_unshift(da, index, 1); 72 errno_t rc = array_reserve(da, da->size); 73 73 assert(rc == EOK); 74 74 } 75 75 76 76 /** Clear dynamic array (empty) */ 77 void dyn_array_clear(dyn_array_t *da)77 void array_clear(array_t *da) 78 78 { 79 79 da->size = 0; … … 86 86 * @param[in] end index behind last item to remove 87 87 */ 88 void dyn_array_clear_range(dyn_array_t *da, size_t begin, size_t end)88 void array_clear_range(array_t *da, size_t begin, size_t end) 89 89 { 90 90 assert(begin < da->size); 91 91 assert(end <= da->size); 92 92 93 _ dyn_array_unshift(da, begin, end - begin);94 errno_t rc = dyn_array_reserve(da, da->size);93 _array_unshift(da, begin, end - begin); 94 errno_t rc = array_reserve(da, da->size); 95 95 assert(rc == EOK); 96 96 } … … 104 104 * @return ENOMEM when allocation fails 105 105 */ 106 errno_t dyn_array_concat(dyn_array_t *da1, dyn_array_t *da2)106 errno_t array_concat(array_t *da1, array_t *da2) 107 107 { 108 108 assert(da1->_item_size == da2->_item_size); 109 109 110 errno_t rc = dyn_array_reserve(da1, da1->size + da2->size);110 errno_t rc = array_reserve(da1, da1->size + da2->size); 111 111 if (rc != EOK) { 112 112 return rc; … … 129 129 * @return ENOMEM 130 130 */ 131 errno_t dyn_array_reserve(dyn_array_t *da, size_t capacity)131 errno_t array_reserve(array_t *da, size_t capacity) 132 132 { 133 133 const size_t factor = 2; … … 141 141 } 142 142 143 return dyn_array_realloc(da, new_capacity);143 return array_realloc(da, new_capacity); 144 144 } 145 145 146 void _ dyn_array_initialize(dyn_array_t *da, size_t item_size)146 void _array_initialize(array_t *da, size_t item_size) 147 147 { 148 148 da->_item_size = item_size; … … 161 161 * @param[in] offset shift in no. of items 162 162 */ 163 void _ dyn_array_shift(dyn_array_t *da, size_t index, size_t offset)163 void _array_shift(array_t *da, size_t index, size_t offset) 164 164 { 165 165 assert(da->capacity >= da->size + offset); … … 180 180 * @param[in] offset shift in no. of items 181 181 */ 182 void _ dyn_array_unshift(dyn_array_t *da, size_t index, size_t offset)182 void _array_unshift(array_t *da, size_t index, size_t offset) 183 183 { 184 184 void *src = da->_data + (index + offset) * da->_item_size; -
uspace/lib/c/include/adt/array.h
r9559cf8 r03daabd 33 33 */ 34 34 35 #ifndef LIBC_ DYN_ARRAY_H_36 #define LIBC_ DYN_ARRAY_H_35 #ifndef LIBC_ARRAY_H_ 36 #define LIBC_ARRAY_H_ 37 37 38 38 #include <errno.h> … … 50 50 /** No. of items in the array */ 51 51 size_t size; 52 } dyn_array_t;52 } array_t; 53 53 54 54 /** Initialize dynamic array … … 58 58 * @return void 59 59 */ 60 #define dyn_array_initialize(dyn_array, type) \61 _ dyn_array_initialize((dyn_array), sizeof(type))60 #define array_initialize(array, type) \ 61 _array_initialize((array), sizeof(type)) 62 62 63 63 /** Dynamic array accessor … … 65 65 * @return lvalue for the given item 66 66 */ 67 #define dyn_array_at(dyn_array, type, index) \68 (*((type *) ( dyn_array)->_data + index))67 #define array_at(array, type, index) \ 68 (*((type *) (array)->_data + index)) 69 69 70 70 /** Access last element … … 72 72 * @return lvalue for the last item 73 73 */ 74 #define dyn_array_last(dyn_array, type) \75 (*((type *) ( dyn_array)->_data + ((dyn_array)->size - 1)))74 #define array_last(array, type) \ 75 (*((type *) (array)->_data + ((array)->size - 1))) 76 76 77 77 /** Insert item at given position, shift rest of array … … 80 80 * @return ENOMEM on failure 81 81 */ 82 #define dyn_array_insert(dyn_array, type, index, value) \83 ({ 84 size_t _index = (index); 85 dyn_array_t *_da = (dyn_array);\86 errno_t rc = dyn_array_reserve(_da, _da->size + 1);\87 if (!rc) { 88 _ dyn_array_shift(_da, _index, 1);\89 dyn_array_at(_da, type, _index) = (value); \90 } 91 rc; 82 #define array_insert(array, type, index, value) \ 83 ({ \ 84 size_t _index = (index); \ 85 array_t *_da = (array); \ 86 errno_t rc = array_reserve(_da, _da->size + 1); \ 87 if (!rc) { \ 88 _array_shift(_da, _index, 1); \ 89 array_at(_da, type, _index) = (value); \ 90 } \ 91 rc; \ 92 92 }) 93 93 … … 97 97 * @return ENOMEM on failure 98 98 */ 99 #define dyn_array_append(dyn_array, type, value) \100 dyn_array_insert(dyn_array, type, (dyn_array)->size, (value))99 #define array_append(array, type, value) \ 100 array_insert(array, type, (array)->size, (value)) 101 101 102 102 /** Dynamic array iteration 103 103 * 104 * @param[in] dyn_array dyn_array_t (not pointer)105 * @param[in] it 106 * 104 * @param[in] array array_t (not pointer) 105 * @param[in] it name of variable used as iterator, it's pointer 106 * to @p type 107 107 */ 108 #define dyn_array_foreach(dyn_array, type, it) \109 for (type *it = NULL; it == NULL; it = (type *)1) 110 for (type *_it = (type *)( dyn_array)._data; \111 it = _it, _it != ((type *)( dyn_array)._data + (dyn_array).size);\108 #define array_foreach(array, type, it) \ 109 for (type *it = NULL; it == NULL; it = (type *)1) \ 110 for (type *_it = (type *)(array)._data; \ 111 it = _it, _it != ((type *)(array)._data + (array).size); \ 112 112 ++_it) 113 113 114 114 /** Find first occurence of value 115 115 * 116 * @param[in] dyn_array dyn_array_t *116 * @param[in] array array_t * 117 117 * @param[in] value value to search for 118 118 * 119 119 * @return index of found value or size of array when no found 120 120 */ 121 #define dyn_array_find(dyn_array, type, value) \122 ({ 123 size_t _result = ( dyn_array)->size; \124 dyn_array_foreach(*(dyn_array), type, _it) {\121 #define array_find(array, type, value) \ 122 ({ \ 123 size_t _result = (array)->size; \ 124 array_foreach(*(array), type, _it) { \ 125 125 if (*_it == value) { \ 126 _result = _it - (type *)( dyn_array)->_data;\127 break; \126 _result = _it - (type *)(array)->_data; \ 127 break; \ 128 128 } \ 129 } 130 _result; 129 } \ 130 _result; \ 131 131 }) 132 132 133 extern void dyn_array_destroy(dyn_array_t *);134 extern void dyn_array_remove(dyn_array_t *, size_t);135 void dyn_array_clear(dyn_array_t *);136 void dyn_array_clear_range(dyn_array_t *, size_t, size_t);137 extern errno_t dyn_array_concat(dyn_array_t *, dyn_array_t *);138 extern errno_t dyn_array_reserve(dyn_array_t *, size_t);133 extern void array_destroy(array_t *); 134 extern void array_remove(array_t *, size_t); 135 void array_clear(array_t *); 136 void array_clear_range(array_t *, size_t, size_t); 137 extern errno_t array_concat(array_t *, array_t *); 138 extern errno_t array_reserve(array_t *, size_t); 139 139 140 extern void _ dyn_array_initialize(dyn_array_t *, size_t);141 extern void _ dyn_array_shift(dyn_array_t *, size_t, size_t);142 extern void _ dyn_array_unshift(dyn_array_t *, size_t, size_t);140 extern void _array_initialize(array_t *, size_t); 141 extern void _array_shift(array_t *, size_t, size_t); 142 extern void _array_unshift(array_t *, size_t, size_t); 143 143 144 144 #endif -
uspace/lib/c/test/main.c
r9559cf8 r03daabd 32 32 PCUT_INIT; 33 33 34 PCUT_IMPORT(array); 34 35 PCUT_IMPORT(cap); 35 36 PCUT_IMPORT(casting); 36 37 PCUT_IMPORT(circ_buf); 37 38 PCUT_IMPORT(double_to_str); 38 PCUT_IMPORT(dyn_array);39 39 PCUT_IMPORT(fibril_timer); 40 40 PCUT_IMPORT(getopt); -
uspace/srv/sysman/job.c
r9559cf8 r03daabd 70 70 job->unit = u; 71 71 72 dyn_array_initialize(&job->blocked_jobs, job_t *);72 array_initialize(&job->blocked_jobs, job_t *); 73 73 job->blocking_jobs = 0; 74 74 job->blocking_job_failed = false; … … 120 120 assert(!link_used(&job->job_queue)); 121 121 122 dyn_array_foreach(job->blocked_jobs, job_t *, job_it) {122 array_foreach(job->blocked_jobs, job_t *, job_it) { 123 123 job_del_ref(&(*job_it)); 124 124 } 125 dyn_array_destroy(&job->blocked_jobs);125 array_destroy(&job->blocked_jobs); 126 126 127 127 free(job); … … 257 257 /* First remove references, then clear the array */ 258 258 assert(job->blocked_jobs.size == job->blocked_jobs_count); 259 dyn_array_foreach(job->blocked_jobs, job_t *, job_it) {259 array_foreach(job->blocked_jobs, job_t *, job_it) { 260 260 job_unblock(*job_it, job); 261 261 } 262 dyn_array_clear(&job->blocked_jobs);262 array_clear(&job->blocked_jobs); 263 263 264 264 /* Add reference for event handler */ -
uspace/srv/sysman/job.h
r9559cf8 r03daabd 30 30 #define SYSMAN_JOB_H 31 31 32 #include <adt/ dyn_array.h>32 #include <adt/array.h> 33 33 #include <adt/list.h> 34 34 #include <stdatomic.h> … … 64 64 65 65 /** Jobs that this job is preventing from running */ 66 dyn_array_t blocked_jobs;66 array_t blocked_jobs; 67 67 /** 68 68 * No. of jobs that the job is actually blocking (may differ from size -
uspace/srv/sysman/job_closure.c
r9559cf8 r03daabd 66 66 blocking_job->blocked_jobs_count); 67 67 68 errno_t rc = dyn_array_append(&blocking_job->blocked_jobs, job_t *,68 errno_t rc = array_append(&blocking_job->blocked_jobs, job_t *, 69 69 blocked_job); 70 70 if (rc != EOK) { … … 97 97 goto finish; 98 98 } 99 job_t *first_job = dyn_array_last(closure, job_t *);99 job_t *first_job = array_last(closure, job_t *); 100 100 101 101 job_add_ref(first_job); … … 119 119 120 120 /* Pass job reference to closure and add one for unit */ 121 rc = dyn_array_append(closure, job_t *, created_job);121 rc = array_append(closure, job_t *, created_job); 122 122 if (rc != EOK) { 123 123 goto finish; … … 165 165 166 166 /* Pass job reference to closure and add one for unit */ 167 rc = dyn_array_append(closure, job_t *, created_job);167 rc = array_append(closure, job_t *, created_job); 168 168 if (rc != EOK) { 169 169 goto finish; … … 308 308 } 309 309 310 errno_t rc = dyn_array_append(job_closure, job_t *, main_job);310 errno_t rc = array_append(job_closure, job_t *, main_job); 311 311 if (rc != EOK) { 312 312 return rc; … … 343 343 344 344 if (rc == EOK) { 345 dyn_array_foreach(*job_closure, job_t *, job_it) {345 array_foreach(*job_closure, job_t *, job_it) { 346 346 sysman_log(LVL_DEBUG2, "%s\t%s, refs: %u", __func__, 347 347 unit_name((*job_it)->unit), atomic_load(&(*job_it)->refcnt)); … … 350 350 351 351 /* Clean after ourselves (BFS tag jobs) */ 352 dyn_array_foreach(*job_closure, job_t *, job_it) {352 array_foreach(*job_closure, job_t *, job_it) { 353 353 job_t *j = (*job_it)->unit->bfs_data; 354 354 assert(*job_it == j); -
uspace/srv/sysman/job_closure.h
r9559cf8 r03daabd 30 30 #define SYSMAN_JOB_CLOSURE_H 31 31 32 #include <adt/ dyn_array.h>32 #include <adt/array.h> 33 33 34 34 #include "job.h" … … 36 36 #define CLOSURE_ISOLATE 0x1 37 37 38 typedef dyn_array_t job_closure_t;38 typedef array_t job_closure_t; 39 39 40 40 extern errno_t job_create_closure(job_t *, job_closure_t *, int); -
uspace/srv/sysman/job_queue.c
r9559cf8 r03daabd 110 110 assert(other->merged_into == NULL); 111 111 112 errno_t rc = dyn_array_concat(&trunk->blocked_jobs, &other->blocked_jobs);112 errno_t rc = array_concat(&trunk->blocked_jobs, &other->blocked_jobs); 113 113 if (rc != EOK) { 114 114 return rc; 115 115 } 116 dyn_array_clear(&other->blocked_jobs);116 array_clear(&other->blocked_jobs); 117 117 118 118 // TODO allocate observed object … … 145 145 { 146 146 assert(trunk->blocked_jobs.size >= trunk->blocked_jobs_count); 147 dyn_array_clear_range(&trunk->blocked_jobs,147 array_clear_range(&trunk->blocked_jobs, 148 148 trunk->blocked_jobs_count, trunk->blocked_jobs.size); 149 149 } … … 172 172 173 173 /* Check consistency with existing jobs. */ 174 dyn_array_foreach(*closure, job_t *, job_it) {174 array_foreach(*closure, job_t *, job_it) { 175 175 job_t *job = *job_it; 176 176 job_t *other_job = job->unit->job; … … 214 214 /* Aggregate merged jobs, or rollback any changes in existing jobs */ 215 215 bool finish_merge = (rc == EOK) && !has_error; 216 dyn_array_foreach(*closure, job_t *, job_it) {216 array_foreach(*closure, job_t *, job_it) { 217 217 if ((*job_it)->merged_into == NULL) { 218 218 continue; … … 236 236 * in their blocked_jobs array. 237 237 */ 238 dyn_array_foreach(*closure, job_t *, job_it) {238 array_foreach(*closure, job_t *, job_it) { 239 239 job_t *job = (*job_it); 240 240 if (job->merged_into != NULL) { … … 255 255 256 256 /* We've stolen references from the closure, so erase it */ 257 dyn_array_clear(closure);257 array_clear(closure); 258 258 259 259 return EOK; -
uspace/srv/sysman/sysman.c
r9559cf8 r03daabd 366 366 job_t *job = job_args->job; 367 367 int flags = job_args->flags; 368 dyn_array_t job_closure;369 dyn_array_initialize(&job_closure, job_t *);368 array_t job_closure; 369 array_initialize(&job_closure, job_t *); 370 370 371 371 if (job_args->callback != NULL) { … … 402 402 job_del_ref(&job); 403 403 404 dyn_array_foreach(job_closure, job_t *, closure_job) {404 array_foreach(job_closure, job_t *, closure_job) { 405 405 job_del_ref(&(*closure_job)); 406 406 } 407 dyn_array_destroy(&job_closure);407 array_destroy(&job_closure); 408 408 } 409 409 -
uspace/srv/sysman/test/job_closure.c
r9559cf8 r03daabd 40 40 PCUT_TEST_SUITE(job_closure); 41 41 42 static dyn_array_t exp_closure;43 static dyn_array_t act_closure;42 static array_t exp_closure; 43 static array_t act_closure; 44 44 45 45 static bool same_job(job_t *expected, job_t *actual) … … 49 49 } 50 50 51 static bool same_jobs( dyn_array_t *expected, dyn_array_t *actual)51 static bool same_jobs(array_t *expected, array_t *actual) 52 52 { 53 53 if (expected->size != actual->size) { … … 58 58 59 59 /* Verify expected \subseteq actual (we've compared sizes) */ 60 dyn_array_foreach(*expected, job_t *, it_exp) {60 array_foreach(*expected, job_t *, it_exp) { 61 61 bool found = false; 62 dyn_array_foreach(*actual, job_t *, it_act) {62 array_foreach(*actual, job_t *, it_act) { 63 63 if (same_job(*it_exp, *it_act)) { 64 64 found = true; … … 79 79 { 80 80 bool found = false; 81 dyn_array_foreach(blocking_job->blocked_jobs, job_t *, it) {81 array_foreach(blocking_job->blocked_jobs, job_t *, it) { 82 82 if (*it == blocked_job) { 83 83 found = true; … … 94 94 } 95 95 96 static void dummy_add_closure( dyn_array_t *closure)97 { 98 dyn_array_foreach(*closure, job_t *, it) {96 static void dummy_add_closure(array_t *closure) 97 { 98 array_foreach(*closure, job_t *, it) { 99 99 (*it)->unit->job = *it; 100 100 } 101 101 } 102 102 103 static void destroy_job_closure( dyn_array_t *closure)104 { 105 dyn_array_foreach(*closure, job_t *, it) {103 static void destroy_job_closure(array_t *closure) 104 { 105 array_foreach(*closure, job_t *, it) { 106 106 job_del_ref(&(*it)); 107 107 } … … 113 113 mock_set_units_state(STATE_STOPPED); 114 114 115 dyn_array_initialize(&exp_closure, job_t *);116 errno_t rc = dyn_array_reserve(&exp_closure, MAX_TYPES * MAX_UNITS);115 array_initialize(&exp_closure, job_t *); 116 errno_t rc = array_reserve(&exp_closure, MAX_TYPES * MAX_UNITS); 117 117 assert(rc == EOK); 118 118 119 dyn_array_initialize(&act_closure, job_t *);120 rc = dyn_array_reserve(&act_closure, MAX_TYPES * MAX_UNITS);119 array_initialize(&act_closure, job_t *); 120 rc = array_reserve(&act_closure, MAX_TYPES * MAX_UNITS); 121 121 assert(rc == EOK); 122 122 … … 127 127 { 128 128 destroy_job_closure(&act_closure); 129 dyn_array_destroy(&act_closure);129 array_destroy(&act_closure); 130 130 131 131 destroy_job_closure(&exp_closure); 132 dyn_array_destroy(&exp_closure);132 array_destroy(&exp_closure); 133 133 134 134 mock_destroy_units(); … … 156 156 PCUT_ASSERT_INT_EQUALS(EOK, rc); 157 157 158 dyn_array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED));159 dyn_array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED));160 dyn_array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STARTED));158 array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED)); 159 array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED)); 160 array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STARTED)); 161 161 162 162 dummy_add_closure(&act_closure); … … 188 188 PCUT_ASSERT_INT_EQUALS(EOK, rc); 189 189 190 dyn_array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED));191 dyn_array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED));192 dyn_array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STARTED));190 array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED)); 191 array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED)); 192 array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STARTED)); 193 193 194 194 dummy_add_closure(&act_closure); … … 222 222 PCUT_ASSERT_INT_EQUALS(EOK, rc); 223 223 224 dyn_array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED));225 dyn_array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED));226 dyn_array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STARTED));224 array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED)); 225 array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED)); 226 array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STARTED)); 227 227 228 228 dummy_add_closure(&act_closure); … … 269 269 PCUT_ASSERT_INT_EQUALS(EOK, rc); 270 270 271 dyn_array_append(&exp_closure, job_t *, dummy_job(u0, STATE_STOPPED));272 dyn_array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED));273 dyn_array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED));274 dyn_array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STOPPED));275 dyn_array_append(&exp_closure, job_t *, dummy_job(u4, STATE_STOPPED));276 dyn_array_append(&exp_closure, job_t *, dummy_job(u5, STATE_STOPPED));277 dyn_array_append(&exp_closure, job_t *, dummy_job(u6, STATE_STOPPED));271 array_append(&exp_closure, job_t *, dummy_job(u0, STATE_STOPPED)); 272 array_append(&exp_closure, job_t *, dummy_job(u1, STATE_STARTED)); 273 array_append(&exp_closure, job_t *, dummy_job(u2, STATE_STARTED)); 274 array_append(&exp_closure, job_t *, dummy_job(u3, STATE_STOPPED)); 275 array_append(&exp_closure, job_t *, dummy_job(u4, STATE_STOPPED)); 276 array_append(&exp_closure, job_t *, dummy_job(u5, STATE_STOPPED)); 277 array_append(&exp_closure, job_t *, dummy_job(u6, STATE_STOPPED)); 278 278 279 279 dummy_add_closure(&act_closure);
Note:
See TracChangeset
for help on using the changeset viewer.