path: root/shared/nm-glib-aux/nm-dedup-multi.c

// SPDX-License-Identifier: LGPL-2.1+
/*
 * Copyright (C) 2017 Red Hat, Inc.
 */

#include "nm-default.h"

#include "nm-dedup-multi.h"

#include "nm-hash-utils.h"
#include "nm-c-list.h"

/*****************************************************************************/

typedef struct {
    /* the stack-allocated lookup entry. It has a compatible
	 * memory layout with NMDedupMultiEntry and NMDedupMultiHeadEntry.
	 *
	 * It is recognizable by having lst_entries_sentinel.next set to NULL.
	 * Contrary to the other entries, which have lst_entries.next
	 * always non-NULL.
	 * */
    CList                      lst_entries_sentinel;
    const NMDedupMultiObj *    obj;
    const NMDedupMultiIdxType *idx_type;
    bool                       lookup_head;
} LookupEntry;

struct _NMDedupMultiIndex {
    int         ref_count;
    GHashTable *idx_entries;
    GHashTable *idx_objs;
};

/*****************************************************************************/

static void
ASSERT_idx_type(const NMDedupMultiIdxType *idx_type)
{
    nm_assert(idx_type);
#if NM_MORE_ASSERTS > 10
    nm_assert(idx_type->klass);
    nm_assert(idx_type->klass->idx_obj_id_hash_update);
    nm_assert(idx_type->klass->idx_obj_id_equal);
    nm_assert(!!idx_type->klass->idx_obj_partition_hash_update
              == !!idx_type->klass->idx_obj_partition_equal);
    nm_assert(idx_type->lst_idx_head.next);
#endif
}

void
nm_dedup_multi_idx_type_init(NMDedupMultiIdxType *idx_type, const NMDedupMultiIdxTypeClass *klass)
{
    nm_assert(idx_type);
    nm_assert(klass);

    *idx_type = (NMDedupMultiIdxType){
        .klass        = klass,
        .lst_idx_head = C_LIST_INIT(idx_type->lst_idx_head),
    };

    ASSERT_idx_type(idx_type);
}

/*****************************************************************************/

static NMDedupMultiEntry *
_entry_lookup_obj(const NMDedupMultiIndex *  self,
                  const NMDedupMultiIdxType *idx_type,
                  const NMDedupMultiObj *    obj)
{
    const LookupEntry stack_entry = {
        .obj         = obj,
        .idx_type    = idx_type,
        .lookup_head = FALSE,
    };

    ASSERT_idx_type(idx_type);
    return g_hash_table_lookup(self->idx_entries, &stack_entry);
}

static NMDedupMultiHeadEntry *
_entry_lookup_head(const NMDedupMultiIndex *  self,
                   const NMDedupMultiIdxType *idx_type,
                   const NMDedupMultiObj *    obj)
{
    NMDedupMultiHeadEntry *head_entry;
    const LookupEntry      stack_entry = {
        .obj         = obj,
        .idx_type    = idx_type,
        .lookup_head = TRUE,
    };

    ASSERT_idx_type(idx_type);

    if (!idx_type->klass->idx_obj_partition_equal) {
        if (c_list_is_empty(&idx_type->lst_idx_head))
            head_entry = NULL;
        else {
            nm_assert(c_list_length(&idx_type->lst_idx_head) == 1);
            head_entry = c_list_entry(idx_type->lst_idx_head.next, NMDedupMultiHeadEntry, lst_idx);
        }
        nm_assert(head_entry == g_hash_table_lookup(self->idx_entries, &stack_entry));
        return head_entry;
    }

    return g_hash_table_lookup(self->idx_entries, &stack_entry);
}

static void
_entry_unpack(const NMDedupMultiEntry *   entry,
              const NMDedupMultiIdxType **out_idx_type,
              const NMDedupMultiObj **    out_obj,
              gboolean *                  out_lookup_head)
{
    const NMDedupMultiHeadEntry *head_entry;
    const LookupEntry *          lookup_entry;

    nm_assert(entry);

    G_STATIC_ASSERT_EXPR(G_STRUCT_OFFSET(LookupEntry, lst_entries_sentinel)
                         == G_STRUCT_OFFSET(NMDedupMultiEntry, lst_entries));
    G_STATIC_ASSERT_EXPR(G_STRUCT_OFFSET(NMDedupMultiEntry, lst_entries)
                         == G_STRUCT_OFFSET(NMDedupMultiHeadEntry, lst_entries_head));
    G_STATIC_ASSERT_EXPR(G_STRUCT_OFFSET(NMDedupMultiEntry, obj)
                         == G_STRUCT_OFFSET(NMDedupMultiHeadEntry, idx_type));
    G_STATIC_ASSERT_EXPR(G_STRUCT_OFFSET(NMDedupMultiEntry, is_head)
                         == G_STRUCT_OFFSET(NMDedupMultiHeadEntry, is_head));

    if (!entry->lst_entries.next) {
        /* the entry is stack-allocated by _entry_lookup(). */
        lookup_entry     = (LookupEntry *) entry;
        *out_obj         = lookup_entry->obj;
        *out_idx_type    = lookup_entry->idx_type;
        *out_lookup_head = lookup_entry->lookup_head;
    } else if (entry->is_head) {
        head_entry = (NMDedupMultiHeadEntry *) entry;
        nm_assert(!c_list_is_empty(&head_entry->lst_entries_head));
        *out_obj =
            c_list_entry(head_entry->lst_entries_head.next, NMDedupMultiEntry, lst_entries)->obj;
        *out_idx_type    = head_entry->idx_type;
        *out_lookup_head = TRUE;
    } else {
        *out_obj         = entry->obj;
        *out_idx_type    = entry->head->idx_type;
        *out_lookup_head = FALSE;
    }

    nm_assert(NM_IN_SET(*out_lookup_head, FALSE, TRUE));
    ASSERT_idx_type(*out_idx_type);

    /* for lookup of the head, we allow to omit object, but only
	 * if the idx_type does not partition the objects. Otherwise, we
	 * require a obj to compare. */
    nm_assert(!*out_lookup_head || (*out_obj || !(*out_idx_type)->klass->idx_obj_partition_equal));

    /* lookup of the object requires always an object. */
    nm_assert(*out_lookup_head || *out_obj);
}

