sort.c 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126
  1. #include <arm/NXP/LPC17xx/LPC17xx.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include "config.h"
  5. #include "uart.h"
  6. #include "memory.h"
  7. #include "sort.h"
  8. /*
  9. heap sort algorithm for data located outside RAM
  10. addr: start address of pointer table
  11. i: index (in 32-bit elements)
  12. heapsize: size of heap (in 32-bit elements)
  13. */
  14. uint32_t stat_getstring = 0;
  15. static char sort_str1[SORT_STRLEN+1], sort_str2[SORT_STRLEN+1];
  16. uint32_t ptrcache[QSORT_MAXELEM] IN_AHBRAM;
  17. /* get element from pointer table in external RAM*/
  18. uint32_t sort_get_elem(uint32_t base, unsigned int index) {
  19. return sram_readlong(base+4*index);
  20. }
  21. /* put element from pointer table in external RAM */
  22. void sort_put_elem(uint32_t base, unsigned int index, uint32_t elem) {
  23. sram_writelong(elem, base+4*index);
  24. }
  25. /* compare strings pointed to by elements of pointer table */
  26. int sort_cmp_idx(uint32_t base, unsigned int index1, unsigned int index2) {
  27. uint32_t elem1, elem2;
  28. elem1 = sort_get_elem(base, index1);
  29. elem2 = sort_get_elem(base, index2);
  30. return sort_cmp_elem((void*)&elem1, (void*)&elem2);
  31. }
  32. int sort_cmp_elem(const void* elem1, const void* elem2) {
  33. uint32_t el1 = *(uint32_t*)elem1;
  34. uint32_t el2 = *(uint32_t*)elem2;
  35. sort_getstring_for_dirent(sort_str1, el1);
  36. sort_getstring_for_dirent(sort_str2, el2);
  37. /*printf("i1=%d i2=%d elem1=%lx elem2=%lx ; compare %s --- %s\n", index1, index2, elem1, elem2, sort_str1, sort_str2); */
  38. if ((el1 & 0x80000000) && !(el2 & 0x80000000)) {
  39. return -1;
  40. }
  41. if (!(el1 & 0x80000000) && (el2 & 0x80000000)) {
  42. return 1;
  43. }
  44. if (*sort_str1 == '.') return -1;
  45. if (*sort_str2 == '.') return 1;
  46. /* Do not compare trailing slashes of directory names */
  47. if ((el1 & 0x80000000) && (el2 & 0x80000000)) {
  48. char *str1_slash = strrchr(sort_str1, '/');
  49. char *str2_slash = strrchr(sort_str2, '/');
  50. if(str1_slash != NULL) *str1_slash = 0;
  51. if(str2_slash != NULL) *str2_slash = 0;
  52. }
  53. return strcasecmp(sort_str1, sort_str2);
  54. }
  55. /* get truncated string from database */
  56. void sort_getstring_for_dirent(char *ptr, uint32_t addr) {
  57. uint8_t leaf_offset;
  58. if(addr & 0x80000000) {
  59. /* is directory link, name offset 4 */
  60. leaf_offset = sram_readbyte(addr + 4 + SRAM_MENU_ADDR);
  61. sram_readstrn(ptr, addr + 5 + leaf_offset + SRAM_MENU_ADDR, SORT_STRLEN);
  62. } else {
  63. /* is file link, name offset 6 */
  64. leaf_offset = sram_readbyte(addr + 6 + SRAM_MENU_ADDR);
  65. sram_readstrn(ptr, addr + 7 + leaf_offset + SRAM_MENU_ADDR, SORT_STRLEN);
  66. }
  67. }
  68. void sort_heapify(uint32_t addr, unsigned int i, unsigned int heapsize)
  69. {
  70. while(1) {
  71. unsigned int l = 2*i+1;
  72. unsigned int r = 2*i+2;
  73. unsigned int largest = (l < heapsize && sort_cmp_idx(addr, i, l) < 0) ? l : i;
  74. if(r < heapsize && sort_cmp_idx(addr, largest, r) < 0)
  75. largest = r;
  76. if(largest != i) {
  77. uint32_t tmp = sort_get_elem(addr, i);
  78. sort_put_elem(addr, i, sort_get_elem(addr, largest));
  79. sort_put_elem(addr, largest, tmp);
  80. i = largest;
  81. }
  82. else break;
  83. }
  84. }
  85. void sort_dir(uint32_t addr, unsigned int size)
  86. {
  87. stat_getstring=0;
  88. if(size > QSORT_MAXELEM) {
  89. printf("more than %d dir entries, doing slower in-place sort\n", QSORT_MAXELEM);
  90. ext_heapsort(addr, size);
  91. } else {
  92. /* retrieve, sort, and store dir table */
  93. sram_readblock(ptrcache, addr, size*4);
  94. qsort((void*)ptrcache, size, 4, sort_cmp_elem);
  95. sram_writeblock(ptrcache, addr, size*4);
  96. }
  97. }
  98. void ext_heapsort(uint32_t addr, unsigned int size) {
  99. for(unsigned int i = size/2; i > 0;) sort_heapify(addr, --i, size);
  100. for(unsigned int i = size-1; i>0; --i) {
  101. uint32_t tmp = sort_get_elem(addr, 0);
  102. sort_put_elem(addr, 0, sort_get_elem(addr, i));
  103. sort_put_elem(addr, i, tmp);
  104. sort_heapify(addr, 0, i);
  105. }
  106. }