multiset.c

/*
|| 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: multiset.c,v 1.87 2004/06/13 14:24:31 mast Exp $
*/

#include "global.h"

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

#include "builtin_functions.h"
#include "gc.h"
#include "interpret.h"
#include "multiset.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"

RCSID("$Id: multiset.c,v 1.87 2004/06/13 14:24:31 mast Exp $");

/* FIXME: Optimize finds and searches on type fields? (But not when
 * objects are involved!) Well.. Although cheap I suspect it pays off
 * so extremely seldom that it isn't worth it. /mast */

#include <assert.h>

#define sp Pike_sp

/* The following defines the allocation policy. It's almost the same
 * as for mappings. */
#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)

#if defined (PIKE_DEBUG) || defined (TEST_MULTISET)
static void debug_dump_ind_data (struct msnode_ind *node,
				 struct multiset_data *msd);
static void debug_dump_indval_data (struct msnode_indval *node,
				    struct multiset_data *msd);
DECLSPEC(noreturn) static void debug_multiset_fatal (
  struct multiset *l, const char *fmt, ...) ATTRIBUTE((noreturn, format (printf, 2, 3)));
#define multiset_fatal (fprintf (stderr, "%s:%d: Fatal in multiset: ", \
				 __FILE__, __LINE__), debug_multiset_fatal)
#endif

#ifdef PIKE_DEBUG

/* To get good type checking. */
static INLINE union msnode **msnode_ptr_check (union msnode **x)
  {return x;}
static INLINE struct msnode_ind *msnode_ind_check (struct msnode_ind *x)
  {return x;}
static INLINE struct msnode_indval *msnode_indval_check (struct msnode_indval *x)
  {return x;}

#define sub_extra_ref(X) do {						\
    if (!sub_ref (X)) Pike_fatal ("Got too few refs to " #X ".\n");	\
  } while (0)

PMOD_EXPORT const char msg_no_multiset_flag_marker[] =
  "Multiset index lacks MULTISET_FLAG_MARKER. It might be externally clobbered.\n";
PMOD_EXPORT const char msg_multiset_no_node_refs[] =