ut0sort.h
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:3k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /**********************************************************************
  2. Sort utility
  3. (c) 1995 Innobase Oy
  4. Created 11/9/1995 Heikki Tuuri
  5. ***********************************************************************/
  6. #ifndef ut0sort_h
  7. #define ut0sort_h
  8. #include "univ.i"
  9. /* This module gives a macro definition of the body of
  10. a standard sort function for an array of elements of any
  11. type. The comparison function is given as a parameter to
  12. the macro. The sort algorithm is mergesort which has logarithmic
  13. worst case.
  14. */
  15. /***********************************************************************
  16. This macro expands to the body of a standard sort function.
  17. The sort function uses mergesort and must be defined separately
  18. for each type of array.
  19. Also the comparison function has to be defined individually
  20. for each array cell type. SORT_FUN is the sort function name.
  21. The function takes the array to be sorted (ARR),
  22. the array of auxiliary space (AUX_ARR) of same size,
  23. and the low (LOW), inclusive, and high (HIGH), noninclusive,
  24. limits for the sort interval as arguments.
  25. CMP_FUN is the comparison function name. It takes as arguments
  26. two elements from the array and returns 1, if the first is bigger,
  27. 0 if equal, and -1 if the second bigger. For an eaxmaple of use
  28. see test program in tsut.c. */
  29. #define UT_SORT_FUNCTION_BODY(SORT_FUN, ARR, AUX_ARR, LOW, HIGH, CMP_FUN)
  30. {
  31. ulint ut_sort_mid77;
  32. ulint ut_sort_i77;
  33. ulint ut_sort_low77;
  34. ulint ut_sort_high77;
  35.    ut_ad((LOW) < (HIGH));
  36.    ut_ad(ARR);
  37.    ut_ad(AUX_ARR);
  38.    if ((LOW) == (HIGH) - 1) {
  39.    return;
  40.    } else if ((LOW) == (HIGH) - 2) {
  41.    if (CMP_FUN((ARR)[LOW], (ARR)[(HIGH) - 1]) > 0) {
  42.    (AUX_ARR)[LOW] = (ARR)[LOW];
  43.    (ARR)[LOW] = (ARR)[(HIGH) - 1];
  44.    (ARR)[(HIGH) - 1] = (AUX_ARR)[LOW];
  45.    }
  46.    return;
  47.    }
  48. ut_sort_mid77 = ((LOW) + (HIGH)) / 2;
  49. SORT_FUN((ARR), (AUX_ARR), (LOW), ut_sort_mid77);
  50. SORT_FUN((ARR), (AUX_ARR), ut_sort_mid77, (HIGH));
  51. ut_sort_low77 = (LOW);
  52. ut_sort_high77 = ut_sort_mid77;
  53.    for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {
  54.    if (ut_sort_low77 >= ut_sort_mid77) {
  55.    (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];
  56.    ut_sort_high77++;
  57.    } else if (ut_sort_high77 >= (HIGH)) {
  58.    (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];
  59.    ut_sort_low77++;
  60.    } else if (CMP_FUN((ARR)[ut_sort_low77],
  61.    (ARR)[ut_sort_high77]) > 0) {
  62.    (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];
  63.    ut_sort_high77++;
  64. } else {
  65.    (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];
  66.    ut_sort_low77++;
  67. }
  68. }
  69.    for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {
  70.    (ARR)[ut_sort_i77] = (AUX_ARR)[ut_sort_i77];
  71.    }
  72. }
  73. #endif