1 /*
2 * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License").
5 * You may not use this file except in compliance with the License.
6 * A copy of the License is located at
7 *
8 * http://aws.amazon.com/apache2.0
9 *
10 * or in the "license" file accompanying this file. This file is distributed
11 * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
12 * express or implied. See the License for the specific language governing
13 * permissions and limitations under the License.
14 */
15 #include "utils/s2n_blob.h"
16 #include "utils/s2n_mem.h"
17 #include "utils/s2n_result.h"
18 #include "utils/s2n_safety.h"
19 #include "utils/s2n_set.h"
20 #include "utils/s2n_array.h"
21
22 #define S2N_INITIAL_SET_SIZE 16
23
s2n_set_validate(const struct s2n_set * set)24 S2N_RESULT s2n_set_validate(const struct s2n_set *set)
25 {
26 RESULT_ENSURE_REF(set);
27 RESULT_GUARD(s2n_array_validate(set->data));
28 return S2N_RESULT_OK;
29 }
30
31 /* Sets "out" to the index at which the element should be inserted.
32 * Returns an error if the element already exists */
s2n_set_binary_search(struct s2n_set * set,void * element,uint32_t * out)33 static S2N_RESULT s2n_set_binary_search(struct s2n_set *set, void *element, uint32_t* out)
34 {
35 RESULT_GUARD(s2n_set_validate(set));
36 RESULT_ENSURE(S2N_MEM_IS_READABLE(element, set->data->element_size), S2N_ERR_NULL);
37 RESULT_ENSURE_REF(out);
38 struct s2n_array *array = set->data;
39 int (*comparator)(const void*, const void*) = set->comparator;
40
41 uint32_t len = 0;
42 RESULT_GUARD(s2n_array_num_elements(array, &len));
43
44 if (len == 0) {
45 *out = 0;
46 return S2N_RESULT_OK;
47 }
48
49 /* Use 64 bit ints to avoid possibility of overflow */
50 int64_t low = 0;
51 int64_t top = len - 1;
52
53 while (low <= top) {
54 int64_t mid = low + ((top - low) / 2);
55 void* array_element = NULL;
56 RESULT_GUARD(s2n_array_get(array, mid, &array_element));
57 int m = comparator(array_element, element);
58
59 /* the element is already in the set */
60 if (m == 0) {
61 RESULT_BAIL(S2N_ERR_SET_DUPLICATE_VALUE);
62 }
63
64 if (m > 0) {
65 top = mid - 1;
66 } else {
67 low = mid + 1;
68 }
69 }
70
71 *out = low;
72 return S2N_RESULT_OK;
73 }
74
s2n_set_new(uint32_t element_size,int (* comparator)(const void *,const void *))75 struct s2n_set *s2n_set_new(uint32_t element_size, int (*comparator)(const void*, const void*))
76 {
77 PTR_ENSURE_REF(comparator);
78 struct s2n_blob mem = {0};
79 PTR_GUARD_POSIX(s2n_alloc(&mem, sizeof(struct s2n_set)));
80 struct s2n_set *set = (void *) mem.data;
81 *set = (struct s2n_set) {.data = s2n_array_new(element_size), .comparator = comparator};
82 if(set->data == NULL) {
83 PTR_GUARD_POSIX(s2n_free(&mem));
84 return NULL;
85 }
86 return set;
87 }
88
s2n_set_add(struct s2n_set * set,void * element)89 S2N_RESULT s2n_set_add(struct s2n_set *set, void *element)
90 {
91 RESULT_GUARD(s2n_set_validate(set));
92
93 uint32_t idx = 0;
94 RESULT_GUARD(s2n_set_binary_search(set, element, &idx));
95 RESULT_GUARD(s2n_array_insert_and_copy(set->data, idx, element));
96
97 return S2N_RESULT_OK;
98 }
99
s2n_set_get(struct s2n_set * set,uint32_t idx,void ** element)100 S2N_RESULT s2n_set_get(struct s2n_set *set, uint32_t idx, void **element)
101 {
102 RESULT_GUARD(s2n_set_validate(set));
103 RESULT_ENSURE_REF(element);
104
105 RESULT_GUARD(s2n_array_get(set->data, idx, element));
106
107 return S2N_RESULT_OK;
108 }
109
s2n_set_remove(struct s2n_set * set,uint32_t idx)110 S2N_RESULT s2n_set_remove(struct s2n_set *set, uint32_t idx)
111 {
112 RESULT_GUARD(s2n_set_validate(set));
113 RESULT_GUARD(s2n_array_remove(set->data, idx));
114
115 return S2N_RESULT_OK;
116 }
117
s2n_set_free_p(struct s2n_set ** pset)118 S2N_RESULT s2n_set_free_p(struct s2n_set **pset)
119 {
120 RESULT_ENSURE_REF(pset);
121 struct s2n_set *set = *pset;
122
123 RESULT_ENSURE_REF(set);
124 RESULT_GUARD(s2n_array_free(set->data));
125
126 /* And finally the set object. */
127 RESULT_GUARD_POSIX(s2n_free_object((uint8_t **)pset, sizeof(struct s2n_set)));
128
129 return S2N_RESULT_OK;
130
131 }
132
s2n_set_free(struct s2n_set * set)133 S2N_RESULT s2n_set_free(struct s2n_set *set)
134 {
135 RESULT_ENSURE_REF(set);
136 return s2n_set_free_p(&set);
137 }
138
139
s2n_set_len(struct s2n_set * set,uint32_t * len)140 S2N_RESULT s2n_set_len(struct s2n_set *set, uint32_t *len)
141 {
142 RESULT_GUARD(s2n_set_validate(set));
143
144 RESULT_GUARD(s2n_array_num_elements(set->data, len));
145
146 return S2N_RESULT_OK;
147 }
148