]>
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 JR |
35 | impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]); |
36 | impl->size = 0; | |
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); | |
fe7cfa5c JR |
120 | |
121 | ovs_assert(ptr != NULL); | |
122 | ||
fe7cfa5c | 123 | /* Check if can add to the end without reallocation. */ |
802f84ff | 124 | if (!temp && old->allocated > old->size && |
fe7cfa5c JR |
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); | |
131 | ++old->size; | |
132 | } else { | |
802f84ff | 133 | if (!temp) { |
da9cfca6 JR |
134 | temp = pvector_impl_dup(old); |
135 | pvec->temp = temp; | |
136 | } else if (temp->size == temp->allocated) { | |
137 | temp = pvector_impl_dup(temp); | |
138 | free(pvec->temp); | |
139 | pvec->temp = temp; | |
802f84ff | 140 | } |
da9cfca6 JR |
141 | /* Insert at the end, publish will sort. */ |
142 | temp->vector[temp->size].ptr = ptr; | |
143 | temp->vector[temp->size].priority = priority; | |
144 | temp->size += 1; | |
fe7cfa5c JR |
145 | } |
146 | } | |
147 | ||
148 | void | |
da9cfca6 | 149 | pvector_remove(struct pvector *pvec, void *ptr) |
fe7cfa5c | 150 | { |
da9cfca6 JR |
151 | struct pvector_impl *temp = pvec->temp; |
152 | int index; | |
fe7cfa5c | 153 | |
802f84ff | 154 | if (!temp) { |
da9cfca6 JR |
155 | temp = pvector_impl_dup(pvector_impl_get(pvec)); |
156 | pvec->temp = temp; | |
802f84ff JR |
157 | } |
158 | ovs_assert(temp->size > 0); | |
da9cfca6 JR |
159 | index = pvector_impl_find(temp, ptr); |
160 | ovs_assert(index >= 0); | |
161 | /* Now at the index of the entry to be deleted. | |
162 | * Swap another entry in if needed, publish will sort anyway. */ | |
163 | temp->size--; | |
164 | if (index != temp->size) { | |
165 | temp->vector[index] = temp->vector[temp->size]; | |
166 | } | |
fe7cfa5c JR |
167 | } |
168 | ||
169 | /* Change entry's 'priority' and keep the vector ordered. */ | |
170 | void | |
da9cfca6 | 171 | pvector_change_priority(struct pvector *pvec, void *ptr, int priority) |
fe7cfa5c | 172 | { |
da9cfca6 | 173 | struct pvector_impl *old = pvec->temp; |
802f84ff JR |
174 | int index; |
175 | ||
176 | if (!old) { | |
da9cfca6 | 177 | old = pvector_impl_get(pvec); |
802f84ff JR |
178 | } |
179 | ||
da9cfca6 | 180 | index = pvector_impl_find(old, ptr); |
fe7cfa5c JR |
181 | |
182 | ovs_assert(index >= 0); | |
183 | /* Now at the index of the entry to be updated. */ | |
184 | ||
802f84ff | 185 | /* Check if can not update in place. */ |
fe7cfa5c JR |
186 | if ((priority > old->vector[index].priority && index > 0 |
187 | && priority > old->vector[index - 1].priority) | |
188 | || (priority < old->vector[index].priority && index < old->size - 1 | |
189 | && priority < old->vector[index + 1].priority)) { | |
802f84ff | 190 | /* Have to use a temp. */ |
da9cfca6 | 191 | if (!pvec->temp) { |
802f84ff | 192 | /* Have to reallocate to reorder. */ |
da9cfca6 JR |
193 | pvec->temp = pvector_impl_dup(old); |
194 | old = pvec->temp; | |
802f84ff JR |
195 | /* Publish will sort. */ |
196 | } | |
197 | } | |
198 | old->vector[index].priority = priority; | |
199 | } | |
fe7cfa5c | 200 | |
802f84ff | 201 | /* Make the modified pvector available for iteration. */ |
da9cfca6 | 202 | void pvector_publish__(struct pvector *pvec) |
802f84ff | 203 | { |
da9cfca6 | 204 | struct pvector_impl *temp = pvec->temp; |
fe7cfa5c | 205 | |
da9cfca6 JR |
206 | pvec->temp = NULL; |
207 | pvector_impl_sort(temp); /* Also removes gaps. */ | |
208 | ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector_impl *, | |
209 | &pvec->impl)); | |
210 | ovsrcu_set(&pvec->impl, temp); | |
fe7cfa5c | 211 | } |