// SPDX-License-Identifier: LGPL-2.1+

/*

 * Copyright (C) 2017 Red Hat, Inc.

 */

#ifndef __NM_DEDUP_MULTI_H__

#define __NM_DEDUP_MULTI_H__

#include "nm-obj.h"

#include "nm-std-aux/c-list-util.h"

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

struct _NMHashState;

typedef struct _NMDedupMultiObj             NMDedupMultiObj;

typedef struct _NMDedupMultiObjClass        NMDedupMultiObjClass;

typedef struct _NMDedupMultiIdxType         NMDedupMultiIdxType;

typedef struct _NMDedupMultiIdxTypeClass    NMDedupMultiIdxTypeClass;

typedef struct _NMDedupMultiEntry           NMDedupMultiEntry;

typedef struct _NMDedupMultiHeadEntry       NMDedupMultiHeadEntry;

typedef struct _NMDedupMultiIndex           NMDedupMultiIndex;

typedef enum _NMDedupMultiIdxMode {

	NM_DEDUP_MULTI_IDX_MODE_PREPEND,

	NM_DEDUP_MULTI_IDX_MODE_PREPEND_FORCE,

	/* append new objects to the end of the list.

	 * If the object is already in the cache, don't move it. */

	NM_DEDUP_MULTI_IDX_MODE_APPEND,

	/* like NM_DEDUP_MULTI_IDX_MODE_APPEND, but if the object

	 * is already in the cache, move it to the end. */

	NM_DEDUP_MULTI_IDX_MODE_APPEND_FORCE,

} NMDedupMultiIdxMode;

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

struct _NMDedupMultiObj {

	union {

		NMObjBaseInst parent;

		const NMDedupMultiObjClass *klass;

	};

	NMDedupMultiIndex *_multi_idx;

	guint _ref_count;

};

struct _NMDedupMultiObjClass {

	NMObjBaseClass parent;

	const NMDedupMultiObj *(*obj_clone) (const NMDedupMultiObj *obj);

	gboolean (*obj_needs_clone) (const NMDedupMultiObj *obj);

	void (*obj_destroy) (NMDedupMultiObj *obj);

	/* the NMDedupMultiObj can be deduplicated. For that the obj_full_hash_update()

	 * and obj_full_equal() compare *all* fields of the object, even minor ones. */

	void (*obj_full_hash_update)  (const NMDedupMultiObj *obj,

	                               struct _NMHashState *h);

	gboolean (*obj_full_equal) (const NMDedupMultiObj *obj_a,

	                            const NMDedupMultiObj *obj_b);

};

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

static inline const NMDedupMultiObj *

nm_dedup_multi_obj_ref (const NMDedupMultiObj *obj)

{

	/* ref and unref accept const pointers. Objects is supposed to be shared

	 * and kept immutable. Disallowing to take/return a reference to a const

	 * NMPObject is cumbersome, because callers are precisely expected to

	 * keep a ref on the otherwise immutable object. */

	nm_assert (obj);

	nm_assert (obj->_ref_count != NM_OBJ_REF_COUNT_STACKINIT);

	nm_assert (obj->_ref_count > 0);

	((NMDedupMultiObj *) obj)->_ref_count++;

	return obj;

}

void                   nm_dedup_multi_obj_unref       (const NMDedupMultiObj *obj);

const NMDedupMultiObj *nm_dedup_multi_obj_clone       (const NMDedupMultiObj *obj);

gboolean               nm_dedup_multi_obj_needs_clone (const NMDedupMultiObj *obj);

gconstpointer nm_dedup_multi_index_obj_intern (NMDedupMultiIndex *self,

                                               /* const NMDedupMultiObj * */ gconstpointer obj);

void nm_dedup_multi_index_obj_release (NMDedupMultiIndex *self,

                                       /* const NMDedupMultiObj * */ gconstpointer obj);

/* const NMDedupMultiObj * */ gconstpointer nm_dedup_multi_index_obj_find (NMDedupMultiIndex *self,

                                                                           /* const NMDedupMultiObj * */ gconstpointer obj);

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

