sort.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169
  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. {
  20. return sram_readlong( base + 4 * index );
  21. }
  22. /* put element from pointer table in external RAM */
  23. void sort_put_elem( uint32_t base, unsigned int index, uint32_t elem )
  24. {
  25. sram_writelong( elem, base + 4 * index );
  26. }
  27. /* compare strings pointed to by elements of pointer table */
  28. int sort_cmp_idx( uint32_t base, unsigned int index1, unsigned int index2 )
  29. {
  30. uint32_t elem1, elem2;
  31. elem1 = sort_get_elem( base, index1 );
  32. elem2 = sort_get_elem( base, index2 );
  33. return sort_cmp_elem( ( void * )&elem1, ( void * )&elem2 );
  34. }
  35. int sort_cmp_elem( const void *elem1, const void *elem2 )
  36. {
  37. uint32_t el1 = *( uint32_t * )elem1;
  38. uint32_t el2 = *( uint32_t * )elem2;
  39. sort_getstring_for_dirent( sort_str1, el1 );
  40. sort_getstring_for_dirent( sort_str2, el2 );
  41. /*printf("i1=%d i2=%d elem1=%lx elem2=%lx ; compare %s --- %s\n", index1, index2, elem1, elem2, sort_str1, sort_str2); */
  42. if ( ( el1 & 0x80000000 ) && !( el2 & 0x80000000 ) )
  43. {
  44. return -1;
  45. }
  46. if ( !( el1 & 0x80000000 ) && ( el2 & 0x80000000 ) )
  47. {
  48. return 1;
  49. }
  50. if ( *sort_str1 == '.' )
  51. {
  52. return -1;
  53. }
  54. if ( *sort_str2 == '.' )
  55. {
  56. return 1;
  57. }
  58. /* Do not compare trailing slashes of directory names */
  59. if ( ( el1 & 0x80000000 ) && ( el2 & 0x80000000 ) )
  60. {
  61. char *str1_slash = strrchr( sort_str1, '/' );
  62. char *str2_slash = strrchr( sort_str2, '/' );
  63. if ( str1_slash != NULL )
  64. {
  65. *str1_slash = 0;
  66. }
  67. if ( str2_slash != NULL )
  68. {
  69. *str2_slash = 0;
  70. }
  71. }
  72. return strcasecmp( sort_str1, sort_str2 );
  73. }
  74. /* get truncated string from database */
  75. void sort_getstring_for_dirent( char *ptr, uint32_t addr )
  76. {
  77. uint8_t leaf_offset;
  78. if ( addr & 0x80000000 )
  79. {
  80. /* is directory link, name offset 4 */
  81. leaf_offset = sram_readbyte( addr + 4 + SRAM_MENU_ADDR );
  82. sram_readstrn( ptr, addr + 5 + leaf_offset + SRAM_MENU_ADDR, SORT_STRLEN );
  83. }
  84. else
  85. {
  86. /* is file link, name offset 6 */
  87. leaf_offset = sram_readbyte( addr + 6 + SRAM_MENU_ADDR );
  88. sram_readstrn( ptr, addr + 7 + leaf_offset + SRAM_MENU_ADDR, SORT_STRLEN );
  89. }
  90. }
  91. void sort_heapify( uint32_t addr, unsigned int i, unsigned int heapsize )
  92. {
  93. while ( 1 )
  94. {
  95. unsigned int l = 2 * i + 1;
  96. unsigned int r = 2 * i + 2;
  97. unsigned int largest = ( l < heapsize && sort_cmp_idx( addr, i, l ) < 0 ) ? l : i;
  98. if ( r < heapsize && sort_cmp_idx( addr, largest, r ) < 0 )
  99. {
  100. largest = r;
  101. }
  102. if ( largest != i )
  103. {
  104. uint32_t tmp = sort_get_elem( addr, i );
  105. sort_put_elem( addr, i, sort_get_elem( addr, largest ) );
  106. sort_put_elem( addr, largest, tmp );
  107. i = largest;
  108. }
  109. else
  110. {
  111. break;
  112. }
  113. }
  114. }
  115. void sort_dir( uint32_t addr, unsigned int size )
  116. {
  117. stat_getstring = 0;
  118. if ( size > QSORT_MAXELEM )
  119. {
  120. printf( "more than %d dir entries, doing slower in-place sort\n", QSORT_MAXELEM );
  121. ext_heapsort( addr, size );
  122. }
  123. else
  124. {
  125. /* retrieve, sort, and store dir table */
  126. sram_readblock( ptrcache, addr, size * 4 );
  127. qsort( ( void * )ptrcache, size, 4, sort_cmp_elem );
  128. sram_writeblock( ptrcache, addr, size * 4 );
  129. }
  130. }
  131. void ext_heapsort( uint32_t addr, unsigned int size )
  132. {
  133. for ( unsigned int i = size / 2; i > 0; )
  134. {
  135. sort_heapify( addr, --i, size );
  136. }
  137. for ( unsigned int i = size - 1; i > 0; --i )
  138. {
  139. uint32_t tmp = sort_get_elem( addr, 0 );
  140. sort_put_elem( addr, 0, sort_get_elem( addr, i ) );
  141. sort_put_elem( addr, i, tmp );
  142. sort_heapify( addr, 0, i );
  143. }
  144. }