static guint
_dict_idx_entries_hash(const NMDedupMultiEntry *entry)
{
    const NMDedupMultiIdxType *idx_type;
    const NMDedupMultiObj *    obj;
    gboolean                   lookup_head;
    NMHashState                h;

    _entry_unpack(entry, &idx_type, &obj, &lookup_head);

    nm_hash_init(&h, 1914869417u);
    if (idx_type->klass->idx_obj_partition_hash_update) {
        nm_assert(obj);
        idx_type->klass->idx_obj_partition_hash_update(idx_type, obj, &h);
    }

    if (!lookup_head)
        idx_type->klass->idx_obj_id_hash_update(idx_type, obj, &h);

    nm_hash_update_val(&h, idx_type);
    return nm_hash_complete(&h);
}

static gboolean
_dict_idx_entries_equal(const NMDedupMultiEntry *entry_a, const NMDedupMultiEntry *entry_b)
{
    const NMDedupMultiIdxType *idx_type_a, *idx_type_b;
    const NMDedupMultiObj *    obj_a, *obj_b;
    gboolean                   lookup_head_a, lookup_head_b;

    _entry_unpack(entry_a, &idx_type_a, &obj_a, &lookup_head_a);
    _entry_unpack(entry_b, &idx_type_b, &obj_b, &lookup_head_b);

    if (idx_type_a != idx_type_b || lookup_head_a != lookup_head_b)
        return FALSE;
    if (!nm_dedup_multi_idx_type_partition_equal(idx_type_a, obj_a, obj_b))
        return FALSE;
    if (!lookup_head_a && !nm_dedup_multi_idx_type_id_equal(idx_type_a, obj_a, obj_b))
        return FALSE;
    return TRUE;
}

/*****************************************************************************/

