]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/pvector.c
2 * Copyright (c) 2014, 2016 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 /* Writers will preallocate space for some entries at the end to avoid future
22 enum { PVECTOR_EXTRA_ALLOC
= 4 };
24 static struct pvector_impl
*
25 pvector_impl_get(const struct pvector
*pvec
)
27 return ovsrcu_get(struct pvector_impl
*, &pvec
->impl
);
30 static struct pvector_impl
*
31 pvector_impl_alloc(size_t size
)
33 struct pvector_impl
*impl
;
35 impl
= xmalloc(sizeof *impl
+ size
* sizeof impl
->vector
[0]);
36 atomic_init(&impl
->size
, 0);
37 impl
->allocated
= size
;
42 static struct pvector_impl
*
43 pvector_impl_dup(struct pvector_impl
*old
)
45 struct pvector_impl
*impl
;
46 size_t alloc
= old
->size
+ PVECTOR_EXTRA_ALLOC
;
48 impl
= xmalloc(sizeof *impl
+ alloc
* sizeof impl
->vector
[0]);
49 impl
->allocated
= alloc
;
50 impl
->size
= old
->size
;
51 memcpy(impl
->vector
, old
->vector
, old
->size
* sizeof old
->vector
[0]);
55 /* Initializes 'pvec' as an empty concurrent priority vector. */
57 pvector_init(struct pvector
*pvec
)
59 ovsrcu_set(&pvec
->impl
, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC
));
65 * The client is responsible for destroying any data previously held in
68 pvector_destroy(struct pvector
*pvec
)
72 ovsrcu_postpone(free
, pvector_impl_get(pvec
));
73 ovsrcu_set(&pvec
->impl
, NULL
); /* Poison. */
76 /* Iterators for callers that need the 'index' afterward. */
77 #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL) \
79 (INDEX) < (IMPL)->size \
80 && ((ENTRY) = &(IMPL)->vector[INDEX], true); \
84 pvector_entry_cmp(const void *a_
, const void *b_
)
86 const struct pvector_entry
*ap
= a_
;
87 const struct pvector_entry
*bp
= b_
;
91 return a
> b
? -1 : a
< b
;
95 pvector_impl_sort(struct pvector_impl
*impl
)
97 qsort(impl
->vector
, impl
->size
, sizeof *impl
->vector
, pvector_entry_cmp
);
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
);
122 ovs_assert(ptr
!= NULL
);
124 /* There is no possible concurrent writer. Insertions must be protected
125 * by mutex or be always excuted from the same thread. */
126 atomic_read_relaxed(&old
->size
, &size
);
128 /* Check if can add to the end without reallocation. */
129 if (!temp
&& old
->allocated
> size
&&
130 (!size
|| priority
<= old
->vector
[size
- 1].priority
)) {
131 old
->vector
[size
].ptr
= ptr
;
132 old
->vector
[size
].priority
= priority
;
133 /* Size increment must not be visible to the readers before the new
134 * entry is stored. */
135 atomic_store_explicit(&old
->size
, size
+ 1, memory_order_release
);
138 temp
= pvector_impl_dup(old
);
140 } else if (temp
->size
== temp
->allocated
) {
141 temp
= pvector_impl_dup(temp
);
145 /* Insert at the end, publish will sort. */
146 temp
->vector
[temp
->size
].ptr
= ptr
;
147 temp
->vector
[temp
->size
].priority
= priority
;
153 pvector_remove(struct pvector
*pvec
, void *ptr
)
155 struct pvector_impl
*temp
= pvec
->temp
;
159 temp
= pvector_impl_dup(pvector_impl_get(pvec
));
162 ovs_assert(temp
->size
> 0);
163 index
= pvector_impl_find(temp
, ptr
);
164 ovs_assert(index
>= 0);
165 /* Now at the index of the entry to be deleted.
166 * Swap another entry in if needed, publish will sort anyway. */
168 if (index
!= temp
->size
) {
169 temp
->vector
[index
] = temp
->vector
[temp
->size
];
173 /* Change entry's 'priority' and keep the vector ordered. */
175 pvector_change_priority(struct pvector
*pvec
, void *ptr
, int priority
)
177 struct pvector_impl
*old
= pvec
->temp
;
181 old
= pvector_impl_get(pvec
);
184 index
= pvector_impl_find(old
, ptr
);
186 ovs_assert(index
>= 0);
187 /* Now at the index of the entry to be updated. */
189 /* Check if can not update in place. */
190 if ((priority
> old
->vector
[index
].priority
&& index
> 0
191 && priority
> old
->vector
[index
- 1].priority
)
192 || (priority
< old
->vector
[index
].priority
&& index
< old
->size
- 1
193 && priority
< old
->vector
[index
+ 1].priority
)) {
194 /* Have to use a temp. */
196 /* Have to reallocate to reorder. */
197 pvec
->temp
= pvector_impl_dup(old
);
199 /* Publish will sort. */
202 old
->vector
[index
].priority
= priority
;
205 /* Make the modified pvector available for iteration. */
206 void pvector_publish__(struct pvector
*pvec
)
208 struct pvector_impl
*temp
= pvec
->temp
;
211 pvector_impl_sort(temp
); /* Also removes gaps. */
212 ovsrcu_postpone(free
, ovsrcu_get_protected(struct pvector_impl
*,
214 ovsrcu_set(&pvec
->impl
, temp
);