Main Page | Class List | Directories | File List | Class Members | File Members
src

multiset.c File Reference

#include "global.h"
#include "builtin_functions.h"
#include "gc.h"
#include "interpret.h"
#include "multiset.h"
#include "mapping.h"
#include "object.h"
#include "opcodes.h"
#include "pike_error.h"
#include "rbtree_low.h"
#include "pike_security.h"
#include "svalue.h"
#include "block_alloc.h"
#include <assert.h>

Classes

struct  tree_build_data
struct  recovery_data
struct  merge_data

Defines

#define sp   Pike_sp
#define ALLOC_SIZE(size)   ((size) ? (size) + 4 : 0)
#define ENLARGE_SIZE(size)   (((size) << 1) + 4)
#define DO_SHRINK(msd, extra)   ((((msd)->size + extra) << 2) + 4 <= (msd)->allocsize)
#define msnode_ptr_check(X)   ((union msnode **) (X))
#define msnode_ind_check(X)   ((struct msnode_ind *) (X))
#define msnode_indval_check(X)   ((struct msnode_indval *) (X))
#define sub_extra_ref(X)   do {sub_ref (X);} while (0)
#define ALLOC_TRACE(X)
#define INTERNAL_CMP(A, B, CMP_RES)
#define EXTERNAL_CMP(CMP_LESS)
#define SAME_CMP_LESS(MSD_A, MSD_B)
#define HDR(NODE)   ((struct rb_node_hdr *) msnode_check (NODE))
#define PHDR(NODEPTR)   ((struct rb_node_hdr **) msnode_ptr_check (NODEPTR))
#define RBNODE(NODE)   ((union msnode *) rb_node_check (NODE))
#define INODE(NODE)   ((union msnode *) msnode_ind_check (NODE))
#define IVNODE(NODE)   ((union msnode *) msnode_indval_check (NODE))
#define NEXT_FREE(NODE)   INODE (msnode_check (NODE)->i.next)
#define SET_NEXT_FREE(NODE, NEXT)   (msnode_check (NODE)->i.next = (struct msnode_ind *) msnode_check (NEXT))
#define DELETED_PREV(NODE)   INODE (msnode_check (NODE)->i.prev)
#define DELETED_NEXT(NODE)   ((union msnode *) msnode_check (NODE)->i.ind.u.ptr)
#define NODE_AT(MSD, TYPE, POS)   ((struct TYPE *) &(MSD)->nodes + (POS))
#define NODE_OFFSET(TYPE, POS)   PTR_TO_INT (NODE_AT ((struct multiset_data *) NULL, TYPE, POS))
#define SHIFT_PTR(PTR, FROM, TO)   ((char *) (PTR) - (char *) (FROM) + (char *) (TO))
#define SHIFT_NODEPTR(NODEPTR, FROM_MSD, TO_MSD)   ((union msnode *) SHIFT_PTR (msnode_check (NODEPTR), FROM_MSD, TO_MSD))
#define SHIFT_HDRPTR(HDRPTR, FROM_MSD, TO_MSD)   ((struct rb_node_hdr *) SHIFT_PTR (rb_node_check (HDRPTR), FROM_MSD, TO_MSD))
#define COPY_NODE_PTRS(OLD, OLDBASE, NEW, NEWBASE, TYPE)
#define COPY_DELETED_PTRS_EXTRA(OLD, OLDBASE, NEW, NEWBASE)
#define COPY_NODE_IND(OLD, NEW, TYPE)
#define EXPAND_ARG(X)   X
#define IGNORE_ARG(X)
#define DO_WITH_NODES(MSD)
#define INIT_MULTISET(L)
#define EXIT_BLOCK(L)
#define COUNT_OTHER()
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define CLEAR_DELETED_ON_FREE_LIST(MSD)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define MOVE_MSD_REF(L, MSD)
#define MOVE_MSD_REF_AND_FREE(L, MSD)
#define ALLOC_MSNODE(MSD, GOT_NODE_REFS, NODE)
#define ADD_TO_FREE_LIST(MSD, NODE)
#define SHIFT_BY_POS(OLD, OLDBASE, OLDTYPE, NEWBASE, NEWTYPE)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define ADD_NODE(MSD, RBSTACK, NEW, IND, VAL, FIND_TYPE)
#define TEST_LESS(MSD, A, B, CMP_RES)
#define GET_RANGE_SIZE_AND_END(BEGPOS, ENDPOS, MSD, MSD_SIZE, RANGE_SIZE, END)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define COPY_MSD_AND_KEEP_FLAGS(FROM, TO)
#define EMPTY_MSD_AND_KEEP_FLAGS(L)
#define ALLOC_COPY_AND_SET_FLAGS(FROM, RES, FLAGSRC)
#define ALLOC_EMPTY_AND_SET_FLAGS(RES, FLAGSRC)
#define ALLOC_RES_NODE(RES, RES_MSD, NEW_NODE)
#define UNLINK_RES_NODE(RES_MSD, RES_LIST, GOT_NODE_REFS, NODE)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define GC_MSD_GOT_NODE_REFS   GC_USER_1
#define GC_MSD_VISITED   GC_USER_2
#define WITH_NODES_BLOCK(TYPE, OTHERTYPE, IND, INDVAL)
#define GC_RECURSE_MSD_IN_USE(MSD, RECURSE_FN, IND_TYPES, VAL_TYPES)
#define GC_RECURSE(MSD, GOT_NODE_REFS, REC_NODE_I, REC_NODE_IV, TYPE, IND_TYPES, VAL_TYPES)
#define GC_REC_I_WEAK_NONE(IND, REMOVE, N_REC, W_REC)
#define GC_REC_I_WEAK_IND(IND, REMOVE, N_REC, W_REC)
#define GC_REC_IV_WEAK_NONE(IND, VAL, REMOVE, N_REC, W_REC, N_TST, W_TST)
#define GC_REC_IV_WEAK_IND(IND, VAL, REMOVE, N_REC, W_REC, N_TST, W_TST)
#define GC_REC_IV_WEAK_VAL(IND, VAL, REMOVE, N_REC, W_REC, N_TST, W_TST)
#define GC_REC_IV_WEAK_BOTH(IND, VAL, REMOVE, N_REC, W_REC, N_TST, W_TST)