static gboolean
_add(NMDedupMultiIndex *       self,
     NMDedupMultiIdxType *     idx_type,
     const NMDedupMultiObj *   obj,
     NMDedupMultiEntry *       entry,
     NMDedupMultiIdxMode       mode,
     const NMDedupMultiEntry * entry_order,
     NMDedupMultiHeadEntry *   head_existing,
     const NMDedupMultiEntry **out_entry,
     const NMDedupMultiObj **  out_obj_old)
{
    NMDedupMultiHeadEntry *head_entry;
    const NMDedupMultiObj *obj_new, *obj_old;
    gboolean               add_head_entry = FALSE;

    nm_assert(self);
    ASSERT_idx_type(idx_type);
    nm_assert(obj);
    nm_assert(NM_IN_SET(mode,
                        NM_DEDUP_MULTI_IDX_MODE_PREPEND,
                        NM_DEDUP_MULTI_IDX_MODE_PREPEND_FORCE,
                        NM_DEDUP_MULTI_IDX_MODE_APPEND,
                        NM_DEDUP_MULTI_IDX_MODE_APPEND_FORCE));
    nm_assert(!head_existing || head_existing->idx_type == idx_type);
    nm_assert(({
        const NMDedupMultiHeadEntry *_h;
        gboolean                     _ok = TRUE;
        if (head_existing) {
            _h = nm_dedup_multi_index_lookup_head(self, idx_type, obj);
            if (head_existing == NM_DEDUP_MULTI_HEAD_ENTRY_MISSING)
                _ok = (_h == NULL);
            else
                _ok = (_h == head_existing);
        }
        _ok;
    }));

    if (entry) {
        gboolean changed = FALSE;

        nm_dedup_multi_entry_set_dirty(entry, FALSE);

        nm_assert(!head_existing || entry->head == head_existing);
        nm_assert(!entry_order || entry_order->head == entry->head);
        nm_assert(!entry_order || c_list_contains(&entry->lst_entries, &entry_order->lst_entries));
        nm_assert(!entry_order || c_list_contains(&entry_order->lst_entries, &entry->lst_entries));

        switch (mode) {
        case NM_DEDUP_MULTI_IDX_MODE_PREPEND_FORCE:
            if (entry_order) {
                if (nm_c_list_move_before((CList *) &entry_order->lst_entries, &entry->lst_entries))
                    changed = TRUE;
            } else {
                if (nm_c_list_move_front((CList *) &entry->head->lst_entries_head,
                                         &entry->lst_entries))
                    changed = TRUE;
            }
            break;
        case NM_DEDUP_MULTI_IDX_MODE_APPEND_FORCE:
            if (entry_order) {
                if (nm_c_list_move_after((CList *) &entry_order->lst_entries, &entry->lst_entries))
                    changed = TRUE;
            } else {
                if (nm_c_list_move_tail((CList *) &entry->head->lst_entries_head,
                                        &entry->lst_entries))
                    changed = TRUE;
            }
            break;
        case NM_DEDUP_MULTI_IDX_MODE_PREPEND:
        case NM_DEDUP_MULTI_IDX_MODE_APPEND:
            break;
        };

        nm_assert(obj->klass == ((const NMDedupMultiObj *) entry->obj)->klass);
        if (obj == entry->obj || obj->klass->obj_full_equal(obj, entry->obj)) {
            NM_SET_OUT(out_entry, entry);
            NM_SET_OUT(out_obj_old, nm_dedup_multi_obj_ref(entry->obj));
            return changed;
        }

        obj_new = nm_dedup_multi_index_obj_intern(self, obj);

        obj_old    = entry->obj;
        entry->obj = obj_new;

        NM_SET_OUT(out_entry, entry);
        if (out_obj_old)
            *out_obj_old = obj_old;
        else
            nm_dedup_multi_obj_unref(obj_old);
        return TRUE;
    }

    if (idx_type->klass->idx_obj_partitionable
        && !idx_type->klass->idx_obj_partitionable(idx_type, obj)) {
        /* this object cannot be partitioned by this idx_type. */
        nm_assert(!head_existing || head_existing == NM_DEDUP_MULTI_HEAD_ENTRY_MISSING);
        NM_SET_OUT(out_entry, NULL);
        NM_SET_OUT(out_obj_old, NULL);
        return FALSE;
    }

    obj_new = nm_dedup_multi_index_obj_intern(self, obj);

    if (!head_existing)
        head_entry = _entry_lookup_head(self, idx_type, obj_new);
    else if (head_existing == NM_DEDUP_MULTI_HEAD_ENTRY_MISSING)
        head_entry = NULL;
    else
        head_entry = head_existing;

    if (!head_entry) {
        head_entry           = g_slice_new0(NMDedupMultiHeadEntry);
        head_entry->is_head  = TRUE;
        head_entry->idx_type = idx_type;
        c_list_init(&head_entry->lst_entries_head);
        c_list_link_tail(&idx_type->lst_idx_head, &head_entry->lst_idx);
        add_head_entry = TRUE;
    } else
        nm_assert(c_list_contains(&idx_type->lst_idx_head, &head_entry->lst_idx));

    if (entry_order) {
        nm_assert(!add_head_entry);
        nm_assert(entry_order->head == head_entry);
        nm_assert(c_list_contains(&head_entry->lst_entries_head, &entry_order->lst_entries));
        nm_assert(c_list_contains(&entry_order->lst_entries, &head_entry->lst_entries_head));
    }

    entry       = g_slice_new0(NMDedupMultiEntry);
    entry->obj  = obj_new;
    entry->head = head_entry;

    switch (mode) {
    case NM_DEDUP_MULTI_IDX_MODE_PREPEND:
    case NM_DEDUP_MULTI_IDX_MODE_PREPEND_FORCE:
        if (entry_order)
            c_list_link_before((CList *) &entry_order->lst_entries, &entry->lst_entries);
        else
            c_list_link_front(&head_entry->lst_entries_head, &entry->lst_entries);
        break;
    default:
        if (entry_order)
            c_list_link_after((CList *) &entry_order->lst_entries, &entry->lst_entries);
        else
            c_list_link_tail(&head_entry->lst_entries_head, &entry->lst_entries);
        break;
    };

    idx_type->len++;
    head_entry->len++;

    if (add_head_entry && !g_hash_table_add(self->idx_entries, head_entry))
        nm_assert_not_reached();

    if (!g_hash_table_add(self->idx_entries, entry))
        nm_assert_not_reached();

    NM_SET_OUT(out_entry, entry);
    NM_SET_OUT(out_obj_old, NULL);
    return TRUE;
}

gboolean
nm_dedup_multi_index_add(NMDedupMultiIndex *                        self,
                         NMDedupMultiIdxType *                      idx_type,
                         /*const NMDedupMultiObj * */ gconstpointer obj,
                         NMDedupMultiIdxMode                        mode,
                         const NMDedupMultiEntry **                 out_entry,
                         /* const NMDedupMultiObj ** */ gpointer    out_obj_old)
{
    NMDedupMultiEntry *entry;

    g_return_val_if_fail(self, FALSE);
    g_return_val_if_fail(idx_type, FALSE);
    g_return_val_if_fail(obj, FALSE);
    g_return_val_if_fail(NM_IN_SET(mode,
                                   NM_DEDUP_MULTI_IDX_MODE_PREPEND,
                                   NM_DEDUP_MULTI_IDX_MODE_PREPEND_FORCE,
                                   NM_DEDUP_MULTI_IDX_MODE_APPEND,
                                   NM_DEDUP_MULTI_IDX_MODE_APPEND_FORCE),
                         FALSE);

    entry = _entry_lookup_obj(self, idx_type, obj);
    return _add(self, idx_type, obj, entry, mode, NULL, NULL, out_entry, out_obj_old);
}

