1 /** 2 * Copyright (c) 2007-2012, Timothy Stack 3 * 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * * Redistributions of source code must retain the above copyright notice, this 10 * list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above copyright notice, 12 * this list of conditions and the following disclaimer in the documentation 13 * and/or other materials provided with the distribution. 14 * * Neither the name of Timothy Stack nor the names of its contributors 15 * may be used to endorse or promote products derived from this software 16 * without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND ANY 19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 21 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY 22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 25 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #ifndef sequence_matcher_hh 31 #define sequence_matcher_hh 32 33 #include <list> 34 #include <string> 35 #include <vector> 36 37 #include "byte_array.hh" 38 39 class sequence_matcher { 40 public: 41 typedef std::vector<std::string> field_row_t; 42 typedef std::list<field_row_t> field_col_t; 43 44 typedef byte_array<2, uint64_t> id_t; 45 46 enum field_type_t { 47 FT_VARIABLE, 48 FT_CONSTANT, 49 }; 50 51 struct field { fieldsequence_matcher::field52 field() : sf_type(FT_VARIABLE) { }; 53 54 field_type_t sf_type; 55 field_row_t sf_value; 56 }; 57 58 sequence_matcher(field_col_t &example); 59 60 void identity(const std::vector<std::string> &values, id_t &id_out); 61 62 template<typename T> match(const std::vector<std::string> & values,std::vector<T> & state,T index)63 bool match(const std::vector<std::string> &values, 64 std::vector<T> &state, 65 T index) 66 { 67 bool index_match = true; 68 int lpc = 0; 69 70 retry: 71 for (std::list<field>::iterator iter = this->sm_fields.begin(); 72 iter != this->sm_fields.end(); 73 ++iter, lpc++) { 74 if (iter->sf_type != sequence_matcher::FT_CONSTANT) { 75 continue; 76 } 77 78 if (iter->sf_value[state.size()] != values[lpc]) { 79 if (!state.empty()) { 80 state.clear(); 81 lpc = 0; 82 goto retry; 83 } 84 else { 85 index_match = false; 86 break; 87 } 88 } 89 } 90 91 if (index_match) { 92 state.push_back(index); 93 } 94 95 return (size_t)this->sm_count == state.size(); 96 }; 97 98 private: 99 int sm_count; 100 std::list<field> sm_fields; 101 }; 102 #endif 103