1 /* Copyright (c) 2010, 2017, Oracle and/or its affiliates. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License, version 2.0, 5 as published by the Free Software Foundation. 6 7 This program is also distributed with certain software (including 8 but not limited to OpenSSL) that is licensed under separate terms, 9 as designated in a particular file or component or in included license 10 documentation. The authors of MySQL hereby grant you an additional 11 permission to link the program and your derivative works with the 12 separately licensed software that they have included with MySQL. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License, version 2.0, for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ 22 23 #ifndef XDR_UTILS_H 24 #define XDR_UTILS_H 25 26 #ifdef __cplusplus 27 extern "C" { 28 #endif 29 30 #include <assert.h> 31 32 /** 33 Initialize an array 34 */ 35 #define def_init_xdr_array(name) static inline void init_##name##_array(name##_array *x) 36 #define init_xdr_array(name) \ 37 def_init_xdr_array(name) { \ 38 x->name##_array_len = 2; \ 39 x->name##_array_val = calloc((size_t)x->name##_array_len, sizeof(name)); \ 40 } 41 42 /** 43 Free the contents of an array 44 */ 45 #define def_free_xdr_array(name) static inline void free_##name##_array(name##_array *x) 46 #define free_xdr_array(name)\ 47 def_free_xdr_array(name)\ 48 {\ 49 free(x->name##_array_val);\ 50 x->name##_array_val = 0;\ 51 x->name##_array_len = 0;\ 52 } 53 54 #define in_range(x, name, n) ((n) >= 0 && (n) < ((x).name##_array_len)) 55 56 /** 57 Resize an array 58 */ 59 #define expand_xdr_array(name) \ 60 u_int old_length = x->name##_array_len; \ 61 if(n+1 > (x->name##_array_len)){ \ 62 if(x->name##_array_len == 0) x->name##_array_len = 1; \ 63 do{x->name##_array_len *= 2;}while( n+1 > (x->name##_array_len)); \ 64 x->name##_array_val = realloc(x->name##_array_val,x->name##_array_len*sizeof(name)); \ 65 memset(&x->name##_array_val[old_length], 0, (x->name##_array_len-old_length) * sizeof(name)); \ 66 } 67 68 /** 69 Define a set function for an array 70 */ 71 #define def_set_xdr_array(name) \ 72 static inline void set_##name(name##_array *x, name a, u_int n) 73 #define set_xdr_array(name) \ 74 def_set_xdr_array(name) { \ 75 expand_xdr_array(name); \ 76 assert(n < x->name##_array_len); \ 77 x->name##_array_val[n] = a; \ 78 } 79 80 /** 81 Define a get function for an array 82 */ 83 #define def_get_xdr_array(name) static inline name get_##name(name##_array *x, u_int n) 84 #define get_xdr_array(name) \ 85 def_get_xdr_array(name) \ 86 { \ 87 expand_xdr_array(name); \ 88 assert(n < x->name##_array_len); \ 89 return x->name##_array_val[n]; \ 90 } 91 92 93 /** 94 Define a function to clone an array 95 */ 96 #define def_clone_xdr_array(name) \ 97 static inline name##_array clone_##name##_array(name##_array x) 98 #define clone_xdr_array(name) \ 99 def_clone_xdr_array(name) { \ 100 name##_array retval = x; \ 101 u_int i; \ 102 retval.name##_array_len = x.name##_array_len; \ 103 DBGOUT(FN; STRLIT("clone_xdr_array"); NDBG(retval.name##_array_len, u)); \ 104 if (retval.name##_array_len > 0) { \ 105 retval.name##_array_val = \ 106 calloc((size_t)x.name##_array_len, sizeof(name)); \ 107 for (i = 0; i < retval.name##_array_len; i++) { \ 108 retval.name##_array_val[i] = x.name##_array_val[i]; \ 109 DBGOUT(FN; STRLIT("clone_xdr_array"); NDBG(i, u)); \ 110 } \ 111 } else { \ 112 retval.name##_array_val = 0; \ 113 } \ 114 return retval; \ 115 } 116 117 /** 118 Declare all functions for an array 119 */ 120 #define d_xdr_funcs(name)\ 121 def_init_xdr_array(name); \ 122 def_free_xdr_array(name); \ 123 def_set_xdr_array(name); \ 124 def_get_xdr_array(name); \ 125 def_clone_xdr_array(name); 126 127 /** 128 Define all functions for an array 129 */ 130 #define define_xdr_funcs(name) \ 131 init_xdr_array(name) \ 132 free_xdr_array(name) \ 133 set_xdr_array(name) \ 134 get_xdr_array(name) \ 135 clone_xdr_array(name) 136 137 /** 138 Macro to do insertion sort 139 */ 140 #define insert_sort(type,x,n) { \ 141 int i,j; \ 142 for(i = 1; i < n; i++){ /* x[0..i-1] is sorted */ \ 143 type tmp; \ 144 j = i; \ 145 tmp = x[j]; \ 146 while(j > 0 && insert_sort_gt(x[j-1], tmp)){ \ 147 x[j] = x[j-1]; \ 148 j--; \ 149 } \ 150 x[j] = tmp; \ 151 } \ 152 } 153 154 /** 155 Macro to do binary search for first occurence 156 157 Invariant: x[l] < key and x[u] >= key and l < u 158 */ 159 #define bin_search_first_body(x,first,last,key,p) \ 160 int l = first-1; \ 161 int u = last+1; \ 162 int m = 0; \ 163 while(l+1 != u){ \ 164 m = (l+u)/2; \ 165 if(bin_search_lt((x)[m],(key))){ \ 166 l = m; \ 167 }else{ \ 168 u = m; \ 169 } \ 170 } 171 172 /** 173 Macro to do binary search for last occurence. 174 175 Invariant: x[l] <= key and x[u] > key and l < u 176 */ 177 #define bin_search_last_body(x,first,last,key,p) \ 178 int l = first-1; \ 179 int u = last+1; \ 180 int m = 0; \ 181 while(l+1 != u){ \ 182 m = (l+u)/2; \ 183 if(bin_search_gt((x)[m],(key))){ \ 184 u = m; \ 185 }else{ \ 186 l = m; \ 187 } \ 188 } 189 190 /** 191 Find first element which matches key 192 */ 193 #define bin_search_first(x,first,last,key,p) { \ 194 bin_search_first_body(x,first,last,key,p); \ 195 p = u; \ 196 if(p > last || (! bin_search_eq((x)[p],(key)))) p = -1; \ 197 } 198 199 /** 200 Find first element which is greater than key 201 */ 202 #define bin_search_first_gt(x,first,last,key,p) { \ 203 bin_search_last_body(x,first,last,key,p); \ 204 p = u; \ 205 if(p > last || (! bin_search_gt((x)[p],(key)))) p = -1; \ 206 } 207 208 /** 209 Find last element which matches key 210 */ 211 #define bin_search_last(x,first,last,key,p) { \ 212 bin_search_last_body(x,first,last,key,p); \ 213 p = l; \ 214 if(p < first || (! bin_search_eq((x)[p],(key)))) p = -1; \ 215 } 216 217 /** 218 Find first element which is less than key 219 */ 220 #define bin_search_last_lt(x,first,last,key,p) { \ 221 bin_search_first_body(x,first,last,key,p); \ 222 p = l; \ 223 if(p < first || (! bin_search_lt((x)[p],(key)))) p = -1; \ 224 } 225 226 #define diff_get(type,a,i) get_##type##_array(a,i) 227 #define diff_output(type,x) set_##type##_array(&retval,x,retval_i++) 228 #define diff_gt(x,y) insert_sort_gt(x,y) 229 230 /** 231 Macro to compute diff of two arrays, which as a side effect will 232 be sorted after the operation has completed. 233 */ 234 #define diff_xdr_array(type, x, y) \ 235 type##_array diff_##type##_array(type##_array x, type##_array y) \ 236 { \ 237 int x_i = 0; \ 238 int y_i = 0; \ 239 type retval; \ 240 int retval_i = 0; \ 241 init_##type##_array(&retval); \ 242 insert_sort(type, x.type##_val, x.type##_len); \ 243 insert_sort(type, y.type##_val, y.type##_len); \ 244 while(x_i < x.type##_len && y < y.type##_len){ \ 245 if(diff_eq(diff_get(type,x, x_i), diff_get(type,y,y_i))){ \ 246 x_i++; \ 247 y_i++; \ 248 }else if(diff_lt(diff_get(type,x,x_i), diff_get(type,y,y_i))){ \ 249 diff_output(type,diff_get(type,x,x_i++)); \ 250 }else{ \ 251 diff_output(type,diff_get(type,y,y_i++)); \ 252 } \ 253 } \ 254 while(x_i < x.type##_len){ \ 255 diff_output(type,diff_get(type,x,x_i++)); \ 256 } \ 257 while(y_i < y.type##_len){ \ 258 diff_output(type,diff_get(type,y,y_i++)); \ 259 } \ 260 retval.type##_len = retval_i; \ 261 return retval; \ 262 } 263 264 /* {{{ Reverse elements n1..n2 */ 265 266 #define x_reverse(type, x, in_n1, in_n2) \ 267 { \ 268 int n1 = in_n1; \ 269 int n2 = in_n2; \ 270 while((n1) < (n2)){ \ 271 type tmp = (x)[n1]; \ 272 (x)[n1] = (x)[n2]; \ 273 (x)[n2] = tmp; \ 274 (n1)++; \ 275 (n2)--; \ 276 } \ 277 } 278 279 /* }}} */ 280 281 /* {{{ Move elements n1..n2 to after n3 */ 282 283 #define x_blkmove(type, x, n1, n2, n3) \ 284 { \ 285 if((n3) < (n1)-1){ \ 286 x_reverse(type, (x), (n3)+1, (n1)-1); \ 287 x_reverse(type, (x), (n1), (n2)); \ 288 x_reverse(type, (x), (n3)+1, (n2)); \ 289 }else if((n3) > (n2)){ \ 290 x_reverse(type, (x), (n1), (n2)); \ 291 x_reverse(type, (x), (n2)+1, (n3)); \ 292 x_reverse(type, (x), (n1), (n3)); \ 293 } \ 294 } 295 296 /* }}} */ 297 298 299 300 #ifdef __cplusplus 301 } 302 #endif 303 304 #endif 305 306