/* nm_dedup_multi_index_add_full:
 * @self: the index instance.
 * @idx_type: the index handle for storing @obj.
 * @obj: the NMDedupMultiObj instance to add.
 * @mode: whether to append or prepend the new item. If @entry_order is given,
 *   the entry will be sorted after/before, instead of appending/prepending to
 *   the entire list. If a comparable object is already tracked, then it may
 *   still be resorted by specifying one of the "FORCE" modes.
 * @entry_order: if not NULL, the new entry will be sorted before or after @entry_order.
 *   If given, @entry_order MUST be tracked by @self, and the object it points to MUST
 *   be in the same partition tracked by @idx_type. That is, they must have the same
 *   head_entry and it means, you must ensure that @entry_order and the created/modified
 *   entry will share the same head.
 * @entry_existing: if not NULL, it safes a hash lookup of the entry where the
 *   object will be placed in. You can omit this, and it will be automatically
 *   detected (at the expense of an additional hash lookup).
 *   Basically, this is the result of nm_dedup_multi_index_lookup_obj(),
 *   with the peculiarity that if you know that @obj is not yet tracked,
 *   you may specify %NM_DEDUP_MULTI_ENTRY_MISSING.
 * @head_existing: an optional argument to safe a lookup for the head. If specified,
 *   it must be identical to nm_dedup_multi_index_lookup_head(), with the peculiarity
 *   that if the head is not yet tracked, you may specify %NM_DEDUP_MULTI_HEAD_ENTRY_MISSING
 * @out_entry: if give, return the added entry. This entry may have already exists (update)
 *   or be newly created. If @obj is not partitionable according to @idx_type, @obj
 *   is not to be added and it returns %NULL.
 * @out_obj_old: if given, return the previously contained object. It only
 *   returns a  object, if a matching entry was tracked previously, not if a
 *   new entry was created. Note that when passing @out_obj_old you obtain a reference
 *   to the boxed object and MUST return it with nm_dedup_multi_obj_unref().
 *
 * Adds and object to the index.
 *
 * Return: %TRUE if anything changed, %FALSE if nothing changed.
 */
gboolean
nm_dedup_multi_index_add_full(NMDedupMultiIndex *                        self,
                              NMDedupMultiIdxType *                      idx_type,
                              /*const NMDedupMultiObj * */ gconstpointer obj,
                              NMDedupMultiIdxMode                        mode,
                              const NMDedupMultiEntry *                  entry_order,
                              const NMDedupMultiEntry *                  entry_existing,
                              const NMDedupMultiHeadEntry *              head_existing,
                              const NMDedupMultiEntry **                 out_entry,
                              /* const NMDedupMultiObj ** */ gpointer    out_obj_old)
{
    NMDedupMultiEntry *entry;

    g_return_val_if_fail(self, FALSE);
    g_return_val_if_fail(idx_type, FALSE);
    g_return_val_if_fail(obj, FALSE);
    g_return_val_if_fail(NM_IN_SET(mode,
                                   NM_DEDUP_MULTI_IDX_MODE_PREPEND,
                                   NM_DEDUP_MULTI_IDX_MODE_PREPEND_FORCE,
                                   NM_DEDUP_MULTI_IDX_MODE_APPEND,
                                   NM_DEDUP_MULTI_IDX_MODE_APPEND_FORCE),
                         FALSE);

    if (entry_existing == NULL)
        entry = _entry_lookup_obj(self, idx_type, obj);
    else if (entry_existing == NM_DEDUP_MULTI_ENTRY_MISSING) {
        nm_assert(!_entry_lookup_obj(self, idx_type, obj));
        entry = NULL;
    } else {
        nm_assert(entry_existing == _entry_lookup_obj(self, idx_type, obj));
        entry = (NMDedupMultiEntry *) entry_existing;
    }
    return _add(self,
                idx_type,
                obj,
                entry,
                mode,
                entry_order,
                (NMDedupMultiHeadEntry *) head_existing,
                out_entry,
                out_obj_old);
}

/*****************************************************************************/

