authz-core/src/main/java/com/att/cssa/rserv/Match.java

   1 /*******************************************************************************\r
   2  * ============LICENSE_START====================================================\r
   3  * * org.onap.aai\r
   4  * * ===========================================================================\r
   5  * * Copyright © 2017 AT&T Intellectual Property. All rights reserved.\r
   6  * * Copyright © 2017 Amdocs\r
   7  * * ===========================================================================\r
   8  * * Licensed under the Apache License, Version 2.0 (the "License");\r
   9  * * you may not use this file except in compliance with the License.\r
  10  * * You may obtain a copy of the License at\r
  11  * * \r
  12  *  *      http://www.apache.org/licenses/LICENSE-2.0\r
  13  * * \r
  14  *  * Unless required by applicable law or agreed to in writing, software\r
  15  * * distributed under the License is distributed on an "AS IS" BASIS,\r
  16  * * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  17  * * See the License for the specific language governing permissions and\r
  18  * * limitations under the License.\r
  19  * * ============LICENSE_END====================================================\r
  20  * *\r
  21  * * ECOMP is a trademark and service mark of AT&T Intellectual Property.\r
  22  * *\r
  23  ******************************************************************************/\r
  24 package com.att.cssa.rserv;\r
  25 \r
  26 import java.util.HashMap;\r
  27 import java.util.Map;\r
  28 import java.util.Set;\r
  29 \r
  30 /**\r
  31  * This path matching algorithm avoids using split strings during the critical transactional run-time.  By pre-analyzing the\r
  32  * content at "set Param" time, and storing data in an array-index model which presumably is done once and at the beginning, \r
  33  * we can match in much less time when it actually counts.\r
  34  * \r
  35  *\r
  36  */\r
  37 public class Match {\r
  38         private Map<String, Integer> params;\r
  39         private byte[]  values[];\r
  40         private Integer vars[];\r
  41         private boolean wildcard;\r
  42 \r
  43         \r
  44         /*\r
  45          * These two methods are pairs of searching performance for variables Spark Style.\r
  46          * setParams evaluates the target path, and sets a HashMap that will return an Integer.\r
  47          * the Keys are both :key and key so that there will be no string operations during\r
  48          * a transaction\r
  49          * \r
  50          * For the Integer, if the High Order is 0, then it is just one value.  If High Order >0, then it is \r
  51          * a multi-field option, i.e. ending with a wild-card.\r
  52          */\r
  53         public Match(String path) {\r
  54                 // IF DEBUG: System.out.print("\n[" + path + "]");\r
  55                 params = new HashMap<String,Integer>();\r
  56                 if(path!=null) {\r
  57                         String[] pa = path.split("/");\r
  58                         values = new byte[pa.length][];\r
  59                         vars = new Integer[pa.length];\r
  60                         \r
  61                         int val = 0;\r
  62                         String key;\r
  63                         for(int i=0;i<pa.length && !wildcard;++i) {\r
  64                                 if(pa[i].startsWith(":")) {\r
  65                                         if(pa[i].endsWith("*")) {\r
  66                                                 val = i | pa.length<<16; // load end value in high order bits\r
  67                                                 key = pa[i].substring(0, pa[i].length()-1);// remove *\r
  68                                                 wildcard = true;\r
  69                                         } else {\r
  70                                                 val = i;\r
  71                                                 key = pa[i];\r
  72                                         }\r
  73                                         params.put(key,val); //put in :key \r
  74                                         params.put(key.substring(1,key.length()), val); // put in just key, better than adding a missing one, like Spark\r
  75                                         // values[i]=null; // null stands for Variable\r
  76                                         vars[i]=val;\r
  77                                 } else {\r
  78                                         values[i]=pa[i].getBytes();\r
  79                                         if(pa[i].endsWith("*")) {\r
  80                                                 wildcard = true;\r
  81                                                 if(pa[i].length()>1) {\r
  82                                                         /* remove * from value */\r
  83                                                         int newlength = values[i].length-1;\r
  84                                                         byte[] real = new byte[newlength];\r
  85                                                         System.arraycopy(values[i],0,real,0,newlength);\r
  86                                                         values[i]=real;\r
  87                                                 } else {\r
  88                                                         vars[i]=0; // this is actually a variable, if it only contains a "*"\r
  89                                                 }\r
  90                                         }\r
  91                                         // vars[i]=null;\r
  92                                 }\r
  93                         }\r
  94                 }\r
  95         }\r
  96 \r
  97         /*\r
  98          * This is the second of the param evaluation functions.  First, we look up to see if there is\r
  99          * any reference by key in the params Map created by the above.\r
 100          * \r
 101          * The resulting Integer, if not null, is split high/low order into start and end.\r
 102          * We evaluate the string for '/', rather than splitting into  String[] to avoid the time/mem needed\r
 103          * We traverse to the proper field number for slash, evaluate the end (whether wild card or no), \r
 104          * and return the substring.  \r
 105          * \r
 106          * The result is something less than .003 milliseconds per evaluation\r
 107          * \r
 108          */\r
 109         public String param(String path,String key) {\r
 110                 Integer val = params.get(key); // :key or key\r
 111                 if(val!=null) {\r
 112                         int start = val & 0xFFFF;\r
 113                         int end = (val >> 16) & 0xFFFF;\r
 114                         int idx = -1;\r
 115                         int i;\r
 116                         for(i=0;i<start;++i) {\r
 117                                 idx = path.indexOf('/',idx+1);\r
 118                                 if(idx<0)break;\r
 119                         }\r
 120                         if(i==start) { \r
 121                                 ++idx;\r
 122                                 if(end==0) {\r
 123                                         end = path.indexOf('/',idx);\r
 124                                         if(end<0)end=path.length();\r
 125                                 } else {\r
 126                                         end=path.length();\r
 127                                 }\r
 128                                 return path.substring(idx,end);\r
 129                         } else if(i==start-1) { // if last spot was left blank, i.e. :key*\r
 130                                 return "";\r
 131                         }\r
 132                 }\r
 133                 return null;\r
 134         }\r
 135         \r
 136         public boolean match(String path) {\r
 137                 if(path==null|| path.length()==0 || "/".equals(path) ) {\r
 138                         if(values==null)return true;\r
 139                         switch(values.length) {\r
 140                                 case 0: return true;\r
 141                                 case 1: return values[0].length==0;\r
 142                                 default: return false;\r
 143                         }\r
 144                 }                       \r
 145                 boolean rv = true;\r
 146                 byte[] pabytes = path.getBytes();\r
 147                 int field=0;\r
 148                 int fieldIdx = 0;\r
 149 \r
 150                 int lastField = values.length;\r
 151                 int lastByte = pabytes.length;\r
 152                 boolean fieldMatched = false; // = lastByte>0?(pabytes[0]=='/'):false;\r
 153                 // IF DEBUG: System.out.println("\n -- " + path + " --");\r
 154                 for(int i=0;rv && i<lastByte;++i) {\r
 155                         if(field>=lastField) { // checking here allows there to be a non-functional ending /\r
 156                                 rv = false;\r
 157                                 break;\r
 158                         }\r
 159                         if(values[field]==null) { // it's a variable, just look for /s\r
 160                                 if(wildcard && field==lastField-1) return true;// we've made it this far.  We accept all remaining characters\r
 161                                 Integer val = vars[field];\r
 162                                 int start = val & 0xFFFF;\r
 163                                 int end = (val >> 16) & 0xFFFF;\r
 164                                 if(end==0)end=start+1;\r
 165                                 int k = i;\r
 166                                 for(int j=start; j<end && k<lastByte; ++k) {\r
 167                                         // IF DEBUG: System.out.print((char)pabytes[k]);\r
 168                                         if(pabytes[k]=='/') {\r
 169                                                 ++field;\r
 170                                                 ++j;\r
 171                                         }\r
 172                                 }\r
 173                                 \r
 174                                 if(k==lastByte && pabytes[k-1]!='/')++field;\r
 175                                 if(k>i)i=k-1; // if we've incremented, have to accommodate the outer for loop incrementing as well\r
 176                                 fieldMatched = false; // reset\r
 177                                 fieldIdx = 0;\r
 178                         } else {\r
 179                                 // IF DEBUG: System.out.print((char)pabytes[i]);\r
 180                                 if(pabytes[i]=='/') { // end of field, eval if Field is matched\r
 181                                         // if double slash, check if supposed to be empty\r
 182                                         if(fieldIdx==0 && values[field].length==0) {\r
 183                                                 fieldMatched = true;\r
 184                                         }\r
 185                                         rv = fieldMatched && ++field<lastField;\r
 186                                         // reset\r
 187                                         fieldMatched = false; \r
 188                                         fieldIdx = 0;\r
 189                                 } else if(values[field].length==0) {\r
 190                                         // double slash in path, but content in field.  We check specially here to avoid \r
 191                                         // Array out of bounds issues.\r
 192                                         rv = false;\r
 193                                 } else {\r
 194                                         if(fieldMatched) {\r
 195                                                 rv =false; // field is already matched, now there's too many bytes\r
 196                                         } else {\r
 197                                                 rv = pabytes[i]==values[field][fieldIdx++]; // compare expected (pabytes[i]) with value for particular field\r
 198                                                 fieldMatched=values[field].length==fieldIdx; // are all the bytes match in the field?\r
 199                                                 if(fieldMatched && (i==lastByte-1 || (wildcard && field==lastField-1)))\r
 200                                                         return true; // last field info\r
 201                                         }\r
 202                                 }\r
 203                         }\r
 204                 }\r
 205                 if(field!=lastField || pabytes.length!=lastByte) rv = false; // have we matched all the fields and all the bytes?\r
 206                 return rv;\r
 207         }\r
 208         \r
 209         public Set<String> getParamNames() {\r
 210                 return params.keySet();\r
 211         }\r
 212 }\r