Enumerations

enum  find_types {
  FIND_EQUAL, FIND_NOEQUAL, FIND_LESS, FIND_GREATER,
  FIND_NOROOT, FIND_DESTRUCTED
}

Functions

void free_multiset_data (struct multiset_data *msd)
PMOD_EXPORT void multiset_clear_node_refs (struct multiset *l)
PMOD_EXPORT INT32 multiset_sizeof (struct multiset *l)
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 do_sub_msnode_ref (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 int msnode_is_deleted (struct multiset *l, ptrdiff_t nodepos)
msnode * low_multiset_find_eq (struct multiset *l, struct svalue *key)
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_ge (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_gt (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)
void multiset_fix_type_field (struct multiset *l)
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 nodepos, 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 nodepos)
PMOD_EXPORT int multiset_member (struct multiset *l, struct svalue *key)
PMOD_EXPORT struct svalue * multiset_lookup (struct multiset *l, struct svalue *key)
array * multiset_indices (struct multiset *l)
array * multiset_values (struct multiset *l)
array * multiset_range_indices (struct multiset *l, ptrdiff_t begpos, ptrdiff_t endpos)
array * multiset_range_values (struct multiset *l, ptrdiff_t begpos, ptrdiff_t endpos)
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 *vect, 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 (INT32 args)
multiset * copy_multiset_recursively (struct multiset *l, struct mapping *p)
PMOD_EXPORT ptrdiff_t multiset_get_nth (struct multiset *l, size_t n)
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 real_gc_cycle_check_multiset (struct multiset *l, int weak)
void gc_cycle_check_all_multisets (void)
void gc_zap_ext_weak_refs_in_multisets (void)
size_t gc_free_all_unreferenced_multisets (void)
void init_multiset ()
void exit_multiset ()

Variables

multiset * first_multiset = NULL
multiset * gc_internal_multiset = NULL
svalue svalue_int_one

Define Documentation

#define ADD_NODE (  MSD,
RBSTACK,
NEW,
IND,
VAL,
FIND_TYPE   ) 
 

Value:

do {            \
    assign_svalue_no_free (&NEW->i.ind, IND);                           \
    MSD->ind_types |= 1 << IND->type;                                   \
    DO_IF_DEBUG (NEW->i.ind.type |= MULTISET_FLAG_MARKER);              \
    if (MSD->flags & MULTISET_INDVAL) {                                 \
      if (VAL) {                                                        \
        assign_svalue_no_free (&NEW->iv.val, VAL);                      \
        MSD->val_types |= 1 << VAL->type;                               \
      }                                                                 \
      else {                                                            \
        NEW->iv.val.type = T_INT;                                       \
        NEW->iv.val.u.integer = 1;                                      \
        MSD->val_types |= BIT_INT;                                      \
      }                                                                 \
    }                                                                   \
    switch (FIND_TYPE) {                                                \
      case FIND_LESS:                                                   \
        low_rb_link_at_next (PHDR (&MSD->root), RBSTACK, HDR (NEW));    \
        break;                                                          \
      case FIND_GREATER:                                                \
        low_rb_link_at_prev (PHDR (&MSD->root), RBSTACK, HDR (NEW));    \
        break;                                                          \
      case FIND_NOROOT:                                                 \
        MSD->root = NEW;                                                \
        low_rb_init_root (HDR (NEW));                                   \
        break;                                                          \
      default: DO_IF_DEBUG (Pike_fatal ("Invalid find_type.\n"));       \
    }                                                                   \
  } while (0)

#define ADD_TO_FREE_LIST (  MSD,
NODE   ) 
 

Value:

do {                            \
    SET_NEXT_FREE (NODE, (MSD)->free_list);                             \
    (MSD)->free_list = (NODE);                                          \
  } while (0)

#define ALLOC_COPY_AND_SET_FLAGS (  FROM,
RES,
FLAGSRC   ) 
 

Value:

do {            \
    (RES) = copy_multiset (FROM);                                       \
    SET_ONERROR (uwp, do_free_multiset, (RES));                         \
    multiset_set_flags ((RES), (FLAGSRC)->msd->flags);                  \
    multiset_set_cmp_less ((RES), &(FLAGSRC)->msd->cmp_less);           \
    UNSET_ONERROR (uwp);                                                \
  } while (0)

