KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > archive > util > fingerprint > MemLongFPSet


1 /* MemLongSet
2  *
3  * $Id: MemLongFPSet.java,v 1.1.16.1 2007/01/13 01:31:40 stack-sf Exp $
4  *
5  * Created on Oct 19, 2003
6  *
7  * Copyright (C) 2003 Internet Archive.
8  *
9  * This file is part of the Heritrix web crawler (crawler.archive.org).
10  *
11  * Heritrix is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU Lesser Public License as published by
13  * the Free Software Foundation; either version 2.1 of the License, or
14  * any later version.
15  *
16  * Heritrix is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU Lesser Public License for more details.
20  *
21  * You should have received a copy of the GNU Lesser Public License
22  * along with Heritrix; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24  */
25 package org.archive.util.fingerprint;
26
27 import java.io.Serializable JavaDoc;
28 import java.util.logging.Logger JavaDoc;
29
30 import org.archive.util.AbstractLongFPSet;
31
32 /**
33  * Open-addressing in-memory hash set for holding primitive long fingerprints.
34  *
35  * @author Gordon Mohr
36  */
37 public class MemLongFPSet extends AbstractLongFPSet
38 implements LongFPSet, Serializable JavaDoc {
39     
40     
41     private static final long serialVersionUID = -4301879539092625698L;
42
43
44     private static Logger JavaDoc logger =
45         Logger.getLogger(MemLongFPSet.class.getName());
46     private static final int DEFAULT_CAPACITY_POWER_OF_TWO = 10;
47     private static final float DEFAULT_LOAD_FACTOR = 0.75f;
48     protected byte[] slots;
49     protected long[] values;
50
51     public MemLongFPSet() {
52         this(DEFAULT_CAPACITY_POWER_OF_TWO, DEFAULT_LOAD_FACTOR);
53     }
54
55     /**
56      * @param capacityPowerOfTwo The capacity as the exponent of a power of 2.
57      * e.g if the capacity is <code>4</code> this means <code>2^^4</code>
58      * entries.
59      * @param loadFactor The load factor as a fraction. This gives the amount
60      * of free space to keep in the Set.
61      */
62     public MemLongFPSet(int capacityPowerOfTwo, float loadFactor) {
63         super(capacityPowerOfTwo, loadFactor);
64         slots = new byte[1 << capacityPowerOfTwo];
65         for(int i = 0; i < (1 << capacityPowerOfTwo); i++) {
66             slots[i] = EMPTY; // flag value for unused
67 }
68         values = new long[1 << capacityPowerOfTwo];
69     }
70
71     protected void setAt(long i, long val) {
72         slots[(int)i] = 1;
73         values[(int)i] = val;
74     }
75
76     protected long getAt(long i) {
77         return values[(int)i];
78     }
79
80     protected void makeSpace() {
81         grow();
82     }
83
84     private void grow() {
85         // Catastrophic event. Log its occurance.
86 logger.info("Doubling fingerprinting slots to "
87             + (1 << this.capacityPowerOfTwo));
88         long[] oldValues = values;
89         byte[] oldSlots = slots;
90         capacityPowerOfTwo++;
91         values = new long[1 << capacityPowerOfTwo];
92         slots = new byte[1 << capacityPowerOfTwo];
93         for(int i = 0; i < (1 << capacityPowerOfTwo); i++) {
94             slots[i]=EMPTY; // flag value for unused
95 }
96         count=0;
97         for(int i = 0; i< oldValues.length; i++) {
98             if(oldSlots[i]>=0) {
99                 add(oldValues[i]);
100             }
101         }
102     }
103
104     protected void relocate(long val, long oldIndex, long newIndex) {
105         values[(int)newIndex] = values[(int)oldIndex];
106         slots[(int)newIndex] = slots[(int)oldIndex];
107         slots[(int)oldIndex] = EMPTY;
108     }
109
110     protected int getSlotState(long i) {
111         return slots[(int)i];
112     }
113
114     protected void clearAt(long index) {
115         slots[(int)index]=EMPTY;
116         values[(int)index]=0;
117     }
118
119     public boolean quickContains(long fp) {
120         return contains(fp);
121     }
122 }
Popular Tags