Method and apparatus for a hardware-implemented AVL tree module
US10095765B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 4, 2014 |
| Grant date | Oct 9, 2018 |
| Priority date | — |
| Expiry date | May 21, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/28
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present disclosure describes techniques and apparatuses for a hardware-implemented Adelson-Velskii and Landis' (AVL) tree module. In some aspects, commands are received at the AVL tree module that request operations be performed for an AVL tree table stored in memory. Each command is written to one of multiple hardware threads of the AVL tree module that perform AVL tree operations by causing records of the AVL tree table to be read from memory using a single read operation and then written to the AVL tree module, modifying those records without accessing memory, and causing modified records to be written back to memory using a single write operation. Once a command is written to a hardware thread, the hardware thread can perform the corresponding AVL tree operation. After the AVL tree operation is performed, results are returned to the requesting agent to indicate whether the AVL tree operation was performed successfully.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.