pike7.8-dev 7.8.866-8.1 / usr / include / pike7.8 / pike / multiset.h

/*
|| This file is part of Pike. For copyright information see COPYRIGHT.
|| Pike is distributed under GPL, LGPL and MPL. See the file COPYING
|| for more information.
|| $Id: ac9178d77e353d07f73751cf8cf247cd27a60edc $
*/

#ifndef MULTISET_H
#define MULTISET_H

/* Multisets using rbtree.
 *
 * Created by Martin Stjernholm 2001-05-07
 */

/* #define TEST_MULTISET */

#include "svalue.h"
#include "dmalloc.h"
#include "rbtree.h"
#include "block_alloc_h.h"

/* Keep this defined so that code can test which multiset API is in use. */
#define PIKE_NEW_MULTISETS

/* Note: Don't access the ind svalue (or at least not its type field)
 * in the following directly, since the rbtree flags overlay that. Use
 * assign_multiset_index_no_free() or similar instead. */

struct msnode_ind
{
  struct msnode_ind *prev, *next; /* Must be first. */
  struct svalue ind;		/* Must be second. */
};

struct msnode_indval
{
  struct msnode_indval *prev, *next; /* Must be first. */
  struct svalue ind;		/* Must be second. */
  struct svalue val;
};

union msnode
{
  struct msnode_ind i;
  struct msnode_indval iv;
};

#define MULTISET_FLAG_MARKER	0x1000
#define MULTISET_FLAG_MASK	(RB_FLAG_MASK | MULTISET_FLAG_MARKER)
/* The flag marker is used to reliably nail direct uses of the ind
 * type field. */

struct multiset_data
{
  INT32 refs, noval_refs;
#ifdef PIKE_RUN_UNLOCKED
#error multiset_data has not been adapted for running unlocked.
#endif
  union msnode *root, *free_list;
  struct svalue cmp_less;
  INT32 size, allocsize;
  TYPE_FIELD ind_types;
  TYPE_FIELD val_types;		/* Always BIT_INT in valueless multisets. */
  INT16 flags;
  union msnode nodes[1];
};

struct multiset
{
  PIKE_MEMORY_OBJECT_MEMBERS;
  struct multiset_data *msd;
  struct multiset *next, *prev;
  INT32 node_refs;
};

/* Data structure notes:
 *
 * o  The node free list through multiset_data.free_list is singly
 *    linked by the next pointers. Nodes on the free list are either
 *    free or deleted (see below). Free nodes have ind.type set to
 *    PIKE_T_UNKNOWN, and deleted nodes are flagged with T_DELETED.
 *
 *    Deleted nodes are always before free nodes on the free list.
 *    multiset_data.size counts both the allocated and the deleted
 *    nodes. Note that deleted nodes might still be on the free list
 *    even when there are no node references (see below).
 *
 * o  multiset_data.cmp_less is the integer zero when the internal set
 *    order is used. It must not have any other integer value.
 *
 * o  multset_data.refs counts the number of "independent" references
 *    to the data block. When it's greater than one, the data block
 *    must always be copied if anything but a node value is changed.
 *    Changes of node values might be allowed depending on
 *    multset_data.noval_refs.
 *
 *    A direct pointer to or into the data block can only be kept if
 *    it's accounted for by this ref counter, otherwise an indirection
 *    via a multiset struct must be used.
 *
 *    When the gc runs, it won't touch a multiset_data block that got
 *    direct external references, i.e. if multiset_data.refs is
 *    greater than the number of multiset objects that points to
 *    it.
 *
 * o  multiset_data.noval_refs is the number of the multiset_data.refs
 *    references that don't lock the value part of the data block.
 *    Thus, values may be changed without copy if (refs - noval_refs)
 *    is 1 (if youself have a value lock) or 0 (if you don't). The
 *    functions below that change only values assume that the caller
 *    has a value lock.
 *
 *    Note that you should not do any operation that might cause a
 *    copy of the data block (which includes insert and delete) when
 *    you've increased noval_refs, since it then won't be possible for
 *    the copying function to know whether one ref in noval_refs
 *    should be moved to the copy or not. All copy operations let
 *    noval_refs stay with the original.
 *
 * o  multiset.node_refs counts the number of references to nodes in
 *    the multiset. The references are array offsets in
 *    multiset.msd->nodes, so the data block may be reallocated but no
 *    nodes may be moved relatively within it. Values but not indices
 *    may be changed when there are node references, nodes may be
 *    added and removed, and the order may be changed.
 *
 *    Nodes that are deleted during nonzero node_refs are linked in
 *    first on the free list as usual, but ind.type is set to
 *    T_DELETED. They are thereby flagged to not be used again.
 *    Deleted nodes on the free list are flagged as free as soon as
 *    possible after all node references are gone. There are however
 *    some combinations of node references and shared data blocks that
 *    results in deleted nodes on the free list even after all node
 *    references are gone.
 *
 *    The prev and ind.u.ptr pointers in deleted nodes point to the
 *    previous and next neighbor, respectively, of the node at the
 *    time it was deleted. Thus the relative position of the node is
 *    remembered even after it has been deleted.
 */