static void
_remove_entry(NMDedupMultiIndex *self, NMDedupMultiEntry *entry, gboolean *out_head_entry_removed)
{
    const NMDedupMultiObj *obj;
    NMDedupMultiHeadEntry *head_entry;
    NMDedupMultiIdxType *  idx_type;

    nm_assert(self);
    nm_assert(entry);
    nm_assert(entry->obj);
    nm_assert(entry->head);
    nm_assert(!c_list_is_empty(&entry->lst_entries));
    nm_assert(g_hash_table_lookup(self->idx_entries, entry) == entry);

    head_entry = (NMDedupMultiHeadEntry *) entry->head;
    obj        = entry->obj;

    nm_assert(head_entry);
    nm_assert(head_entry->len > 0);
    nm_assert(g_hash_table_lookup(self->idx_entries, head_entry) == head_entry);

    idx_type = (NMDedupMultiIdxType *) head_entry->idx_type;
    ASSERT_idx_type(idx_type);

    nm_assert(idx_type->len >= head_entry->len);
    if (--head_entry->len > 0) {
        nm_assert(idx_type->len > 1);
        idx_type->len--;
        head_entry = NULL;
    }

    NM_SET_OUT(out_head_entry_removed, head_entry != NULL);

    if (!g_hash_table_remove(self->idx_entries, entry))
        nm_assert_not_reached();

    if (head_entry && !g_hash_table_remove(self->idx_entries, head_entry))
        nm_assert_not_reached();

    c_list_unlink_stale(&entry->lst_entries);
    g_slice_free(NMDedupMultiEntry, entry);

    if (head_entry) {
        nm_assert(c_list_is_empty(&head_entry->lst_entries_head));
        c_list_unlink_stale(&head_entry->lst_idx);
        g_slice_free(NMDedupMultiHeadEntry, head_entry);
    }

    nm_dedup_multi_obj_unref(obj);
}

static guint
_remove_head(NMDedupMultiIndex *    self,
             NMDedupMultiHeadEntry *head_entry,
             gboolean               remove_all /* otherwise just dirty ones */,
             gboolean               mark_survivors_dirty)
{
    guint    n;
    gboolean head_entry_removed;
    CList *  iter_entry, *iter_entry_safe;

    nm_assert(self);
    nm_assert(head_entry);
    nm_assert(head_entry->len > 0);
    nm_assert(head_entry->len == c_list_length(&head_entry->lst_entries_head));
    nm_assert(g_hash_table_lookup(self->idx_entries, head_entry) == head_entry);

    n = 0;
    c_list_for_each_safe (iter_entry, iter_entry_safe, &head_entry->lst_entries_head) {
        NMDedupMultiEntry *entry;

        entry = c_list_entry(iter_entry, NMDedupMultiEntry, lst_entries);
        if (remove_all || entry->dirty) {
            _remove_entry(self, entry, &head_entry_removed);
            n++;
            if (head_entry_removed)
                break;
        } else if (mark_survivors_dirty)
            nm_dedup_multi_entry_set_dirty(entry, TRUE);
    }

    return n;
}

static guint
_remove_idx_entry(NMDedupMultiIndex *  self,
                  NMDedupMultiIdxType *idx_type,
                  gboolean             remove_all /* otherwise just dirty ones */,
                  gboolean             mark_survivors_dirty)
{
    guint  n;
    CList *iter_idx, *iter_idx_safe;

    nm_assert(self);
    ASSERT_idx_type(idx_type);

    n = 0;
    c_list_for_each_safe (iter_idx, iter_idx_safe, &idx_type->lst_idx_head) {
        n += _remove_head(self,
                          c_list_entry(iter_idx, NMDedupMultiHeadEntry, lst_idx),
                          remove_all,
                          mark_survivors_dirty);
    }
    return n;
}

guint
nm_dedup_multi_index_remove_entry(NMDedupMultiIndex *self, gconstpointer entry)
{
    g_return_val_if_fail(self, 0);

    nm_assert(entry);

    if (!((NMDedupMultiEntry *) entry)->is_head) {
        _remove_entry(self, (NMDedupMultiEntry *) entry, NULL);
        return 1;
    }
    return _remove_head(self, (NMDedupMultiHeadEntry *) entry, TRUE, FALSE);
}

guint
nm_dedup_multi_index_remove_obj(NMDedupMultiIndex *                          self,
                                NMDedupMultiIdxType *                        idx_type,
                                /*const NMDedupMultiObj * */ gconstpointer   obj,
                                /*const NMDedupMultiObj ** */ gconstpointer *out_obj)
{
    const NMDedupMultiEntry *entry;

    entry = nm_dedup_multi_index_lookup_obj(self, idx_type, obj);
    if (!entry) {
        NM_SET_OUT(out_obj, NULL);
        return 0;
    }

    /* since we are about to remove the object, we obviously pass
	 * a reference to @out_obj, the caller MUST unref the object,
	 * if he chooses to provide @out_obj. */
    NM_SET_OUT(out_obj, nm_dedup_multi_obj_ref(entry->obj));

    _remove_entry(self, (NMDedupMultiEntry *) entry, NULL);
    return 1;
}

guint
nm_dedup_multi_index_remove_head(NMDedupMultiIndex *                        self,
                                 NMDedupMultiIdxType *                      idx_type,
                                 /*const NMDedupMultiObj * */ gconstpointer obj)
{
    const NMDedupMultiHeadEntry *entry;

    entry = nm_dedup_multi_index_lookup_head(self, idx_type, obj);
    return entry ? _remove_head(self, (NMDedupMultiHeadEntry *) entry, TRUE, FALSE) : 0;
}

