/* SPDX-License-Identifier: LGPL-2.1-or-later */
/*
* Copyright (C) 2017 Red Hat, Inc.
*/
#include "nm-glib-aux/nm-default-glib-i18n-lib.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;
}