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 struct pvector_impl *impl;
42 size_t alloc = old->size + PVECTOR_EXTRA_ALLOC;
44 impl = xmalloc(sizeof *impl + alloc * sizeof impl->vector[0]);
45 impl->allocated = alloc;
46 impl->size = old->size;
47 memcpy(impl->vector, old->vector, old->size * sizeof old->vector[0]);
51 /* Initializes 'pvec' as an empty concurrent priority vector. */
53 pvector_init(struct pvector *pvec)
55 ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
61 * The client is responsible for destroying any data previously held in
64 pvector_destroy(struct pvector *pvec)
68 ovsrcu_postpone(free, pvector_impl_get(pvec));
69 ovsrcu_set(&pvec->impl, NULL); /* Poison. */
72 /* Iterators for callers that need the 'index' afterward. */
73 #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL) \
75 (INDEX) < (IMPL)->size \
76 && ((ENTRY) = &(IMPL)->vector[INDEX], true); \
80 pvector_entry_cmp(const void *a_, const void *b_)
82 const struct pvector_entry *ap = a_;
83 const struct pvector_entry *bp = b_;
87 return a > b ? -1 : a < b;
91 pvector_impl_sort(struct pvector_impl *impl)
93 qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
95 while (impl->size && impl->vector[impl->size - 1].priority == INT_MIN) {
96 impl->size = impl->size - 1;
100 /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */
102 pvector_impl_find(struct pvector_impl *impl, void *target)
104 const struct pvector_entry *entry;
107 PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
108 if (entry->ptr == target) {
116 pvector_insert(struct pvector *pvec, void *ptr, int priority)
118 struct pvector_impl *temp = pvec->temp;
119 struct pvector_impl *old = pvector_impl_get(pvec);
121 ovs_assert(ptr != NULL);
123 /* Check if can add to the end without reallocation. */
124 if (!temp && old->allocated > old->size &&
125 (!old->size || priority <= old->vector[old->size - 1].priority)) {
126 old->vector[old->size].ptr = ptr;
127 old->vector[old->size].priority = priority;
128 /* Size increment must not be visible to the readers before the new
129 * entry is stored. */
130 atomic_thread_fence(memory_order_release);
134 temp = pvector_impl_dup(old);
136 } else if (temp->size == temp->allocated) {
137 temp = pvector_impl_dup(temp);
141 /* Insert at the end, publish will sort. */
142 temp->vector[temp->size].ptr = ptr;
143 temp->vector[temp->size].priority = priority;
149 pvector_remove(struct pvector *pvec, void *ptr)
151 struct pvector_impl *temp = pvec->temp;
155 temp = pvector_impl_dup(pvector_impl_get(pvec));
158 ovs_assert(temp->size > 0);
159 index = pvector_impl_find(temp, ptr);
160 ovs_assert(index >= 0);
161 /* Now at the index of the entry to be deleted.
162 * Clear in place, publish will sort and clean these off. */
163 temp->vector[index].ptr = NULL;
164 temp->vector[index].priority = INT_MIN;
167 /* Change entry's 'priority' and keep the vector ordered. */
169 pvector_change_priority(struct pvector *pvec, void *ptr, int priority)
171 struct pvector_impl *old = pvec->temp;
175 old = pvector_impl_get(pvec);
178 index = pvector_impl_find(old, ptr);
180 ovs_assert(index >= 0);
181 /* Now at the index of the entry to be updated. */
183 /* Check if can not update in place. */
184 if ((priority > old->vector[index].priority && index > 0
185 && priority > old->vector[index - 1].priority)
186 || (priority < old->vector[index].priority && index < old->size - 1
187 && priority < old->vector[index + 1].priority)) {
188 /* Have to use a temp. */
190 /* Have to reallocate to reorder. */
191 pvec->temp = pvector_impl_dup(old);
193 /* Publish will sort. */
196 old->vector[index].priority = priority;
199 /* Make the modified pvector available for iteration. */
200 void pvector_publish__(struct pvector *pvec)
202 struct pvector_impl *temp = pvec->temp;
205 pvector_impl_sort(temp); /* Also removes gaps. */
206 ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector_impl *,
208 ovsrcu_set(&pvec->impl, temp);