/* The following are compatible with PIKE_WEAK_INDICES and PIKE_WEAK_VALUES. */
#define MULTISET_WEAK_INDICES	2
#define MULTISET_WEAK_VALUES	4
#define MULTISET_WEAK		6

#define MULTISET_INDVAL		8

extern struct multiset *first_multiset;
extern struct multiset *gc_internal_multiset;

PMOD_EXPORT void multiset_clear_node_refs (struct multiset *l);

#ifdef PIKE_DEBUG
/* To get good type checking. */
static INLINE union msnode *msnode_check (union msnode *x)
  {return x;}
PMOD_EXPORT extern const char msg_no_multiset_flag_marker[];
#else
#define msnode_check(X) ((union msnode *) (X))
#endif

#define MULTISET_STEP_FUNC(FUNC, NODE)					\
  ((union msnode *) FUNC ((struct rb_node_hdr *) msnode_check (NODE)))
#define low_multiset_first(MSD) MULTISET_STEP_FUNC (rb_first, (MSD)->root)
#define low_multiset_last(MSD) MULTISET_STEP_FUNC (rb_last, (MSD)->root)
#define low_multiset_prev(NODE) MULTISET_STEP_FUNC (rb_prev, NODE)
#define low_multiset_next(NODE) MULTISET_STEP_FUNC (rb_next, NODE)
#define low_multiset_get_nth(MSD, N)					\
  ((union msnode *) rb_get_nth ((struct rb_node_hdr *) (MSD)->root, (N)))
union msnode *low_multiset_find_eq (struct multiset *l, struct svalue *key);

#define low_assign_multiset_index_no_free(TO, NODE) do {		\
    struct svalue *_ms_index_to_ = (TO);				\
    *_ms_index_to_ = msnode_check (NODE)->i.ind;			\
    DO_IF_DEBUG (							\
      if (!(_ms_index_to_->type & MULTISET_FLAG_MARKER))		\
	Pike_fatal (msg_no_multiset_flag_marker);			\
    );									\
    _ms_index_to_->type &= ~MULTISET_FLAG_MASK;				\
    add_ref_svalue (_ms_index_to_);					\
  } while (0)
#define low_assign_multiset_index(TO, NODE) do {			\
    struct svalue *_ms_index_to2_ = (TO);				\
    free_svalue (_ms_index_to2_);					\
    low_assign_multiset_index_no_free (_ms_index_to2_, (NODE));		\
  } while (0)
#define low_push_multiset_index(NODE)					\
  low_assign_multiset_index_no_free (Pike_sp++, (NODE))
#define low_use_multiset_index(NODE, VAR)				\
  ((VAR) = msnode_check (NODE)->i.ind,					\
   DO_IF_DEBUG ((VAR).type & MULTISET_FLAG_MARKER ? 0 :			\
		(Pike_fatal (msg_no_multiset_flag_marker), 0) COMMA)	\
   (VAR).type &= ~MULTISET_FLAG_MASK,					\
   &(VAR))

#define low_get_multiset_value(MSD, NODE)				\
  ((MSD)->flags & MULTISET_INDVAL ? &(NODE)->iv.val :			\
   /* Caller better not try to change this. */				\
   (struct svalue *) &svalue_int_one)
#define low_set_multiset_value(MSD, NODE, VAL) do {			\
    if ((MSD)->flags & MULTISET_INDVAL)					\
      assign_svalue (&(NODE)->iv.val, VAL);				\
  } while (0)

#define OFF2MSNODE(MSD, OFFSET)						\
  ((MSD)->flags & MULTISET_INDVAL ?					\
   (union msnode *) (&(MSD)->nodes->iv + (OFFSET)) :			\
   (union msnode *) (&(MSD)->nodes->i + (OFFSET)))
