codegen_c_sort.c (7351B)
1 #include "codegen_c_sort.h" 2 3 /* 4 * We choose heapsort because it is about as fast as quicksort, avoids 5 * recursion, the code is compact which makes it practical to specialize for 6 * different vector types, it can sort the flatbuffer arrays in-place, 7 * and it has only a few places with comparisons. Furthermore, heapsort 8 * has worst case (n log n) upperbound where quicksort has O(n^2) which 9 * is an attack vector, and could be a problem with large datasets 10 * The sort is not stable. 11 * 12 * Some arguments are similar to those of the __%sfind_by_field macro. 13 * 14 * NS: The namespace 15 * N: the name of the vector type 16 * X: the name suffix when there are multiple sorts for same vector type. 17 * E: Element accessor (elem = E(vector, index)). 18 * L: Vector length. 19 * A: Field accessor (or the identity function), result must match the diff function D. 20 * TK: The scalar, enum or string key type, (either the element, or a field of the element). 21 * TE: The raw element type - uoffset_t for tables and strings. 22 * for swap. 23 * D: The diff function, but unlike __find_by_field, the second 24 * argument is returned by A, not a search key, and there is no third argument. 25 * S: Swap operation - must handle offset change when offset elements are moved. 26 */ 27 28 int gen_sort(fb_output_t *out) 29 { 30 fprintf(out->fp, 31 "#define __%sheap_sort(N, X, A, E, L, TK, TE, D, S)\\\n" 32 "static inline void __ ## N ## X ## __heap_sift_down(\\\n" 33 " N ## _mutable_vec_t vec__tmp, size_t start__tmp, size_t end__tmp)\\\n" 34 "{ size_t child__tmp, root__tmp; TK v1__tmp, v2__tmp, vroot__tmp;\\\n" 35 " root__tmp = start__tmp;\\\n" 36 " while ((root__tmp << 1) <= end__tmp) {\\\n" 37 " child__tmp = root__tmp << 1;\\\n" 38 " if (child__tmp < end__tmp) {\\\n" 39 " v1__tmp = A(E(vec__tmp, child__tmp));\\\n" 40 " v2__tmp = A(E(vec__tmp, child__tmp + 1));\\\n" 41 " if (D(v1__tmp, v2__tmp) < 0) {\\\n" 42 " child__tmp++;\\\n" 43 " }\\\n" 44 " }\\\n" 45 " vroot__tmp = A(E(vec__tmp, root__tmp));\\\n" 46 " v1__tmp = A(E(vec__tmp, child__tmp));\\\n" 47 " if (D(vroot__tmp, v1__tmp) < 0) {\\\n" 48 " S(vec__tmp, root__tmp, child__tmp, TE);\\\n" 49 " root__tmp = child__tmp;\\\n" 50 " } else {\\\n" 51 " return;\\\n" 52 " }\\\n" 53 " }\\\n" 54 "}\\\n" 55 "static inline void __ ## N ## X ## __heap_sort(N ## _mutable_vec_t vec__tmp)\\\n" 56 "{ size_t start__tmp, end__tmp, size__tmp;\\\n" 57 " size__tmp = L(vec__tmp); if (size__tmp == 0) return; end__tmp = size__tmp - 1; start__tmp = size__tmp >> 1;\\\n" 58 " do { __ ## N ## X ## __heap_sift_down(vec__tmp, start__tmp, end__tmp); } while (start__tmp--);\\\n" 59 " while (end__tmp > 0) { \\\n" 60 " S(vec__tmp, 0, end__tmp, TE);\\\n" 61 " __ ## N ## X ## __heap_sift_down(vec__tmp, 0, --end__tmp); } }\n", 62 out->nsc); 63 fprintf(out->fp, 64 "#define __%sdefine_sort_by_field(N, NK, TK, TE, D, S)\\\n" 65 " __%sheap_sort(N, _sort_by_ ## NK, N ## _ ## NK ## _get, N ## _vec_at, N ## _vec_len, TK, TE, D, S)\\\n" 66 "static inline void N ## _vec_sort_by_ ## NK(N ## _mutable_vec_t vec__tmp)\\\n" 67 "{ __ ## N ## _sort_by_ ## NK ## __heap_sort(vec__tmp); }\n", 68 out->nsc, out->nsc); 69 fprintf(out->fp, 70 "#define __%sdefine_sort(N, TK, TE, D, S)\\\n" 71 "__%sheap_sort(N, , __%sidentity, N ## _vec_at, N ## _vec_len, TK, TE, D, S)\\\n" 72 "static inline void N ## _vec_sort(N ## _mutable_vec_t vec__tmp) { __ ## N ## __heap_sort(vec__tmp); }\n", 73 out->nsc, out->nsc, out->nsc); 74 fprintf(out->fp, 75 /* Subtractions doesn't work for unsigned types. */ 76 "#define __%sscalar_diff(x, y) ((x) < (y) ? -1 : (x) > (y))\n" 77 "#define __%sstring_diff(x, y) __%sstring_n_cmp((x), (const char *)(y), %sstring_len(y))\n", 78 out->nsc, out->nsc, out->nsc, out->nsc); 79 fprintf(out->fp, 80 "#define __%svalue_swap(vec, a, b, TE) { TE x__tmp = vec[b]; vec[b] = vec[a]; vec[a] = x__tmp; }\n" 81 "#define __%suoffset_swap(vec, a, b, TE)\\\n" 82 "{ TE ta__tmp, tb__tmp, d__tmp;\\\n" 83 " d__tmp = (TE)((a - b) * sizeof(vec[0]));\\\n" 84 " ta__tmp = __flatbuffers_uoffset_read_from_pe(vec + b) - d__tmp;\\\n" 85 " tb__tmp = __flatbuffers_uoffset_read_from_pe(vec + a) + d__tmp;\\\n" 86 " __flatbuffers_uoffset_write_to_pe(vec + a, ta__tmp);\\\n" 87 " __flatbuffers_uoffset_write_to_pe(vec + b, tb__tmp); }\n", 88 out->nsc, out->nsc); 89 fprintf(out->fp, 90 "#define __%sscalar_swap(vec, a, b, TE) __%svalue_swap(vec, a, b, TE)\n", 91 out->nsc, out->nsc); 92 fprintf(out->fp, 93 "#define __%sstring_swap(vec, a, b, TE) __%suoffset_swap(vec, a, b, TE)\n", 94 out->nsc, out->nsc); 95 fprintf(out->fp, 96 "#define __%sstruct_swap(vec, a, b, TE) __%svalue_swap(vec, a, b, TE)\n", 97 out->nsc, out->nsc); 98 fprintf(out->fp, 99 "#define __%stable_swap(vec, a, b, TE) __%suoffset_swap(vec, a, b, TE)\n", 100 out->nsc, out->nsc); 101 fprintf(out->fp, 102 "#define __%sdefine_struct_sort_by_scalar_field(N, NK, TK, TE)\\\n" 103 " __%sdefine_sort_by_field(N, NK, TK, TE, __%sscalar_diff, __%sstruct_swap)\n", 104 out->nsc, out->nsc, out->nsc, out->nsc); 105 fprintf(out->fp, 106 "#define __%sdefine_table_sort_by_scalar_field(N, NK, TK)\\\n" 107 " __%sdefine_sort_by_field(N, NK, TK, %suoffset_t, __%sscalar_diff, __%stable_swap)\n", 108 out->nsc, out->nsc, out->nsc, out->nsc, out->nsc); 109 fprintf(out->fp, 110 "#define __%sdefine_table_sort_by_string_field(N, NK)\\\n" 111 " __%sdefine_sort_by_field(N, NK, %sstring_t, %suoffset_t, __%sstring_diff, __%stable_swap)\n", 112 out->nsc, out->nsc, out->nsc, out->nsc, out->nsc, out->nsc); 113 fprintf(out->fp, 114 "#define __%sdefine_scalar_sort(N, T) __%sdefine_sort(N, T, T, __%sscalar_diff, __%sscalar_swap)\n", 115 out->nsc, out->nsc, out->nsc, out->nsc); 116 fprintf(out->fp, 117 "#define __%sdefine_string_sort() __%sdefine_sort(%sstring, %sstring_t, %suoffset_t, __%sstring_diff, __%sstring_swap)\n", 118 out->nsc, out->nsc, out->nsc, out->nsc, out->nsc, out->nsc, out->nsc); 119 return 0; 120 } 121 122 /* reference implementation */ 123 #if 0 124 125 /* from github swenson/sort */ 126 /* heap sort: based on wikipedia */ 127 static __inline void HEAP_SIFT_DOWN(SORT_TYPE *dst, const int64_t start, const int64_t end) { 128 int64_t root = start; 129 130 while ((root << 1) <= end) { 131 int64_t child = root << 1; 132 133 if ((child < end) && (SORT_CMP(dst[child], dst[child + 1]) < 0)) { 134 child++; 135 } 136 137 if (SORT_CMP(dst[root], dst[child]) < 0) { 138 SORT_SWAP(dst[root], dst[child]); 139 root = child; 140 } else { 141 return; 142 } 143 } 144 } 145 146 static __inline void HEAPIFY(SORT_TYPE *dst, const size_t size) { 147 int64_t start = size >> 1; 148 149 while (start >= 0) { 150 HEAP_SIFT_DOWN(dst, start, size - 1); 151 start--; 152 } 153 } 154 155 void HEAP_SORT(SORT_TYPE *dst, const size_t size) { 156 /* don't bother sorting an array of size 0 */ 157 if (size == 0) { 158 return; 159 } 160 161 int64_t end = size - 1; 162 HEAPIFY(dst, size); 163 164 while (end > 0) { 165 SORT_SWAP(dst[end], dst[0]); 166 HEAP_SIFT_DOWN(dst, 0, end - 1); 167 end--; 168 } 169 } 170 171 #endif