#define ALLOC_EMPTY_AND_SET_FLAGS (  RES,
FLAGSRC   ) 
 

Value:

do {                    \
    (RES) = allocate_multiset (0, (FLAGSRC)->msd->flags,                \
                               &(FLAGSRC)->msd->cmp_less);              \
  } while (0)

#define ALLOC_MSNODE (  MSD,
GOT_NODE_REFS,
NODE   ) 
 

Value:

do {                    \
    if (GOT_NODE_REFS)                                                  \
      (NODE) = alloc_msnode_verbatim (MSD);                             \
    else {                                                              \
      (NODE) = (MSD)->free_list;                                        \
      DO_IF_DEBUG (                                                     \
        if (!(NODE)) Pike_fatal ("Multiset data block unexpectedly full.\n"); \
      );                                                                \
      (MSD)->free_list = NEXT_FREE (NODE);                              \
      if ((NODE)->i.ind.type == PIKE_T_UNKNOWN) (MSD)->size++;          \
    }                                                                   \
  } while (0)

#define ALLOC_RES_NODE (  RES,
RES_MSD,
NEW_NODE   ) 
 

Value:

do {                                                                    \
    union msnode *node;                                                 \
    if (prepare_for_add (RES, 1)) {                                     \
      merge_shift_ptrs (RES_MSD, (RES)->msd, &m);                       \
      (RES_MSD) = (RES)->msd;                                           \
    }                                                                   \
    ALLOC_MSNODE (RES_MSD, (RES)->node_refs, node);                     \
    NEW_NODE = HDR (node);                                              \
  } while (0)

#define ALLOC_SIZE (  size   )     ((size) ? (size) + 4 : 0)
 

#define ALLOC_TRACE (  X   ) 
 

#define CLEAR_DELETED_ON_FREE_LIST (  MSD   ) 
 

Value:

do {                            \
    assert ((MSD)->refs == 1);                                          \
    if ((MSD)->free_list && (MSD)->free_list->i.ind.type == T_DELETED)  \
      clear_deleted_on_free_list (MSD);                                 \
  } while (0)

#define COPY_DELETED_PTRS_EXTRA (  OLD,
OLDBASE,
NEW,
NEWBASE   ) 
 

Value:

do {    \
    (NEW)->ind.u.ptr = (OLD)->ind.u.ptr ?                               \
      SHIFT_PTR ((OLD)->ind.u.ptr, OLDBASE, NEWBASE) : NULL;            \
  } while (0)

#define COPY_MSD_AND_KEEP_FLAGS (  FROM,
TO   ) 
 

Value:

do {                            \
    struct multiset_data *oldmsd = (TO)->msd;                           \
    SET_ONERROR (uwp, free_indirect_multiset_data, &oldmsd);            \
    add_ref ((TO)->msd = (FROM)->msd);                                  \
    multiset_set_flags ((TO), oldmsd->flags);                           \
    multiset_set_cmp_less ((TO), &oldmsd->cmp_less);                    \
    UNSET_ONERROR (uwp);                                                \
    if (!sub_ref (oldmsd)) free_multiset_data (oldmsd);                 \
  } while (0)

#define COPY_NODE_IND (  OLD,
NEW,
TYPE   ) 
 

Value:

do {                            \
    (NEW)->ind = (OLD)->ind;                                            \
    (NEW)->ind.type &= ~MULTISET_FLAG_MASK;                             \
    add_ref_svalue (&(NEW)->ind);                                       \
    (NEW)->ind.type = (OLD)->ind.type;                                  \
  } while (0)

#define COPY_NODE_PTRS (  OLD,
OLDBASE,
NEW,
NEWBASE,
TYPE   ) 
 

Value:

do {            \
    (NEW)->prev = (OLD)->prev ?                                         \
      (struct TYPE *) SHIFT_PTR ((OLD)->prev, OLDBASE, NEWBASE) : NULL; \
    (NEW)->next = (OLD)->next ?                                         \
      (struct TYPE *) SHIFT_PTR ((OLD)->next, OLDBASE, NEWBASE) : NULL; \
  } while (0)

 
#define COUNT_OTHER (   ) 
 

Value:

do {                                            \
    struct multiset *l;                                                 \
    double datasize = 0.0;                                              \
    for (l = first_multiset; l; l = l->next)                            \
      datasize += (l->msd->flags & MULTISET_INDVAL ?                    \
                   NODE_OFFSET (msnode_indval, l->msd->allocsize) :     \
                   NODE_OFFSET (msnode_ind, l->msd->allocsize)) /       \
        (double) l->msd->refs;                                          \
    size += (int) datasize;                                             \
  } while (0)

#define DELETED_NEXT (  NODE   )     ((union msnode *) msnode_check (NODE)->i.ind.u.ptr)
 

#define DELETED_PREV (  NODE   )     INODE (msnode_check (NODE)->i.prev)
 

#define DO_SHRINK (  msd,
extra   )     ((((msd)->size + extra) << 2) + 4 <= (msd)->allocsize)
 

