2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Implementation of sets with sorted arrays.
24 * @author Sebastian Hack
26 * Follows the same API/specialization scheme as hashset.c and is thus interchangable.
27 * To remain compatible, all specializations as in hashset.c must be done.
28 * Additionally, we need a ValueCmp macro comapring two values not only for equality.
29 * That macro follows the same scheme as the compare functions in qsort(3).
34 #include "firm_config.h"
37 static INLINE int hashset_bsearch(ValueType *arr, const ValueType elm)
41 int hi = ARR_LEN(arr);
44 int md = lo + ((hi - lo) >> 1);
45 int cmp = ValueCmp(arr[md], elm);
62 static INLINE int hashset_is_at(ValueType *arr, int idx, const ValueType what)
64 return idx < ARR_LEN(arr) && ValueCmp(arr[idx], what) == 0;
67 void hashset_init_size(HashSet *set, size_t expected_elements)
69 set->arr = NEW_ARR_F(ValueType, expected_elements);
73 ARR_SHRINKLEN(set->arr, 0);
76 void hashset_init(HashSet *set)
78 hashset_init_size(set, 16);
81 void hashset_destroy(HashSet *set)
86 int hashset_insert(HashSet *set, ValueType elt)
88 ValueType *arr = set->arr;
89 int i, idx = hashset_bsearch(arr, elt);
92 assert(set->in_order);
94 if (!hashset_is_at(arr, idx, elt)) {
95 ARR_EXTEND(ValueType, set->arr, 1);
97 for (i = ARR_LEN(arr) - 1; i > idx; --i)
106 void hashset_insert_quick(HashSet *set, ValueType elt)
108 ValueType *arr = set->arr;
109 ARR_EXTEND(ValueType, set->arr, 1);
111 arr[ARR_LEN(arr) - 1] = elt;
114 static INLINE int _hashset_remove_idx(ValueType *arr, int idx)
118 for (n = ARR_LEN(arr) - 1; idx < n; ++idx)
119 arr[idx] = arr[idx + 1];
124 void hashset_remove(HashSet *set, const ValueType elt)
126 ValueType *arr = set->arr;
127 int idx = hashset_bsearch(arr, elt);
130 assert(set->in_order);
132 if (hashset_is_at(arr, idx, elt)) {
133 int new_len = _hashset_remove_idx(arr, idx);
134 ARR_SHRINKLEN(arr, new_len);
138 void hashset_remove_quick(HashSet *set, const ValueType elt)
140 ValueType *arr = set->arr;
141 int idx = hashset_bsearch(arr, elt);
146 if (hashset_is_at(arr, idx, elt)) {
147 int n = ARR_LEN(arr);
149 arr[idx] = arr[n - 1];
150 ARR_SHRINKLEN(arr, n - 1);
154 void hashset_fixup(HashSet *set)
156 ValueType *arr = set->arr;
160 CLONE_ARR_A(ValueType, tmp, arr);
162 memcpy(tmp, arr, n * sizeof(arr[0]));
163 ARR_SHRINKLEN(arr, 0);
164 for (i = 0, n = ARR_LEN(arr); i < n; ++i)
165 hashset_insert(set, tmp[0]);
171 ValueType hashset_find(const HashSet *set, const ValueType elt)
173 int idx = hashset_bsearch(set->arr, elt);
175 assert(set->in_order);
177 return hashset_is_at(set->arr, idx, elt) ? set->arr[idx] : NullValue;
180 size_t hashset_size(const HashSet *set)
182 return ARR_LEN(set->arr);
185 void hashset_iterator_init(HashSetIterator *iter, const HashSet *set)
187 iter->arr = set->arr;
191 ValueType ir_nodeset_iterator_next(HashSetIterator *iter)
194 return iter->curr < ARR_LEN(iter->arr) ? iter->arr[iter->curr] : NullValue;
197 void hashset_remove_iterator(HashSet *set, const HashSetIterator *iter)
200 (void) _hashset_remove_idx(iter->arr, iter->curr);
201 ARR_SHRINKLEN(iter->arr, ARR_LEN(iter->arr) - 1);