Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/ntirpc/misc/rbtree_x.h


$ cat -n /usr/include/ntirpc/misc/rbtree_x.h

     1	
     2	#ifndef _RBTREE_X_H
     3	#define _RBTREE_X_H
     4	
     5	#include <misc/portable.h>
     6	#include <inttypes.h>
     7	#include <misc/stdio.h>
     8	#include <misc/rbtree.h>
     9	#include <rpc/types.h>
    10	
    11	struct rbtree_x_part {
    12		CACHE_PAD(0);
    13		pthread_rwlock_t lock;
    14		pthread_mutex_t mtx;
    15		pthread_spinlock_t sp;
    16		void *u1;
    17		void *u2;
    18		struct opr_rbtree t;
    19		struct opr_rbtree_node **cache;
    20		 CACHE_PAD(1);
    21	};
    22	
    23	struct rbtree_x {
    24		uint32_t npart;
    25		uint32_t flags;
    26		int32_t cachesz;
    27		struct rbtree_x_part *tree;
    28	};
    29	
    30	#define RBT_X_FLAG_NONE      0x0000
    31	#define RBT_X_FLAG_ALLOC     0x0001
    32	
    33	/* Cache strategies.
    34	 *
    35	 * In read-through strategy, entries are always inserted in the
    36	 * tree, but lookups may be O(1) when an entry is shadowed in cache.
    37	 *
    38	 * In the write through strategy, t->cache and t->tree partition
    39	 * t, and t->cache is always consulted first.
    40	 */
    41	
    42	#define RBT_X_FLAG_CACHE_RT   0x0002
    43	#define RBT_X_FLAG_CACHE_WT   0x0004
    44	
    45	#define rbtx_idx_of_scalar(xt, k) ((k)%((xt)->npart))
    46	#define rbtx_partition_of_ix(xt, ix) ((xt)->tree+(ix))
    47	#define rbtx_partition_of_scalar(xt, k) \
    48		(rbtx_partition_of_ix((xt), rbtx_idx_of_scalar((xt), (k))))
    49	
    50	extern int rbtx_init(struct rbtree_x *xt, opr_rbtree_cmpf_t cmpf,
    51			     uint32_t npart, uint32_t flags);
    52	
    53	static inline struct opr_rbtree_node *rbtree_x_cached_lookup(
    54		struct rbtree_x *xt,
    55		struct rbtree_x_part *t,
    56		struct opr_rbtree_node *nk, uint64_t hk)
    57	{
    58		struct opr_rbtree_node *nv_cached, *nv = NULL;
    59		uint32_t offset;
    60	
    61		if (!t)
    62			t = rbtx_partition_of_scalar(xt, hk);
    63	
    64		offset = hk % xt->cachesz;
    65		nv_cached = t->cache[offset];
    66		if (nv_cached) {
    67			if (t->t.cmpf(nv_cached, nk) == 0) {
    68				nv = nv_cached;
    69				goto out;
    70			}
    71		}
    72	
    73		nv = opr_rbtree_lookup(&t->t, nk);
    74		if (nv && (xt->flags & RBT_X_FLAG_CACHE_RT))
    75			t->cache[offset] = nv;
    76	
    77		__warnx(TIRPC_DEBUG_FLAG_RBTREE,
    78			"rbtree_x_cached_lookup: t %p nk %p nv %p" "(%s hk %" PRIx64
    79			" slot/offset %d)", t, nk, nv, (nv_cached) ? "CACHED" : "", hk,
    80			offset);
    81	
    82	 out:
    83		return (nv);
    84	}
    85	
    86	static inline struct opr_rbtree_node *rbtree_x_cached_insert(
    87		struct rbtree_x *xt,
    88		struct rbtree_x_part *t,
    89		struct opr_rbtree_node *nk, uint64_t hk)
    90	{
    91		struct opr_rbtree_node *v_cached, *nv = NULL;
    92		uint32_t offset;
    93	
    94		int cix = rbtx_idx_of_scalar(xt, hk);
    95		struct rbtree_x_part *ct = rbtx_partition_of_ix(xt, cix);
    96	
    97		if (!t)
    98			t = ct;
    99	
   100		offset = hk % xt->cachesz;
   101		v_cached = t->cache[offset];
   102	
   103		__warnx(TIRPC_DEBUG_FLAG_RBTREE,
   104			"rbtree_x_cached_insert: cix %d ct %p t %p inserting %p "
   105			"(%s hk %" PRIx64 " slot/offset %d) flags %d", cix, ct, t, nk,
   106			(v_cached) ? "rbt" : "cache", hk, offset, xt->flags);
   107	
   108		if (xt->flags & RBT_X_FLAG_CACHE_WT) {
   109			if (!v_cached) {
   110				nv = t->cache[offset] = nk;
   111			} else {
   112				nv = opr_rbtree_insert(&t->t, nk);
   113				if (!nv)
   114					nv = nk;
   115			}
   116		} else {
   117			/* RBT_X_FLAG_CACHE_RT */
   118			nv = v_cached = t->cache[offset] = nk;
   119			(void)opr_rbtree_insert(&t->t, nk);
   120		}
   121	
   122		return (nv);
   123	}
   124	
   125	static inline void rbtree_x_cached_remove(struct rbtree_x *xt,
   126						  struct rbtree_x_part *t,
   127						  struct opr_rbtree_node *nk,
   128						  uint64_t hk)
   129	{
   130		struct opr_rbtree_node *v_cached;
   131		uint32_t offset;
   132	
   133		int cix = rbtx_idx_of_scalar(xt, hk);
   134		struct rbtree_x_part *ct = rbtx_partition_of_ix(xt, cix);
   135	
   136		if (!t)
   137			t = ct;
   138	
   139		offset = hk % xt->cachesz;
   140		v_cached = t->cache[offset];
   141	
   142		__warnx(TIRPC_DEBUG_FLAG_RBTREE,
   143			"rbtree_x_cached_remove: cix %d ct %p t %p removing %p "
   144			"(%s hk %" PRIx64 " slot/offset %d) flags %d", cix, ct, t, nk,
   145			(v_cached) ? "cache" : "rbt", hk, offset, xt->flags);
   146	
   147		if (xt->flags & RBT_X_FLAG_CACHE_WT) {
   148			if (v_cached && (t->t.cmpf(nk, v_cached) == 0))
   149				t->cache[offset] = NULL;
   150			else
   151				return (opr_rbtree_remove(&t->t, nk));
   152		} else {
   153			/* RBT_X_FLAG_CACHE_RT */
   154			if (v_cached && (t->t.cmpf(nk, v_cached) == 0))
   155				t->cache[offset] = NULL;
   156			return (opr_rbtree_remove(&t->t, nk));
   157		}
   158	}
   159	
   160	#endif				/* _RBTREE_X_H */