/* the NMDedupMultiIdxType is an access handle under which you can store and

 * retrieve NMDedupMultiObj instances in NMDedupMultiIndex.

 *

 * The NMDedupMultiIdxTypeClass determines its behavior, but you can have

 * multiple instances (of the same class).

 *

 * For example, NMIP4Config can have idx-type to put there all IPv4 Routes.

 * This idx-type instance is private to the NMIP4Config instance. Basically,

 * the NMIP4Config instance uses the idx-type to maintain an ordered list

 * of routes in NMDedupMultiIndex.

 *

 * However, a NMDedupMultiIdxType may also partition the set of objects

 * in multiple distinct lists. NMIP4Config doesn't do that (because instead

 * of creating one idx-type for IPv4 and IPv6 routes, it just cretaes

 * to distinct idx-types, one for each address family.

 * This partitioning is used by NMPlatform to maintain a lookup index for

 * routes by ifindex. As the ifindex is dynamic, it does not create an

 * idx-type instance for each ifindex. Instead, it has one idx-type for

 * all routes. But whenever accessing NMDedupMultiIndex with an NMDedupMultiObj,

 * the partitioning NMDedupMultiIdxType takes into account the NMDedupMultiObj

 * instance to associate it with the right list.

 *

 * Hence, a NMDedupMultiIdxEntry has a list of possibly multiple NMDedupMultiHeadEntry

 * instances, which each is the head for a list of NMDedupMultiEntry instances.

 * In the platform example, the NMDedupMultiHeadEntry partition the indexed objects

 * by their ifindex. */

struct _NMDedupMultiIdxType {

	union {

		NMObjBaseInst parent;

		const NMDedupMultiIdxTypeClass *klass;

	};

	CList lst_idx_head;

	guint len;

};

void nm_dedup_multi_idx_type_init (NMDedupMultiIdxType *idx_type,

                                   const NMDedupMultiIdxTypeClass *klass);

struct _NMDedupMultiIdxTypeClass {

	NMObjBaseClass parent;

	void (*idx_obj_id_hash_update)  (const NMDedupMultiIdxType *idx_type,

	                                 const NMDedupMultiObj *obj,

	                                 struct _NMHashState *h);

	gboolean (*idx_obj_id_equal) (const NMDedupMultiIdxType *idx_type,

	                              const NMDedupMultiObj *obj_a,

	                              const NMDedupMultiObj *obj_b);

	/* an NMDedupMultiIdxTypeClass which implements partitioning of the

	 * tracked objects, must implement the idx_obj_partition*() functions.

	 *

	 * idx_obj_partitionable() may return NULL if the object cannot be tracked.

	 * For example, a index for routes by ifindex, may not want to track any

	 * routes that don't have a valid ifindex. If the idx-type says that the

	 * object is not partitionable, it is never added to the NMDedupMultiIndex. */

	gboolean (*idx_obj_partitionable)   (const NMDedupMultiIdxType *idx_type,

	                                     const NMDedupMultiObj *obj);

	void (*idx_obj_partition_hash_update) (const NMDedupMultiIdxType *idx_type,

	                                       const NMDedupMultiObj *obj,

	                                       struct _NMHashState *h);

	gboolean (*idx_obj_partition_equal) (const NMDedupMultiIdxType *idx_type,

	                                     const NMDedupMultiObj *obj_a,

	                                     const NMDedupMultiObj *obj_b);

};

static inline gboolean

nm_dedup_multi_idx_type_id_equal (const NMDedupMultiIdxType *idx_type,

                                  /* const NMDedupMultiObj * */ gconstpointer obj_a,

                                  /* const NMDedupMultiObj * */ gconstpointer obj_b)

{

	nm_assert (idx_type);

	return    obj_a == obj_b

	       || idx_type->klass->idx_obj_id_equal (idx_type,

	                                             obj_a,

	                                             obj_b);

}

static inline gboolean

nm_dedup_multi_idx_type_partition_equal (const NMDedupMultiIdxType *idx_type,

                                         /* const NMDedupMultiObj * */ gconstpointer obj_a,

                                         /* const NMDedupMultiObj * */ gconstpointer obj_b)

