2 * Copyright (c) 2014 Nicira, Inc.
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 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
20 static struct pvector_impl *
21 pvector_impl_get(const struct pvector *pvec)
23 return ovsrcu_get(struct pvector_impl *, &pvec->impl);
26 static struct pvector_impl *
27 pvector_impl_alloc(size_t size)
29 struct pvector_impl *impl;
31 impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]);
33 impl->allocated = size;
38 static struct pvector_impl *
39 pvector_impl_dup(struct pvector_impl *old)
41 return xmemdup(old, sizeof *old + old->allocated * sizeof old->vector[0]);
44 /* Initializes 'pvec' as an empty concurrent priority vector. */
46 pvector_init(struct pvector *pvec)
48 ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
53 * The client is responsible for destroying any data previously held in
56 pvector_destroy(struct pvector *pvec)
58 ovsrcu_postpone(free, pvector_impl_get(pvec));
59 ovsrcu_set(&pvec->impl, NULL); /* Poison. */
62 /* Iterators for callers that need the 'index' afterward. */
63 #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL) \
65 (INDEX) < (IMPL)->size \
66 && ((ENTRY) = &(IMPL)->vector[INDEX], true); \
70 pvector_entry_cmp(const void *a_, const void *b_)
72 unsigned int a = ((const struct pvector_entry *)a_)->priority;
73 unsigned int b = ((const struct pvector_entry *)b_)->priority;
75 return a > b ? -1 : a < b;
79 pvector_impl_sort(struct pvector_impl *impl)
81 qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
84 /* Returns the index with priority equal or lower than 'target_priority',
85 * which will be one past the vector if none exists. */
87 pvector_impl_find_priority(struct pvector_impl *impl,
88 unsigned int target_priority)
90 const struct pvector_entry *entry;
93 PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
94 if (entry->priority <= target_priority) {
101 /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */
103 pvector_impl_find(struct pvector_impl *impl, void *target)
105 const struct pvector_entry *entry;
108 PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
109 if (entry->ptr == target) {
117 pvector_insert(struct pvector *pvec, void *ptr, unsigned int priority)
119 struct pvector_impl *old, *new;
122 ovs_assert(ptr != NULL);
124 old = pvector_impl_get(pvec);
126 /* Check if can add to the end without reallocation. */
127 if (old->allocated > old->size &&
128 (!old->size || priority <= old->vector[old->size - 1].priority)) {
129 old->vector[old->size].ptr = ptr;
130 old->vector[old->size].priority = priority;
131 /* Size increment must not be visible to the readers before the new
132 * entry is stored. */
133 atomic_thread_fence(memory_order_release);
136 new = pvector_impl_alloc(old->size + 1 + PVECTOR_EXTRA_ALLOC);
138 index = pvector_impl_find_priority(old, priority);
139 /* Now at the insertion index. */
140 memcpy(new->vector, old->vector, index * sizeof old->vector[0]);
141 new->vector[index].ptr = ptr;
142 new->vector[index].priority = priority;
143 memcpy(&new->vector[index + 1], &old->vector[index],
144 (old->size - index) * sizeof old->vector[0]);
145 new->size = old->size + 1;
147 ovsrcu_set(&pvec->impl, new);
148 ovsrcu_postpone(free, old);
153 pvector_remove(struct pvector *pvec, void *ptr)
155 struct pvector_impl *old, *new;
158 old = pvector_impl_get(pvec);
160 ovs_assert(old->size > 0);
162 index = pvector_impl_find(old, ptr);
163 ovs_assert(index >= 0);
164 /* Now at the index of the entry to be deleted. */
166 /* We do not try to delete the last entry without reallocation so that
167 * the readers can read the 'size' once in the beginning of each iteration.
170 /* Keep extra space for insertions to the end. */
171 new = pvector_impl_alloc(old->size - 1 + PVECTOR_EXTRA_ALLOC);
173 memcpy(new->vector, old->vector, index * sizeof old->vector[0]);
174 memcpy(&new->vector[index], &old->vector[index + 1],
175 (old->size - (index + 1)) * sizeof old->vector[0]);
177 new->size = old->size - 1;
179 ovsrcu_set(&pvec->impl, new);
180 ovsrcu_postpone(free, old);
183 /* Change entry's 'priority' and keep the vector ordered. */
185 pvector_change_priority(struct pvector *pvec, void *ptr, unsigned int priority)
187 struct pvector_impl *old = pvector_impl_get(pvec);
188 int index = pvector_impl_find(old, ptr);
190 ovs_assert(index >= 0);
191 /* Now at the index of the entry to be updated. */
193 if ((priority > old->vector[index].priority && index > 0
194 && priority > old->vector[index - 1].priority)
195 || (priority < old->vector[index].priority && index < old->size - 1
196 && priority < old->vector[index + 1].priority)) {
197 /* Have to reallocate to reorder. */
198 struct pvector_impl *new = pvector_impl_dup(old);
200 new->vector[index].priority = priority;
201 pvector_impl_sort(new);
203 ovsrcu_set(&pvec->impl, new);
204 ovsrcu_postpone(free, old);
206 /* Can update in place. Readers are free to use either value,
207 * so we do not try to synchronize here. */
208 old->vector[index].priority = priority;