SplayInserter.h

Go to the documentation of this file.

/*
 * Copyright (C) 1996-2023 The Squid Software Foundation and contributors
 *
 * Squid software is distributed under GPLv2+ license and includes
 * contributions from numerous individuals and organizations.
 * Please see the COPYING and CONTRIBUTORS files for details.
 */
 
#ifndef SQUID_SRC_ACL_SPLAYINSERTER_H
#define SQUID_SRC_ACL_SPLAYINSERTER_H
 
#include "acl/Acl.h"
#include "debug/Stream.h"
#include "globals.h"
#include "splay.h"
 
namespace Acl {
 
template <class DataValue>
class SplayInserter
{
public:
    using Value = DataValue;
 
    static void Merge(Splay<Value> &, Value &&);
 
private:
 
    static int Compare(const Value &a, const Value &b);
 
    static bool IsSubset(const Value &a, const Value &b);
 
    static Value MakeCombinedValue(const Value &a, const Value &b);
 
    static void DestroyValue(Value v) { delete v; }
};
 
} // namespace Acl
 
template <class DataValue>
void
Acl::SplayInserter<DataValue>::Merge(Splay<Value> &storage, Value &&newItem)
{
    const auto comparator = &SplayInserter<Value>::Compare;
    while (const auto oldItemPointer = storage.insert(newItem, comparator)) {
        const auto oldItem = *oldItemPointer;
 
        if (IsSubset(newItem, oldItem)) {
            debugs(28, DBG_PARSE_NOTE(DBG_IMPORTANT), "WARNING: Ignoring " << newItem << " because it is already covered by " << oldItem <<
                   Debug::Extra << "advice: Remove value " << newItem << " from the ACL");
            DestroyValue(newItem);
            return;
        }
 
        if (IsSubset(oldItem, newItem)) {
            debugs(28, DBG_PARSE_NOTE(DBG_IMPORTANT), "WARNING: Ignoring earlier " << oldItem << " because it is covered by " << newItem <<
                   Debug::Extra << "advice: Remove value " << oldItem << " from the ACL");
            storage.remove(oldItem, comparator);
            DestroyValue(oldItem);
            continue; // still need to insert newItem (and it may conflict with other old items)
        }
 
        const auto combinedItem = MakeCombinedValue(oldItem, newItem);
        debugs(28, DBG_PARSE_NOTE(DBG_IMPORTANT), "WARNING: Merging overlapping " << newItem << " and " << oldItem << " into " << combinedItem <<
               Debug::Extra << "advice: Replace values " << newItem << " and " << oldItem << " with " << combinedItem << " in the ACL");
        DestroyValue(newItem);
        newItem = combinedItem;
        storage.remove(oldItem, comparator);
        DestroyValue(oldItem);
        continue; // still need to insert updated newItem (and it may conflict with other old items)
    }
}
 
#endif /* SQUID_SRC_ACL_SPLAYINSERTER_H */