# FastFindCache.java

    /*
    ** Module   : FastFindCache.java
    ** Abstract : Caches and serves record information based on the find properties in order to avoid the database
    **            trip, making the simple queries much faster.
    **
    ** Copyright (c) 2020-2024, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- ---------------------------------------Description---------------------------------------
    ** 001 OM  20200708 First revision.
    ** 002 ECF 20201201 Minor optimization.
    **     OM  20210927 The cache must take into account changes of all field, not only from unique indexes.
    **     ECF 20211005 Reworked invalidation of cached results referencing non-indexed properties to be more
    **                  performant. As a trade-off, queries referencing non-indexed properties, which produce a
    **                  negative result (i.e., no record is found) do not have the negative result cached.
    **     CA  20220104 Node.l3Cache must be a weak reference, otherwise once the direct cache invalidates a key,
    **                  the reverse lookup has no chance of being cleaned up, as this is not done explicitly.
    ** 003 AL2 20220608 Implemented synchronizeWithReturn to avoid creating separate results array.
    ** 004 DDF 20230608 Made the size of the L2 and L3 caches configurable.
    **     DDF 20230613 Removed the static block that reads the configuration sizes of the cache.
    **                  CacheManager will handle the finding of the configuration size and the
    **                  cache creation.
    **     DDF 20230627 Made the cache final.
    ** 005 CA  20240323 Resolve the FieldReference value when the cache key is built, to allow cachine on this
    **                  value.
    ** 006 AI  20240418 Updated constructor of Key to take the non indexed props as difference of all props and
    **                  only indexed props used in query instead of all indexed props.
    ** 007 RAA 20240613 Added tenantInstances map for storing instances of FastFindCache per tenant + database id.
    **     BS  20230511 Shared cache instance per persistent database.
    **     RAA 20240627 Added removeCache method.
    ** 008 SP  20240731 Replaced calls to synchronizeWithReturn and synchronize with specific function calls,
    **                  to reduce capturing lambda usage.
    ** 009 OM  20240909 Tenant caches use tenant databases as keys and are stored as normal values.
    ** 010 CA  20240924 Allow a L2/L3 cache to be cleared instead of discarding the instace, to help the garbage
    **                  collector.
    */

    /*
    ** This program is free software: you can redistribute it and/or modify
    ** it under the terms of the GNU Affero General Public License as
    ** published by the Free Software Foundation, either version 3 of the
    ** License, or (at your option) any later version.
    **
    ** This program 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 Affero General Public License for more details.
    **
    ** You may find a copy of the GNU Affero GPL version 3 at the following
    ** location: https://www.gnu.org/licenses/agpl-3.0.en.html
    **
    ** Additional terms under GNU Affero GPL version 3 section 7:
    **
    **   Under Section 7 of the GNU Affero GPL version 3, the following additional
    **   terms apply to the works covered under the License.  These additional terms
    **   are non-permissive additional terms allowed under Section 7 of the GNU
    **   Affero GPL version 3 and may not be removed by you.
    **
    **   0. Attribution Requirement.
    **
    **     You must preserve all legal notices or author attributions in the covered
    **     work or Appropriate Legal Notices displayed by works containing the covered
    **     work.  You may not remove from the covered work any author or developer
    **     credit already included within the covered work.
    **
    **   1. No License To Use Trademarks.
    **
    **     This license does not grant any license or rights to use the trademarks
    **     Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
    **     of Golden Code Development Corporation. You are not authorized to use the
    **     name Golden Code, FWD, or the names of any author or contributor, for
    **     publicity purposes without written authorization.
    **
    **   2. No Misrepresentation of Affiliation.
    **
    **     You may not represent yourself as Golden Code Development Corporation or FWD.
    **
    **     You may not represent yourself for publicity purposes as associated with
    **     Golden Code Development Corporation, FWD, or any author or contributor to
    **     the covered work, without written authorization.
    **
    **   3. No Misrepresentation of Source or Origin.
    **
    **     You may not represent the covered work as solely your work.  All modified
    **     versions of the covered work must be marked in a reasonable way to make it
    **     clear that the modified work is not originating from Golden Code Development
    **     Corporation or FWD.  All modified versions must contain the notices of
    **     attribution required in this license.
    */

    package com.goldencode.p2j.persist;

    import com.goldencode.cache.*;
    import com.goldencode.p2j.persist.orm.*;
    import com.goldencode.p2j.security.*;
    import com.goldencode.p2j.util.*;
    import java.lang.ref.*;
    import java.util.*;
    import java.util.BitSet;
    import java.util.concurrent.ConcurrentHashMap;

    /**
     * Implementation of FastFind caching algorithm. The internal structures use a triple-cache to store the
     * id-s of the records that should be present in session cache. The first level is keyed by the table unique
     * identifier. The second level is the index id, also guaranteed to be unique (positive for unique indexes and
     * negative for the rest). The last level is keyed by the FQL of the query, the navigation type, and
     * substitution parameters. We need to store the identifier (private key) as the cache value, rather than the
     * DMO instance itself, because:
     * <ul>
     *    <li>DMO instances cannot be shared across contexts;</li>
     *    <li>we don't want two sources of cached DMO instances.</li>
     * </ul>
     * <p>
     * Temporary tables are handled as context-local. Permanent tables are shared, but only within one database to
     * avoid mix-ups when separate databases use same names for tables. Thus, pointer to a database is required to
     * lookup tables - it is used as a key leading to appropriate cache instance.
     * <p>
     * The first two levels of cache size are not limited. They are the table and indexes unique ids and are
     * stable, governed by database structure. Only the very last level is an actual {@code LRUCache} object
     * whose size will need to be configured based on how many records should be cached for each index of a
     * table. However, since the invalidation of the cache will occur quite often, the value can be kept small.
     * <p>
     * Cache Invalidation: the cache is individually invalidated for each affected index when a record is updated.
     * On insert and delete operations all indices are invalidated for respective table. On a rollback event all
     * affected tables are invalidated.
     * <p>
     * Concurrency: The cache access is thread-safe for temporary because the instances are context local. When
     * accessing the permanent table shared instances, all accesses are synchronized since the LRU cache
     * implementation also alter the internal structure.
     *
     * TODO: implement support for {@code Resolvable} substitution parameters.
     */
    public class FastFindCache
    {
       /** Constant for representing a negative result (i.e., the lack of result) for a query. */
       public static final RecordIdentifier<String> NO_RECORD = new RecordIdentifier<>("", -1L);

       /** The instances for permanent database(s). */
       private static final Map<Database, FastFindCache> permanentInstances = new ConcurrentHashMap<>();

       /** The context-local instance for the current session for temp-tables. */
       private static final ContextLocal<FastFindCache> tempTableInstances = new ContextLocal<FastFindCache>()
       {
          @Override
          protected FastFindCache initialValue()
          {
             return new FastFindCache(false);
          }
       };

       /** The internal data, as a triple-level cache: table-uid x index x other-information. */
       private final Map<Long, Map<Integer, Cache<L2Key, RecordIdentifier<String>>>> cache = new HashMap<>();

       /** Reverse cache of record identifiers to invalidation info, for queries with non-indexed properties */
       private final ReverseLookup reverseLookup = new ReverseLookup();

       /** Differentiate between permanent and temporary tables and caches. */
       private final boolean isPermanent;

       /**
        * Constructor for internal use.
        *
        * @param   isPermanent
        *          Differentiate between permanent and temporary tables and caches.
        */
       private FastFindCache(boolean isPermanent)
       {
          this.isPermanent = isPermanent;
       }

       /**
        * Obtain the singleton instance, if FastFind mode enabled.
        * Return {@code null} to disable FastFind mode.
        *
        * @param   temporary
        *          Use {@code true} to get the instance object for a temp-table database. They are context-local
        *          objects. When {@code false} the global instance for permanent databases is returned.
        * @param   database
        *          The instance of the database to work with.
        *
        * @return  the static instance of {@code FastFindCache}, or {@code null} if FastFind mode is disabled.
        */
       public static FastFindCache getInstance(boolean temporary, Database database)
       {
          if (temporary)
          {
             return tempTableInstances.get();
          }

          if (database == null)
          {
             throw new IllegalArgumentException("Database can not be null when instantiating FastFindCache");
          }

          return permanentInstances.computeIfAbsent(database, db -> new FastFindCache(true));
       }

       /**
        * Remove a cache based on a (tenant id, database id) key.
        *
        * @param   db
        *          The database to be deleted.
        */
       public static void removeTenantCache(Database db)
       {
          if (!db.isTenant())
          {
             System.err.println("This API can be used only for tenant databases.");
             return;
          }

          permanentInstances.remove(db);
       }

       /**
        * Combines the DMO uid and the optional temp-table multiplex value into a single {@code long} value.
        *
        * @param   uid
        *          The DMO uid.
        * @param   multiplex
        *          The {@code multiplex} value of a temp-table. Must be positive. Use 0 or {@code null} for
        *          permanent tables.
        *
        * @return  a single {@code long} value used as level 1 key in cache.
        */
       public static long combine(int uid, Integer multiplex)
       {
          if (multiplex == null || multiplex == 0)
          {
             return uid; // permanent tables
          }

          return (((long) multiplex) << 32) | uid;
       }

       /**
        * Creates a cache key.
        * <p>
        * If provided, all substitution parameters ({@code values}) are checked if they are instances of
        * {@code Resolvable}. These are not yet supported so no key is generated if they are encountered.
        *
        * @param   buffer
        *          The buffer that holds the record. Used for obtaining the DMO uid and multiplex (for
        *          temp-tables).
        * @param   indexId
        *          The id of the index used when executing the query.
        * @param   fql
        *          The fql of the query which selected the keyed record.
        * @param   properties
        *          The set of properties used in {@code fql}.
        * @param   type
        *          The type of navigation. Must be one of {@code FIRST}, {@code LAST} or {@code UNIQUE} values
        *          of the {@code QueryConstants}.
        * @param   values
        *          The substitution values. May be {@code null}.
        *
        * @return  a new {@code Key} for the provided parameters or {@code null} if not supported.
        */
       static Key createKey(RecordBuffer buffer,
                            int indexId,
                            String fql,
                            BitSet properties,
                            int type,
                            Object[] values)
       {
          if (values != null)
          {
             Object[] resolved = null;
             for (int i = 0; i < values.length; i++)
             {
                Object subst = values[i];
                if (subst instanceof FieldReference)
                {
                   if (resolved == null)
                   {
                      resolved = new Object[values.length];
                      System.arraycopy(values, 0, resolved, 0, values.length);
                      values = resolved;
                   }
                   resolved[i] = ((Resolvable) subst).resolve();
                }
                else if (subst instanceof Resolvable)
                {
                   return null;
                }
             }
          }

          // all substitution parameters were checked and none is a Resolvable.
          return new Key(buffer, indexId, fql, properties, type, values);
       }

       /**
        * Query the cache for a value.
        *
        * @param   k
        *          The key for cache.
        *
        * @return  a {@code RecordIdentifier} structure. In the case of a cache-hit, this is the key for
        *          a {@code Session} cache, and {@code null} otherwise.
        */
       public RecordIdentifier<String> get(Key k)
       {
          if (k == null)
          {
             // an invalid key caused by the presence of Resolvable substitution parameters in values
             return null;
          }

          if (!isPermanent)
          {
             // no synchronization needed here
             return getImpl(k);
          }

          synchronized (this)
          {
             return getImpl(k);
          }
       }

       /**
        * Saves a result in cache. Supports both real records and also "NOT-FOUND" results, when the second
        * parameter is {@code null}.
        *
        * @param   k
        *          The key for cache.
        * @param   value
        *          The value to be stored in cache. Only the primary key is important. If {@code null}, -1 will
        *          be used to mark the result as not present in database.
        */
       public void put(Key k, Record value)
       {
          // if no key or record represents a housekeeping (e.g., dirty database) copy or an incomplete record
          // (partial fields are populated due to EXCEPT/FIELDS options), don't store it
          if (k == null ||
              (value != null && (value.checkState(DmoState.COPY) || value.checkState(DmoState.INCOMPLETE))))
          {
             return; // throw some error?
          }

          if (!isPermanent)
          {
             // no synchronization needed here
             putImpl(k, value);
             return;
          }

          synchronized (this)
          {
             putImpl(k, value);
          }
       }

       /**
        * Invalidates the index for a table. Called when an operation on the table affected an index.
        *
        * @param   dmoUid
        *          The unique id of the table.
        * @param   multiplex
        *          The multiplex of the records to be invalidated, if any.
        * @param   unique
        *          The set of dirty unique indices which need to be invalidated.
        * @param   nonUnique
        *          The set of dirty unique indices which need to be invalidated.
        */
       public void invalidate(int dmoUid, Integer multiplex, BitSet unique, BitSet nonUnique)
       {
          if ((unique == null || unique.isEmpty()) && (nonUnique == null || nonUnique.isEmpty()))
          {
             return;
          }

          if (!isPermanent)
          {
             // no synchronization needed here
             invalidateImpl(dmoUid, multiplex, unique, nonUnique);
             return;
          }

          synchronized (this)
          {
             invalidateImpl(dmoUid, multiplex, unique, nonUnique);
          }
       }

       /**
        * Invalidate any cached result which matches the given DMO name and primary key, iff {@code dirtyProps}
        * intersects with the set of non-indexed properties used in the associated FQL query.
        *
        * @param   dmoName
        *          DMO implementation class name of the record that was touched.
        * @param   id
        *          Primary key of the DMO that was touched.
        * @param   dirtyProps
        *          The set of properties touched by an update to the DMO.
        */
       public void invalidate(String dmoName, long id, BitSet dirtyProps)
       {
          // quick out if nothing to do
          if (dirtyProps.isEmpty() || cache.isEmpty())
          {
             return; // this should not happen, anyway
          }

          if (!isPermanent)
          {
             // no synchronization needed here
             reverseLookup.invalidate(new RecordIdentifier<>(dmoName, id), dirtyProps);
             return;
          }

          synchronized (this)
          {
             reverseLookup.invalidate(new RecordIdentifier<>(dmoName, id), dirtyProps);
          }
       }

       /**
        * Invalidates all indexes of a table.
        *
        * @param   dmoUid
        *          The table uid whose indexes are invalidated.
        * @param   multiplex
        *          The multiplex of the records to be invalidated if any.
        */
       public void invalidate(int dmoUid, Integer multiplex)
       {
          invalidate(dmoUid, multiplex, false);
       }

       /**
        * Invalidates all indexes of a table.
        *
        * @param   dmoUid
        *          The table uid whose indexes are invalidated.
        * @param   multiplex
        *          The multiplex of the records to be invalidated if any.
        * @param   remove
        *          Flag indicating if the cache can be actual cleared, as the DMO is out of scope.
        */
       public void invalidate(int dmoUid, Integer multiplex, boolean remove)
       {
          long dmoId = combine(dmoUid, multiplex);
          if (!isPermanent)
          {
             if (remove)
             {
                cache.remove(dmoId);
                return;
             }

             // no synchronization needed here
             Map<Integer, Cache<L2Key, RecordIdentifier<String>>> map = cache.get(dmoId);
             if (map != null)
             {
                map.forEach((idxId, cache) -> cache.clear());
             }
             return;
          }

          synchronized (this)
          {
             if (remove)
             {
                cache.remove(dmoId);
                return;
             }

             Map<Integer, Cache<L2Key, RecordIdentifier<String>>> map = cache.get(dmoId);
             if (map != null)
             {
                map.forEach((idxId, cache) -> cache.clear());
             }
             return;
          }
       }

       /**
        * Invalidate a single index of a table.
        *
        * @param   dmoUid
        *          The table uid whose indexes are invalidated.
        * @param   multiplex
        *          Multiplex ID for a temp-table ({@code null} for a persistent table).
        * @param   idxUid
        *          Index identifier, unique to its table.
        */
       public void invalidate(int dmoUid, Integer multiplex, int idxUid)
       {
          if (!isPermanent)
          {
             // no synchronization needed here
             invalidateImpl(dmoUid, multiplex, idxUid);
             return;
          }

          synchronized (this)
          {
             invalidateImpl(dmoUid, multiplex, idxUid);
          }
       }

       /**
        * Invalidates records from a list of DMOs.
        *
        * @param   dmoList
        *          The collection of unique identifiers of the DMOs to be invalidated.
        */
       public void invalidate(Collection<Long> dmoList)
       {
          if (!isPermanent)
          {
             // no synchronization needed here
             invalidateImpl(dmoList);
             return;
          }

          synchronized (this)
          {
             invalidateImpl(dmoList);
          }
       }

       /**
        * Saves a result in cache. Supports both real records and also "NOT-FOUND" results, when the second
        * parameter is {@code null}.
        *
        * @param   k
        *          The key for cache.
        * @param   value
        *          The value to be stored in cache. Only the primary key is important. If {@code null}, -1 will
        *          be used to mark the result as not present in database.
        */
       private void putImpl(Key k, Record value)
       {
          // There are multiple configured sizes for the caches, the discriminator for the
          // L2 and L3 caches should not be changes since it is must be the same one
          // used in the directory configuration.
          Map<Integer, Cache<L2Key, RecordIdentifier<String>>> l2Cache =
             cache.computeIfAbsent(k.tableId, x -> CacheManager.createLinkedMapCache(FastFindCache.class,
                                                                                     "L2",
                                                                                     10));

          Cache<L2Key, RecordIdentifier<String>> l3Cache =
             l2Cache.computeIfAbsent(k.indexId, x -> CacheManager.createLRUCache(FastFindCache.class,
                                                                                 "L3",
                                                                                 100));

          // for a positive result (i.e., a record was found), ensure we use the canonical instance of the
          // record identifier, so that if it is stored in the reverse lookup cache, the weak keys can be
          // garbage collected
          RecordIdentifier<String> cacheVal =
             value == null
                ? NO_RECORD
                : reverseLookup.getCanonicalRecordIdentifier(new RecordIdentifier<>(value.getClass().getName(),
                                                                                    value.primaryKey()));

          boolean hasNonIndexedProps = k.k2.nonIndexedProps != null && !k.k2.nonIndexedProps.isEmpty();

          // cache all positive results (i.e., a record was found); only cache negative results (i.e., no
          // record was found) when the query references NO non-indexed properties
          if (cacheVal != NO_RECORD || !hasNonIndexedProps)
          {
             l3Cache.put(k.k2, cacheVal);
          }

          // if the query has a positive result AND uses non-indexed properties, create a reverse lookup entry
          // for it, to permit fast invalidation
          if (cacheVal != NO_RECORD && hasNonIndexedProps)
          {
             reverseLookup.put(cacheVal, l3Cache, k.k2);
          }
       }

       /**
        * Query the cache for a value.
        *
        * @param   k
        *          The key for cache.
        *
        * @return  a {@code RecordIdentifier} structure. In the case of a cache-hit, this is the key for
        *          a {@code Session} cache, and {@code null} otherwise.
        */
       private RecordIdentifier<String> getImpl(Key k)
       {
          Map<Integer, Cache<L2Key, RecordIdentifier<String>>> l2Cache = cache.get(k.tableId);
          if (l2Cache == null || l2Cache.isEmpty())
          {
             return null;
          }

          Cache<L2Key, RecordIdentifier<String>> l3Cache = l2Cache.get(k.indexId);
          if (l3Cache == null || l3Cache.size() == 0)
          {
             return null;
          }

          return l3Cache.get(k.k2);
       }

       /**
        * Invalidates the index for a table. Called when an operation on the table affected an index.
        *
        * @param   dmoUid
        *          The unique id of the table.
        * @param   multiplex
        *          The multiplex of the records to be invalidated, if any.
        * @param   unique
        *          The set of dirty unique indices which need to be invalidated.
        * @param   nonUnique
        *          The set of dirty unique indices which need to be invalidated.
        */
       private void invalidateImpl(int dmoUid, Integer multiplex, BitSet unique, BitSet nonUnique)
       {
          Map<Integer, Cache<L2Key, RecordIdentifier<String>>> table = cache.get(combine(dmoUid, multiplex));
          if (table == null)
          {
             return;
          }
          if (unique != null)
          {
             for (int u = unique.nextSetBit(0); u >= 0; u = unique.nextSetBit(u + 1))
             {
                // unique indexes have non-null, positive ids
                Cache<L2Key, RecordIdentifier<String>> l3 = table.get(u + 1);
                if (l3 != null)
                {
                   l3.clear();
                }
             }
          }

          if (nonUnique != null)
          {
             for (int i = nonUnique.nextSetBit(0); i >= 0; i = nonUnique.nextSetBit(i + 1))
             {
                // nonunique indexes have non-null, negative ids
                Cache<L2Key, RecordIdentifier<String>> l3 = table.get(-i - 1);
                if (l3 != null)
                {
                   l3.clear();
                }
             }
          }
       }

       /**
        * Invalidate a single index of a table.
        *
        * @param   dmoUid
        *          The table uid whose indexes are invalidated.
        * @param   multiplex
        *          Multiplex ID for a temp-table ({@code null} for a persistent table).
        * @param   idxUid
        *          Index identifier, unique to its table.
        */
       private void invalidateImpl(int dmoUid, Integer multiplex, int idxUid)
       {
          Map<Integer, Cache<L2Key, RecordIdentifier<String>>> table = cache.get(combine(dmoUid, multiplex));
          if (table != null)
          {
             Cache<L2Key, RecordIdentifier<String>> l3 = table.get(idxUid);
             if (l3 != null)
             {
                l3.clear();
             }
          }
       }

       /**
        * Invalidates records from a list of DMOs.
        *
        * @param   dmoList
        *          The collection of unique identifiers of the DMOs to be invalidated.
        */
       private void invalidateImpl(Collection<Long> dmoList)
       {
          for (Long dmoId : dmoList)
          {
             Map<Integer, Cache<L2Key, RecordIdentifier<String>>> map = cache.get(dmoId);
             if (map != null)
             {
                map.forEach((idxId, cache) -> cache.clear());
             }
          }
       }

       /**
        * The second level key for Fast Find algorithm. It uses this class as cache key for quickly checking
        * whether a particular record was found recently.
        */
       private static class L2Key
       {
          /** The fql of the query which selected the keyed record. */
          private final String fql;

          /** The set of <em>non-indexed</em> properties used in {@code fql}. */
          private final BitSet nonIndexedProps;

          /** The type of navigation. Must be one of FIRST, LAST or UNIQUE values of the {@code QueryConstants} */
          private final int type;

          /** The substitution values. May be {@code null}. */
          private final Object[] values;

          /** The precomputed hash code. */
          private final int hash;

          /**
           * The unique constructor builds the immutable key.
           *
           * @param   fql
           *          The fql of the query which selected the keyed record.
           * @param   nonIndexedProps
           *          The set of <em>non-indexed</em> properties used in {@code fql}. May be {@code null} if
           *          {@code fql} is {@code null} or references no non-indexed properties.
           * @param   type
           *          The type of navigation. Must be one of {@code FIRST}, {@code LAST} or {@code UNIQUE} values
           *          of the {@code QueryConstants}.
           * @param   values
           *          The substitution values. May be {@code null}.
           */
          private L2Key(String fql, BitSet nonIndexedProps, int type, Object[] values)
          {
             this.fql = fql;
             this.nonIndexedProps = nonIndexedProps;
             this.type = type;
             this.values = values;

             // precompute hash key
             // The [nonIndexedProps] do not need to be part of key because they are deterministically
             // derived/extracted from [fql]. They are used only to invalidate objects in the cache later.
             this.hash = 31 * (31 * type + Arrays.hashCode(values)) + (fql != null ? fql.hashCode() : 0);
          }

          /**
           * Test for equality with another object.
           *
           * @param   o
           *          The other object.
           *
           * @return  {@code true} if and only if the objects are equals.
           */
          @Override
          public boolean equals(Object o)
          {
             if (this == o)
             {
                return true;
             }
             if (o == null || getClass() != o.getClass())
             {
                return false;
             }

             L2Key l2Key = (L2Key) o;

             if (hash != l2Key.hash)
             {
                return false;
             }
             if (type != l2Key.type)
             {
                return false;
             }
             if (!Objects.equals(fql, l2Key.fql))
             {
                return false;
             }

             return Arrays.equals(values, l2Key.values);
          }

          /**
           * Obtain the precomputed hash code.
           *
           * @return  the precomputed hash code.
           */
          @Override
          public int hashCode()
          {
             return hash;
          }
       }

       /**
        * A special key used for accessing values in cache. Internally, it is compound from two private keys, one
        * for each cache level. They are grouped together to simplify the external interface to a single entity
        * instead of two.
        */
       static class Key
       {
          /**
           * An computed value that uniquely identifies the DMO table and, in case temp-table the multiplex.
           * It is composed from: the unique id of the DMO interface of the keyed record in lower 4 bytes and
           * the optional multiplex number in the higher bits.
           */
          private final long tableId;

          /** The id of the index used when executing the query. */
          private final int indexId;

          /**
           * The key for the second level cache, composed of type of query (one of {@code FIRST}, {@code LAST} or
           * {@code UNIQUE} constants of the {@link QueryConstants}, the optional FQL predicate used in query and
           * the optional substitution values.
           */
          private final L2Key k2;

          /**
           * Creates the immutable key object for accessing values in cache.
           *
           * @param   buffer
           *          The buffer that holds the record. Used for obtaining the DMO uid and multiplex (for
           *          temp-tables).
           * @param   indexId
           *          The id of the index used when executing the query.
           * @param   fql
           *          The fql of the query which selected the keyed record.
           * @param   properties
           *          The set of properties used in {@code fql}.
           * @param   type
           *          The type of navigation. Must be one of {@code FIRST}, {@code LAST} or {@code UNIQUE} values
           *          of the {@code QueryConstants}.
           * @param   values
           *          The substitution values. May be {@code null}.
           */
          private Key(RecordBuffer buffer,
                      int indexId,
                      String fql,
                      BitSet properties,
                      int type,
                      Object[] values)
          {
             int tableId = 0;
             int multiplex = 0;
             if (buffer != null)
             {
                tableId = buffer.getDmoInfo().getId();
                if (buffer.isTemporary())
                {
                   multiplex = buffer.getMultiplexID();
                }
             }
             this.tableId = combine(tableId, multiplex);
             this.indexId = indexId;

             BitSet nonIndexedProps = null;
             if (properties != null)
             {
                RecordMeta recMeta = buffer.getDmoInfo().getRecordMeta();
                // determine all properties used by the query which do NOT represent indexed fields for the table
                BitSet allIndexedProps = indexId > 0 ?
                         recMeta.getUniqueIndices()[indexId - 1] :
                         recMeta.getNonuniqueIndices()[-indexId - 1];
                nonIndexedProps = (BitSet) properties.clone();
                nonIndexedProps.andNot(allIndexedProps);
                if (nonIndexedProps.isEmpty())
                {
                   nonIndexedProps = null;
                }
             }

             this.k2 = new L2Key(fql, nonIndexedProps, type, values);
          }
       }

       /**
        * A reverse cache of record identifiers to values which contain information to enable the quick
        * invalidation of individual, cached results from the primary cache. Only results of queries which
        * use non-indexed properties exist in this reverse cache. It is not necessary to store other mappings,
        * because these are already "bulk" invalidated by record inserts/deletes (all results for a table) or
        * by updates to indexed properties (all results for a set of indices).
        * <p>
        * <strong>Important implementation note:</strong> it is imperative that only a "canonical" {@link
        * RecordIdentifier} is used as a key in this reverse cache. The same canonical instance of the record
        * identifier must be used as the cached result in the primary cache (i.e., at the L3 level). Not doing
        * so can cause a memory leak, because we use a weak map for this reverse cache. This is necessary
        * because bulk invalidation (i.e., for an entire table or set of indices) can "orphan" entries in this
        * reverse cache. However, if only canonical {@code RecordIdentifier} instances are used as keys for
        * this cache (and as values in the primary, L3 caches), any orphaned entries in this reverse cache will
        * be cleaned up eventually during garbage collection.
        * <p>
        * The {@link ReverseLookup#getCanonicalRecordIdentifier(RecordIdentifier)} method is used to retrieve
        * a canonical {@code RecordIdentifier}.
        */
       private static class ReverseLookup
       {
          /** Weak map of canonical record identifiers to information needed to invalidate cache entries */
          private final Map<RecordIdentifier<String>, Value> cache = new WeakHashMap<>();

          /**
           * Add an entry to the reverse cache.
           *
           * @param   recID
           *          Unique record identifier, which may represent one or more primary cache entries.
           * @param   l3Cache
           *          The third level of the primary cache, in which a cache result for the given record
           *          identifier is stored.
           * @param   l2Key
           *          The key used to identify a cached result in the {@code l3Cache}.
           */
          void put(RecordIdentifier<String> recID, Cache<L2Key, RecordIdentifier<String>> l3Cache, L2Key l2Key)
          {
             Value value = cache.get(recID);
             if (value == null)
             {
                value = new Value(recID);
                cache.put(recID, value);
             }

             value.addNode(l3Cache, l2Key);
          }

          /**
           * Get the canonical instance of the given {@code RecordIdentifier}.
           *
           * @param   recID
           *          A record identifier.
           *
           * @return  The canonical {@code RecordIdentifier} instance for {@code recID}. If there is not yet a
           *          reverse lookup entry for {@code recID}, it is returned as the canonical instance.
           */
          RecordIdentifier<String> getCanonicalRecordIdentifier(RecordIdentifier<String> recID)
          {
             Value value = cache.get(recID);
             if (value != null)
             {
                RecordIdentifier<String> referent = value.ref.get();
                if (referent != null)
                {
                   recID = referent;
                }
             }

             return recID;
          }

          /**
           * If any cached results with non-indexed properties are associated with the given record identifier,
           * invalidate each result whose FQL's non-indexed properties intersect with the given set of dirty
           * properties.
           *
           * @param   recID
           *          Record identifier of any cached result which might require invalidation.
           * @param   dirtyProps
           *          The set of properties touched by an update. For performance reasons, we do not compare
           *          the old and new values of each property, only check whether the property was touched.
           */
          void invalidate(RecordIdentifier<String> recID, BitSet dirtyProps)
          {
             if (cache.isEmpty())
             {
                return;
             }

             Value value = cache.get(recID);
             if (value != null)
             {
                value.invalidate(dirtyProps);
                if (value.head == null)
                {
                   cache.remove(recID);
                }
             }
          }

          /**
           * The value object in the reverse cache, which contains the information needed to invalidate all
           * cached results associated with the {@link RecordIdentifier} keys in the reverse cache. This
           * includes a weak reference to the canonical {@code RecordIdentifier} instance, and a linked list
           * of nodes containing invalidation information. Each node represents a single, L3 result in the
           * primary cache.
           */
          private static class Value
          {
             /** A weak reference to the canonical record identifier instance */
             private final WeakReference<RecordIdentifier<String>> ref;

             /** Head of the list; always the newest node added */
             private Node head;

             /**
              * Constructor.
              *
              * @param   recID
              *          Record identifier. This must be the canonical instance.
              */
             Value(RecordIdentifier<String> recID)
             {
                this.ref = new WeakReference<>(recID);
             }

             /**
              * Add a node to the linked list of invalidation nodes.
              *
              * @param   l3Cache
              *          The L3 cache containing a cached result for the record associated with the record
              *          identifier.
              * @param   l2Key
              *          The key used to remove a single cached result from the {@code l3Cache} upon
              *          invalidation.
              */
             void addNode(Cache<L2Key, RecordIdentifier<String>> l3Cache, L2Key l2Key)
             {
                Node node = new Node(l3Cache, l2Key);

                // make the new node the head of the list and have it point to the previous head, if any
                node.next = head;
                head = node;
             }

             /**
              * Walk the linked list of nodes and invalidate any L3 cached result whose non-indexed properties
              * intersects with the given set of dirty properties. If a result is invalidated, drop the
              * associated node from the linked list.
              *
              * @param   dirtyProps
              *          The set of properties touched by an update.
              */
             private void invalidate(BitSet dirtyProps)
             {
                for (Node node = head, prev = null; node != null; prev = node, node = node.next)
                {
                   if (!node.l2Key.nonIndexedProps.intersects(dirtyProps))
                   {
                      continue;
                   }

                   // remove the entry from the L3 cache
                   Cache<L2Key, RecordIdentifier<String>> l3 = node.l3Cache.get();
                   if (l3 != null)
                   {
                      l3.remove(node.l2Key);
                   }

                   // remove the node from the list
                   if (head == node)
                   {
                      head = node.next;
                   }
                   else if (prev != null)
                   {
                      prev.next = node.next;
                   }
                }
             }
          }

          /**
           * A node containing information required to invalidate a single, L3 cached result. The node is an
           * element of the linked list in a {@code Value} object.
           */
          private static class Node
          {
             /** L3 cache containing the cached result which may require invalidation */
             private final WeakReference<Cache<L2Key, RecordIdentifier<String>>> l3Cache;

             /** Key associated with an L3 cached result */
             private final L2Key l2Key;

             /** The next node in a linked list, if any */
             private Node next = null;

             /**
              * Constructor.
              *
              * @param   l3Cache
              *          L3 cache containing the cached result which may require invalidation.
              * @param   l2Key
              *          Key associated with an L3 cached result.
              */
             Node(Cache<L2Key, RecordIdentifier<String>> l3Cache, L2Key l2Key)
             {
                this.l3Cache = new WeakReference<>(l3Cache);
                this.l2Key = l2Key;
             }
          }
       }
    }