You are viewing a plain text version of this content. The canonical link for it is here.
Posted to mapreduce-user@hadoop.apache.org by Arpit Wanchoo <Ar...@guavus.com> on 2012/09/26 11:00:51 UTC

Updates in common trie code at com.guavus.mapred.common.trie

Hi

There are a few updates in the trie code under com.guavus.mapred.common.trie.

The change was initially done under  com.guavus.mapred.bizreflex.trie by Anand. A new trie class TrieReadOnly was introduced which stores the trie in the form of compact binary stream.
There were two reasons behind this change in our solution :
 1. Decrease the memory used for storing the trie
 2. Decreasing the load time of IB tries during the map reduce init phase.

The new trie class ( TrieReadOnly) is generic and can be used in other solutions.
( com.guavus.mapred.bizreflex.trie.BinaryEibAsibConvertor was also written to convert the text Asib, Eib to merged binary IB but later RE code was updated to do the same. Hence this not being used currently)


I have moved the code from com.guavus.mapred.bizreflex.trie to com.guavus.mapred.common.trie. Following is the summary of changes in the common trie :
1. An interface BaseTrie has been added. Classes Trie (old trie) and TrieReadOnly implements this interface.
2. Class IpVersionFour has been added with some additional functionalities
3. Few functions were present in both the classes i.e Trie and IpToInt. I have removed them from Trie class and put at one place in the class IpToInt.

The changes have been done ensuring that old Trie functionality is not affected.
Still you can look at the changes in common trie if you are using it in your solution and confirm  there is no impact on the existing functionality.



Regards,
Arpit Wanchoo | Sr. Software Engineer
Guavus Network Systems.
6th Floor, Enkay Towers, Tower B & B1,Vanijya Nikunj, Udyog Vihar Phase - V, Gurgaon,Haryana.
Mobile Number +91-9899949788

Begin forwarded message:

From: arpit.wanchoo <ar...@guavus.com>>
Subject: [GIT mapreduce] HBZ-734: Moved trie code under bizreflex to common trie package
Date: 26 September 2012 12:52:46 PM GMT+05:30
To: <te...@guavus.com>>


Commit
18dd99a91de22633cfe6354f5672bed3c058ebef<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;a=commitdiff;h=18dd99a91de22633cfe6354f5672bed3c058ebef>
Branch
master
Author
arpit.wanchoo
Date
Wed, 26 Sep 2012 13:04:13 +0530
Message
HBZ-734:<http://deepthought.guavus.com:8080/jira/browse/HBZ-734> Moved trie code under bizreflex to common trie package
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/AsibAnnotation.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/AsibAnnotation.java;h=318ceca;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
16      16       import com.guavus.mapred.bizreflex.trie.*;
17      17       import com.guavus.mapred.bizreflex.annotation.EibAnnotation.*;
18      18       import gnu.trove.map.hash.TIntObjectHashMap;
        19       import com.guavus.mapred.common.trie.*;
