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>