#define MSNODE2OFF(MSD, NODE)						\
  ((MSD)->flags & MULTISET_INDVAL ?					\
   &(NODE)->iv - &(MSD)->nodes->iv : &(NODE)->i - &(MSD)->nodes->i)

PMOD_EXPORT INT32 multiset_sizeof (struct multiset *l);
#define l_sizeof(L) multiset_sizeof (L)
#define multiset_ind_types(L) ((L)->msd->ind_types)
#define multiset_val_types(L) ((L)->msd->val_types)
#define multiset_get_flags(L) ((L)->msd->flags)
#define multiset_get_cmp_less(L) (&(L)->msd->cmp_less)
#define multiset_indval(L) ((L)->msd->flags & MULTISET_INDVAL)

/* This is somewhat faster than using multiset_sizeof just to
 * check whether or not the multiset has no elements at all. */
#define multiset_is_empty(L) (!(L)->msd->root)

#if defined(USE_DLL) && defined(DYNAMIC_MODULE)
/* Use the function in modules so we don't have to export the block
 * alloc stuff. */
#define free_multiset(M) do_free_multiset (M)
#else

void really_free_multiset (struct multiset *l);

#define free_multiset(L) do {						\
    struct multiset *_ms_ = (L);					\
    debug_malloc_touch (_ms_);						\
    DO_IF_DEBUG (							\
      DO_IF_PIKE_CLEANUP (						\
	if (gc_external_refs_zapped)					\
	  gc_check_zapped (_ms_, PIKE_T_MULTISET, __FILE__, __LINE__))); \
    if (!sub_ref (_ms_)) really_free_multiset (_ms_);			\
  } while (0)

#endif	/* !(USE_DLL && DYNAMIC_MODULE) */

#ifdef PIKE_DEBUG

PMOD_EXPORT union msnode *debug_check_msnode (
  struct multiset *l, ptrdiff_t nodepos, int allow_deleted,
  char *file, int line);
#define check_msnode(L, NODEPOS, ALLOW_DELETED)				\
  debug_check_msnode ((L), (NODEPOS), (ALLOW_DELETED), __FILE__, __LINE__)
#define access_msnode(L, NODEPOS)					\
  check_msnode ((L), (NODEPOS), 0)

#else

#define check_msnode(L, NODEPOS, ALLOW_DELETED)
#define access_msnode(L, NODEPOS) OFF2MSNODE ((L)->msd, (NODEPOS))

#endif

BLOCK_ALLOC_FILL_PAGES (multiset, 2);

/* See rbtree.h for a description of the operations.
 *
 * If cmp_less is used, it's a function pointer used as `< to compare
 * the entries, otherwise the internal set order is used. `< need not
 * define a total order for the possible indices; if neither a < b nor
 * b < a is true then a and b are considered equal orderwise. The
 * order between such indices is arbitrary and stable. The orderwise
 * equality doesn't affect searches on equality, however; if several
 * orderwise equal values are found, then they are searched linearly
 * backwards until one is found which is equal to the key according to
 * `==.
 *
 * It's possible to keep references to individual nodes. The node
 * offset within the multiset data block is used then, which together
 * with the multiset struct can access the node. Use add_msnode_ref
 * when you store a node reference and sub_msnode_ref when you throw
 * it away. The multiset_find_*, multiset_first, multiset_last and
 * multiset_get_nth functions do add_msnode_ref for you (if they
 * return a match). Other functions, like multiset_insert_2, doesn't,
 * even though they might return a node offset.
 *
 * msnode_is_deleted tells whether the referenced node has been
 * deleted. The relative position of a deleted node is remembered by
 * keeping pointers to the neighbors it had when it was deleted. A
 * "defensive" strategy is employed when a deleted node is used in a
 * function: If going forward then the previous neighbor links are
 * followed until a nondeleted neighbor is found, which is then used
 * as the base for the forward movement. Vice versa in the backward
 * direction. This has the effect that if nodes are added and removed
 * in a multiset that is being traversed in some direction, then no
 * newly added nodes in the vicinity of the current one are missed. It
 * also has the effect that the node returned by multiset_next for a
 * deleted node might be before the one returned by multiset_prev.
 *
 * Since the functions might run pike code when comparing entries
 * (even when cmp_less isn't used), the multiset may change during the
 * search in it. If that happens for a destructive operation, it's
 * remade in one way or the other to ensure that the change has been
 * made in the multiset that is current upon return. This normally has
 * no caller visible effects, except for multiset_add_after, which
 * might fail to add the requested entry (it returns less than zero in
 * that case).
 */

