Branch data     Line data    Source code

       1                 :             : /**
       2                 :             : * Copyright © 2025 Valentin Gorelov
       3                 :             : *
       4                 :             : * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
       5                 :             : * documentation files (the “Software”), to deal in the Software without restriction,
       6                 :             : * including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
       7                 :             : * and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
       8                 :             : * subject to the following conditions:
       9                 :             : *
      10                 :             : * The above copyright notice and this permission notice
      11                 :             : * shall be included in all copies or substantial portions of the Software.
      12                 :             : *
      13                 :             : * THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
      14                 :             : * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
      15                 :             : * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
      16                 :             : * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      17                 :             : * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
      18                 :             : */
      19                 :             : 
      20                 :             : /**
      21                 :             :  * @brief
      22                 :             :  * @author Valentin Gorelov <gorelov.valentin@gmail.com>
      23                 :             :  */
      24                 :             : 
      25                 :             : #ifndef ATCMD_TRIE_H
      26                 :             : #define ATCMD_TRIE_H
      27                 :             : 
      28                 :             : #include <atcmd/detail/triebuilder.h>
      29                 :             : #include <atcmd/detail/characters.h>
      30                 :             : 
      31                 :             : namespace atcmd::detail {
      32                 :             : 
      33                 :             : template<std::size_t N, std::array<const char*, N> names>
      34                 :             : struct TrieBase
      35                 :             : {
      36                 :           9 :         TrieBase() : m_pos{0}
      37                 :           9 :         {}
      38                 :             : 
      39                 :       32768 :         void reset()
      40                 :             :         {
      41                 :       32768 :                 m_pos = 0;
      42                 :       32768 :         }
      43                 :             : 
      44                 :       82415 :         bool feed(char ch)
      45                 :             :         {
      46                 :             :                 // Goto the first child
      47                 :       82415 :                 skipCommandIndex();
      48                 :       82415 :                 if (getSubtreeSize() == 0)
      49                 :             :                 {
      50                 :           1 :                         return false;
      51                 :             :                 }
      52                 :             : 
      53                 :      682323 :                 while (true)
      54                 :             :                 {
      55                 :      764737 :                         if (currentChar() == ch)
      56                 :             :                         {
      57                 :       66031 :                                 return true;
      58                 :             :                         }
      59                 :      698706 :                         if (isLast())
      60                 :             :                         {
      61                 :       16383 :                                 m_pos = 0;
      62                 :       16383 :                                 return false;
      63                 :             :                         }
      64                 :             :                         // Go to the right sibling
      65                 :      682323 :                         skipCommandIndex();
      66                 :      682323 :                         uint32_t s = getSubtreeSize();
      67                 :      682323 :                         m_pos += s;
      68                 :             :                 }
      69                 :             :         }
      70                 :             : 
      71                 :      781122 :         bool isLeaf() const
      72                 :             :         {
      73                 :      781122 :                 return current() & TrieBuilder::MASKS::MASKS_LEAF;
      74                 :             :         }
      75                 :             : 
      76                 :       16383 :         uint16_t getCommandIndex() const
      77                 :             :         {
      78                 :             :                 assert(isLeaf());
      79                 :             : 
      80                 :       16383 :                 uint8_t b = m_trie[m_pos + 1];
      81                 :       16383 :                 uint32_t r = b & 0x7F;
      82                 :       16383 :                 if ((b & (1u << 7)) == 0)
      83                 :             :                 {
      84                 :         128 :                         return r;
      85                 :             :                 }
      86                 :       16255 :                 r |= m_trie[m_pos + 2] << 7;
      87                 :       16255 :                 return r;
      88                 :             :         }
      89                 :             : 
      90                 :             : private:
      91                 :     5680359 :         uint8_t current() const
      92                 :             :         {
      93                 :     5680359 :                 return m_trie[m_pos];
      94                 :             :         }
      95                 :             : 
      96                 :      764737 :         char currentChar() const
      97                 :             :         {
      98                 :      764737 :                 return Characters::decode(current() & TrieBuilder::MASKS::MASKS_CHAR);
      99                 :             :         }
     100                 :             : 
     101                 :      698706 :         bool isLast() const
     102                 :             :         {
     103                 :      698706 :                 return current() & TrieBuilder::MASKS::MASKS_LAST;
     104                 :             :         }
     105                 :             : 
     106                 :      764738 :         void skipCommandIndex()
     107                 :             :         {
     108                 :      764738 :                 if (!isLeaf())
     109                 :             :                 {
     110                 :       42768 :                         m_pos++;
     111                 :       42768 :                         return;
     112                 :             :                 }
     113                 :             : 
     114                 :      721970 :                 m_pos++;
     115                 :      721970 :                 if ((current() & (1u << 7)))
     116                 :             :                 {
     117                 :      288171 :                         m_pos++;
     118                 :             :                 }
     119                 :      721970 :                 m_pos++;
     120                 :             :         }
     121                 :             : 
     122                 :      764738 :         uint32_t getSubtreeSize()
     123                 :             :         {
     124                 :      764738 :                 uint32_t r = 0;
     125                 :             : 
     126                 :             :                 // First 2 bytes
     127                 :     1375554 :                 for (uint_fast8_t i = 0; i < 2; i++)
     128                 :             :                 {
     129                 :     1338270 :                         r |= (current() & 0x7F) << (7 * i);
     130                 :     1338270 :                         if ((current() & (1u << 7)) == 0)
     131                 :             :                         {
     132                 :      727454 :                                 m_pos++;
     133                 :      727454 :                                 return r;
     134                 :             :                         }
     135                 :      610816 :                         m_pos++;
     136                 :             :                 }
     137                 :             : 
     138                 :             :                 // Third byte
     139                 :       37284 :                 r |= current() << 14;
     140                 :       37284 :                 m_pos++;
     141                 :       37284 :                 return r;
     142                 :             :         }
     143                 :             : 
     144                 :             :         std::size_t m_pos;
     145                 :             : 
     146                 :             :         static constexpr auto m_trie =
     147                 :             :                         TrieBuilder::getTrie<TrieBuilder::getTrieSize(names.data(), names.size())>(names.data(), names.size());
     148                 :             : };
     149                 :             : 
     150                 :             : template<const char*... names>
     151                 :             : struct Trie : public TrieBase<sizeof... (names), {names...}>
     152                 :             : {};
     153                 :             : 
     154                 :             : } /* namespace atcmd::detail */
     155                 :             : 
     156                 :             : #endif // ATCMD_TRIE_H