Algebra Integral
HomepageSocialsIntegrate
  • Overview / FAQ
    • 💡What is Algebra?
    • 🫂The Algebra Ecosystem
    • 🧑‍🔬Algebra Integral
    • 📚Glossary
    • 🪙Tokenomics
    • 📱Social Media & Links
    • 👨‍🎨Brand Assets
    • Partners
      • Algebra V1.0
        • QuickSwap Polygon
        • ZyberSwap
        • Thena
        • StellaSwap
        • QuickSwap Dogechain
        • SkullSwap
        • UbeSwap
        • Litx
      • Algebra V1.9
        • Camelot
        • Lynex
        • Swapbased
        • Synthswap
        • Zyberswap Optimism
        • Hercules
      • Integral 1.0
        • Swapsicle Telos
        • Swapsicle Mantle
        • Kim
        • Fenix
        • Blade
        • SilverSwap Fantom
        • Horizon
        • Glyph Exchange
        • SilverSwap Sonic
        • SwapX
        • Bulla
      • Integral 1.1
        • Scribe
      • Integral 1.2
        • Fibonacci
        • Voltage
        • Henjin
        • Wasabee
        • Holiverse
        • MorFi
        • StellaSwap
        • QuickSwap Soneium
  • Algebra Integral / Technical Reference
    • ℹ️Intro
    • 🔍Audits
    • 🏗️Integration Process
      • Specification and API of contracts
        • Algebra Pool
        • Algebra Factory
        • Swap Router
        • Nonfungible Position Manager
        • Quoter
        • QuoterV2
        • TickLens
      • Interaction with pools
        • Getting data from pools
      • Subgraphs and analytics
        • Examples of queries
      • Technical Guides
        • Intro
        • Swaps
          • Single swaps
          • Multihop swaps
        • Providing liquidity
          • Setting up your contract
          • Mint a new position
          • Collect fees
          • Decrease liquidity
          • Increase liquidity
          • Final Contract
        • Flashloans
          • Setting up your contract
          • Calling flash
          • Flash callback
          • Final contract
      • Migration from UniswapV3
    • 🖲️Core Logic
      • Pool overview
      • Swap calculation
      • Liquidity and positions
      • Ticks
        • Ticks search tree
      • Reserves
      • Flash
      • Plugins
      • AlgebraFactory and roles
    • 🧩Plugins
      • Overview
      • Adaptive Fee
      • Sliding Fee
      • Whitelist Discount Fee
      • Safety Switch
      • Position Limit Orders
      • Managed Swap Fee
      • FAQ
    • 📖Guides
      • 🔨Plugin Development
      • 🔬Plugin Testing
      • ☄️Plugin Deployment
    • ⬆️Changes V1
    • ⬆️Changes V1.1
    • ⬆️Changes v1.2
  • ⬆️Changes v1.2.1
  • Algebra V1 / Technical Reference
    • 🔏Contracts
      • API Reference v1.0
        • V1.0 - Core
          • AlgebraFactory
          • AlgebraPool
          • AlgebraPoolDeployer
          • DataStorage
          • DataStorageOperator
          • IAlgebraFactory
          • IAlgebraFlashCallback
          • IAlgebraMintCallback
          • IAlgebraPoolActions
          • IAlgebraPoolDeployer
          • IAlgebraPoolDerivedState
          • IAlgebraPoolEvents
          • IAlgebraPoolImmutables
          • IAlgebraPoolPermissionedActions
          • IAlgebraPoolState
          • IAlgebraSwapCallback
          • IAlgebraVirtualPool
          • IDataStorageOperator
          • IERC20Minimal
          • PoolImmutables
          • PoolState
        • V1.0 - Periphery
          • AlgebraInterfaceMulticall
          • ERC20
          • ERC20Permit
          • ERC165
          • ERC721
          • ERC721Permit
          • IAlgebraMintCallback
          • IAlgebraFactory
          • IAlgebraPoolDerivedState
          • IAlgebraPoolActions
          • IAlgebraPoolEvents
          • IAlgebraPoolImmutables
          • IAlgebraPoolPermissionedActions
          • IAlgebraPoolState
          • IAlgebraSwapCallback
          • IERC20
          • IDataStorageOperator
          • IERC20Metadata
          • IERC20Permit
          • IERC20PermitAllowed
          • IERC165
          • IERC721
          • IERC721Enumerable
          • IERC721Metadata
          • IERC721Permit
          • IERC721Receiver
          • IERC1271
          • IMulticall
          • INonfungiblePositionManager
          • INonfungibleTokenPositionDescriptor
          • IPeripheryImmutableState
          • IPeripheryPayments
          • IPeripheryPaymentsWithFee
          • IPoolInitializer
          • IQuoter
          • IQuoterV2
          • ISelfPermit
          • ISwapRouter
          • ITickLens
          • IUniswapV2Pair
          • IV3Migrator
          • IWNativeToken
          • LiquidityManagement
          • Multicall
          • NFTDescriptor
          • NonfungiblePositionManager
          • NonfungibleTokenPositionDescriptor
          • PeripheryImmutableState
          • PeripheryPayments
          • PeripheryPaymentsWithFee
          • PoolInitializer
          • Quoter
          • QuoterV2
          • SwapRouter
          • SelfPermit
          • TickLens
          • V3Migrator
        • V1.0 - Tokenomics
          • AlgebraEternalFarming
          • AlgebraFarming
          • AlgebraIncentiveFarming
          • AlgebraLimitFarming
          • AlgebraTokenStaking
          • AlgebraVault
          • AlgebraVirtualPoolBase
          • ERC20
          • ERC165
          • ERC721
          • ERC721Permit
          • EternalVirtualPool
          • FarmingCenter
          • FarmingCenterVault
          • FreezableToken
          • IAlgebraEternalFarming
          • IAlgebraEternalVirtualPool
          • IAlgebraFactory
          • IAlgebraFarming
          • IAlgebraIncentiveFarming
          • IAlgebraIncentiveVirtualPool
          • IAlgebraLimitFarming
          • IAlgebraLimitVirtualPool
          • IAlgebraPoolActions
          • IAlgebraPoolDeployer
          • IAlgebraPoolDerivedState
          • IAlgebraPoolEvents
          • IAlgebraPoolImmutables
          • IAlgebraPoolPermissionedActions
          • IAlgebraPoolState
          • IAlgebraSwapCallback
          • IAlgebraVirtualPool
          • IAlgebraVirtualPoolBase
          • IDataStorageOperator
          • IERC20
          • IERC20Minimal
          • IERC165
          • IERC721
          • IERC721Enumerable
          • IERC721Metadata
          • IERC721Permit
          • IERC721Receiver
          • IERC1271
          • IFarmingCenter
          • IFarmingCenterVault
          • IMulticall
          • IncentiveVirtualPool
          • INonfungiblePositionManager
          • IPeripheryPayments
          • IPeripheryImmutableState
          • IPoolInitializer
          • ISwapRouter
          • IWNativeToken
          • LimitVirtualPool
          • Multicall
          • PeripheryPayments
      • API Reference v1.9
        • V1.9 - Core
          • AlgebraFactory
          • AlgebraPool
          • AlgebraPoolDeployer
          • DataStorage
          • DataStorageOperator
          • IAlgebraFactory
          • IAlgebraFlashCallback
          • IAlgebraMintCallback
          • IAlgebraPoolActions
          • IAlgebraPoolDeployer
          • IAlgebraPoolDerivedState
          • IAlgebraPoolEvents
          • IAlgebraPoolImmutables
          • IAlgebraPoolPermissionedActions
          • IAlgebraPoolState
          • IAlgebraSwapCallback
          • IAlgebraVirtualPool
          • IDataStorageOperator
          • IERC20Minimal
          • PoolImmutables
          • PoolState
        • V1.9 - Periphery
          • ERC721Permit
          • AlgebraInterfaceMulticall
          • IERC20Metadata
          • IERC20PermitAllowed
          • IERC721Permit
          • IERC1271
          • IMulticall
          • INonfungiblePositionManager
          • INonfungibleTokenPositionDescriptor
          • IPeripheryImmutableState
          • IPeripheryPayments
          • IPeripheryPaymentsWithFee
          • IPoolInitializer
          • IQuoter
          • IQuoterV2
          • ISelfPermit
          • ISwapRouter
          • ITickLens
          • IV3Migrator
          • IWNativeToken
          • LiquidityManagement
          • Multicall
          • NFTDescriptor
          • NonfungiblePositionManager
          • NonfungibleTokenPositionDescriptor
          • PeripheryImmutableState
          • PeripheryPayments
          • PoolInitializer
          • PeripheryPaymentsWithFee
          • Quoter
          • QuoterV2
          • SelfPermit
          • SwapRouter
          • TickLens
          • V3Migrator
        • V1.9 - Tokenomics
          • AlgebraFarming
          • AlgebraEternalFarming
          • AlgebraLimitFarming
          • AlgebraTokenStaking
          • AlgebraVault
          • AlgebraVirtualPoolBase
          • ERC20
          • EternalVirtualPool
          • FarmingCenter
          • FarmingCenterVault
          • FreezableToken
          • IAlgebraEternalFarming
          • IAlgebraEternalVirtualPool
          • IAlgebraFarming
          • IAlgebraLimitFarming
          • IAlgebraLimitVirtualPool
          • IAlgebraVirtualPoolBase
          • IERC20Minimal
          • IFarmingCenter
          • IFarmingCenterVault
          • LimitVirtualPool
          • PeripheryPayments
      • API Reference v1.9 - Directional Fees
        • V1.9 (Directional Fees) - Core
          • AlgebraFactory
          • AlgebraPool
          • AlgebraPoolDeployer
          • DataStorage
          • DataStorageOperator
          • IAlgebraFactory
          • IAlgebraFlashCallback
          • IAlgebraMintCallback
          • IAlgebraPoolActions
          • IAlgebraPoolDeployer
          • IAlgebraPoolDerivedState
          • IAlgebraPoolEvents
          • IAlgebraPoolImmutables
          • IAlgebraPoolPermissionedActions
          • IAlgebraSwapCallback
          • IAlgebraPoolState
          • IAlgebraVirtualPool
          • IDataStorageOperator
          • IERC20Minimal
          • PoolImmutables
          • PoolState
        • V1.9 (Directional Fees) - Periphery
          • AlgebraInterfaceMulticall
          • ERC721Permit
          • IERC20Metadata
          • IERC20PermitAllowed
          • IERC721Permit
          • IERC1271
          • IMulticall
          • INonfungiblePositionManager
          • INonfungibleTokenPositionDescriptor
          • IPeripheryImmutableState
          • IPeripheryPayments
          • IPeripheryPaymentsWithFee
          • IPoolInitializer
          • IQuoter
          • IQuoterV2
          • ISelfPermit
          • ISwapRouter
          • ITickLens
          • IV3Migrator
          • IWNativeToken
          • LiquidityManagement
          • Multicall
          • NFTDescriptor
          • NonfungiblePositionManager
          • NonfungibleTokenPositionDescriptor
          • PeripheryImmutableState
          • PeripheryPayments
          • PeripheryPaymentsWithFee
          • PoolInitializer
          • Quoter
          • QuoterV2
          • SelfPermit
          • SwapRouter
          • TickLens
          • V3Migrator
        • V1.9 (Directional Fees) - Tokenomics
          • AlgebraFarming
          • AlgebraEternalFarming
          • AlgebraLimitFarming
          • AlgebraTokenStaking
          • AlgebraVault
          • AlgebraVirtualPoolBase
          • ERC20
          • EternalVirtualPool
          • FarmingCenter
          • FarmingCenterVault
          • FreezableToken
          • IAlgebraEternalFarming
          • IAlgebraEternalVirtualPool
          • IAlgebraFarming
          • IAlgebraLimitVirtualPool
          • IAlgebraLimitFarming
          • IAlgebraVirtualPoolBase
          • IERC20Minimal
          • IFarmingCenterVault
          • IFarmingCenter
          • LimitVirtualPool
          • PeripheryPayments
      • API Reference v2.0
        • V2.0 - Core
          • AlgebraCommunityVault
          • AlgebraFactory
          • AlgebraFeeConfiguration
          • AlgebraPool
          • AlgebraPoolBase
          • AlgebraPoolDeployer
          • DataStorage
          • DataStorageOperator
          • DerivedState
          • IAlgebraFactory
          • IAlgebraFlashCallback
          • IAlgebraMintCallback
          • IAlgebraPoolActions
          • IAlgebraPoolDeployer
          • IAlgebraPoolDerivedState
          • IAlgebraPoolErrors
          • IAlgebraPoolEvents
          • IAlgebraPoolImmutables
          • IAlgebraPoolPermissionedActions
          • IAlgebraPoolState
          • IAlgebraSwapCallback
          • IAlgebraVirtualPool
          • IDataStorageOperator
          • IERC20Minimal
          • Positions
          • ReservesManager
        • V2.0 - Periphery
          • AlgebraInterfaceMulticall
          • ERC721Permit
          • IERC20Metadata
          • IERC20PermitAllowed
          • IERC721Permit
          • IERC1271
          • ILimitOrderManager
          • IMulticall
          • INonfungiblePositionManager
          • INonfungibleTokenPositionDescriptor
          • IPeripheryImmutableState
          • IPeripheryPayments
          • IPeripheryPaymentsWithFee
          • IPoolInitializer
          • IPositionFollower
          • IQuoter
          • IQuoterV2
          • ISelfPermit
          • ISwapRouter
          • ITickLens
          • IV3Migrator
          • IWNativeToken
          • LimitOrderManagement
          • LimitOrderManager
          • LiquidityManagement
          • Multicall
          • NFTDescriptor
          • NonfungiblePositionManager
          • NonfungibleTokenPositionDescriptor
          • PeripheryImmutableState
          • PeripheryPayments
          • PeripheryPaymentsWithFee
          • PoolInitializer
          • Quoter
          • QuoterV2
          • SelfPermit
          • SwapRouter
          • TickLens
          • V3Migrator
        • V2.0 - Tokenomics
          • AlgebraEternalFarming
          • EternalVirtualPool
          • FarmingCenter
          • IAccessControl
          • IAlgebraEternalFarming
          • IAlgebraEternalVirtualPool
          • IFarmingCenter
          • IncentiveKey
          • VirtualTickStructure
      • API Reference v2.0 - Directional Fees
        • V2.0 (Directional Fees) - Core
          • AlgebraCommunityVault
          • AlgebraFactory
          • AlgebraFeeConfiguration
          • AlgebraPool
          • AlgebraPoolBase
          • AlgebraPoolDeployer
          • DataStorage
          • DataStorageOperator
          • DerivedState
          • IAlgebraFactory
          • IAlgebraFlashCallback
          • IAlgebraMintCallback
          • IAlgebraPoolActions
          • IAlgebraPoolDeployer
          • IAlgebraPoolDerivedState
          • IAlgebraPoolErrors
          • IAlgebraPoolEvents
          • IAlgebraPoolImmutables
          • IAlgebraPoolPermissionedActions
          • IAlgebraPoolState
          • IAlgebraSwapCallback
          • IAlgebraVirtualPool
          • IDataStorageOperator
          • IERC20Minimal
          • Positions
          • ReservesManager
        • V2.0 (Directional Fees) - Periphery
          • AlgebraInterfaceMulticall
          • ERC721Permit
          • IERC20Metadata
          • IERC20PermitAllowed
          • IERC721Permit
          • IERC1271
          • ILimitOrderManager
          • IMulticall
          • INonfungiblePositionManager
          • INonfungibleTokenPositionDescriptor
          • IPeripheryImmutableState
          • IPeripheryPayments
          • IPeripheryPaymentsWithFee
          • IPoolInitializer
          • IPositionFollower
          • IQuoter
          • IQuoterV2
          • ISelfPermit
          • ISwapRouter
          • ITickLens
          • IV3Migrator
          • IWNativeToken
          • LimitOrderManagement
          • LimitOrderManager
          • LiquidityManagement
          • Multicall
          • NFTDescriptor
          • NonfungiblePositionManager
          • NonfungibleTokenPositionDescriptor
          • PeripheryImmutableState
          • PeripheryPayments
          • PeripheryPaymentsWithFee
          • PoolInitializer
          • QuoterV2
          • Quoter
          • SelfPermit
          • SwapRouter
          • TickLens
          • V3Migrator
        • V2.0 (Directional Fees) - Tokenomics
          • AlgebraEternalFarming
          • EternalVirtualPool
          • FarmingCenter
          • IAccessControl
          • IAlgebraEternalFarming
          • IAlgebraEternalVirtualPool
          • IFarmingCenter
          • IncentiveKey
          • VirtualTickStructure
      • Adaptive Fee
        • Adaptive Fee
        • How to set up specific formula behaviour
        • How to tweak formula behaviour
      • Contracts Setup
        • Deployment
          • Contracts Deployment
          • Deployment Scripts
        • Misc
          • POOL_INIT_CODE_HASH
          • Code Audits
          • Deployment Addresses
      • The Algebra Guides
        • Flash Integrations
          • The Full Contract
          • Calling Flash
          • Flash Callback
          • Inheritance constructor
        • Liquidity Mining
          • Liquidity Mining Overview
        • Providing Liquidity
          • Collecting fees
          • Decrease liquidity
          • Increase Liquidity Within The Current Range
          • Mint a new position
          • Set up your contract
          • The full contract
        • Swaps
          • Multihop swaps
          • Single swaps
    • 📊Subgraph
      • Query Examples
        • Query Examples
      • GraphQL Schema
        • Farming GraphQL Schema
        • Algebra GraphQL Schema
      • Subgraph Setup
        • Subgraph Settings
        • Subgraph Deployment
    • 🖥️Frontend
      • Admin Panel
        • Contracts
          • Admin Panel
          • Changing Subgraph
        • Eternal Farmings
          • Create Eternal Farming
          • Managing Eternal Farming
        • Limit Farmings
          • Create Limit Farming
    • ⚙️Backend
      • Backend Setup
    • ⛑️Guides
      • Step by Step Deployment
  • Other
    • 📦Archived Documentation
    • ❗Link Awareness Notice