guint
nm_dedup_multi_index_remove_idx(NMDedupMultiIndex *self, NMDedupMultiIdxType *idx_type)
{
    g_return_val_if_fail(self, 0);
    g_return_val_if_fail(idx_type, 0);

    return _remove_idx_entry(self, idx_type, TRUE, FALSE);
}

/*****************************************************************************/

/**
 * nm_dedup_multi_index_lookup_obj:
 * @self: the index cache
 * @idx_type: the lookup index type
 * @obj: the object to lookup. This means the match is performed
 *   according to NMDedupMultiIdxTypeClass's idx_obj_id_equal()
 *   of @idx_type.
 *
 * Returns: the cache entry or %NULL if the entry wasn't found.
 */
const NMDedupMultiEntry *
nm_dedup_multi_index_lookup_obj(const NMDedupMultiIndex *                  self,
                                const NMDedupMultiIdxType *                idx_type,
                                /*const NMDedupMultiObj * */ gconstpointer obj)
{
    g_return_val_if_fail(self, FALSE);
    g_return_val_if_fail(idx_type, FALSE);
    g_return_val_if_fail(obj, FALSE);

    nm_assert(idx_type && idx_type->klass);
    return _entry_lookup_obj(self, idx_type, obj);
}

/**
 * nm_dedup_multi_index_lookup_head:
 * @self: the index cache
 * @idx_type: the lookup index type
 * @obj: the object to lookup, of type "const NMDedupMultiObj *".
 *   Depending on the idx_type, you *must* also provide a selector
 *   object, even when looking up the list head. That is, because
 *   the idx_type implementation may choose to partition the objects
 *   in distinct list, so you need a selector object to know which
 *   list head to lookup.
 *
 * Returns: the cache entry or %NULL if the entry wasn't found.
 */
const NMDedupMultiHeadEntry *
nm_dedup_multi_index_lookup_head(const NMDedupMultiIndex *                  self,
                                 const NMDedupMultiIdxType *                idx_type,
                                 /*const NMDedupMultiObj * */ gconstpointer obj)
{
    g_return_val_if_fail(self, FALSE);
    g_return_val_if_fail(idx_type, FALSE);

    return _entry_lookup_head(self, idx_type, obj);
}

/*****************************************************************************/

void
nm_dedup_multi_index_dirty_set_head(NMDedupMultiIndex *                        self,
                                    const NMDedupMultiIdxType *                idx_type,
                                    /*const NMDedupMultiObj * */ gconstpointer obj)
{
    NMDedupMultiHeadEntry *head_entry;
    CList *                iter_entry;

    g_return_if_fail(self);
    g_return_if_fail(idx_type);

    head_entry = _entry_lookup_head(self, idx_type, obj);
    if (!head_entry)
        return;

    c_list_for_each (iter_entry, &head_entry->lst_entries_head) {
        NMDedupMultiEntry *entry;

        entry = c_list_entry(iter_entry, NMDedupMultiEntry, lst_entries);
        nm_dedup_multi_entry_set_dirty(entry, TRUE);
    }
}

void
nm_dedup_multi_index_dirty_set_idx(NMDedupMultiIndex *self, const NMDedupMultiIdxType *idx_type)
{
    CList *iter_idx, *iter_entry;

    g_return_if_fail(self);
    g_return_if_fail(idx_type);

    c_list_for_each (iter_idx, &idx_type->lst_idx_head) {
        NMDedupMultiHeadEntry *head_entry;

        head_entry = c_list_entry(iter_idx, NMDedupMultiHeadEntry, lst_idx);
        c_list_for_each (iter_entry, &head_entry->lst_entries_head) {
            NMDedupMultiEntry *entry;

            entry = c_list_entry(iter_entry, NMDedupMultiEntry, lst_entries);
            nm_dedup_multi_entry_set_dirty(entry, TRUE);
        }
    }
}

/**
 * nm_dedup_multi_index_dirty_remove_idx:
 * @self: the index instance
 * @idx_type: the index-type to select the objects.
 * @mark_survivors_dirty: while the function removes all entries that are
 *   marked as dirty, if @set_dirty is true, the surviving objects
 *   will be marked dirty right away.
 *
 * Deletes all entries for @idx_type that are marked dirty. Only
 * non-dirty objects survive. If @mark_survivors_dirty is set to TRUE, the survivors
 * are marked as dirty right away.
 *
 * Returns: number of deleted entries.
 */
guint
nm_dedup_multi_index_dirty_remove_idx(NMDedupMultiIndex *  self,
                                      NMDedupMultiIdxType *idx_type,
                                      gboolean             mark_survivors_dirty)
{
    g_return_val_if_fail(self, 0);
    g_return_val_if_fail(idx_type, 0);

    return _remove_idx_entry(self, idx_type, FALSE, mark_survivors_dirty);
}

/*****************************************************************************/

static guint
_dict_idx_objs_hash(const NMDedupMultiObj *obj)
{
    NMHashState h;

    nm_hash_init(&h, 1748638583u);
    obj->klass->obj_full_hash_update(obj, &h);
    return nm_hash_complete(&h);
}

