1 /* 2 * Copyright © 2019 Manuel Stoeckl 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to deal in the Software without restriction, including 7 * without limitation the rights to use, copy, modify, merge, publish, 8 * distribute, sublicense, and/or sell copies of the Software, and to 9 * permit persons to whom the Software is furnished to do so, subject to 10 * the following conditions: 11 * 12 * The above copyright notice and this permission notice (including the 13 * next paragraph) shall be included in all copies or substantial 14 * portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 19 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 20 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 21 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 22 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23 * SOFTWARE. 24 */ 25 #ifndef WAYPIPE_INTERVAL_H 26 #define WAYPIPE_INTERVAL_H 27 28 #include <stdint.h> 29 30 /** A slight modification of the standard 'damage' rectangle 31 * formulation, written to be agnostic of whatever buffers 32 * underlie the system. 33 * 34 * [start,start+width),[start+stride,start+stride+width), 35 * ... [start+(rep-1)*stride,start+(rep-1)*stride+width) */ 36 struct ext_interval { 37 int32_t start; 38 /** Subinterval width */ 39 int32_t width; 40 /** Number of distinct subinterval start positions. For a single 41 * interval, this is one. */ 42 int32_t rep; 43 /** Spacing between start positions, should be > width, unless 44 * the is only one subinterval, in which case the value shouldn't 45 * matter and is conventionally set to 0. */ 46 int32_t stride; 47 }; 48 /** [start, end). (This is better than {start,width}, since width computations 49 * are rare and trivial, while merging code branches frequently off of 50 * endpoints) */ 51 struct interval { 52 int32_t start; 53 int32_t end; 54 }; 55 56 #define DAMAGE_EVERYTHING ((struct interval *)-1) 57 58 /** Interval-based damage tracking. If damage is NULL, there is 59 * no recorded damage. If damage is DAMAGE_EVERYTHING, the entire 60 * region should be updated. If ndamage_intvs > 0, then 61 * damage points to an array of struct interval objects. */ 62 struct damage { 63 struct interval *damage; 64 int ndamage_intvs; 65 66 int64_t acc_damage_stat; 67 int acc_count; 68 }; 69 70 /** Given an array of extended intervals, update the base damage structure 71 * so that it contains a reasonably small disjoint set of extended intervals 72 * which contains the old base set and the new set. Before merging, all 73 * interval boundaries will be rounded to the next multiple of 74 * `1 << alignment_bits`. */ 75 void merge_damage_records(struct damage *base, int nintervals, 76 const struct ext_interval *const new_list, int alignment_bits); 77 /** Set damage to empty */ 78 void reset_damage(struct damage *base); 79 /** Expand damage to cover everything */ 80 void damage_everything(struct damage *base); 81 82 /* internal merge driver, made visible for testing */ 83 void merge_mergesort(const int old_count, struct interval *old_list, 84 const int new_count, const struct ext_interval *const new_list, 85 int *dst_count, struct interval **dst_list, int merge_margin, 86 int alignment_bits); 87 88 #endif // WAYPIPE_INTERVAL_H 89