Powered by GitBook
On this page
  • TickTree
  • Root
  1. Algebra Integral / Technical Reference
  2. Core Logic
  3. Ticks

Ticks search tree

PreviousTicksNextReserves

Relevant and important files:

  • base/TickStructure.sol

  • libraries/TickTree.sol

TickTree

The tick tree logic is very similar to, and partially compatible with, the tick bitmap logic used in UniswapV3 - the tree uses bitmaps to store information in the nodes of the tree.

Leaves

All ticks are divided into "bundles" of 256 and packed into bitmaps. This structure is called tickTable. tickTable consists of "words" in which each bit corresponds to a tick. If a bit is 1, the tick is active. If the bit is 0, the tick is not active. Indexing of ticks in tickTable goes from right to left, i.e. tick with index 0 in a word is the lowest bit.

Within one word it is quite easy to find the next active tick after the i-th tick, if it exists. To do this, all other bits are zeroed and the getSingleSignificantBit method is used. However, if the nearest next active tick is not in the current word, the search task becomes more complicated: in the worst case, it may be necessary to search all other words in the same style, which is very expensive. For this reason, we complicate the structure of ticks by turning it into a tree.

Intermediate layer

Since one tickTable word can only store information about 256 ticks, another layer of bitmaps is added. In the intermediate layer, each word contains information about words from tickTable. Each bit in a word from the intermediate layer corresponds to a word from the leaf layer (tickTable) and is 1 if at least one bit in the corresponding word is 1 (at least one tick is active).

