diff options
| author | Thomas Haller <thaller@redhat.com> | 2017-06-04 22:43:21 +0200 |
|---|---|---|
| committer | Thomas Haller <thaller@redhat.com> | 2017-07-05 14:22:10 +0200 |
| commit | f9202c2ac120152f047845f859bac22759e634f3 (patch) | |
| tree | b32ee583ac06229e4fcb07a3d82d4b97cb1ef3d0 /Makefile.am | |
| parent | 343c967e662ce6525cfdeeab3af3bdbbca3791ec (diff) | |
| download | NetworkManager-f9202c2ac120152f047845f859bac22759e634f3.tar.gz | |
shared: add NMDedupMultiIndex "nm-dedup-multi.h"
Add the NMDedupMultiIndex cache. It basically tracks
objects as doubly linked list. With the addition that
each object and the list head is indexed by a hash table.
Also, it supports tracking multiple distinct lists,
all indexed by the idx-type instance.
It also deduplicates the tracked objects and shares them.
- the objects that can be put into the cache must be immutable
and ref-counted. That is, the cache will deduplicate them
and share the reference. Also, as these objects are immutable
and ref-counted, it is safe that users outside the cache
own them too (as long as they keep them immutable and manage
their reference properly).
The deduplication uses obj_id_hash_func() and obj_id_equal_func().
These functions must cover *every* aspect of the objects when
comparing equality. For example nm_platform_ip4_route_cmp()
would be a function that qualifies as obj_id_equal_func().
The cache creates references to the objects as needed and
gives them back. This happens via obj_get_ref() and
obj_put_ref(). Note that obj_get_ref() is free to create
a new object, for example to convert a stack-allocated object
to a (ref-counted) heap allocated one.
The deduplication process creates NMDedupIndexBox instances
which are the ref-counted entity. In principle, the objects
themself don't need to be ref-counted as that is handled by
the boxing instance.
- The cache doesn't only do deduplication. It is a multi-index,
meaning, callers add objects using a index handle NMDedupMultiIdxType.
The NMDedupMultiIdxType instance is the access handle to lookup
the list and objects inside the cache. Note that the idx-type
instance may partition the objects in distinct lists.
For all operations there are cross-references and hash table lookups.
Hence, every operation of this data structure is O(1) and the memory
overhead for an index tracking an object is constant.
The cache preserves ordering (due to linked list) and exposes the list
as public API. This allows users to iterate the list without any
additional copying of elements.
Diffstat (limited to 'Makefile.am')
| -rw-r--r-- | Makefile.am | 3 |
1 files changed, 3 insertions, 0 deletions
diff --git a/Makefile.am b/Makefile.am index 336fbd5a7a..98b717021e 100644 --- a/Makefile.am +++ b/Makefile.am @@ -415,6 +415,7 @@ libnm_core_lib_h_pub_real = \ libnm_core_lib_h_pub_mkenums = \ libnm-core/nm-core-enum-types.h libnm_core_lib_h_priv = \ + shared/nm-utils/nm-dedup-multi.h \ shared/nm-utils/nm-enum-utils.h \ shared/nm-utils/nm-shared-utils.h \ shared/nm-utils/nm-udev-utils.h \ @@ -429,6 +430,7 @@ libnm_core_lib_h_priv = \ libnm-core/nm-setting-private.h \ libnm-core/nm-utils-private.h libnm_core_lib_c_real = \ + shared/nm-utils/nm-dedup-multi.c \ shared/nm-utils/nm-enum-utils.c \ shared/nm-utils/nm-shared-utils.c \ shared/nm-utils/nm-udev-utils.c \ @@ -1271,6 +1273,7 @@ $(src_libsystemd_nm_la_OBJECTS): $(libnm_core_lib_h_pub_mkenums) src_libNetworkManagerBase_la_CPPFLAGS = $(src_cppflags) src_libNetworkManagerBase_la_SOURCES = \ + \ src/nm-core-utils.c \ src/nm-core-utils.h \ src/nm-logging.c \ |