]>
Commit | Line | Data |
---|---|---|
fe7cfa5c | 1 | /* |
3d0dc308 | 2 | * Copyright (c) 2014, 2016 Nicira, Inc. |
fe7cfa5c JR |
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 | ||
3d0dc308 JR |
20 | /* Writers will preallocate space for some entries at the end to avoid future |
21 | * reallocations. */ | |
22 | enum { PVECTOR_EXTRA_ALLOC = 4 }; | |
23 | ||
da9cfca6 JR |
24 | static struct pvector_impl * |
25 | pvector_impl_get(const struct pvector *pvec) | |
fe7cfa5c | 26 | { |
da9cfca6 JR |
27 | return ovsrcu_get(struct pvector_impl *, &pvec->impl); |
28 | } | |
29 | ||
30 | static struct pvector_impl * | |
31 | pvector_impl_alloc(size_t size) | |
32 | { | |
33 | struct pvector_impl *impl; | |
fe7cfa5c | 34 | |
da9cfca6 | 35 | impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]); |
4e1ce6f6 | 36 | atomic_init(&impl->size, 0); |
da9cfca6 | 37 | impl->allocated = size; |
fe7cfa5c | 38 | |
da9cfca6 JR |
39 | return impl; |
40 | } | |
41 | ||
42 | static struct pvector_impl * | |
43 | pvector_impl_dup(struct pvector_impl *old) | |
44 | { | |
45 | struct pvector_impl *impl; | |
46 | size_t alloc = old->size + PVECTOR_EXTRA_ALLOC; | |
47 | ||
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]); | |
52 | return impl; | |
fe7cfa5c JR |
53 | } |
54 | ||
da9cfca6 JR |
55 | /* Initializes 'pvec' as an empty concurrent priority vector. */ |
56 | void | |
57 | pvector_init(struct pvector *pvec) | |
fe7cfa5c | 58 | { |
da9cfca6 JR |
59 | ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC)); |
60 | pvec->temp = NULL; | |
61 | } | |
fe7cfa5c | 62 | |
da9cfca6 JR |
63 | /* Destroys 'pvec'. |
64 | * | |
65 | * The client is responsible for destroying any data previously held in | |
66 | * 'pvec'. */ | |
67 | void | |
68 | pvector_destroy(struct pvector *pvec) | |
69 | { | |
70 | free(pvec->temp); | |
71 | pvec->temp = NULL; | |
72 | ovsrcu_postpone(free, pvector_impl_get(pvec)); | |
73 | ovsrcu_set(&pvec->impl, NULL); /* Poison. */ | |
fe7cfa5c JR |
74 | } |
75 | ||
da9cfca6 JR |
76 | /* Iterators for callers that need the 'index' afterward. */ |
77 | #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL) \ | |
fe7cfa5c JR |
78 | for ((INDEX) = 0; \ |
79 | (INDEX) < (IMPL)->size \ | |
80 | && ((ENTRY) = &(IMPL)->vector[INDEX], true); \ | |
81 | (INDEX)++) | |
82 | ||
83 | static int | |
84 | pvector_entry_cmp(const void *a_, const void *b_) | |
85 | { | |
eb391b76 BP |
86 | const struct pvector_entry *ap = a_; |
87 | const struct pvector_entry *bp = b_; | |
88 | int a = ap->priority; | |
89 | int b = bp->priority; | |
fe7cfa5c JR |
90 | |
91 | return a > b ? -1 : a < b; | |
92 | } | |
93 | ||
da9cfca6 JR |
94 | static void |
95 | pvector_impl_sort(struct pvector_impl *impl) | |
fe7cfa5c | 96 | { |
da9cfca6 | 97 | qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp); |
fe7cfa5c JR |
98 | } |
99 | ||
100 | /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */ | |
101 | static int | |
da9cfca6 | 102 | pvector_impl_find(struct pvector_impl *impl, void *target) |
fe7cfa5c JR |
103 | { |
104 | const struct pvector_entry *entry; | |
105 | int index; | |
106 | ||
da9cfca6 | 107 | PVECTOR_IMPL_FOR_EACH (entry, index, impl) { |
fe7cfa5c JR |
108 | if (entry->ptr == target) { |
109 | return index; | |
110 | } | |
111 | } | |
112 | return -1; | |
113 | } | |
114 | ||
115 | void | |
da9cfca6 | 116 | pvector_insert(struct pvector *pvec, void *ptr, int priority) |
fe7cfa5c | 117 | { |
da9cfca6 JR |
118 | struct pvector_impl *temp = pvec->temp; |
119 | struct pvector_impl *old = pvector_impl_get(pvec); | |
4e1ce6f6 | 120 | size_t size; |
fe7cfa5c JR |
121 | |
122 | ovs_assert(ptr != NULL); | |
123 | ||
4e1ce6f6 YW |
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); | |
127 | ||
fe7cfa5c | 128 | /* Check if can add to the end without reallocation. */ |
4e1ce6f6 YW |
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; | |
fe7cfa5c JR |
133 | /* Size increment must not be visible to the readers before the new |
134 | * entry is stored. */ | |
4e1ce6f6 | 135 | atomic_store_explicit(&old->size, size + 1, memory_order_release); |
fe7cfa5c | 136 | } else { |
802f84ff | 137 | if (!temp) { |
da9cfca6 JR |
138 | temp = pvector_impl_dup(old); |
139 | pvec->temp = temp; | |
140 | } else if (temp->size == temp->allocated) { | |
141 | temp = pvector_impl_dup(temp); | |
142 | free(pvec->temp); | |
143 | pvec->temp = temp; | |
802f84ff | 144 | } |
da9cfca6 JR |
145 | /* Insert at the end, publish will sort. */ |
146 | temp->vector[temp->size].ptr = ptr; | |
147 | temp->vector[temp->size].priority = priority; | |
148 | temp->size += 1; | |
fe7cfa5c JR |
149 | } |
150 | } | |
151 | ||
152 | void | |
da9cfca6 | 153 | pvector_remove(struct pvector *pvec, void *ptr) |
fe7cfa5c | 154 | { |
da9cfca6 JR |
155 | struct pvector_impl *temp = pvec->temp; |
156 | int index; | |
fe7cfa5c | 157 | |
802f84ff | 158 | if (!temp) { |
da9cfca6 JR |
159 | temp = pvector_impl_dup(pvector_impl_get(pvec)); |
160 | pvec->temp = temp; | |
802f84ff JR |
161 | } |
162 | ovs_assert(temp->size > 0); | |
da9cfca6 JR |
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. */ | |
167 | temp->size--; | |
168 | if (index != temp->size) { | |
169 | temp->vector[index] = temp->vector[temp->size]; | |
170 | } | |
fe7cfa5c JR |
171 | } |
172 | ||
173 | /* Change entry's 'priority' and keep the vector ordered. */ | |
174 | void | |
da9cfca6 | 175 | pvector_change_priority(struct pvector *pvec, void *ptr, int priority) |
fe7cfa5c | 176 | { |
da9cfca6 | 177 | struct pvector_impl *old = pvec->temp; |
802f84ff JR |
178 | int index; |
179 | ||
180 | if (!old) { | |
da9cfca6 | 181 | old = pvector_impl_get(pvec); |
802f84ff JR |
182 | } |
183 | ||
da9cfca6 | 184 | index = pvector_impl_find(old, ptr); |
fe7cfa5c JR |
185 | |
186 | ovs_assert(index >= 0); | |
187 | /* Now at the index of the entry to be updated. */ | |
188 | ||
802f84ff | 189 | /* Check if can not update in place. */ |
fe7cfa5c JR |
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)) { | |
802f84ff | 194 | /* Have to use a temp. */ |
da9cfca6 | 195 | if (!pvec->temp) { |
802f84ff | 196 | /* Have to reallocate to reorder. */ |
da9cfca6 JR |
197 | pvec->temp = pvector_impl_dup(old); |
198 | old = pvec->temp; | |
802f84ff JR |
199 | /* Publish will sort. */ |
200 | } | |
201 | } | |
202 | old->vector[index].priority = priority; | |
203 | } | |
fe7cfa5c | 204 | |
802f84ff | 205 | /* Make the modified pvector available for iteration. */ |
da9cfca6 | 206 | void pvector_publish__(struct pvector *pvec) |
802f84ff | 207 | { |
da9cfca6 | 208 | struct pvector_impl *temp = pvec->temp; |
fe7cfa5c | 209 | |
da9cfca6 JR |
210 | pvec->temp = NULL; |
211 | pvector_impl_sort(temp); /* Also removes gaps. */ | |
212 | ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector_impl *, | |
213 | &pvec->impl)); | |
214 | ovsrcu_set(&pvec->impl, temp); | |
fe7cfa5c | 215 | } |