Thus, one word of the intermediate layer allows to find out if there is at least one active tick among 256 * 256 (65 536) ticks and to find in which word of the leaves layer it is located.

Ticks themselves can have negative indices. However, to simplify the logic, the indexing in the second layer is shifted to positive values (the tick N corresponds to the word K = floor(N / 256) + 3466 ).

However, the allowed active ticks can be much more than 65536. That's why the problem of searching remains, if the active tick is so far away that we have to search even for the words of the second level. To avoid such a search there is a third level in the tree, which is called the root.

Root

The root of the tree is also a bitmap and contains information about the words of the second (intermediate) level.

The corresponding bit at the root is 1 if the corresponding second-level word has at least one active bit.

The maximum allowed tick is 887272

The minimum allowed tick is -887272.

Thus, there can be (887272 + 887272 + 1).

Then the first level of the tree has ceil((887272 + 887272 + 1) / 256) leaves, i.e. 6932 leaves.

Then the second level needs ceil(6932 / 256) nodes, i.e. 28 nodes.

Thus, the root must store information about 28 descendants and a 32-bit value is sufficient to record it.

Worst case search

In the worst case, the current search algorithm (getNextTick method in TickTree.sol) in Algebra Integral is as follows:

  1. Check the current leaf if it contains the next active tick

  2. Check the current node of the intermediate layer if it has the next active leaf

  3. Find in the root which node in the intermediate layer has an active leaf

  4. Find in the intermediate layer node which leaf has an active tick

  5. Find the index of the active tick in the leaf

🖲️