19      20
20      21       public class AsibAnnotation extends IAnnotation {
21      22           static com.guavus.logging.Logger Logger = new com.guavus.logging.Logger(AsibAnnotation.class);
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/EibAnnotation.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/EibAnnotation.java;h=ddf4c2e;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
12      12       import com.guavus.logging.LogLevel;
13      13       import com.guavus.logging.Logger;
14      14       import com.guavus.mapred.bizreflex.trie.*;
        15       import com.guavus.mapred.common.trie.*;
16      16       import collector.adapters.NetflowRecordIdl;
17      17       import com.guavus.mapred.bizreflex.annotation.Global_Info.*;
18      18
…
43      43
44      44               NetflowRecordIdl inRecord = (NetflowRecordIdl) inputRecord;
45      45               int exporterId = inRecord.getExporter_id();
46                       int dstIP = Trie.byteArrayToInt(Trie.htonl(inRecord.getDstaddr()));
        46               int dstIP = IpToInt.htonl(inRecord.getDstaddr());
47      47               Short egressRtr = 0;
48      48
49      49               // Get the egress router from the fetched trie
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/GleaningAnnotation.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/GleaningAnnotation.java;h=aef11fd;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
19      19       import java.util.List;
20      20       import java.util.regex.Matcher;
21      21       import java.util.regex.Pattern;
        22       import com.guavus.mapred.common.trie.*;
23      23       import com.guavus.mapred.bizreflex.annotation.Global_Info.*;
24      24
25      25       public class GleaningAnnotation {
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/Global_Info.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/Global_Info.java;h=99fcc66;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
3       3        import java.io.DataInputStream;
4       4        import java.io.DataOutputStream;
5       5        import java.io.IOException;
        6        import com.guavus.mapred.common.trie.*;
6       7
7       8        import com.guavus.mapred.bizreflex.trie.*;
8       9
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/IntAnnotation.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/annotation/IntAnnotation.java;h=7e566e1;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
13      13       import com.guavus.mapred.bizreflex.annotation.SibAnnotation.InterfaceData;
14      14       import com.guavus.mapred.bizreflex.annotation.SibAnnotation.SibData;
15      15       import com.guavus.logging.LogLevel;
16               import com.guavus.mapred.bizreflex.trie.Trie;
17      16       import collector.adapters.NetflowRecordIdl;
18      17       import com.guavus.mapred.bizreflex.cube.GLEANINGDimension;
19      18       import com.guavus.mapred.bizreflex.cube.GLEANINGMeasure;
20      19       import com.guavus.mapred.common.collection.*;
21      20       import com.guavus.mapred.bizreflex.annotation.GleaningAnnotation.RoutInt;
22      21       import com.guavus.mapred.bizreflex.annotation.Global_Info.*;
        22       import com.guavus.mapred.common.trie.*;
24      23       public class IntAnnotation {
25      24           static com.guavus.logging.Logger Logger = new com.guavus.logging.Logger(IntAnnotation.class);
26      25
…
61      60               long ingressRtrFinal = exporterId; //Ingress router
62      61               long egressRtrFinal = -1;          //Egress router
63      62
64                       int dstIP = Trie.byteArrayToInt(Trie.htonl((int)dip));
65                       int srcIP = Trie.byteArrayToInt(Trie.htonl((int)sip));
        63               int dstIP = (IpToInt.htonl((int)dip));
        64               int srcIP = (IpToInt.htonl((int)sip));
66      65
67      66              // Get sib data for exporter id
68      67               SibAnnotation.SibData sibData = SibAnnotation.sibHash.get(exporterId);
…
485     484                      long prefixLen = GLEANINGDimension.PrefixLen.getLong(dimension);
486     485                      long count = GLEANINGMeasure.TTS_B.getLong(measure);
487     486
488                              int IP = Trie.byteArrayToInt(Trie.htonl((int)ip));
        487                      int IP = (IpToInt.htonl((int)ip));
489     488
490     489                      if(0 == count)
491     490                      {
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/input/InputRecord.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/input/InputRecord.java;h=78bcdb9;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
2       2
3       3        import collector.adapters.IpfixFlowRecordIdl;
4       4        import collector.adapters.NetflowRecordIdl;
5                import com.guavus.mapred.bizreflex.trie.*;
        5        import com.guavus.mapred.common.trie.*;
6       6        import com.guavus.logging.LogLevel;
7       7
8       8        public class InputRecord {
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/job/AsWhiteListJob/Mapper.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/job/AsWhiteListJob/Mapper.java;h=4ce2e94;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
16      16       import org.apache.hadoop.io.BytesWritable;
17      17       import org.apache.hadoop.io.Text;
18      18
        19       import com.guavus.mapred.common.trie.IpToInt;
19      20       import com.guavus.mapred.common.collection.*;
20      21       import com.guavus.logging.LogLevel;
21      22       import com.guavus.mapred.common.input.*;
22      23       import com.guavus.mapred.common.dao.*;
23      24       import com.guavus.mapred.bizreflex.cube.*;
24               import com.guavus.mapred.bizreflex.trie.IpToInt;
25      25       import java.io.*;
26      26
27      27       public class Mapper extends org.apache.hadoop.mapreduce.Mapper<Object, Object, DimensionSet, MeasureSet> {
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/job/PotentialAsJob/Mapper.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/job/PotentialAsJob/Mapper.java;h=58874d8;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
19      19       import com.guavus.mapred.common.input.*;
20      20       import com.guavus.mapred.common.dao.*;
21      21       import com.guavus.mapred.bizreflex.cube.*;
22               import com.guavus.mapred.bizreflex.trie.IpToInt;
        22       import com.guavus.mapred.common.trie.IpToInt;
23      23
24      24       public class Mapper extends org.apache.hadoop.mapreduce.Mapper<Object, Object, DimensionSet, MeasureSet> {
25      25           static com.guavus.logging.Logger Logger = new com.guavus.logging.Logger(Mapper.class);
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/job/PrefixAsJob/Mapper.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/job/PrefixAsJob/Mapper.java;h=a0b1b22;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
18      18       import com.guavus.logging.LogLevel;
19      19       import com.guavus.mapred.common.input.*;
20      20       import com.guavus.mapred.common.dao.*;
        21       import com.guavus.mapred.common.trie.*;
21      22       import com.guavus.mapred.bizreflex.cube.*;
22               import com.guavus.mapred.bizreflex.trie.IpToInt;
23      23
24      24       public class Mapper extends org.apache.hadoop.mapreduce.Mapper<Object, Object, DimensionSet, MeasureSet> {
25      25           static com.guavus.logging.Logger Logger = new com.guavus.logging.Logger(Mapper.class);
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/BaseTrie.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/BaseTrie.java;h=0000000;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
1                package com.guavus.mapred.bizreflex.trie;
2
3                import java.util.ArrayList;
4
5                import com.guavus.logging.LogLevel;
6
7                public interface BaseTrie<K> {
8
9                    public byte trieGetMatchedLength(int addr, byte prefixLen) ;
10
11                   public K trieGetData(int addr, byte prefixLen) ;
12
13                   public K trieAddNode(int addr, byte prefixLen, K data);
14               }
Changed file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/BinaryEibAsibConvertor.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/BinaryEibAsibConvertor.java;h=2a437cd;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
20      20
21      21       import com.guavus.logging.LogLevel;
22      22       import com.guavus.mapred.bizreflex.annotation.Global_Info.RouterData;
        23       import com.guavus.mapred.common.trie.*;
23      24
24      25       public class BinaryEibAsibConvertor {
25      26           static com.guavus.logging.Logger Logger = new com.guavus.logging.Logger(BinaryEibAsibConvertor.class);
…
212     213                      RouterData dataRO = roTrie.trieGetData(addr, (byte) 32);
213     214                      int prefixLenRO = roTrie.trieGetMatchedLength(addr, (byte)32);
214     215
215                              IpVersionFour<RouterData> nodeRW = rwTrie.getIpv4Node(TrieReadOnly.htonl(addr), (byte)32);
216                              RouterData dataRW = null;
217                              int prefixLenRW = -1;
218
219                              if (nodeRW != null) {
220                                  dataRW = nodeRW.data;
221                                  prefixLenRW = nodeRW.prefixLen;
222                              }
        216                      RouterData dataRW = rwTrie.trieGetData(addr, (byte) 32);
        217                      int prefixLenRW = rwTrie.trieGetMatchedLength(addr, (byte)32);
223     218
224     219                      if (dataRO != null) {
225     220                          if (dataRO.equals(dataRW)) {
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/IpToInt.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/IpToInt.java;h=0000000;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
1                package com.guavus.mapred.bizreflex.trie;
2
3                public class IpToInt {
4                    public static int convert(String addr) {
5                        if (addr.indexOf(".") == -1) {
6                            return Integer.parseInt(addr);
7                        } else {
8                            return(byteArrayToInt(convertToByteArr(addr)));
9                        }
10                   }
11
12                   public static String convertBack(int addr) {
13                       return(byteArrayToString(intToByteArray(addr)));
14                   }
15
16                   private static byte[] convertToByteArr(String addr) {
17                       String[] addrArray = addr.split("\\.");
18
19                       byte[] byteArr = new byte[4];
20
21                       for (int i = 0; i < addrArray.length; i++) {
22                           byteArr[i] = (byte)Integer.parseInt(addrArray[i]);
23                       }
24
25                       return byteArr;
26                   }
27
28                   private static int byteArrayToInt(byte[] b) {
29                       int value = 0;
30                       for (int i = 0; i < 4; i++) {
31                           int shift = (i) * 8;
32                           value += (b[i] & 0x000000FF) << shift;
33                       }
34                       return value;
35                   }
36
37                   private static byte[] intToByteArray(int x) {
38                       byte[] res = new byte[4];
39
40                       for (int i = 3; i >= 0; i--) {
41                           res[i] = (new Integer(x >>> 24)).byteValue();
42                           x <<= 8;
43                       }
44                       return res;
45                   }
46
47                   private static String byteArrayToString(byte[] b) {
48                       return (Integer.toString(promotoToInt(b[3])) + "." +
49                               Integer.toString(promotoToInt(b[2])) + "." +
50                               Integer.toString(promotoToInt(b[1])) + "." +
51                               Integer.toString(promotoToInt(b[0])));
52                   }
53
54                   private static int promotoToInt(byte x) {
55                       byte[] b = new byte[4];
56                       b[0] = x;
57                       b[1] = 0;
58                       b[2] = 0;
59                       b[3] = 0;
60
61                       return byteArrayToInt(b);
62                   }
63
64                   public static int htonl(int x) {
65                       byte[] res = new byte[4];
66
67                       for (int i = 0; i < 4; i++) {
68                           res[i] = (new Integer(x >>> 24)).byteValue();
69                           x <<= 8;
70                       }
71
72                       return byteArrayToInt(res);
73                   }
74               }
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/IpVersionFour.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/IpVersionFour.java;h=0000000;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
1                package com.guavus.mapred.bizreflex.trie;
2
3                import java.nio.ByteBuffer;
4                import java.util.ArrayList;
5                import java.util.HashMap;
6
7                import com.guavus.logging.LogLevel;
8
9                public class IpVersionFour<K> {
10                   static com.guavus.logging.Logger Logger = new com.guavus.logging.Logger(IpVersionFour.class);
11                   public byte prefixLen;
12                   public int addr;
13                   public K data;
14                   public IpVersionFour<K> left;
15                   public IpVersionFour<K> right;
16
17                   protected static final byte DATA_NOT_NULL_MASK = (byte) 0x1;
18                   protected static final byte LEFT_NOT_NULL_MASK = (byte) 0x2;
19                   protected static final byte RIGHT_NOT_NULL_MASK = (byte) 0x4;
20                   protected static final byte DATA_INDEX_SHORT_MASK = (byte) 0x8;
21                   protected static final byte LEFT_OFFSET_SHORT_MASK = (byte) 0x10;
22                   protected static final byte RIGHT_OFFSET_SHORT_MASK = (byte) 0x20;
23
24                   IpVersionFour() {
25                   }
26
27                   protected static final int PREFIX_OFFSET = 0;
28                   protected static final int ADDRESS_OFFSET = 1;
29                   protected static final int FLAG_OFFSET = 5;
30                   protected static final int DATA_OFFSET = 6;
31                   protected static final int[] LEFT_NODE_POSITION = new int[16];
32                   protected static final int[] RIGHT_OFFSET_POSITION = new int[16];
33
34                   /**
35                    * Serialized object format
36                    * -------------------------------------------------------------------------------------------
37                    * | PREFIX | ADDRESS   | FLAG   | DATA INDEX      | RIGHT OFFSET  | LEFT NODE  | RIGHT NODE  |
38                    * | 1 byte | 4 bytes   | 1 byte | 0, 2 or 4 bytes | 0 or 4 bytes  | variable   | variable    |
39                    * -------------------------------------------------------------------------------------------
40                    * |<-------------------------- RIGHT_OFFSET value ---------------------------->|
41                    * |<--------------- LEFT_NODE_POSITION[flag] -------------------->|
42                    * |<-------- RIGHT_OFFSET_POSITION[flag]--------->|
43                    *
44                    * The width of variable fields is captured by the flag value.
45                    */
46                   static {
47                       for (int i = 0; i <= 15; ++i) {
48                           if ((i & LEFT_NOT_NULL_MASK) != 0) {
49                               LEFT_NODE_POSITION[i] = DATA_OFFSET;
50                               if ((i & DATA_NOT_NULL_MASK) != 0) {
51                                   if ((i & DATA_INDEX_SHORT_MASK) != 0) {
52                                       LEFT_NODE_POSITION[i] += 2;
53                                   } else {
54                                       LEFT_NODE_POSITION[i] += 4;
55                                   }
56                               }
57                               if ((i & RIGHT_NOT_NULL_MASK) != 0) {
58                                   if ((i & RIGHT_OFFSET_SHORT_MASK) != 0) {
59                                       LEFT_NODE_POSITION[i] += 4; // possible compression, but unused
60                                   } else {
61                                       LEFT_NODE_POSITION[i] += 4;
62                                   }
63                               }
64                           } else {
65                               LEFT_NODE_POSITION[i] = -1;
66                           }
67
68                           if ((i & RIGHT_NOT_NULL_MASK) != 0) {
69                               RIGHT_OFFSET_POSITION[i] = DATA_OFFSET;
70                               if ((i & DATA_NOT_NULL_MASK) != 0) {
71                                   if ((i & DATA_INDEX_SHORT_MASK) != 0) {
72                                       RIGHT_OFFSET_POSITION[i] += 2;
73                                   } else {
74                                       RIGHT_OFFSET_POSITION[i] += 4;
75                                   }
76                               }
77
78                           } else {
79                               RIGHT_OFFSET_POSITION[i] = -1;
80                           }
81                       }
82                       for (byte i = 0; i <= 15; ++i) {
83                           Logger.log(LogLevel.DEBUG, "flag:\t" + i + " \tLEFT_NODE_POSITION:\t" + LEFT_NODE_POSITION[i] + " \tRIGHT_OFFSET_POSITION:\t"
84                                   + RIGHT_OFFSET_POSITION[i]);
85                       }
86                   }
87
88                   /**
89                    * To be used for testing only, not needed otherwise. Can also be used by utility that created the Trie in required
90                    * format. However, long term solution is to have this logic in Routing Engine
91                    *
92                    * @param buf
93                    * @return
94                    */
95                   int toByteBuffer(ByteBuffer buf, HashMap<K, Integer> dataObjectMap, ArrayList<K> dataObjectList) {
96                       int nodeStartPosition = buf.position();
97                       buf.put(prefixLen);
98                       buf.putInt(addr);
99                       byte flag = 0;
100                      int flagPosition = buf.position();
101                      buf.position(flagPosition + 1); // reserving 1 byte for the flag
102
103                      int dataIndex = -1;
104
105                      if (data != null) {
106                          Integer val = dataObjectMap.get(data);
107                          if (val == null) {
108                              // data object seen for first time, lets insert
109                              dataIndex = dataObjectList.size();
110                              dataObjectList.add(data);
111                              dataObjectMap.put(data, Integer.valueOf(dataIndex));
112                          } else {
113                              dataIndex = val.intValue();
114                          }
115                          if (dataIndex > Short.MAX_VALUE) {
116                              buf.putInt(dataIndex);
117                          } else {
118                              buf.putShort((short) dataIndex);
119                              flag |= DATA_INDEX_SHORT_MASK;
120                          }
121                          flag |= DATA_NOT_NULL_MASK;
122                      }
123                      int rightOffsetPosition = -1;
124                      if (right != null) {
125                          rightOffsetPosition = buf.position();
126                          buf.position(rightOffsetPosition + 4); // reserving for right child position
127                      }
128                      if (left != null) {
129                          left.toByteBuffer(buf, dataObjectMap, dataObjectList);
130                          flag |= LEFT_NOT_NULL_MASK;
131                      }
132                      if (right != null) {
133                          buf.putInt(rightOffsetPosition, buf.position() - nodeStartPosition);
134                          // right child starts now, offset recorded relative to node start
135                          right.toByteBuffer(buf, dataObjectMap, dataObjectList);
136                          flag |= RIGHT_NOT_NULL_MASK;
137                      }
138                      buf.put(flagPosition, flag);
139                      return 0;
140                  }
141
142                  /**
143                   * To be used for testing only, not needed otherwise.
144                   */
145                  void fromByteBuffer(ByteBuffer buf, ArrayList<K> dataObjectList) {
146                      prefixLen = buf.get();
147                      addr = buf.getInt();
148                      byte flag = buf.get();
149                      int dataIndex = ((flag & DATA_NOT_NULL_MASK) != 0) ? (((flag & DATA_INDEX_SHORT_MASK) != 0) ? buf.getShort()
150                              : buf.getInt()) : -1;
151                      int rightStart = ((flag & RIGHT_NOT_NULL_MASK) != 0) ? buf.getInt() : -1; // right child offset, can validate
152                      if (dataIndex != -1) {
153                          data = dataObjectList.get(dataIndex);
154                      } else {
155                          data = null;
156                      }
157                      if ((flag & LEFT_NOT_NULL_MASK) == 0) {
158                          left = null;
159                      } else {
160                          left = new IpVersionFour<K>();
161                          left.fromByteBuffer(buf, dataObjectList);
162                      }
163                      if (rightStart == -1) {
164                          right = null;
165                      } else {
166                          if (rightStart != buf.position()) {
167                              throw new IllegalArgumentException();
168                          }
169                          right = new IpVersionFour<K>();
170                          right.fromByteBuffer(buf, dataObjectList);
171                      }
172                  }
173              }
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/Trie.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/Trie.java;h=0000000;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
1                package com.guavus.mapred.bizreflex.trie;
2
3                import java.util.ArrayList;
4                import java.util.HashMap;
5
6                import com.guavus.logging.LogLevel;
7                import com.guavus.logging.Logger;
8
9
10               public class Trie<K> implements BaseTrie<K>{
11                   static com.guavus.logging.Logger Logger = new com.guavus.logging.Logger(Trie.class);
12                   public static boolean traceLookup = false;
13                   private IpVersionFour<K> root;
14
15                   public Trie() {
16                       root = null;
17                   }
18
19                   public static byte[] htonl(int x)   {
20                       byte[] res = new byte[4];
21
22                       for (int i = 0; i < 4; i++) {
23                           res[i] = (new Integer(x >>> 24)).byteValue();
24                           x <<= 8;
25                       }
26                       return res;
27                   }
28
29                   public static int byteArrayToInt(byte[] b) {
30                       int value = 0;
31                       for (int i = 0; i < 4; i++) {
32                           int shift = (i) * 8;
33                           value += (b[i] & 0x000000FF) << shift;
34                       }
35                       return value;
36                   }
37
38                   private int promotoToInt(byte x) {
39                       byte[] b = new byte[4];
40                       b[0] = x;
41                       b[1] = 0;
42                       b[2] = 0;
43                       b[3] = 0;
44
45                       return byteArrayToInt(b);
46                   }
47
48                   private boolean matchIpV4(int n, byte nLen, int p, byte pLen) {
49                       int diffBits;
50
51                       if (nLen > pLen) {
52                           return false;
53                       }
54
55                       if (nLen == 0) {
56                           return true;
57                       }
58
59                       diffBits = (n ^ p) >>> (32 - nLen);
60
61                       return (diffBits == 0);
62                   }
63
64                   public K trieAddNode(int addr, byte prefixLen, K data) {
65                       IpVersionFour<K> node;
66                       boolean left = true;
67                       IpVersionFour<K> p, newNode;
68                       int v4Addr;
69                       byte[] diffBits, tmp;
70                       byte i = 0;
71                       byte j = 0;
72
73                       node = root;
74                       v4Addr = byteArrayToInt(htonl(addr));
75
76                       for (p = root; ((p != null) && matchIpV4(p.addr, p.prefixLen, v4Addr, prefixLen));) {
77                           if (p.prefixLen == prefixLen)
78                           {
79                               if(p.data == null)
80                               {
81                                    p.data = data;
82                               }
83                               return p.data;
84                           }
85
86                           node = p;
87
88                           if (((v4Addr >>> (31 - p.prefixLen)) & 1) != 0) {
89                               p = p.right;
90                               left = false;
91                           } else {
92                               p = p.left;
93                               left = true;
94                           }
95                       }
96
97                       if (p != null) {
98                           newNode = new IpVersionFour<K>();
99                           newNode.data = null;
100                          newNode.addr = v4Addr;
101
102                          diffBits = htonl (v4Addr ^ p.addr);
103
104                          if (byteArrayToInt(diffBits) != 0) {
105                              for (tmp = diffBits, i = 0; tmp[i] == 0; i++);
106
107                              j = tmp[i];
Diff too large and stripped…
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/TrieReadOnly.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/bizreflex/trie/TrieReadOnly.java;h=0000000;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/BaseTrie.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/BaseTrie.java;h=2ccd6cc;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/IpToInt.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/IpToInt.java;h=aba9a2f;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/IpVersionFour.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/IpVersionFour.java;h=443efc3;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/Trie.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/Trie.java;h=4125942;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>
Deleted file AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/TrieReadOnly.java<https://guavus-gurgaon/gitweb?p=solutions/mapreduce.git;f=AtlasCubeCreator/src/main/java/com/guavus/mapred/common/trie/TrieReadOnly.java;h=f58b2be;hb=18dd99a91de22633cfe6354f5672bed3c058ebef>