{

	nm_assert (idx_type);

	if (idx_type->klass->idx_obj_partition_equal) {

		nm_assert (obj_a);

		nm_assert (obj_b);

		return    obj_a == obj_b

		       || idx_type->klass->idx_obj_partition_equal (idx_type,

		                                                    obj_a,

		                                                    obj_b);

	}

	return TRUE;

}

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

struct _NMDedupMultiEntry {

	/* this is the list of all entries that share the same head entry.

	 * All entries compare equal according to idx_obj_partition_equal(). */

	CList lst_entries;

	/* const NMDedupMultiObj * */ gconstpointer obj;

	bool is_head;

	bool dirty;

	const NMDedupMultiHeadEntry *head;

};

struct _NMDedupMultiHeadEntry {

	/* this is the list of all entries that share the same head entry.

	 * All entries compare equal according to idx_obj_partition_equal(). */

	CList lst_entries_head;

	const NMDedupMultiIdxType *idx_type;

	bool is_head;

	guint len;

	CList lst_idx;

};

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

static inline gconstpointer

nm_dedup_multi_entry_get_obj (const NMDedupMultiEntry *entry)

{

	/* convenience method that allows to skip the %NULL check on

	 * @entry. Think of the NULL-conditional operator ?. of C# */

	return entry ? entry->obj : NULL;

}

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

static inline void

nm_dedup_multi_entry_set_dirty (const NMDedupMultiEntry *entry,

                                gboolean dirty)

{

	/* NMDedupMultiEntry is always exposed as a const object, because it is not

	 * supposed to be modified outside NMDedupMultiIndex API. Except the "dirty"

	 * flag. In C++ speak, it is a mutable field.

	 *

	 * Add this inline function, to cast-away constness and set the dirty flag. */

	nm_assert (entry);

	((NMDedupMultiEntry *) entry)->dirty = dirty;

}

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

NMDedupMultiIndex *nm_dedup_multi_index_new (void);

NMDedupMultiIndex *nm_dedup_multi_index_ref (NMDedupMultiIndex *self);

NMDedupMultiIndex *nm_dedup_multi_index_unref (NMDedupMultiIndex *self);

static inline void

_nm_auto_unref_dedup_multi_index (NMDedupMultiIndex **v)

{

	if (*v)

		nm_dedup_multi_index_unref (*v);

}

#define nm_auto_unref_dedup_multi_index nm_auto(_nm_auto_unref_dedup_multi_index)

#define NM_DEDUP_MULTI_ENTRY_MISSING      ((const NMDedupMultiEntry *)     GUINT_TO_POINTER (1))

#define NM_DEDUP_MULTI_HEAD_ENTRY_MISSING ((const NMDedupMultiHeadEntry *) GUINT_TO_POINTER (1))

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);

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);

const NMDedupMultiEntry *nm_dedup_multi_index_lookup_obj (const NMDedupMultiIndex *self,

                                                          const NMDedupMultiIdxType *idx_type,

                                                          /*const NMDedupMultiObj * */ gconstpointer obj);

const NMDedupMultiHeadEntry *nm_dedup_multi_index_lookup_head (const NMDedupMultiIndex *self,

                                                               const NMDedupMultiIdxType *idx_type,

                                                               /*const NMDedupMultiObj * */ gconstpointer obj);

guint nm_dedup_multi_index_remove_entry (NMDedupMultiIndex *self,

                                         gconstpointer entry);

guint nm_dedup_multi_index_remove_obj (NMDedupMultiIndex *self,

                                       NMDedupMultiIdxType *idx_type,

                                       /*const NMDedupMultiObj * */ gconstpointer obj,

                                       /*const NMDedupMultiObj ** */ gconstpointer *out_obj);

guint nm_dedup_multi_index_remove_head (NMDedupMultiIndex *self,

                                        NMDedupMultiIdxType *idx_type,

                                        /*const NMDedupMultiObj * */ gconstpointer obj);

guint nm_dedup_multi_index_remove_idx (NMDedupMultiIndex *self,

                                       NMDedupMultiIdxType *idx_type);