#define DO_WITH_NODES (  MSD   ) 
 

Value:

do {                                            \
    if ((MSD)->flags & MULTISET_INDVAL) {                               \
      WITH_NODES_BLOCK (msnode_indval, msnode_ind, IGNORE_ARG, EXPAND_ARG); \
    }                                                                   \
    else {                                                              \
      WITH_NODES_BLOCK (msnode_ind, msnode_indval, EXPAND_ARG, IGNORE_ARG); \
    }                                                                   \
  } while (0)

#define EMPTY_MSD_AND_KEEP_FLAGS (  L   ) 
 

Value:

do {                            \
    struct multiset_data *oldmsd = (L)->msd;                            \
    add_ref ((L)->msd = low_alloc_multiset_data (0, oldmsd->flags));    \
    assign_svalue_no_free (&(L)->msd->cmp_less, &oldmsd->cmp_less);     \
    if (!sub_ref (oldmsd)) free_multiset_data (oldmsd);                 \
  } while (0)

#define ENLARGE_SIZE (  size   )     (((size) << 1) + 4)
 

#define EXIT_BLOCK (  L   ) 
 

Value:

do {                                            \
    FREE_PROT (L);                                                      \
    DO_IF_DEBUG (                                                       \
      if (L->refs) {                                                    \
        DO_IF_DMALLOC(describe_something (L, T_MULTISET, 0,2,0, NULL)); \
        Pike_fatal ("Too few refs %d to multiset.\n", L->refs);         \
      }                                                                 \
      if (L->node_refs) {                                               \
        DO_IF_DMALLOC(describe_something (L, T_MULTISET, 0,2,0, NULL)); \
        Pike_fatal ("Freeing multiset with %d node refs.\n", L->node_refs); \
      }                                                                 \
    );                                                                  \
    if (!sub_ref (L->msd)) free_multiset_data (L->msd);                 \
    DOUBLEUNLINK (first_multiset, L);                                   \
    GC_FREE (L);                                                        \
  } while (0)

#define EXPAND_ARG (  X   )     X
 

#define EXTERNAL_CMP (  CMP_LESS   ) 
 

Value:

do {                                    \
    apply_svalue (CMP_LESS, 2);                                         \
  } while (0)

#define GC_MSD_GOT_NODE_REFS   GC_USER_1
 

#define GC_MSD_VISITED   GC_USER_2
 

#define GC_REC_I_WEAK_IND (  IND,
REMOVE,
N_REC,
W_REC   ) 
 

Value:

do {            \
    REMOVE = W_REC (IND, 1);                                            \
  } while (0)

#define GC_REC_I_WEAK_NONE (  IND,
REMOVE,
N_REC,
W_REC   ) 
 

Value:

do {            \
    REMOVE = N_REC (IND, 1);                                            \
  } while (0)

#define GC_REC_IV_WEAK_BOTH (  IND,
VAL,
REMOVE,
N_REC,
W_REC,
N_TST,
W_TST   ) 
 

Value:

do { \
    if ((REMOVE = W_TST (IND))) /* Don't recurse now. */                \
      gc_free_svalue (VAL);                                             \
    else if ((REMOVE = W_REC (VAL, 1)))                                 \
      gc_free_svalue (IND);                                             \
    else                                                                \
      W_REC (IND, 1); /* Now we can recurse the index. */               \
  } while (0)

#define GC_REC_IV_WEAK_IND (  IND,
VAL,
REMOVE,
N_REC,
W_REC,
N_TST,
W_TST   ) 
 

Value:

do { \
    if ((REMOVE = W_REC (IND, 1)))                                      \
      gc_free_svalue (VAL);                                             \
    else                                                                \
      N_REC (VAL, 1);                                                   \
  } while (0)

#define GC_REC_IV_WEAK_NONE (  IND,
VAL,
REMOVE,
N_REC,
W_REC,
N_TST,
W_TST   ) 
 

Value:

do { \
    if ((REMOVE = N_REC (IND, 1)))                                      \
      gc_free_svalue (VAL);                                             \
    else                                                                \
      N_REC (VAL, 1);                                                   \
  } while (0)

#define GC_REC_IV_WEAK_VAL (  IND,
VAL,
REMOVE,
N_REC,
W_REC,
N_TST,
W_TST   ) 
 

Value:

do { \
    if ((REMOVE = N_TST (IND))) /* Don't recurse now. */                \
      gc_free_svalue (VAL);                                             \
    else if ((REMOVE = W_REC (VAL, 1)))                                 \
      gc_free_svalue (IND);                                             \
    else                                                                \
      N_REC (IND, 1); /* Now we can recurse the index. */               \
  } while (0)

#define GC_RECURSE (  MSD,
GOT_NODE_REFS,
REC_NODE_I,
REC_NODE_IV,
TYPE,
IND_TYPES,
VAL_TYPES   ) 
 

#define GC_RECURSE_MSD_IN_USE (  MSD,
RECURSE_FN,
IND_TYPES,
VAL_TYPES   ) 
 

Value:

