]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/pvector.c
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
);