]>
Commit | Line | Data |
---|---|---|
fe7cfa5c JR |
1 | /* |
2 | * Copyright (c) 2014 Nicira, Inc. | |
3 | * | |
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: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
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. | |
15 | */ | |
16 | ||
17 | #include <config.h> | |
18 | #include "pvector.h" | |
19 | ||
20 | static struct pvector_impl * | |
21 | pvector_impl_get(const struct pvector *pvec) | |
22 | { | |
23 | return ovsrcu_get(struct pvector_impl *, &pvec->impl); | |
24 | } | |
25 | ||
26 | static struct pvector_impl * | |
27 | pvector_impl_alloc(size_t size) | |
28 | { | |
29 | struct pvector_impl *impl; | |
30 | ||
31 | impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]); | |
32 | impl->size = 0; | |
33 | impl->allocated = size; | |
34 | ||
35 | return impl; | |
36 | } | |
37 | ||
38 | static struct pvector_impl * | |
39 | pvector_impl_dup(struct pvector_impl *old) | |
40 | { | |
41 | return xmemdup(old, sizeof *old + old->allocated * sizeof old->vector[0]); | |
42 | } | |
43 | ||
44 | /* Initializes 'pvec' as an empty concurrent priority vector. */ | |
45 | void | |
46 | pvector_init(struct pvector *pvec) | |
47 | { | |
48 | ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC)); | |
49 | } | |
50 | ||
51 | /* Destroys 'pvec'. | |
52 | * | |
53 | * The client is responsible for destroying any data previously held in | |
54 | * 'pvec'. */ | |
55 | void | |
56 | pvector_destroy(struct pvector *pvec) | |
57 | { | |
58 | ovsrcu_postpone(free, pvector_impl_get(pvec)); | |
59 | ovsrcu_set(&pvec->impl, NULL); /* Poison. */ | |
60 | } | |
61 | ||
62 | /* Iterators for callers that need the 'index' afterward. */ | |
63 | #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL) \ | |
64 | for ((INDEX) = 0; \ | |
65 | (INDEX) < (IMPL)->size \ | |
66 | && ((ENTRY) = &(IMPL)->vector[INDEX], true); \ | |
67 | (INDEX)++) | |
68 | ||
69 | static int | |
70 | pvector_entry_cmp(const void *a_, const void *b_) | |
71 | { | |
72 | unsigned int a = ((const struct pvector_entry *)a_)->priority; | |
73 | unsigned int b = ((const struct pvector_entry *)b_)->priority; | |
74 | ||
75 | return a > b ? -1 : a < b; | |
76 | } | |
77 | ||
78 | static void | |
79 | pvector_impl_sort(struct pvector_impl *impl) | |
80 | { | |
81 | qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp); | |
82 | } | |
83 | ||
84 | /* Returns the index with priority equal or lower than 'target_priority', | |
85 | * which will be one past the vector if none exists. */ | |
86 | static int | |
87 | pvector_impl_find_priority(struct pvector_impl *impl, | |
88 | unsigned int target_priority) | |
89 | { | |
90 | const struct pvector_entry *entry; | |
91 | int index; | |
92 | ||
93 | PVECTOR_IMPL_FOR_EACH (entry, index, impl) { | |
94 | if (entry->priority <= target_priority) { | |
95 | break; | |
96 | } | |
97 | } | |
98 | return index; | |
99 | } | |
100 | ||
101 | /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */ | |
102 | static int | |
103 | pvector_impl_find(struct pvector_impl *impl, void *target) | |
104 | { | |
105 | const struct pvector_entry *entry; | |
106 | int index; | |
107 | ||
108 | PVECTOR_IMPL_FOR_EACH (entry, index, impl) { | |
109 | if (entry->ptr == target) { | |
110 | return index; | |
111 | } | |
112 | } | |
113 | return -1; | |
114 | } | |
115 | ||
116 | void | |
117 | pvector_insert(struct pvector *pvec, void *ptr, unsigned int priority) | |
118 | { | |
119 | struct pvector_impl *old, *new; | |
120 | int index; | |
121 | ||
122 | ovs_assert(ptr != NULL); | |
123 | ||
124 | old = pvector_impl_get(pvec); | |
125 | ||
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); | |
134 | ++old->size; | |
135 | } else { | |
136 | new = pvector_impl_alloc(old->size + 1 + PVECTOR_EXTRA_ALLOC); | |
137 | ||
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; | |
146 | ||
147 | ovsrcu_set(&pvec->impl, new); | |
148 | ovsrcu_postpone(free, old); | |
149 | } | |
150 | } | |
151 | ||
152 | void | |
153 | pvector_remove(struct pvector *pvec, void *ptr) | |
154 | { | |
155 | struct pvector_impl *old, *new; | |
156 | int index; | |
157 | ||
158 | old = pvector_impl_get(pvec); | |
159 | ||
160 | ovs_assert(old->size > 0); | |
161 | ||
162 | index = pvector_impl_find(old, ptr); | |
163 | ovs_assert(index >= 0); | |
164 | /* Now at the index of the entry to be deleted. */ | |
165 | ||
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. | |
168 | */ | |
169 | ||
170 | /* Keep extra space for insertions to the end. */ | |
171 | new = pvector_impl_alloc(old->size - 1 + PVECTOR_EXTRA_ALLOC); | |
172 | ||
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]); | |
176 | ||
177 | new->size = old->size - 1; | |
178 | ||
179 | ovsrcu_set(&pvec->impl, new); | |
180 | ovsrcu_postpone(free, old); | |
181 | } | |
182 | ||
183 | /* Change entry's 'priority' and keep the vector ordered. */ | |
184 | void | |
185 | pvector_change_priority(struct pvector *pvec, void *ptr, unsigned int priority) | |
186 | { | |
187 | struct pvector_impl *old = pvector_impl_get(pvec); | |
188 | int index = pvector_impl_find(old, ptr); | |
189 | ||
190 | ovs_assert(index >= 0); | |
191 | /* Now at the index of the entry to be updated. */ | |
192 | ||
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); | |
199 | ||
200 | new->vector[index].priority = priority; | |
201 | pvector_impl_sort(new); | |
202 | ||
203 | ovsrcu_set(&pvec->impl, new); | |
204 | ovsrcu_postpone(free, old); | |
205 | } else { | |
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; | |
209 | } | |
210 | } |