RE: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash Tree

[lsahn]

> -----Original Message-----
> From: owner-linux-mm@xxxxxxxxx <owner-linux-mm@xxxxxxxxx> On Behalf Of
> JaeJoon Jung
> Sent: Wednesday, August 7, 2024 9:22 AM
> To: Greg Kroah-Hartman <gregkh@xxxxxxxxxxxxxxxxxxx>
> Cc: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>; Sasha Levin
> <levinsasha928@xxxxxxxxx>; Liam R . Howlett <Liam.Howlett@xxxxxxxxxx>;
> Matthew Wilcox <willy@xxxxxxxxxxxxx>; linux-kernel@xxxxxxxxxxxxxxx; linux-
> mm@xxxxxxxxx; maple-tree@xxxxxxxxxxxxxxxxxxx; linux-
> fsdevel@xxxxxxxxxxxxxxx
> Subject: Re: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash
> Tree

...
 
> The Hash Tree I implemented manages the Tree with the characteristic
> of a hash that is accessed in O(1).
> Even if the tree gets deeper, the search time does not increase.
> There is no rotation cost because the tree is kept balanced by hash key.

How does it keep balancing?