zxingorg/src/com/google/zxing/web/IPTrie.java

   1 /*\r
   2  * Copyright 2008 Google Inc.\r
   3  *\r
   4  * Licensed under the Apache License, Version 2.0 (the "License");\r
   5  * you may not use this file except in compliance with the License.\r
   6  * You may obtain a copy of the License at\r
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  * Unless required by applicable law or agreed to in writing, software\r
  11  * distributed under the License is distributed on an "AS IS" BASIS,\r
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  * See the License for the specific language governing permissions and\r
  14  * limitations under the License.\r
  15  */\r
  16 \r
  17 package com.google.zxing.web;\r
  18 \r
  19 import java.net.InetAddress;\r
  20 import java.util.Arrays;\r
  21 \r
  22 /**\r
  23  * A trie data structure for storing a set of IP addresses efficiently.\r
  24  * \r
  25  * @author Sean Owen (srowen@google.com)\r
  26  */\r
  27 final class IPTrie {\r
  28 \r
  29   private final IPTrieNode root;\r
  30 \r
  31   IPTrie() {\r
  32     root = new IPTrieNode(false);\r
  33   }\r
  34 \r
  35   int incrementAndGet(InetAddress ipAddress) {\r
  36     byte[] octets = ipAddress.getAddress();\r
  37     synchronized (root) {\r
  38       IPTrieNode current = root;\r
  39       int max = octets.length - 1;\r
  40       for (int offset = 0; offset < max; offset++) {\r
  41         int index = 0xFF & octets[offset];\r
  42         IPTrieNode child = current.children[index];\r
  43         if (child == null) {\r
  44           child = new IPTrieNode(offset == max - 1);\r
  45           current.children[index] = child;\r
  46         }\r
  47         current = child;\r
  48       }\r
  49       int index = 0xFF & octets[max];\r
  50       current.values[index]++;\r
  51       return current.values[index];\r
  52     }\r
  53   }\r
  54 \r
  55   void clear() {\r
  56     synchronized (root) {\r
  57       Arrays.fill(root.children, null);\r
  58     }\r
  59   }\r
  60 \r
  61   private static final class IPTrieNode {\r
  62     final IPTrieNode[] children;\r
  63     final int[] values;\r
  64 \r
  65     private IPTrieNode(boolean terminal) {\r
  66       if (terminal) {\r
  67         children = null;\r
  68         values = new int[256];\r
  69       } else {\r
  70         children = new IPTrieNode[256];\r
  71         values = null;\r
  72       }\r
  73     }\r
  74   }\r
  75 \r
  76 }