do { \
    union msnode *node = low_multiset_first (MSD);                      \
    IND_TYPES = msd->ind_types;                                         \
    if (node) {                                                         \
      struct svalue ind;                                                \
                                                                        \
      if (msd->flags & MULTISET_INDVAL)                                 \
        do {                                                            \
          low_use_multiset_index (node, ind);                           \
          if (!IS_DESTRUCTED (&ind) && RECURSE_FN (&ind, 1)) {          \
            DO_IF_DEBUG (Pike_fatal ("Didn't expect an svalue zapping now.\n")); \
          }                                                             \
          RECURSE_FN (&node->iv.val, 1);                                \
          VAL_TYPES |= 1 << node->iv.val.type;                          \
        } while ((node = low_multiset_next (node)));                    \
                                                                        \
      else                                                              \
        do {                                                            \
          low_use_multiset_index (node, ind);                           \
          if (!IS_DESTRUCTED (&ind) && RECURSE_FN (&ind, 1)) {          \
            DO_IF_DEBUG (Pike_fatal ("Didn't expect an svalue zapping now.\n")); \
          }                                                             \
        } while ((node = low_multiset_next (node)));                    \
    }                                                                   \
  } while (0)

#define GET_RANGE_SIZE_AND_END (  BEGPOS,
ENDPOS,
MSD,
MSD_SIZE,
RANGE_SIZE,
END   ) 
 

#define HDR (  NODE   )     ((struct rb_node_hdr *) msnode_check (NODE))
 

#define IGNORE_ARG (  X   ) 
 

#define INIT_MULTISET (  L   ) 
 

Value:

do {                                            \
    GC_ALLOC (L);                                                       \
    INITIALIZE_PROT (L);                                                \
    L->refs = 0;                                                        \
    add_ref(L); /* For DMALLOC... */                                    \
    L->node_refs = 0;                                                   \
    DOUBLELINK (first_multiset, L);                                     \
  } while (0)

#define INODE (  NODE   )     ((union msnode *) msnode_ind_check (NODE))
 

#define INTERNAL_CMP (  A,
B,
CMP_RES   ) 
 

Value:

do {                            \
    (CMP_RES) = set_svalue_cmpfun (A, B);                               \
  } while (0)

#define IVNODE (  NODE   )     ((union msnode *) msnode_indval_check (NODE))
 

#define MOVE_MSD_REF (  L,
MSD   ) 
 

Value:

do {                                    \
    sub_extra_ref (MSD);                                                \
    add_ref ((MSD) = (L)->msd);                                         \
  } while (0)

#define MOVE_MSD_REF_AND_FREE (  L,
MSD   ) 
 

Value:

do {                            \
    if (!sub_ref (MSD)) free_multiset_data (MSD);                       \
    add_ref ((MSD) = (L)->msd);                                         \
  } while (0)

#define msnode_ind_check (  X   )     ((struct msnode_ind *) (X))
 

#define msnode_indval_check (  X   )     ((struct msnode_indval *) (X))
 

#define msnode_ptr_check (  X   )     ((union msnode **) (X))
 

#define NEXT_FREE (  NODE   )     INODE (msnode_check (NODE)->i.next)
 

#define NODE_AT (  MSD,
TYPE,
POS   )     ((struct TYPE *) &(MSD)->nodes + (POS))
 

#define NODE_OFFSET (  TYPE,
POS   )     PTR_TO_INT (NODE_AT ((struct multiset_data *) NULL, TYPE, POS))
 

#define PHDR (  NODEPTR   )     ((struct rb_node_hdr **) msnode_ptr_check (NODEPTR))
 

#define RBNODE (  NODE   )     ((union msnode *) rb_node_check (NODE))
 

#define SAME_CMP_LESS (  MSD_A,
MSD_B   ) 
 

Value:

((MSD_A)->cmp_less.type == T_INT ?                                      \
   (MSD_B)->cmp_less.type == T_INT :                                    \
   ((MSD_B)->cmp_less.type != T_INT &&                                  \
    is_identical (&(MSD_A)->cmp_less, &(MSD_B)->cmp_less)))

#define SET_NEXT_FREE (  NODE,
NEXT   )     (msnode_check (NODE)->i.next = (struct msnode_ind *) msnode_check (NEXT))
 

#define SHIFT_BY_POS (  OLD,
OLDBASE,
OLDTYPE,
NEWBASE,
NEWTYPE   ) 
 

Value:

((OLD) ? NODE_AT (NEWBASE, NEWTYPE, 0) + (                              \
      (struct OLDTYPE *) (OLD) - (struct OLDTYPE *) (OLDBASE)->nodes) : 0)

#define SHIFT_HDRPTR (  HDRPTR,
FROM_MSD,
TO_MSD   )     ((struct rb_node_hdr *) SHIFT_PTR (rb_node_check (HDRPTR), FROM_MSD, TO_MSD))
 

#define SHIFT_NODEPTR (  NODEPTR,
FROM_MSD,
TO_MSD   )     ((union msnode *) SHIFT_PTR (msnode_check (NODEPTR), FROM_MSD, TO_MSD))
 

#define SHIFT_PTR (  PTR,
FROM,
TO   )     ((char *) (PTR) - (char *) (FROM) + (char *) (TO))
 

#define sp   Pike_sp
 

#define sub_extra_ref (  X   )     do {sub_ref (X);} while (0)
 

