<commit_before>/*
 * Copyright 2014-present Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#pragma once

#include <algorithm>
#include <exception>
#include <functional>

#include <boost/intrusive/list.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/utility.hpp>

#include <folly/lang/Exception.h>

namespace folly {

/**
 * A general purpose LRU evicting cache. Designed to support constant time
 * set/get operations. It maintains a doubly linked list of items that are
 * threaded through an index (a hash map). The access ordered is maintained
 * on the list by moving an element to the front of list on a get. New elements
 * are added to the front of the list. The index size is set to half the
 * capacity (setting capacity to 0 is a special case. see notes at the end of
 * this section). So assuming uniform distribution of keys, set/get are both
 * constant time operations.
 *
 * On reaching capacity limit, clearSize_ LRU items are evicted at a time. If
 * a callback is specified with setPruneHook, it is invoked for each eviction.
 *
 * This is NOT a thread-safe implementation.
 *
 * Configurability: capacity of the cache, number of items to evict, eviction
 * callback and the hasher to hash the keys can all be supplied by the caller.
 *
 * If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing
 * to index keys as {(N1,N5)->H1, (N4,N5,N5)->H2, N3->Hi}, the datastructure
 * layout is as below. N1 .. N6 is a list threaded through the hash.
 * Assuming, each the number of nodes hashed to each index key is bounded, the
 * following operations run in constant time.
 * i) get computes the index key, walks the list of elements hashed to
 * the key and moves it to the front of the list, if found.
 * ii) set inserts a new node into the list and places the same node on to the
 * list of elements hashing to the corresponding index key.
 * ii) prune deletes nodes from the end of the list as well from the index.<commit_msg>Fix a comment in EvictingCacheMap<commit_after>/*
 * Copyright 2014-present Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#pragma once

#include <algorithm>
#include <exception>
#include <functional>

#include <boost/intrusive/list.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/utility.hpp>

#include <folly/lang/Exception.h>

namespace folly {

/**
 * A general purpose LRU evicting cache. Designed to support constant time
 * set/get operations. It maintains a doubly linked list of items that are
 * threaded through an index (a hash map). The access ordered is maintained
 * on the list by moving an element to the front of list on a get. New elements
 * are added to the front of the list. The index size is set to half the
 * capacity (setting capacity to 0 is a special case. see notes at the end of
 * this section). So assuming uniform distribution of keys, set/get are both
 * constant time operations.
 *
 * On reaching capacity limit, clearSize_ LRU items are evicted at a time. If
 * a callback is specified with setPruneHook, it is invoked for each eviction.
 *
 * This is NOT a thread-safe implementation.
 *
 * Configurability: capacity of the cache, number of items to evict, eviction
 * callback and the hasher to hash the keys can all be supplied by the caller.
 *
 * If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing
 * to index keys as {(N1,N5)->H1, (N4,N2,N6)->H2, N3->Hi}, the datastructure
 * layout is as below. N1 .. N6 is a list threaded through the hash.
 * Assuming, each the number of nodes hashed to each index key is bounded, the
 * following operations run in constant time.
 * i) get computes the index key, walks the list of elements hashed to
 * the key and moves it to the front of the list, if found.
 * ii) set inserts a new node into the list and places the same node on to the
 * list of elements hashing to the corresponding index key.
 * ii) prune deletes nodes from the end of the list as well from the index.
{'fraction_non_alphanumeric': 0.06903276131045241, 'fraction_numerical': 0.008190327613104524, 'mean_word_length': 3.7889822595704947, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3498862', 'n_tokens_mistral': 1418, 'n_tokens_neox': 1383, 'n_words': 769}