/*

 * Copyright (c) 2000, 2018, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 *

 *  (C) Copyright IBM Corp. 1999 All Rights Reserved.

 *  Copyright 1997 The Open Group Research Institute.  All rights reserved.

 */

package sun.security.krb5.internal.rcache;

import sun.security.krb5.internal.Krb5;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.ListIterator;

import sun.security.krb5.internal.KerberosTime;

import sun.security.krb5.internal.KrbApErrException;

/**

 * This class provides an efficient caching mechanism to store AuthTimeWithHash

 * from client authenticators. The cache minimizes the memory usage by doing

 * self-cleanup of expired items in the cache.

 *

 * AuthTimeWithHash objects inside a cache are always sorted from big (new) to

 * small (old) as determined by {@link AuthTimeWithHash#compareTo}. In the most

 * common case a newcomer should be newer than the first element.

 *

 * @author Yanni Zhang

 */

public class AuthList {

    private final LinkedList<AuthTimeWithHash> entries;

    private final int lifespan;

    // entries.getLast().ctime, updated after each cleanup.

    private volatile int oldestTime = Integer.MIN_VALUE;

    /**

     * Constructs a AuthList.

     */

    public AuthList(int lifespan) {

        this.lifespan = lifespan;

        entries = new LinkedList<>();

    }

    /**

     * Puts the authenticator timestamp into the cache in descending order,

     * and throw an exception if it's already there.

     */

    public synchronized void put(AuthTimeWithHash t, KerberosTime currentTime)

            throws KrbApErrException {

        if (entries.isEmpty()) {

            entries.addFirst(t);

            oldestTime = t.ctime;

            return;

        } else {

            AuthTimeWithHash temp = entries.getFirst();

            int cmp = temp.compareTo(t);

            if (cmp < 0) {

                // This is the most common case, newly received authenticator

                // has larger timestamp.

                entries.addFirst(t);

            } else if (cmp == 0) {

                throw new KrbApErrException(Krb5.KRB_AP_ERR_REPEAT);

            } else {

                //unless client clock being re-adjusted.

                ListIterator<AuthTimeWithHash> it = entries.listIterator(1);

                boolean found = false;

                while (it.hasNext()) {

                    temp = it.next();

                    cmp = temp.compareTo(t);

                    if (cmp < 0) {

                        // Find an older one, put in front of it

                        entries.add(entries.indexOf(temp), t);

                        found = true;

                        break;

                    } else if (cmp == 0) {

                        throw new KrbApErrException(Krb5.KRB_AP_ERR_REPEAT);

                    }

                }

                if (!found) {

                    // All is newer than the newcomer. Sigh.

                    entries.addLast(t);

                }

            }

        }

        // let us cleanup while we are here

        long timeLimit = currentTime.getSeconds() - lifespan;

        // Only trigger a cleanup when the earliest entry is

        // lifespan + 5 sec ago. This ensures a cleanup is done

        // at most every 5 seconds so that we don't always

        // addLast(removeLast).

        if (oldestTime > timeLimit - 5) {

            return;

        }

        // and we remove the *enough* old ones (1 lifetime ago)

        while (!entries.isEmpty()) {

            AuthTimeWithHash removed = entries.removeLast();

            if (removed.ctime >= timeLimit) {

                entries.addLast(removed);

                oldestTime = removed.ctime;

                return;

            }

        }

        oldestTime = Integer.MIN_VALUE;

    }

    public boolean isEmpty() {

        return entries.isEmpty();

    }

    public String toString() {

        StringBuilder sb = new StringBuilder();

        Iterator<AuthTimeWithHash> iter = entries.descendingIterator();

        int pos = entries.size();

        while (iter.hasNext()) {

            AuthTimeWithHash at = iter.next();

            sb.append('#').append(pos--).append(": ")

                    .append(at.toString()).append('\n');

        }

        return sb.toString();

    }

}