TokenBucket 2.0!

Bob Balaban  February 7 2015 06:07:16 PM

Greetings, Geeks!

I went back and looked at the code I posted here several months ago for doing time-based access counting. I realized that it could be improved and cleaned up just a bit, so I'm sharing a revised version with you here.


import java.util.Date;
import java.util.LinkedList;

public class TimeBasedAccessList {

     // This is the list of time values. New entries are always
     // added at the "tail", so the "head" is always the oldest value.
     // This collection is a little bit more efficient than using (for
     // example) a TreeSet, which will sort new entries into the tree.
     private LinkedList timeSet = new LinkedList();
     private int nCalls;                        // count of allowed calls
     private long timeWindow;        // in millisec
     
     public TimeBasedAccessList(int N, long M) {
             nCalls = N;
             timeWindow = M;
     }

     public synchronized boolean isCallOK() {
             long now = new Date().getTime();
             long earliest = now - this.timeWindow;
             
             // remove entries older than "earliest"
             // can't use "for" loop with removals inside
             while (!this.timeSet.isEmpty()) {
                     Long L = this.timeSet.peekFirst();         // "lowest" valued element is earliest timestamp
                     if (L.longValue() <= earliest) {
                             this.timeSet.remove(L);
                     }
                     else {
                             // no more entries out of window
                             break;
                     }
             } // end for
             
             // see how many entries there are
             if (this.timeSet.size() >= this.nCalls) {
                     return false;
             }
             
             // add new entry at the end of the list
             this.timeSet.add(new Long(now));
             return true;
     } // end isCallOK
     
} // end class

I really only made 3 changes:
1) removed "volatile" declaration on the member timeSet. Since this member variable is only ever set one time (at object construction time), there's no point in making it volatile.

2) I changed the data structure used to store the list of date/time values from a TreeSet to a somewhat simpler LinkedList, which in this application is a bit more efficient. The reason is that with a TreeSet, every time you add a new element, the TreeSet evaluates the "ordinary value" of that element to see where it should sit in the (sorted) tree. We don't really need that functionality here, because we know for sure that newer elements (later time values) are going to be larger than any earlier ones (because time marches on, naturally). So we just add new elements to the end of the list, and examine and/or remove older elements (smaller time values) from the front or head of the list.

3) Use the LinkedList specific method peekFirst() to look at (but not remove) the element at the head of the list. Note that the remove() and add() methods don't change, they exist in both classes.

So, there you have it. Enjoy, and Geek ya Later!

Follow me on Twitter @LooseleafLLC
This article ©Copyright 2015 by Looseleaf Software LLC, all rights reserved. You may link to this page, but may not copy without prior approval.

• Comments [0]