#define TEST_LESS (  MSD,
A,
B,
CMP_RES   ) 
 

Value:

do {                            \
    if (MSD->cmp_less.type == T_INT)                                    \
      INTERNAL_CMP (A, B, CMP_RES);                                     \
    else {                                                              \
      push_svalue (A);                                                  \
      push_svalue (B);                                                  \
      EXTERNAL_CMP (&MSD->cmp_less);                                    \
      CMP_RES = UNSAFE_IS_ZERO (sp - 1) ? 1 : -1;                       \
      pop_stack();                                                      \
    }                                                                   \
  } while (0)

#define UNLINK_RES_NODE (  RES_MSD,
RES_LIST,
GOT_NODE_REFS,
NODE   ) 
 

Value:

do {                                                                    \
    if (GOT_NODE_REFS) {                                                \
      ADD_TO_FREE_LIST (RES_MSD, RBNODE (NODE));                        \
      RBNODE (NODE)->i.ind.type = T_DELETED;                            \
      /* Knowledge that LOW_RB_MERGE traverses the trees backwards */   \
      /* is used here. */                                               \
      RBNODE (NODE)->i.ind.u.ptr = RES_LIST;                            \
      RBNODE (NODE)->i.prev =                                           \
        (struct msnode_ind *) low_multiset_prev (RBNODE (NODE));        \
    }                                                                   \
    else {                                                              \
      CLEAR_DELETED_ON_FREE_LIST (RES_MSD);                             \
      ADD_TO_FREE_LIST (RES_MSD, RBNODE (NODE));                        \
      RBNODE (NODE)->i.ind.type = PIKE_T_UNKNOWN;                       \
      RBNODE (NODE)->i.prev = NULL;                                     \
      RES_MSD->size--;                                                  \
    }                                                                   \
  } while (0)

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

do {                                                            \
      if (INDVAL (                                                      \
            !svalues_are_constant (&node->iv.val, 1, msd->val_types, p) || \
          )                                                             \
          !svalues_are_constant (low_use_multiset_index (node, ind),    \
                                 1, msd->ind_types, p)) {               \
        res = 0;                                                        \
        break;                                                          \
      }                                                                 \
    } while ((node = low_multiset_next (node)));

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

do {                                                            \
      if (notfirst) my_strcat (",\n");                                  \
      else notfirst = 1;                                                \
                                                                        \
      for (depth = 2; depth < indent; depth++) my_putchar (' ');        \
      low_use_multiset_index (node, ind);                               \
      describe_svalue (&ind, indent, &curr);                            \
                                                                        \
      INDVAL (                                                          \
        my_putchar (':');                                               \
        describe_svalue (&node->iv.val, indent, &curr);                 \
      );                                                                \
    } while ((node = low_multiset_next (node)));

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

do {                                                                    \
    if (INDVAL (                                                        \
          !low_is_equal (&a_node->iv.val, &b_node->iv.val, &curr) ||    \
        )                                                               \
        !low_is_equal (low_use_multiset_index (a_node, a_ind),          \
                       low_use_multiset_index (b_node, b_ind),          \
                       &curr)) {                                        \
      res = 0;                                                          \
      break;                                                            \
    }                                                                   \
    a_node = low_multiset_next (a_node);                                \
    b_node = low_multiset_next (b_node);                                \
  } while (a_node);

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

IND (val_types = BIT_INT);                                              \
    do {                                                                \
      low_use_multiset_index (RBNODE (node), ind);                      \
      if (IS_DESTRUCTED (&ind)) {                                       \
        midflight_remove_node_fast (l, &rbstack, 1);                    \
        msd = l->msd;                                                   \
        node = RBSTACK_PEEK (rbstack);                                  \
      }                                                                 \
      else {                                                            \
        ind_types |= 1 << ind.type;                                     \
        INDVAL (                                                        \
          if (IS_DESTRUCTED (&RBNODE (node)->iv.val)) {                 \
            check_destructed (&RBNODE (node)->iv.val);                  \
            val_types |= BIT_INT;                                       \
          }                                                             \
          else val_types |= 1 << RBNODE (node)->iv.val.type;            \
        );                                                              \
        LOW_RB_TRACK_NEXT (rbstack, node);                              \
      }                                                                 \
    } while (node);

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

IND (val_types = BIT_INT);                                              \
    do {                                                                \
      ind_types |= 1 << (node->i.ind.type & ~MULTISET_FLAG_MASK);       \
      INDVAL (val_types |= 1 << node->iv.val.type);                     \
    } while ((node = low_multiset_next (node)));

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