static gboolean
_dict_idx_objs_equal(const NMDedupMultiObj *obj_a, const NMDedupMultiObj *obj_b)
{
    return obj_a == obj_b
           || (obj_a->klass == obj_b->klass && obj_a->klass->obj_full_equal(obj_a, obj_b));
}

void
nm_dedup_multi_index_obj_release(NMDedupMultiIndex *                         self,
                                 /* const NMDedupMultiObj * */ gconstpointer obj)
{
    nm_assert(self);
    nm_assert(obj);
    nm_assert(g_hash_table_lookup(self->idx_objs, obj) == obj);
    nm_assert(((const NMDedupMultiObj *) obj)->_multi_idx == self);

    ((NMDedupMultiObj *) obj)->_multi_idx = NULL;
    if (!g_hash_table_remove(self->idx_objs, obj))
        nm_assert_not_reached();
}

gconstpointer
nm_dedup_multi_index_obj_find(NMDedupMultiIndex *                         self,
                              /* const NMDedupMultiObj * */ gconstpointer obj)
{
    g_return_val_if_fail(self, NULL);
    g_return_val_if_fail(obj, NULL);

    return g_hash_table_lookup(self->idx_objs, obj);
}

gconstpointer
nm_dedup_multi_index_obj_intern(NMDedupMultiIndex *                         self,
                                /* const NMDedupMultiObj * */ gconstpointer obj)
{
    const NMDedupMultiObj *obj_new = obj;
    const NMDedupMultiObj *obj_old;

    nm_assert(self);
    nm_assert(obj_new);

    if (obj_new->_multi_idx == self) {
        nm_assert(g_hash_table_lookup(self->idx_objs, obj_new) == obj_new);
        nm_dedup_multi_obj_ref(obj_new);
        return obj_new;
    }

    obj_old = g_hash_table_lookup(self->idx_objs, obj_new);
    nm_assert(obj_old != obj_new);

    if (obj_old) {
        nm_assert(obj_old->_multi_idx == self);
        nm_dedup_multi_obj_ref(obj_old);
        return obj_old;
    }

    if (nm_dedup_multi_obj_needs_clone(obj_new))
        obj_new = nm_dedup_multi_obj_clone(obj_new);
    else
        obj_new = nm_dedup_multi_obj_ref(obj_new);

    nm_assert(obj_new);
    nm_assert(!obj_new->_multi_idx);

    if (!g_hash_table_add(self->idx_objs, (gpointer) obj_new))
        nm_assert_not_reached();

    ((NMDedupMultiObj *) obj_new)->_multi_idx = self;
    return obj_new;
}

void
nm_dedup_multi_obj_unref(const NMDedupMultiObj *obj)
{
    if (obj) {
        nm_assert(obj->_ref_count > 0);
        nm_assert(obj->_ref_count != NM_OBJ_REF_COUNT_STACKINIT);

again:
        if (--(((NMDedupMultiObj *) obj)->_ref_count) <= 0) {
            if (obj->_multi_idx) {
                /* restore the ref-count to 1 and release the object first
				 * from the index. Then, retry again to unref. */
                ((NMDedupMultiObj *) obj)->_ref_count++;
                nm_dedup_multi_index_obj_release(obj->_multi_idx, obj);
                nm_assert(obj->_ref_count == 1);
                nm_assert(!obj->_multi_idx);
                goto again;
            }

            obj->klass->obj_destroy((NMDedupMultiObj *) obj);
        }
    }
}

gboolean
nm_dedup_multi_obj_needs_clone(const NMDedupMultiObj *obj)
{
    nm_assert(obj);

    if (obj->_multi_idx || obj->_ref_count == NM_OBJ_REF_COUNT_STACKINIT)
        return TRUE;

    if (obj->klass->obj_needs_clone && obj->klass->obj_needs_clone(obj))
        return TRUE;

    return FALSE;
}

const NMDedupMultiObj *
nm_dedup_multi_obj_clone(const NMDedupMultiObj *obj)
{
    const NMDedupMultiObj *o;

    nm_assert(obj);

    o = obj->klass->obj_clone(obj);
    nm_assert(o);
    nm_assert(o->_ref_count == 1);
    return o;
}

gconstpointer *
nm_dedup_multi_objs_to_array_head(const NMDedupMultiHeadEntry *  head_entry,
                                  NMDedupMultiFcnSelectPredicate predicate,
                                  gpointer                       user_data,
                                  guint *                        out_len)
{
    gconstpointer *result;
    CList *        iter;
    guint          i;

    if (!head_entry) {
        NM_SET_OUT(out_len, 0);
        return NULL;
    }

    result = g_new(gconstpointer, head_entry->len + 1);
    i      = 0;
    c_list_for_each (iter, &head_entry->lst_entries_head) {
        const NMDedupMultiObj *obj = c_list_entry(iter, NMDedupMultiEntry, lst_entries)->obj;

        if (!predicate || predicate(obj, user_data)) {
            nm_assert(i < head_entry->len);
            result[i++] = obj;
        }
    }

    if (i == 0) {
        g_free(result);
        NM_SET_OUT(out_len, 0);
        return NULL;
    }

    nm_assert(i <= head_entry->len);
    NM_SET_OUT(out_len, i);
    result[i++] = NULL;
    return result;
}

