blob: 1b8bfa5ff33e906635bb428b11e425cb88d9324e [file] [log] [blame]
Radek Krejci5aeea3a2018-09-05 13:29:36 +02001/**
2 * @file set.c
3 * @author Radek Krejci <rkrejci@cesnet.cz>
4 * @brief Generic set routines implementations
5 *
6 * Copyright (c) 2015 - 2018 CESNET, z.s.p.o.
7 *
8 * This source code is licensed under BSD 3-Clause License (the "License").
9 * You may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * https://opensource.org/licenses/BSD-3-Clause
13 */
14
Radek Krejci5aeea3a2018-09-05 13:29:36 +020015#include "common.h"
16
Michal Vasko69730152020-10-09 16:30:07 +020017#include <stdint.h>
Radek Krejcie7b95092019-05-15 11:03:07 +020018#include <stdlib.h>
19#include <string.h>
20
21#include "log.h"
22#include "set.h"
23
Jan Kundrátc53a7ec2021-12-09 16:01:19 +010024LIBYANG_API_DEF LY_ERR
Radek Krejciba03a5a2020-08-27 14:40:41 +020025ly_set_new(struct ly_set **set_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +020026{
Radek Krejciba03a5a2020-08-27 14:40:41 +020027 LY_CHECK_ARG_RET(NULL, set_p, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020028
Radek Krejciba03a5a2020-08-27 14:40:41 +020029 *set_p = calloc(1, sizeof **set_p);
30 LY_CHECK_ERR_RET(!(*set_p), LOGMEM(NULL), LY_EMEM);
31
32 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020033}
34
Jan Kundrátc53a7ec2021-12-09 16:01:19 +010035LIBYANG_API_DEF void
Radek Krejcia40f21b2018-09-18 10:42:08 +020036ly_set_clean(struct ly_set *set, void (*destructor)(void *obj))
37{
Michal Vasko52927e22020-03-16 17:26:14 +010038 uint32_t u;
Radek Krejcia40f21b2018-09-18 10:42:08 +020039
Radek Krejci0bfec162019-05-02 09:54:25 +020040 if (!set) {
41 return;
42 }
Radek Krejcia40f21b2018-09-18 10:42:08 +020043
44 if (destructor) {
45 for (u = 0; u < set->count; ++u) {
46 destructor(set->objs[u]);
47 }
48 }
49 set->count = 0;
50}
51
Jan Kundrátc53a7ec2021-12-09 16:01:19 +010052LIBYANG_API_DEF void
Radek Krejcia40f21b2018-09-18 10:42:08 +020053ly_set_erase(struct ly_set *set, void (*destructor)(void *obj))
Radek Krejci5aeea3a2018-09-05 13:29:36 +020054{
Radek Krejci0bfec162019-05-02 09:54:25 +020055 if (!set) {
56 return;
57 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +020058
Radek Krejcia40f21b2018-09-18 10:42:08 +020059 ly_set_clean(set, destructor);
60
Radek Krejci5aeea3a2018-09-05 13:29:36 +020061 free(set->objs);
Radek Krejcia40f21b2018-09-18 10:42:08 +020062 set->size = 0;
63 set->objs = NULL;
64}
65
Jan Kundrátc53a7ec2021-12-09 16:01:19 +010066LIBYANG_API_DEF void
Radek Krejcia40f21b2018-09-18 10:42:08 +020067ly_set_free(struct ly_set *set, void (*destructor)(void *obj))
68{
Radek Krejci0bfec162019-05-02 09:54:25 +020069 if (!set) {
70 return;
71 }
Radek Krejcia40f21b2018-09-18 10:42:08 +020072
73 ly_set_erase(set, destructor);
74
Radek Krejci5aeea3a2018-09-05 13:29:36 +020075 free(set);
76}
77
Jan Kundrátc53a7ec2021-12-09 16:01:19 +010078LIBYANG_API_DEF ly_bool
Michal Vasko193dacd2022-10-13 08:43:05 +020079ly_set_contains(const struct ly_set *set, const void *object, uint32_t *index_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +020080{
Radek Krejciba03a5a2020-08-27 14:40:41 +020081 LY_CHECK_ARG_RET(NULL, set, 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020082
Radek Krejciba03a5a2020-08-27 14:40:41 +020083 for (uint32_t i = 0; i < set->count; i++) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +020084 if (set->objs[i] == object) {
85 /* object found */
Radek Krejciba03a5a2020-08-27 14:40:41 +020086 if (index_p) {
87 *index_p = i;
88 }
89 return 1;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020090 }
91 }
92
93 /* object not found */
Radek Krejciba03a5a2020-08-27 14:40:41 +020094 return 0;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020095}
96
Jan Kundrátc53a7ec2021-12-09 16:01:19 +010097LIBYANG_API_DEF LY_ERR
Michal Vasko193dacd2022-10-13 08:43:05 +020098ly_set_dup(const struct ly_set *set, void *(*duplicator)(const void *obj), struct ly_set **newset_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +020099{
Radek Krejciba03a5a2020-08-27 14:40:41 +0200100 struct ly_set *newset;
Michal Vasko52927e22020-03-16 17:26:14 +0100101 uint32_t u;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200102
Radek Krejci8678fa42020-08-18 16:07:28 +0200103 LY_CHECK_ARG_RET(NULL, set, newset_p, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200104
Michal Vasko08e9b112021-06-11 15:41:17 +0200105 newset = calloc(1, sizeof *newset);
Radek Krejciba03a5a2020-08-27 14:40:41 +0200106 LY_CHECK_ERR_RET(!newset, LOGMEM(NULL), LY_EMEM);
Michal Vasko08e9b112021-06-11 15:41:17 +0200107 if (!set->count) {
108 *newset_p = newset;
109 return LY_SUCCESS;
110 }
111
Radek Krejciba03a5a2020-08-27 14:40:41 +0200112 newset->count = set->count;
113 newset->size = set->count; /* optimize the size */
114 newset->objs = malloc(newset->size * sizeof *(newset->objs));
115 LY_CHECK_ERR_RET(!newset->objs, LOGMEM(NULL); free(newset), LY_EMEM);
Radek Krejci2f2bd902018-09-18 17:04:24 +0200116 if (duplicator) {
117 for (u = 0; u < set->count; ++u) {
Radek Krejciba03a5a2020-08-27 14:40:41 +0200118 newset->objs[u] = duplicator(set->objs[u]);
Radek Krejci2f2bd902018-09-18 17:04:24 +0200119 }
120 } else {
Radek Krejciba03a5a2020-08-27 14:40:41 +0200121 memcpy(newset->objs, set->objs, newset->size * sizeof *(newset->objs));
Radek Krejci2f2bd902018-09-18 17:04:24 +0200122 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200123
Radek Krejciba03a5a2020-08-27 14:40:41 +0200124 *newset_p = newset;
125 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200126}
127
Jan Kundrátc53a7ec2021-12-09 16:01:19 +0100128LIBYANG_API_DEF LY_ERR
Michal Vasko193dacd2022-10-13 08:43:05 +0200129ly_set_add(struct ly_set *set, const void *object, ly_bool list, uint32_t *index_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200130{
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200131 void **new;
132
Radek Krejciba03a5a2020-08-27 14:40:41 +0200133 LY_CHECK_ARG_RET(NULL, set, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200134
Radek Krejci3d92e442020-10-12 12:48:13 +0200135 if (!list) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200136 /* search for duplication */
Radek Krejciba03a5a2020-08-27 14:40:41 +0200137 for (uint32_t i = 0; i < set->count; i++) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200138 if (set->objs[i] == object) {
139 /* already in set */
Radek Krejciba03a5a2020-08-27 14:40:41 +0200140 if (index_p) {
141 *index_p = i;
142 }
143 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200144 }
145 }
146 }
147
Michal Vaskob34480a2018-09-17 10:34:45 +0200148 if (set->size == set->count) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100149#define SET_SIZE_STEP 8
150 new = realloc(set->objs, (set->size + SET_SIZE_STEP) * sizeof *(set->objs));
Radek Krejciba03a5a2020-08-27 14:40:41 +0200151 LY_CHECK_ERR_RET(!new, LOGMEM(NULL), LY_EMEM);
Radek Krejcif13b87b2020-12-01 22:02:17 +0100152 set->size += SET_SIZE_STEP;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200153 set->objs = new;
Radek Krejcif13b87b2020-12-01 22:02:17 +0100154#undef SET_SIZE_STEP
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200155 }
156
Radek Krejciba03a5a2020-08-27 14:40:41 +0200157 if (index_p) {
158 *index_p = set->count;
159 }
Michal Vasko193dacd2022-10-13 08:43:05 +0200160 set->objs[set->count++] = (void *)object;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200161
Radek Krejciba03a5a2020-08-27 14:40:41 +0200162 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200163}
164
Jan Kundrátc53a7ec2021-12-09 16:01:19 +0100165LIBYANG_API_DEF LY_ERR
Michal Vasko193dacd2022-10-13 08:43:05 +0200166ly_set_merge(struct ly_set *trg, const struct ly_set *src, ly_bool list, void *(*duplicator)(const void *obj))
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200167{
Radek Krejciba03a5a2020-08-27 14:40:41 +0200168 uint32_t u;
Radek Krejci2f2bd902018-09-18 17:04:24 +0200169 void *obj;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200170
Radek Krejciba03a5a2020-08-27 14:40:41 +0200171 LY_CHECK_ARG_RET(NULL, trg, LY_EINVAL);
172
173 if (!src) {
174 /* nothing to do */
175 return LY_SUCCESS;
176 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200177
Radek Krejci2f2bd902018-09-18 17:04:24 +0200178 for (u = 0; u < src->count; ++u) {
179 if (duplicator) {
180 obj = duplicator(src->objs[u]);
181 } else {
182 obj = src->objs[u];
183 }
Radek Krejci52ca92d2020-10-12 16:51:22 +0200184 LY_CHECK_RET(ly_set_add(trg, obj, list, NULL));
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200185 }
186
Radek Krejciba03a5a2020-08-27 14:40:41 +0200187 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200188}
189
Jan Kundrátc53a7ec2021-12-09 16:01:19 +0100190LIBYANG_API_DEF LY_ERR
Michal Vasko52927e22020-03-16 17:26:14 +0100191ly_set_rm_index(struct ly_set *set, uint32_t index, void (*destructor)(void *obj))
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200192{
Radek Krejci13246392018-09-07 14:57:41 +0200193 LY_CHECK_ARG_RET(NULL, set, LY_EINVAL);
Radek Krejci820d2262018-09-20 12:15:31 +0200194 LY_CHECK_ERR_RET(index >= set->count, LOGARG(NULL, index), LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200195
Radek Krejci820d2262018-09-20 12:15:31 +0200196 if (destructor) {
197 destructor(set->objs[index]);
198 }
Michal Vaskob34480a2018-09-17 10:34:45 +0200199 if (index == set->count - 1) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200200 /* removing last item in set */
201 set->objs[index] = NULL;
202 } else {
203 /* removing item somewhere in a middle, so put there the last item */
Michal Vaskob34480a2018-09-17 10:34:45 +0200204 set->objs[index] = set->objs[set->count - 1];
205 set->objs[set->count - 1] = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200206 }
Michal Vaskob34480a2018-09-17 10:34:45 +0200207 set->count--;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200208
209 return LY_SUCCESS;
210}
211
Jan Kundrátc53a7ec2021-12-09 16:01:19 +0100212LIBYANG_API_DEF LY_ERR
Radek Krejci820d2262018-09-20 12:15:31 +0200213ly_set_rm(struct ly_set *set, void *object, void (*destructor)(void *obj))
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200214{
Michal Vasko52927e22020-03-16 17:26:14 +0100215 uint32_t i;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200216
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200217 LY_CHECK_ARG_RET(NULL, set, object, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200218
219 /* get index */
Michal Vaskob34480a2018-09-17 10:34:45 +0200220 for (i = 0; i < set->count; i++) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200221 if (set->objs[i] == object) {
222 break;
223 }
224 }
Radek Krejci56616162018-09-18 14:11:00 +0200225 LY_CHECK_ERR_RET((i == set->count), LOGARG(NULL, object), LY_EINVAL); /* object is not in set */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200226
Radek Krejci820d2262018-09-20 12:15:31 +0200227 return ly_set_rm_index(set, i, destructor);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200228}
Michal Vasko413af592021-12-13 11:50:51 +0100229
230LY_ERR
231ly_set_rm_index_ordered(struct ly_set *set, uint32_t index, void (*destructor)(void *obj))
232{
233 if (destructor) {
234 destructor(set->objs[index]);
235 }
236 set->count--;
237 if (index == set->count) {
238 /* removing last item in set */
239 set->objs[index] = NULL;
240 } else {
241 /* removing item somewhere in a middle, move following items */
242 memmove(set->objs + index, set->objs + index + 1, (set->count - index) * sizeof *set->objs);
243 set->objs[set->count] = NULL;
244 }
245
246 return LY_SUCCESS;
247}