void nm_dedup_multi_index_dirty_set_head (NMDedupMultiIndex *self,

                                          const NMDedupMultiIdxType *idx_type,

                                          /*const NMDedupMultiObj * */ gconstpointer obj);

void nm_dedup_multi_index_dirty_set_idx (NMDedupMultiIndex *self,

                                         const NMDedupMultiIdxType *idx_type);

guint nm_dedup_multi_index_dirty_remove_idx (NMDedupMultiIndex *self,

                                             NMDedupMultiIdxType *idx_type,

                                             gboolean mark_survivors_dirty);

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

typedef struct _NMDedupMultiIter {

	const CList *_head;

	const CList *_next;

	const NMDedupMultiEntry *current;

} NMDedupMultiIter;

static inline void

nm_dedup_multi_iter_init (NMDedupMultiIter *iter, const NMDedupMultiHeadEntry *head)

{

	g_return_if_fail (iter);

	if (head && !c_list_is_empty (&head->lst_entries_head)) {

		iter->_head = &head->lst_entries_head;

		iter->_next = head->lst_entries_head.next;

	} else {

		iter->_head = NULL;

		iter->_next = NULL;

	}

	iter->current = NULL;

}

static inline gboolean

nm_dedup_multi_iter_next (NMDedupMultiIter *iter)

{

	g_return_val_if_fail (iter, FALSE);

	if (!iter->_next)

		return FALSE;

	/* we always look ahead for the next. This way, the user

	 * may delete the current entry (but no other entries). */

	iter->current = c_list_entry (iter->_next, NMDedupMultiEntry, lst_entries);

	if (iter->_next->next == iter->_head)

		iter->_next = NULL;

	else

		iter->_next = iter->_next->next;

	return TRUE;

}

#define nm_dedup_multi_iter_for_each(iter, head_entry) \

	for (nm_dedup_multi_iter_init ((iter), (head_entry)); \

	     nm_dedup_multi_iter_next ((iter)); \

	     )

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

typedef gboolean (*NMDedupMultiFcnSelectPredicate) (/* const NMDedupMultiObj * */ gconstpointer obj,

                                                    gpointer user_data);

gconstpointer *nm_dedup_multi_objs_to_array_head (const NMDedupMultiHeadEntry *head_entry,

                                                  NMDedupMultiFcnSelectPredicate predicate,

                                                  gpointer user_data,

                                                  guint *out_len);

GPtrArray *nm_dedup_multi_objs_to_ptr_array_head (const NMDedupMultiHeadEntry *head_entry,

                                                  NMDedupMultiFcnSelectPredicate predicate,

                                                  gpointer user_data);

static inline const NMDedupMultiEntry *

nm_dedup_multi_head_entry_get_idx (const NMDedupMultiHeadEntry *head_entry,

                                   int idx)

{

	CList *iter;

	if (head_entry) {

		if (idx >= 0) {

			c_list_for_each (iter, &head_entry->lst_entries_head) {

				if (idx-- == 0)

					return c_list_entry (iter, NMDedupMultiEntry, lst_entries);

			}

		} else {

			for (iter = head_entry->lst_entries_head.prev;

			     iter != &head_entry->lst_entries_head;

			     iter = iter->prev) {

				if (++idx == 0)

					return c_list_entry (iter, NMDedupMultiEntry, lst_entries);

			}

		}

	}

	return NULL;

}

static inline void

nm_dedup_multi_head_entry_sort (const NMDedupMultiHeadEntry *head_entry,

                                CListSortCmp cmp,

                                gconstpointer user_data)

{

	if (head_entry) {

		/* the head entry can be sorted directly without messing up the

		 * index to which it belongs. Of course, this does mess up any

		 * NMDedupMultiIter instances. */

		c_list_sort ((CList *) &head_entry->lst_entries_head, cmp, user_data);

	}

}

gboolean nm_dedup_multi_entry_reorder (const NMDedupMultiEntry *entry,

                                       const NMDedupMultiEntry *entry_order,

                                       gboolean order_after);

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

#endif /* __NM_DEDUP_MULTI_H__ */