GPtrArray *
nm_dedup_multi_objs_to_ptr_array_head(const NMDedupMultiHeadEntry *  head_entry,
                                      NMDedupMultiFcnSelectPredicate predicate,
                                      gpointer                       user_data)
{
    GPtrArray *result;
    CList *    iter;

    if (!head_entry)
        return NULL;

    result = g_ptr_array_new_full(head_entry->len, (GDestroyNotify) nm_dedup_multi_obj_unref);
    c_list_for_each (iter, &head_entry->lst_entries_head) {
        const NMDedupMultiObj *obj = c_list_entry(iter, NMDedupMultiEntry, lst_entries)->obj;

        if (!predicate || predicate(obj, user_data))
            g_ptr_array_add(result, (gpointer) nm_dedup_multi_obj_ref(obj));
    }

    if (result->len == 0) {
        g_ptr_array_unref(result);
        return NULL;
    }
    return result;
}

/**
 * nm_dedup_multi_entry_reorder:
 * @entry: the entry to reorder. It must not be NULL (and tracked in an index).
 * @entry_order: (allow-none): an optional other entry. It MUST be in the same
 *   list as entry. If given, @entry will be ordered after/before @entry_order.
 *   If left at %NULL, @entry will be moved to the front/end of the list.
 * @order_after: if @entry_order is given, %TRUE means to move @entry after
 *   @entry_order (otherwise before).
 *   If @entry_order is %NULL, %TRUE means to move @entry to the tail of the list
 *   (otherwise the beginning). Note that "tail of the list" here means that @entry
 *   will be linked before the head of the circular list.
 *
 * Returns: %TRUE, if anything was changed. Otherwise, @entry was already at the
 * right place and nothing was done.
 */
gboolean
nm_dedup_multi_entry_reorder(const NMDedupMultiEntry *entry,
                             const NMDedupMultiEntry *entry_order,
                             gboolean                 order_after)
{
    nm_assert(entry);

    if (!entry_order) {
        const NMDedupMultiHeadEntry *head_entry = entry->head;

        if (order_after) {
            if (nm_c_list_move_tail((CList *) &head_entry->lst_entries_head,
                                    (CList *) &entry->lst_entries))
                return TRUE;
        } else {
            if (nm_c_list_move_front((CList *) &head_entry->lst_entries_head,
                                     (CList *) &entry->lst_entries))
                return TRUE;
        }
    } else {
        if (order_after) {
            if (nm_c_list_move_after((CList *) &entry_order->lst_entries,
                                     (CList *) &entry->lst_entries))
                return TRUE;
        } else {
            if (nm_c_list_move_before((CList *) &entry_order->lst_entries,
                                      (CList *) &entry->lst_entries))
                return TRUE;
        }
    }

    return FALSE;
}

/*****************************************************************************/

NMDedupMultiIndex *
nm_dedup_multi_index_new(void)
{
    NMDedupMultiIndex *self;

    self            = g_slice_new0(NMDedupMultiIndex);
    self->ref_count = 1;
    self->idx_entries =
        g_hash_table_new((GHashFunc) _dict_idx_entries_hash, (GEqualFunc) _dict_idx_entries_equal);
    self->idx_objs =
        g_hash_table_new((GHashFunc) _dict_idx_objs_hash, (GEqualFunc) _dict_idx_objs_equal);
    return self;
}

NMDedupMultiIndex *
nm_dedup_multi_index_ref(NMDedupMultiIndex *self)
{
    g_return_val_if_fail(self, NULL);
    g_return_val_if_fail(self->ref_count > 0, NULL);

    self->ref_count++;
    return self;
}

NMDedupMultiIndex *
nm_dedup_multi_index_unref(NMDedupMultiIndex *self)
{
    GHashTableIter             iter;
    const NMDedupMultiIdxType *idx_type;
    NMDedupMultiEntry *        entry;
    const NMDedupMultiObj *    obj;

    g_return_val_if_fail(self, NULL);
    g_return_val_if_fail(self->ref_count > 0, NULL);

    if (--self->ref_count > 0)
        return NULL;

more:
    g_hash_table_iter_init(&iter, self->idx_entries);
    while (g_hash_table_iter_next(&iter, (gpointer *) &entry, NULL)) {
        if (entry->is_head)
            idx_type = ((NMDedupMultiHeadEntry *) entry)->idx_type;
        else
            idx_type = entry->head->idx_type;
        _remove_idx_entry(self, (NMDedupMultiIdxType *) idx_type, TRUE, FALSE);
        goto more;
    }

    nm_assert(g_hash_table_size(self->idx_entries) == 0);

    g_hash_table_iter_init(&iter, self->idx_objs);
    while (g_hash_table_iter_next(&iter, (gpointer *) &obj, NULL)) {
        nm_assert(obj->_multi_idx == self);
        ((NMDedupMultiObj *) obj)->_multi_idx = NULL;
    }
    g_hash_table_remove_all(self->idx_objs);

    g_hash_table_unref(self->idx_entries);
    g_hash_table_unref(self->idx_objs);

    g_slice_free(NMDedupMultiIndex, self);
    return NULL;
}