struct OTHERTYPE *onode;                                                \
    struct TYPE *nnode;                                                 \
    while (pos-- > 0) {                                                 \
      onode = NODE_AT (old, OTHERTYPE, pos);                            \
      nnode = NODE_AT (new, TYPE, pos);                                 \
      /* Like COPY_NODE_PTRS, but shift by node position. */            \
      nnode->prev = SHIFT_BY_POS (onode->prev, old, OTHERTYPE, new, TYPE); \
      nnode->next = SHIFT_BY_POS (onode->next, old, OTHERTYPE, new, TYPE); \
      switch (onode->ind.type) {                                        \
        case T_DELETED:                                                 \
          /* Like COPY_DELETED_PTRS_EXTRA, but shift by node position. */ \
          nnode->ind.u.ptr =                                            \
            SHIFT_BY_POS (onode->ind.u.ptr, old, OTHERTYPE, new, TYPE); \
          /* FALL THROUGH */                                            \
        case PIKE_T_UNKNOWN:                                            \
          nnode->ind.type = onode->ind.type;                            \
          break;                                                        \
        default:                                                        \
          COPY_NODE_IND (onode, nnode, TYPE);                           \
          INDVAL (                                                      \
            nnode->val.type = T_INT;                                    \
            nnode->val.u.integer = 1;                                   \
          );                                                            \
      }                                                                 \
    }                                                                   \
    new->free_list = (union msnode *)                                   \
      SHIFT_BY_POS (old->free_list, old, OTHERTYPE, new, TYPE);         \
    new->root = (union msnode *)                                        \
      SHIFT_BY_POS (old->root, old, OTHERTYPE, new, TYPE);

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

struct TYPE *node;                                              \
      while (1) {                                                       \
        node = NODE_AT (new, TYPE, pos);                                \
        node->ind = oldnode->i.ind;                                     \
        INDVAL (node->val = oldnode->iv.val);                           \
        if (!(oldnode = low_multiset_next (oldnode))) break;            \
        node->next = NODE_AT (new, TYPE, ++pos);                        \
      }                                                                 \
      NODE_AT (new, TYPE, pos)->next = NULL;

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

struct TYPE *oldnodes = (struct TYPE *) old->nodes;                     \
    struct TYPE *newnodes = (struct TYPE *) new->nodes;                 \
    struct TYPE *onode, *nnode;                                         \
    while (pos-- > 0) {                                                 \
      onode = NODE_AT (old, TYPE, pos);                                 \
      nnode = NODE_AT (new, TYPE, pos);                                 \
      COPY_NODE_PTRS (onode, old, nnode, new, TYPE);                    \
      switch (onode->ind.type) {                                        \
        case T_DELETED:                                                 \
          COPY_DELETED_PTRS_EXTRA (onode, old, nnode, new);             \
          /* FALL THROUGH */                                            \
          case PIKE_T_UNKNOWN:                                          \
          nnode->ind.type = onode->ind.type;                            \
          break;                                                        \
        default:                                                        \
          nnode->ind = onode->ind;                                      \
          INDVAL (nnode->val = onode->val);                             \
      }                                                                 \
    }

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

struct TYPE *onode, *nnode;                                             \
  while (pos-- > 0) {                                                   \
    onode = NODE_AT (old, TYPE, pos);                                   \
    nnode = NODE_AT (new, TYPE, pos);                                   \
    COPY_NODE_PTRS (onode, old, nnode, new, TYPE);                      \
    switch (onode->ind.type) {                                          \
      case T_DELETED:                                                   \
        COPY_DELETED_PTRS_EXTRA (onode, old, nnode, new);               \
        /* FALL THROUGH */                                              \
      case PIKE_T_UNKNOWN:                                              \
        nnode->ind.type = onode->ind.type;                              \
        break;                                                          \
      default:                                                          \
        COPY_NODE_IND (onode, nnode, TYPE);                             \
        INDVAL (assign_svalue_no_free (&nnode->val, &onode->val));      \
    }                                                                   \
  }

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

msd->free_list = (union msnode *) NODE_AT (msd, TYPE, first_free);      \
    for (; first_free < alloclast; first_free++) {                      \
      SET_NEXT_FREE ((union msnode *) NODE_AT (msd, TYPE, first_free),  \
                     (union msnode *) NODE_AT (msd, TYPE, first_free + 1)); \
      /* By setting prev to NULL we avoid shifting around garbage in */ \
      /* COPY_NODE_PTRS. */                                             \
      NODE_AT (msd, TYPE, first_free)->prev = NULL;                     \
      NODE_AT (msd, TYPE, first_free)->ind.type = PIKE_T_UNKNOWN;       \
    }                                                                   \
    SET_NEXT_FREE ((union msnode *) NODE_AT (msd, TYPE, first_free),    \
                   orig_free_list);                                     \
    NODE_AT (msd, TYPE, first_free)->prev = NULL;                       \
    NODE_AT (msd, TYPE, first_free)->ind.type = PIKE_T_UNKNOWN;

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

do {                                                            \
      next = low_multiset_next (node);                                  \
      node->i.ind.type &= ~MULTISET_FLAG_MASK;                          \
      free_svalue (&node->i.ind);                                       \
      INDVAL (free_svalue (&node->iv.val));                             \
    } while ((node = next));

#define WITH_NODES_BLOCK (  TYPE,
OTHERTYPE,
IND,
INDVAL   ) 
 

Value:

if ((node = build->node)) {                                             \
    node->i.ind.type &= ~MULTISET_FLAG_MASK;                            \
    free_svalue (&node->i.ind);                                         \
    INDVAL (free_svalue (&node->iv.val));                               \
  }                                                                     \
  if ((node = build->list))                                             \
    do {                                                                \
      next = low_multiset_next (node);                                  \
      node->i.ind.type &= ~MULTISET_FLAG_MASK;                          \
      free_svalue (&node->i.ind);                                       \
      INDVAL (free_svalue (&node->iv.val));                             \
    } while ((node = next));