/* Returns the node offset, or -1 if no match was found. */
PMOD_EXPORT ptrdiff_t multiset_find_eq (struct multiset *l, struct svalue *key);
PMOD_EXPORT ptrdiff_t multiset_find_lt (struct multiset *l, struct svalue *key);
PMOD_EXPORT ptrdiff_t multiset_find_gt (struct multiset *l, struct svalue *key);
PMOD_EXPORT ptrdiff_t multiset_find_le (struct multiset *l, struct svalue *key);
PMOD_EXPORT ptrdiff_t multiset_find_ge (struct multiset *l, struct svalue *key);
PMOD_EXPORT ptrdiff_t multiset_first (struct multiset *l);
PMOD_EXPORT ptrdiff_t multiset_last (struct multiset *l);
PMOD_EXPORT ptrdiff_t multiset_prev (struct multiset *l, ptrdiff_t nodepos);
PMOD_EXPORT ptrdiff_t multiset_next (struct multiset *l, ptrdiff_t nodepos);

#ifdef PIKE_DEBUG
PMOD_EXPORT extern const char msg_multiset_no_node_refs[];
#endif

#define add_msnode_ref(L) do {(L)->node_refs++;} while (0)
#define sub_msnode_ref(L) do {						\
    struct multiset *_ms_ = (L);					\
    DO_IF_DEBUG (							\
      if (!_ms_->node_refs) Pike_fatal (msg_multiset_no_node_refs);	\
    );									\
    if (!--_ms_->node_refs && _ms_->msd->refs == 1)			\
      multiset_clear_node_refs (_ms_);					\
  } while (0)

PMOD_EXPORT void do_sub_msnode_ref (struct multiset *l);
PMOD_EXPORT int msnode_is_deleted (struct multiset *l, ptrdiff_t nodepos);

#define assign_multiset_index_no_free(TO, L, NODEPOS) do {		\
    struct multiset *_ms_ = (L);					\
    union msnode *_ms_node_ = access_msnode (_ms_, (NODEPOS));		\
    low_assign_multiset_index_no_free (TO, _ms_node_);			\
  } while (0)
#define assign_multiset_index(TO, L, NODEPOS) do {			\
    struct multiset *_ms_ = (L);					\
    union msnode *_ms_node_ = access_msnode (_ms_, (NODEPOS));		\
    low_assign_multiset_index (TO, _ms_node_);				\
  } while (0)
#define push_multiset_index(L, NODEPOS)					\
  assign_multiset_index_no_free (Pike_sp++, (L), (NODEPOS))
#define use_multiset_index(L, NODEPOS, VAR)				\
  ((VAR) = access_msnode ((L), (NODEPOS))->i.ind,			\
   (VAR).type &= ~MULTISET_FLAG_MASK,					\
   &(VAR))

#define get_multiset_value(L, NODEPOS)					\
  ((L)->msd->flags & MULTISET_INDVAL ?					\
   &access_msnode ((L), (NODEPOS))->iv.val :				\
   /* Caller better not try to change this. */				\
   (struct svalue *) &svalue_int_one)
#define set_multiset_value(L, NODEPOS, VAL) do {			\
    if ((L)->msd->flags & MULTISET_INDVAL)				\
      assign_svalue (&access_msnode ((L), (NODEPOS))->iv.val, VAL);	\
  } while (0)
/* Note: It's intentional that the value is silently ignored for
 * index-only multisets. */

#define assign_multiset_value_no_free(TO, L, NODEPOS)			\
  assign_svalue_no_free (TO, get_multiset_value (L, NODEPOS))
#define assign_multiset_value(TO, L, NODEPOS)				\
  assign_svalue (TO, get_multiset_value (L, NODEPOS))
#define push_multiset_value(L, NODEPOS)					\
  push_svalue (get_multiset_value (L, NODEPOS))

#define allocate_multiset(allocsize, flags, cmp_less)			\
  dmalloc_touch (struct multiset *,					\
		 real_allocate_multiset ((allocsize), (flags), (cmp_less)))

