blob: 2249494f644fe34c456b0c9f8e7e4a044356672e [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
Radek Krejcie7b95092019-05-15 11:03:07 +020017#include <stdlib.h>
18#include <string.h>
Michal Vasko52927e22020-03-16 17:26:14 +010019#include <stdint.h>
Radek Krejcie7b95092019-05-15 11:03:07 +020020
21#include "log.h"
22#include "set.h"
23
Radek Krejciba03a5a2020-08-27 14:40:41 +020024API LY_ERR
25ly_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
35API 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
52API void
53ly_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
66API void
67ly_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
Radek Krejci857189e2020-09-01 13:26:36 +020078API ly_bool
Radek Krejciba03a5a2020-08-27 14:40:41 +020079ly_set_contains(const struct ly_set *set, 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
Radek Krejciba03a5a2020-08-27 14:40:41 +020097API LY_ERR
98ly_set_dup(const struct ly_set *set, void *(*duplicator)(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 Krejciba03a5a2020-08-27 14:40:41 +0200103 LY_CHECK_ARG_RET(NULL, set, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200104
Radek Krejciba03a5a2020-08-27 14:40:41 +0200105 newset = malloc(sizeof *newset);
106 LY_CHECK_ERR_RET(!newset, LOGMEM(NULL), LY_EMEM);
107 newset->count = set->count;
108 newset->size = set->count; /* optimize the size */
109 newset->objs = malloc(newset->size * sizeof *(newset->objs));
110 LY_CHECK_ERR_RET(!newset->objs, LOGMEM(NULL); free(newset), LY_EMEM);
Radek Krejci2f2bd902018-09-18 17:04:24 +0200111 if (duplicator) {
112 for (u = 0; u < set->count; ++u) {
Radek Krejciba03a5a2020-08-27 14:40:41 +0200113 newset->objs[u] = duplicator(set->objs[u]);
Radek Krejci2f2bd902018-09-18 17:04:24 +0200114 }
115 } else {
Radek Krejciba03a5a2020-08-27 14:40:41 +0200116 memcpy(newset->objs, set->objs, newset->size * sizeof *(newset->objs));
Radek Krejci2f2bd902018-09-18 17:04:24 +0200117 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200118
Radek Krejciba03a5a2020-08-27 14:40:41 +0200119 *newset_p = newset;
120 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200121}
122
Radek Krejciba03a5a2020-08-27 14:40:41 +0200123API LY_ERR
124ly_set_add(struct ly_set *set, void *object, uint32_t options, uint32_t *index_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200125{
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200126 void **new;
127
Radek Krejciba03a5a2020-08-27 14:40:41 +0200128 LY_CHECK_ARG_RET(NULL, set, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200129
130 if (!(options & LY_SET_OPT_USEASLIST)) {
131 /* search for duplication */
Radek Krejciba03a5a2020-08-27 14:40:41 +0200132 for (uint32_t i = 0; i < set->count; i++) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200133 if (set->objs[i] == object) {
134 /* already in set */
Radek Krejciba03a5a2020-08-27 14:40:41 +0200135 if (index_p) {
136 *index_p = i;
137 }
138 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200139 }
140 }
141 }
142
Michal Vaskob34480a2018-09-17 10:34:45 +0200143 if (set->size == set->count) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200144 new = realloc(set->objs, (set->size + 8) * sizeof *(set->objs));
Radek Krejciba03a5a2020-08-27 14:40:41 +0200145 LY_CHECK_ERR_RET(!new, LOGMEM(NULL), LY_EMEM);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200146 set->size += 8;
147 set->objs = new;
148 }
149
Radek Krejciba03a5a2020-08-27 14:40:41 +0200150 if (index_p) {
151 *index_p = set->count;
152 }
Michal Vaskob34480a2018-09-17 10:34:45 +0200153 set->objs[set->count++] = object;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200154
Radek Krejciba03a5a2020-08-27 14:40:41 +0200155 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200156}
157
Radek Krejciba03a5a2020-08-27 14:40:41 +0200158API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200159ly_set_merge(struct ly_set *trg, struct ly_set *src, uint32_t options, void *(*duplicator)(void *obj))
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200160{
Radek Krejciba03a5a2020-08-27 14:40:41 +0200161 uint32_t u;
Radek Krejci2f2bd902018-09-18 17:04:24 +0200162 void *obj;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200163
Radek Krejciba03a5a2020-08-27 14:40:41 +0200164 LY_CHECK_ARG_RET(NULL, trg, LY_EINVAL);
165
166 if (!src) {
167 /* nothing to do */
168 return LY_SUCCESS;
169 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200170
Radek Krejci2f2bd902018-09-18 17:04:24 +0200171 for (u = 0; u < src->count; ++u) {
172 if (duplicator) {
173 obj = duplicator(src->objs[u]);
174 } else {
175 obj = src->objs[u];
176 }
Radek Krejciba03a5a2020-08-27 14:40:41 +0200177 LY_CHECK_RET(ly_set_add(trg, obj, options, NULL));
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200178 }
179
Radek Krejciba03a5a2020-08-27 14:40:41 +0200180 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200181}
182
183API LY_ERR
Michal Vasko52927e22020-03-16 17:26:14 +0100184ly_set_rm_index(struct ly_set *set, uint32_t index, void (*destructor)(void *obj))
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200185{
Radek Krejci13246392018-09-07 14:57:41 +0200186 LY_CHECK_ARG_RET(NULL, set, LY_EINVAL);
Radek Krejci820d2262018-09-20 12:15:31 +0200187 LY_CHECK_ERR_RET(index >= set->count, LOGARG(NULL, index), LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200188
Radek Krejci820d2262018-09-20 12:15:31 +0200189 if (destructor) {
190 destructor(set->objs[index]);
191 }
Michal Vaskob34480a2018-09-17 10:34:45 +0200192 if (index == set->count - 1) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200193 /* removing last item in set */
194 set->objs[index] = NULL;
195 } else {
196 /* removing item somewhere in a middle, so put there the last item */
Michal Vaskob34480a2018-09-17 10:34:45 +0200197 set->objs[index] = set->objs[set->count - 1];
198 set->objs[set->count - 1] = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200199 }
Michal Vaskob34480a2018-09-17 10:34:45 +0200200 set->count--;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200201
202 return LY_SUCCESS;
203}
204
205API LY_ERR
Radek Krejci820d2262018-09-20 12:15:31 +0200206ly_set_rm(struct ly_set *set, void *object, void (*destructor)(void *obj))
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200207{
Michal Vasko52927e22020-03-16 17:26:14 +0100208 uint32_t i;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200209
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200210 LY_CHECK_ARG_RET(NULL, set, object, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200211
212 /* get index */
Michal Vaskob34480a2018-09-17 10:34:45 +0200213 for (i = 0; i < set->count; i++) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200214 if (set->objs[i] == object) {
215 break;
216 }
217 }
Radek Krejci56616162018-09-18 14:11:00 +0200218 LY_CHECK_ERR_RET((i == set->count), LOGARG(NULL, object), LY_EINVAL); /* object is not in set */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200219
Radek Krejci820d2262018-09-20 12:15:31 +0200220 return ly_set_rm_index(set, i, destructor);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200221}