123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169 |
- #include <arm/NXP/LPC17xx/LPC17xx.h>
- #include <string.h>
- #include <stdlib.h>
- #include "config.h"
- #include "uart.h"
- #include "memory.h"
- #include "sort.h"
- /*
- heap sort algorithm for data located outside RAM
- addr: start address of pointer table
- i: index (in 32-bit elements)
- heapsize: size of heap (in 32-bit elements)
- */
- uint32_t stat_getstring = 0;
- static char sort_str1[SORT_STRLEN + 1], sort_str2[SORT_STRLEN + 1];
- uint32_t ptrcache[QSORT_MAXELEM] IN_AHBRAM;
- /* get element from pointer table in external RAM*/
- uint32_t sort_get_elem( uint32_t base, unsigned int index )
- {
- return sram_readlong( base + 4 * index );
- }
- /* put element from pointer table in external RAM */
- void sort_put_elem( uint32_t base, unsigned int index, uint32_t elem )
- {
- sram_writelong( elem, base + 4 * index );
- }
- /* compare strings pointed to by elements of pointer table */
- int sort_cmp_idx( uint32_t base, unsigned int index1, unsigned int index2 )
- {
- uint32_t elem1, elem2;
- elem1 = sort_get_elem( base, index1 );
- elem2 = sort_get_elem( base, index2 );
- return sort_cmp_elem( ( void * )&elem1, ( void * )&elem2 );
- }
- int sort_cmp_elem( const void *elem1, const void *elem2 )
- {
- uint32_t el1 = *( uint32_t * )elem1;
- uint32_t el2 = *( uint32_t * )elem2;
- sort_getstring_for_dirent( sort_str1, el1 );
- sort_getstring_for_dirent( sort_str2, el2 );
- /*printf("i1=%d i2=%d elem1=%lx elem2=%lx ; compare %s --- %s\n", index1, index2, elem1, elem2, sort_str1, sort_str2); */
- if ( ( el1 & 0x80000000 ) && !( el2 & 0x80000000 ) )
- {
- return -1;
- }
- if ( !( el1 & 0x80000000 ) && ( el2 & 0x80000000 ) )
- {
- return 1;
- }
- if ( *sort_str1 == '.' )
- {
- return -1;
- }
- if ( *sort_str2 == '.' )
- {
- return 1;
- }
- /* Do not compare trailing slashes of directory names */
- if ( ( el1 & 0x80000000 ) && ( el2 & 0x80000000 ) )
- {
- char *str1_slash = strrchr( sort_str1, '/' );
- char *str2_slash = strrchr( sort_str2, '/' );
- if ( str1_slash != NULL )
- {
- *str1_slash = 0;
- }
- if ( str2_slash != NULL )
- {
- *str2_slash = 0;
- }
- }
- return strcasecmp( sort_str1, sort_str2 );
- }
- /* get truncated string from database */
- void sort_getstring_for_dirent( char *ptr, uint32_t addr )
- {
- uint8_t leaf_offset;
- if ( addr & 0x80000000 )
- {
- /* is directory link, name offset 4 */
- leaf_offset = sram_readbyte( addr + 4 + SRAM_MENU_ADDR );
- sram_readstrn( ptr, addr + 5 + leaf_offset + SRAM_MENU_ADDR, SORT_STRLEN );
- }
- else
- {
- /* is file link, name offset 6 */
- leaf_offset = sram_readbyte( addr + 6 + SRAM_MENU_ADDR );
- sram_readstrn( ptr, addr + 7 + leaf_offset + SRAM_MENU_ADDR, SORT_STRLEN );
- }
- }
- void sort_heapify( uint32_t addr, unsigned int i, unsigned int heapsize )
- {
- while ( 1 )
- {
- unsigned int l = 2 * i + 1;
- unsigned int r = 2 * i + 2;
- unsigned int largest = ( l < heapsize && sort_cmp_idx( addr, i, l ) < 0 ) ? l : i;
- if ( r < heapsize && sort_cmp_idx( addr, largest, r ) < 0 )
- {
- largest = r;
- }
- if ( largest != i )
- {
- uint32_t tmp = sort_get_elem( addr, i );
- sort_put_elem( addr, i, sort_get_elem( addr, largest ) );
- sort_put_elem( addr, largest, tmp );
- i = largest;
- }
- else
- {
- break;
- }
- }
- }
- void sort_dir( uint32_t addr, unsigned int size )
- {
- stat_getstring = 0;
- if ( size > QSORT_MAXELEM )
- {
- printf( "more than %d dir entries, doing slower in-place sort\n", QSORT_MAXELEM );
- ext_heapsort( addr, size );
- }
- else
- {
- /* retrieve, sort, and store dir table */
- sram_readblock( ptrcache, addr, size * 4 );
- qsort( ( void * )ptrcache, size, 4, sort_cmp_elem );
- sram_writeblock( ptrcache, addr, size * 4 );
- }
- }
- void ext_heapsort( uint32_t addr, unsigned int size )
- {
- for ( unsigned int i = size / 2; i > 0; )
- {
- sort_heapify( addr, --i, size );
- }
- for ( unsigned int i = size - 1; i > 0; --i )
- {
- uint32_t tmp = sort_get_elem( addr, 0 );
- sort_put_elem( addr, 0, sort_get_elem( addr, i ) );
- sort_put_elem( addr, i, tmp );
- sort_heapify( addr, 0, i );
- }
- }
|