ceph/src/pmdk/src/libpmem2/ravl_interval.c

   1 // SPDX-License-Identifier: BSD-3-Clause
   2 /* Copyright 2020, Intel Corporation */
   3
   4 /*
   5  * ravl_interval.c -- ravl_interval implementation
   6  */
   7
   8 #include "alloc.h"
   9 #include "map.h"
  10 #include "ravl_interval.h"
  11 #include "pmem2_utils.h"
  12 #include "sys_util.h"
  13 #include "os_thread.h"
  14 #include "ravl.h"
  15
  16 /*
  17  * ravl_interval - structure representing two points
  18  *                 on the number line
  19  */
  20 struct ravl_interval {
  21         struct ravl *tree;
  22         ravl_interval_min *get_min;
  23         ravl_interval_max *get_max;
  24 };
  25
  26 /*
  27  * ravl_interval_node - structure holding min, max functions and address
  28  */
  29 struct ravl_interval_node {
  30         void *addr;
  31         ravl_interval_min *get_min;
  32         ravl_interval_max *get_max;
  33 };
  34
  35 /*
  36  * ravl_interval_compare -- compare intervals by its boundaries,
  37  *                          no overlapping allowed
  38  */
  39 static int
  40 ravl_interval_compare(const void *lhs, const void *rhs)
  41 {
  42         const struct ravl_interval_node *left = lhs;
  43         const struct ravl_interval_node *right = rhs;
  44
  45         if (left->get_max(left->addr) <= right->get_min(right->addr))
  46                 return -1;
  47         if (left->get_min(left->addr) >= right->get_max(right->addr))
  48                 return 1;
  49         return 0;
  50 }
  51
  52 /*
  53  * ravl_interval_delete - finalize the ravl interval module
  54  */
  55 void
  56 ravl_interval_delete(struct ravl_interval *ri)
  57 {
  58         ravl_delete(ri->tree);
  59         ri->tree = NULL;
  60         Free(ri);
  61 }
  62
  63 /*
  64  * ravl_interval_new -- initialize the ravl interval module
  65  */
  66 struct ravl_interval *
  67 ravl_interval_new(ravl_interval_min *get_min, ravl_interval_max *get_max)
  68 {
  69         int ret;
  70         struct ravl_interval *interval = pmem2_malloc(sizeof(*interval), &ret);
  71         if (ret)
  72                 goto ret_null;
  73
  74         interval->tree = ravl_new_sized(ravl_interval_compare,
  75                         sizeof(struct ravl_interval_node));
  76         if (!(interval->tree))
  77                 goto free_alloc;
  78
  79         interval->get_min = get_min;
  80         interval->get_max = get_max;
  81
  82         return interval;
  83
  84 free_alloc:
  85         Free(interval);
  86 ret_null:
  87         return NULL;
  88 }
  89
  90 /*
  91  * ravl_interval_insert -- insert interval entry into the tree
  92  */
  93 int
  94 ravl_interval_insert(struct ravl_interval *ri, void *addr)
  95 {
  96         struct ravl_interval_node rin;
  97         rin.addr = addr;
  98         rin.get_min = ri->get_min;
  99         rin.get_max = ri->get_max;
 100
 101         if (ravl_emplace_copy(ri->tree, &rin))
 102                 return PMEM2_E_ERRNO;
 103
 104         return 0;
 105 }
 106
 107 /*
 108  * ravl_interval_remove -- remove interval entry from the tree
 109  */
 110 int
 111 ravl_interval_remove(struct ravl_interval *ri, struct ravl_interval_node *rin)
 112 {
 113         struct ravl_node *node = ravl_find(ri->tree, rin,
 114                         RAVL_PREDICATE_EQUAL);
 115         if (!node)
 116                 return PMEM2_E_MAPPING_NOT_FOUND;
 117
 118         ravl_remove(ri->tree, node);
 119
 120         return 0;
 121 }
 122
 123 /*
 124  * ravl_interval_find_prior_or_eq -- find overlapping interval starting prior to
 125  *                                   the current one or at the same place
 126  */
 127 static struct ravl_interval_node *
 128 ravl_interval_find_prior_or_eq(struct ravl *tree,
 129                 struct ravl_interval_node *rin)
 130 {
 131         struct ravl_node *node;
 132         struct ravl_interval_node *cur;
 133
 134         node = ravl_find(tree, rin, RAVL_PREDICATE_LESS_EQUAL);
 135         if (!node)
 136                 return NULL;
 137
 138         cur = ravl_data(node);
 139         /*
 140          * If the end of the found interval is below the searched boundary, then
 141          * this is not our interval.
 142          */
 143         if (cur->get_max(cur->addr) <= rin->get_min(rin->addr))
 144                 return NULL;
 145
 146         return cur;
 147 }
 148
 149 /*
 150  * ravl_interval_find_later -- find overlapping interval starting later than
 151  *                             the current one
 152  */
 153 static struct ravl_interval_node *
 154 ravl_interval_find_later(struct ravl *tree, struct ravl_interval_node *rin)
 155 {
 156         struct ravl_node *node;
 157         struct ravl_interval_node *cur;
 158
 159         node = ravl_find(tree, rin, RAVL_PREDICATE_GREATER);
 160         if (!node)
 161                 return NULL;
 162
 163         cur = ravl_data(node);
 164
 165         /*
 166          * If the beginning of the found interval is above the end of
 167          * the searched range, then this is not our interval.
 168          */
 169         if (cur->get_min(cur->addr) >= rin->get_max(rin->addr))
 170                 return NULL;
 171
 172         return cur;
 173 }
 174
 175 /*
 176  * ravl_interval_find_equal -- find the interval with exact (min, max) range
 177  */
 178 struct ravl_interval_node *
 179 ravl_interval_find_equal(struct ravl_interval *ri, void *addr)
 180 {
 181         struct ravl_interval_node range;
 182         range.addr = addr;
 183         range.get_min = ri->get_min;
 184         range.get_max = ri->get_max;
 185
 186         struct ravl_node *node;
 187         node = ravl_find(ri->tree, &range, RAVL_PREDICATE_EQUAL);
 188         if (!node)
 189                 return NULL;
 190
 191         return ravl_data(node);
 192 }
 193
 194 /*
 195  * ravl_interval_find -- find the earliest interval within (min, max) range
 196  */
 197 struct ravl_interval_node *
 198 ravl_interval_find(struct ravl_interval *ri, void *addr)
 199 {
 200         struct ravl_interval_node range;
 201         range.addr = addr;
 202         range.get_min = ri->get_min;
 203         range.get_max = ri->get_max;
 204
 205         struct ravl_interval_node *cur;
 206         cur = ravl_interval_find_prior_or_eq(ri->tree, &range);
 207         if (!cur)
 208                 cur = ravl_interval_find_later(ri->tree, &range);
 209
 210         return cur;
 211 }
 212
 213 /*
 214  * ravl_interval_find_closest_prior -- find the closest interval
 215  *                                     neighbor prior to the current one
 216  */
 217 struct ravl_interval_node *
 218 ravl_interval_find_closest_prior(struct ravl_interval *ri, void *addr)
 219 {
 220         struct ravl_interval_node range;
 221         range.addr = addr;
 222         range.get_min = ri->get_min;
 223         range.get_max = ri->get_max;
 224
 225         struct ravl_node *node;
 226         node = ravl_find(ri->tree, &range, RAVL_PREDICATE_LESS);
 227         if (!node)
 228                 return NULL;
 229
 230         return ravl_data(node);
 231 }
 232
 233 /*
 234  * ravl_interval_find_closest_later -- find the closest interval neighbor
 235  *                                     that occurs after the current one
 236  */
 237 struct ravl_interval_node *
 238 ravl_interval_find_closest_later(struct ravl_interval *ri, void *addr)
 239 {
 240         struct ravl_interval_node range;
 241         range.addr = addr;
 242         range.get_min = ri->get_min;
 243         range.get_max = ri->get_max;
 244
 245         struct ravl_node *node;
 246         node = ravl_find(ri->tree, &range, RAVL_PREDICATE_GREATER);
 247         if (!node)
 248                 return NULL;
 249
 250         return ravl_data(node);
 251 }
 252
 253 /*
 254  * ravl_interval_data -- returns the data contained within an interval node
 255  */
 256 void *
 257 ravl_interval_data(struct ravl_interval_node *rin)
 258 {
 259         return (void *)rin->addr;
 260 }