PMOD_EXPORT struct multiset *real_allocate_multiset (int allocsize,
						     int flags,
						     struct svalue *cmp_less);
PMOD_EXPORT void do_free_multiset (struct multiset *l);
PMOD_EXPORT void multiset_fix_type_field (struct multiset *l);
PMOD_EXPORT void multiset_set_flags (struct multiset *l, int flags);
PMOD_EXPORT void multiset_set_cmp_less (struct multiset *l,
					struct svalue *cmp_less);
PMOD_EXPORT struct multiset *mkmultiset (struct array *indices);
PMOD_EXPORT struct multiset *mkmultiset_2 (struct array *indices,
					   struct array *values,
					   struct svalue *cmp_less);
PMOD_EXPORT void multiset_insert (struct multiset *l,
				  struct svalue *ind);
PMOD_EXPORT ptrdiff_t multiset_insert_2 (struct multiset *l,
					 struct svalue *ind,
					 struct svalue *val,
					 int replace);
PMOD_EXPORT ptrdiff_t multiset_add (struct multiset *l,
				    struct svalue *ind,
				    struct svalue *val);
PMOD_EXPORT ptrdiff_t multiset_add_after (struct multiset *l,
					  ptrdiff_t node,
					  struct svalue *ind,
					  struct svalue *val);
PMOD_EXPORT int multiset_delete (struct multiset *l,
				 struct svalue *ind);
PMOD_EXPORT int multiset_delete_2 (struct multiset *l,
				   struct svalue *ind,
				   struct svalue *removed_val);
PMOD_EXPORT void multiset_delete_node (struct multiset *l,
				       ptrdiff_t node);
PMOD_EXPORT int multiset_member (struct multiset *l,
				 struct svalue *key);
PMOD_EXPORT struct svalue *multiset_lookup (struct multiset *l,
					    struct svalue *key);
struct array *multiset_indices (struct multiset *l);
struct array *multiset_values (struct multiset *l);
struct array *multiset_range_indices (struct multiset *l,
				      ptrdiff_t beg, ptrdiff_t end);
struct array *multiset_range_values (struct multiset *l,
				     ptrdiff_t beg, ptrdiff_t end);
PMOD_EXPORT void check_multiset_for_destruct (struct multiset *l);
PMOD_EXPORT struct multiset *copy_multiset (struct multiset *l);
PMOD_EXPORT struct multiset *merge_multisets (struct multiset *a,
					      struct multiset *b,
					      int operation);
PMOD_EXPORT struct multiset *add_multisets (struct svalue *argp, int count);
PMOD_EXPORT int multiset_equal_p (struct multiset *a, struct multiset *b,
				  struct processing *p);
void describe_multiset (struct multiset *l, struct processing *p, int indent);
void simple_describe_multiset (struct multiset *l);
int multiset_is_constant (struct multiset *l, struct processing *p);
node *make_node_from_multiset (struct multiset *l);
PMOD_EXPORT void f_aggregate_multiset (int args);
struct multiset *copy_multiset_recursively (struct multiset *l,
					    struct mapping *p);
PMOD_EXPORT ptrdiff_t multiset_get_nth (struct multiset *l, size_t n);

PMOD_EXPORT void visit_multiset (struct multiset *l, int action);
unsigned gc_touch_all_multisets (void);
void gc_check_all_multisets (void);
void gc_mark_multiset_as_referenced (struct multiset *l);
void gc_mark_all_multisets (void);
void gc_zap_ext_weak_refs_in_multisets (void);
void real_gc_cycle_check_multiset (struct multiset *l, int weak);
void gc_cycle_check_all_multisets (void);
size_t gc_free_all_unreferenced_multisets (void);

#define visit_multiset_ref(L, REF_TYPE)				\
  visit_ref (pass_multiset (L), (REF_TYPE),			\
	     (visit_thing_fn *) &visit_multiset, NULL)
#define gc_cycle_check_multiset(X, WEAK) \
  gc_cycle_enqueue ((gc_cycle_check_cb *) real_gc_cycle_check_multiset, (X), (WEAK))

#ifdef PIKE_DEBUG
void check_multiset (struct multiset *l, int safe);
void check_all_multisets (int safe);
void debug_dump_multiset (struct multiset *l);
#endif

void count_memory_in_multisets (size_t *num, size_t *size);
void init_multiset (void);
void exit_multiset (void);
void test_multiset (void);

#endif /* MULTISET_H */