Page 187 - ARM 64 Bit Assembly Language

174 Chapter 6

Figure 6.2: Binary tree of word frequencies with index added.

6.2.3 Indexing and sorting by frequency

With the tree implementation, wl_print_numerical could build a new tree, sorted on the
word frequency counts. However, it may be more efficient to build a separate index, and sort
the index by word frequency counts. The assembly code will allocate an array of pointers,
and set each pointer to one of the nodes in the tree, as shown in Fig. 6.2. Then, it will use a
quicksort to rearrange the pointers into descending order by word frequency count, as shown
in Fig. 6.3. This implementation is shown in Listing 6.11.
Listing 6.11 AArch64 assembly implementation of wl_print_numerical with a tree.

1 ### Definitions for the wordlistnode type
2 .equ wln_word, 0 // word field
3 .equ wln_count, 8 // count filed
4 .equ wln_left, 16 // left field
5 .equ wln_right, 24 // right field
6 .equ wln_height, 32 // height of this node
7 .equ wln_size, 40 // sizeof(wordlistnode)
8 ### Definitions for the wordlist type