lib/pvector.c

   1 /*
   2  * Copyright (c) 2014, 2016 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 /* Writers will preallocate space for some entries at the end to avoid future
  21  * reallocations. */
  22 enum { PVECTOR_EXTRA_ALLOC = 4 };
  23
  24 static struct pvector_impl *
  25 pvector_impl_get(const struct pvector *pvec)
  26 {
  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;
  34
  35     impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]);
  36     impl->size = 0;
  37     impl->allocated = size;
  38
  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;
  53 }
  54
  55 /* Initializes 'pvec' as an empty concurrent priority vector. */
  56 void
  57 pvector_init(struct pvector *pvec)
  58 {
  59     ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
  60     pvec->temp = NULL;
  61 }
  62
  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. */
  74 }
  75
  76 /* Iterators for callers that need the 'index' afterward. */
  77 #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL)          \
  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 {
  86     const struct pvector_entry *ap = a_;
  87     const struct pvector_entry *bp = b_;
  88     int a = ap->priority;
  89     int b = bp->priority;
  90
  91     return a > b ? -1 : a < b;
  92 }
  93
  94 static void
  95 pvector_impl_sort(struct pvector_impl *impl)
  96 {
  97     qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
  98 }
  99
 100 /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */
 101 static int
 102 pvector_impl_find(struct pvector_impl *impl, void *target)
 103 {
 104     const struct pvector_entry *entry;
 105     int index;
 106
 107     PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
 108         if (entry->ptr == target) {
 109             return index;
 110         }
 111     }
 112     return -1;
 113 }
 114
 115 void
 116 pvector_insert(struct pvector *pvec, void *ptr, int priority)
 117 {
 118     struct pvector_impl *temp = pvec->temp;
 119     struct pvector_impl *old = pvector_impl_get(pvec);
 120
 121     ovs_assert(ptr != NULL);
 122
 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);
 131         ++old->size;
 132     } else {
 133         if (!temp) {
 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;
 140         }
 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;
 145     }
 146 }
 147
 148 void
 149 pvector_remove(struct pvector *pvec, void *ptr)
 150 {
 151     struct pvector_impl *temp = pvec->temp;
 152     int index;
 153
 154     if (!temp) {
 155         temp = pvector_impl_dup(pvector_impl_get(pvec));
 156         pvec->temp = temp;
 157     }
 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      * 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     }
 167 }
 168
 169 /* Change entry's 'priority' and keep the vector ordered. */
 170 void
 171 pvector_change_priority(struct pvector *pvec, void *ptr, int priority)
 172 {
 173     struct pvector_impl *old = pvec->temp;
 174     int index;
 175
 176     if (!old) {
 177         old = pvector_impl_get(pvec);
 178     }
 179
 180     index = pvector_impl_find(old, ptr);
 181
 182     ovs_assert(index >= 0);
 183     /* Now at the index of the entry to be updated. */
 184
 185     /* Check if can not update in place. */
 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)) {
 190         /* Have to use a temp. */
 191         if (!pvec->temp) {
 192             /* Have to reallocate to reorder. */
 193             pvec->temp = pvector_impl_dup(old);
 194             old = pvec->temp;
 195             /* Publish will sort. */
 196         }
 197     }
 198     old->vector[index].priority = priority;
 199 }
 200
 201 /* Make the modified pvector available for iteration. */
 202 void pvector_publish__(struct pvector *pvec)
 203 {
 204     struct pvector_impl *temp = pvec->temp;
 205
 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);
 211 }