1 /* Copyright (C) 2003 Internet Archive.
2 *
3 * This file is part of the Heritrix web crawler (crawler.archive.org).
4 *
5 * Heritrix is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU Lesser Public License as published by
7 * the Free Software Foundation; either version 2.1 of the License, or
8 * any later version.
9 *
10 * Heritrix is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Lesser Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser Public License
16 * along with Heritrix; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 *
19 * LongFPSetCache.java
20 * Created on Oct 21, 2003
21 *
22 * $Header$
23 */
24 package org.archive.util.fingerprint;
25
26
27
28 /***
29 * Like a MemLongFPSet, but with fixed capacity and maximum size.
30 * When an add would expand past the maximum size, an old entry
31 * is deleted via a clock/counter algorithm.
32 *
33 * @author gojomo
34 *
35 */
36 public class LongFPSetCache extends MemLongFPSet {
37
38 private static final long serialVersionUID = -5307436423975825566L;
39
40 long sweepHand = 0;
41
42 public LongFPSetCache() {
43 super();
44 }
45
46 public LongFPSetCache(int capacityPowerOfTwo, float loadFactor) {
47 super(capacityPowerOfTwo, loadFactor);
48 }
49
50 protected void noteAccess(long index) {
51 if(slots[(int)index]<Byte.MAX_VALUE) {
52 slots[(int)index]++;
53 }
54 }
55
56 protected void makeSpace() {
57 discard(1);
58 }
59
60 private void discard(int i) {
61 int toDiscard = i;
62 while(toDiscard>0) {
63 if(slots[(int)sweepHand]==0) {
64 removeAt(sweepHand);
65 toDiscard--;
66 } else {
67 if (slots[(int)sweepHand]>0) {
68 slots[(int)sweepHand]--;
69 }
70 }
71 sweepHand++;
72 if (sweepHand==slots.length) {
73 sweepHand = 0;
74 }
75 }
76 }
77 }