Enumeration Type Documentation

enum find_types
 

Enumeration values:
FIND_EQUAL 
FIND_NOEQUAL 
FIND_LESS 
FIND_GREATER 
FIND_NOROOT 
FIND_DESTRUCTED 

Function Documentation

PMOD_EXPORT struct multiset* add_multisets (  struct svalue *  vect,
int  count
) 
 

PMOD_EXPORT void check_multiset_for_destruct (  struct multiset *  l  ) 
 

PMOD_EXPORT struct multiset* copy_multiset (  struct multiset *  l  ) 
 

struct multiset* copy_multiset_recursively (  struct multiset *  l,
struct mapping *  p
) 
 

void describe_multiset (  struct multiset *  l,
struct processing *  p,
int  indent
) 
 

PMOD_EXPORT void do_free_multiset (  struct multiset *  l  ) 
 

PMOD_EXPORT void do_sub_msnode_ref (  struct multiset *  l  ) 
 

void exit_multiset (  void   ) 
 

PMOD_EXPORT void f_aggregate_multiset (  INT32  args  ) 
 

void free_multiset_data (  struct multiset_data *  msd  ) 
 

void gc_check_all_multisets (  void   ) 
 

void gc_cycle_check_all_multisets (  void   ) 
 

size_t gc_free_all_unreferenced_multisets (  void   ) 
 

void gc_mark_all_multisets (  void   ) 
 

void gc_mark_multiset_as_referenced (  struct multiset *  l  ) 
 

unsigned gc_touch_all_multisets (  void   ) 
 

void gc_zap_ext_weak_refs_in_multisets (  void   ) 
 

void init_multiset (  void   ) 
 

union msnode* low_multiset_find_eq (  struct multiset *  l,
struct svalue *  key
) 
 

node* make_node_from_multiset (  struct multiset *  l  ) 
 

PMOD_EXPORT struct multiset* merge_multisets (  struct multiset *  a,
struct multiset *  b,
int  operation
) 
 

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 int msnode_is_deleted (  struct multiset *  l,
ptrdiff_t  nodepos
) 
 

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  nodepos,
struct svalue *  ind,
struct svalue *  val
) 
 

PMOD_EXPORT void multiset_clear_node_refs (  struct multiset *  l  ) 
 

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

PMOD_EXPORT int multiset_equal_p (  struct multiset *  a,
struct multiset *  b,
struct processing *  p
) 
 

PMOD_EXPORT ptrdiff_t multiset_find_eq (  struct multiset *  l,
struct svalue *  key
) 
 

PMOD_EXPORT ptrdiff_t multiset_find_ge (  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_lt (  struct multiset *  l,
struct svalue *  key
) 
 

PMOD_EXPORT ptrdiff_t multiset_first (  struct multiset *  l  ) 
 

void multiset_fix_type_field (  struct multiset *  l  ) 
 

PMOD_EXPORT ptrdiff_t multiset_get_nth (  struct multiset *  l,
size_t  n
) 
 

struct array* multiset_indices (  struct multiset *  l  ) 
 

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
) 
 

int multiset_is_constant (  struct multiset *  l,
struct processing *  p
) 
 

PMOD_EXPORT ptrdiff_t multiset_last (  struct multiset *  l  ) 
 

PMOD_EXPORT struct svalue* multiset_lookup (  struct multiset *  l,
struct svalue *  key
) 
 

PMOD_EXPORT int multiset_member (  struct multiset *  l,
struct svalue *  key
) 
 

PMOD_EXPORT ptrdiff_t multiset_next (  struct multiset *  l,
ptrdiff_t  nodepos
) 
 

PMOD_EXPORT ptrdiff_t multiset_prev (  struct multiset *  l,
ptrdiff_t  nodepos
) 
 

struct array* multiset_range_indices (  struct multiset *  l,
ptrdiff_t  begpos,
ptrdiff_t  endpos
) 
 

struct array* multiset_range_values (  struct multiset *  l,
ptrdiff_t  begpos,
ptrdiff_t  endpos
) 
 

PMOD_EXPORT void multiset_set_cmp_less (  struct multiset *  l,
struct svalue *  cmp_less
) 
 

PMOD_EXPORT void multiset_set_flags (  struct multiset *  l,
int  flags
) 
 

PMOD_EXPORT INT32 multiset_sizeof (  struct multiset *  l  ) 
 

struct array* multiset_values (  struct multiset *  l  ) 
 

PMOD_EXPORT struct multiset* real_allocate_multiset (  int  allocsize,
int  flags,
struct svalue *  cmp_less
) 
 

void real_gc_cycle_check_multiset (  struct multiset *  l,
int  weak
) 
 

void simple_describe_multiset (  struct multiset *  l  ) 
 

Variable Documentation

struct multiset* first_multiset = NULL
 

struct multiset* gc_internal_multiset = NULL
 

struct svalue svalue_int_one
 

Initial value:

 {T_INT, NUMBER_NUMBER,



                               }

Generated on Fri Jul 22 23:44:29 2005 for Pike by  doxygen 1.3.9.1