lib/pvector.c

   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     struct pvector_impl *impl;
  42     size_t alloc = old->size + PVECTOR_EXTRA_ALLOC;
  43
  44     impl = xmalloc(sizeof *impl + alloc * sizeof impl->vector[0]);
  45     impl->allocated = alloc;
  46     impl->size = old->size;
  47     memcpy(impl->vector, old->vector, old->size * sizeof old->vector[0]);
  48     return impl;
  49 }
  50
  51 /* Initializes 'pvec' as an empty concurrent priority vector. */
  52 void
  53 pvector_init(struct pvector *pvec)
  54 {
  55     ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
  56     pvec->temp = NULL;
  57 }
  58
  59 /* Destroys 'pvec'.
  60  *
  61  * The client is responsible for destroying any data previously held in
  62  * 'pvec'. */
  63 void
  64 pvector_destroy(struct pvector *pvec)
  65 {
  66     free(pvec->temp);
  67     pvec->temp = NULL;
  68     ovsrcu_postpone(free, pvector_impl_get(pvec));
  69     ovsrcu_set(&pvec->impl, NULL); /* Poison. */
  70 }
  71
  72 /* Iterators for callers that need the 'index' afterward. */
  73 #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL)          \
  74     for ((INDEX) = 0;                                      \
  75          (INDEX) < (IMPL)->size                            \
  76              && ((ENTRY) = &(IMPL)->vector[INDEX], true);  \
  77          (INDEX)++)
  78
  79 static int
  80 pvector_entry_cmp(const void *a_, const void *b_)
  81 {
  82     const struct pvector_entry *ap = a_;
  83     const struct pvector_entry *bp = b_;
  84     int a = ap->priority;
  85     int b = bp->priority;
  86
  87     return a > b ? -1 : a < b;
  88 }
  89
  90 static void
  91 pvector_impl_sort(struct pvector_impl *impl)
  92 {
  93     qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
  94     /* Trim gaps. */
  95     while (impl->size && impl->vector[impl->size - 1].priority == INT_MIN) {
  96         impl->size = impl->size - 1;
  97     }
  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      * Clear in place, publish will sort and clean these off. */
 163     temp->vector[index].ptr = NULL;
 164     temp->vector[index].priority = INT_MIN;
 165 }
 166
 167 /* Change entry's 'priority' and keep the vector ordered. */
 168 void
 169 pvector_change_priority(struct pvector *pvec, void *ptr, int priority)
 170 {
 171     struct pvector_impl *old = pvec->temp;
 172     int index;
 173
 174     if (!old) {
 175         old = pvector_impl_get(pvec);
 176     }
 177
 178     index = pvector_impl_find(old, ptr);
 179
 180     ovs_assert(index >= 0);
 181     /* Now at the index of the entry to be updated. */
 182
 183     /* Check if can not update in place. */
 184     if ((priority > old->vector[index].priority && index > 0
 185          && priority > old->vector[index - 1].priority)
 186         || (priority < old->vector[index].priority && index < old->size - 1
 187             && priority < old->vector[index + 1].priority)) {
 188         /* Have to use a temp. */
 189         if (!pvec->temp) {
 190             /* Have to reallocate to reorder. */
 191             pvec->temp = pvector_impl_dup(old);
 192             old = pvec->temp;
 193             /* Publish will sort. */
 194         }
 195     }
 196     old->vector[index].priority = priority;
 197 }
 198
 199 /* Make the modified pvector available for iteration. */
 200 void pvector_publish__(struct pvector *pvec)
 201 {
 202     struct pvector_impl *temp = pvec->temp;
 203
 204     pvec->temp = NULL;
 205     pvector_impl_sort(temp); /* Also removes gaps. */
 206     ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector_impl *,
 207                                                &pvec->impl));
 208     ovsrcu_set(&pvec->impl, temp);
 209 }