#include <stdio.h>
#include "config.h"
#include "lint.h"
#include "interpret.h"
#include "lang.h"
#include "instrs.h"
#include "object.h"
#include "wiz_list.h"
#include "regexp.h"
#include "stralloc.h"
#include "smalloc.h"

#define MIN_P_INT ( -1 << (sizeof(p_int) * 8 - 1) )
#define MIN_PH_INT ( -1 << (sizeof(ph_int) * 8 - 1) )

#define EMPTY_MAPPING_THRESHOLD 2000

extern struct svalue const0;
extern int extra_jobs_to_do;
extern struct wiz_list default_wizlist_entry;
extern void push_referenced_mapping PROT((struct mapping *));

extern void m_indices_filter PROT((struct svalue *, struct svalue *, char *));

struct hash_mapping dirty_mapping_head_hash;
struct mapping dirty_mapping_head = {
    /* ref        */ 1,
    /* hash       */ &dirty_mapping_head_hash,
    /* condensed  */ 0,
    /* user       */ 0,
    /* num_values */ 0
};

mp_int num_mappings = 0;

struct mapping *last_dirty_mapping = &dirty_mapping_head;
mp_int num_dirty_mappings = 0;

static mp_int empty_mapping_load = 2*-EMPTY_MAPPING_THRESHOLD;
static mp_int empty_mapping_base = 0;

struct mapping *stale_mappings; /* for garbage_collection */
extern struct lambda *stale_misc_closures;

struct mapping *allocate_mapping(size, num_values)
mp_int size, num_values;
{
    struct hash_mapping *hm = 0;
    struct condensed_mapping *cm;
    struct mapping *m;

    m = (struct mapping *)xalloc(sizeof *m);
    if (size) {
	struct map_chain **mcp;

	size |= size >> 1;
	size |= size >> 2;
	size |= size >> 4;
	if (size & ~0xff) {
	    size |= size >> 8;
	    size |= size >> 16;
	}
	size >>= 1; /* This is now actually the mask, which is one lower */
	hm = (struct hash_mapping *)
	  xalloc(sizeof *hm + sizeof *mcp * size);
	hm->mask = size;
	hm->used = hm->condensed_deleted = hm->ref = 0;
	last_dirty_mapping->hash->next_dirty = m;
	last_dirty_mapping = m;
#ifdef DEBUG
	hm->next_dirty = 0;
	hm->deleted = 0;
#endif
	num_dirty_mappings++;
	extra_jobs_to_do = 1;
	mcp = hm->chains;
	do *mcp++ = 0; while (--size >= 0);
    }
    cm = (struct condensed_mapping *)xalloc(sizeof *cm);
    cm->string_size = 0;
    cm->misc_size = 0;
    m->hash = hm;
    m->condensed = cm;
    m->num_values = num_values;
    m->ref = 1;
    (m->user =
      current_object->user ? current_object->user : &default_wizlist_entry
    )->mapping_total +=
      sizeof *m + sizeof(char*) + sizeof *cm + sizeof(char*);
    num_mappings++;
    return m;
}

static void remove_empty_mappings();

void free_mapping(m)
struct mapping *m;
{
    struct hash_mapping *hm;
    struct condensed_mapping *cm;
    char **str;
    struct svalue *svp;
    int i, j, num_values;

#ifdef DEBUG
    if (!m->user)
	fatal("No wizlist pointer for mapping");
#endif
    if (--m->ref)
	return;
    num_mappings--;
    num_values = m->num_values;
    cm = m->condensed;
    str = CM_STRING(cm);
    i = cm->string_size;
    while ( (i -= sizeof *str) >= 0) {
	if ( !((p_int)*str & 1) )
	    free_string(*str);
	str++;
    }
    svp = (struct svalue *)str;
    i = cm->string_size * num_values;
    while ( (i -= sizeof *str) >= 0) {
	free_svalue(svp++);
    }
    svp = CM_MISC(cm);
    i = cm->misc_size * (num_values + 1);
    while ( (i -= sizeof *svp) >= 0)
	free_svalue(--svp);
    m->user->mapping_total -=
      sizeof *m + 4 + sizeof *cm + 4 +
        (cm->string_size * (sizeof *svp/sizeof *str)+ cm->misc_size) *
          (1 + num_values) -
	cm->string_size * (sizeof *svp/sizeof *str - 1);
    xfree( (char *)svp); /* free the condensed mapping part */
    if (hm = m->hash) {
	struct map_chain **mcp, *mc, *next;
	struct mapping *next_dirty;

#ifdef DEBUG
	if (hm->ref)
	    fatal("Ref count in freed hash mapping: %d\n", hm->ref);
#endif
	mcp = hm->chains;
	i = hm->mask + 1;
	do {
	    for (next = *mcp++; mc = next; ) {
		svp = &mc->key;
		j = num_values;
		do {
		    free_svalue(svp++);
		} while (--j >= 0);
		next = mc->next;
		xfree( (char *)mc );
	    }
	} while (--i);
	next_dirty = hm->next_dirty;
	xfree( (char *)hm );
	hm = (struct hash_mapping *)xalloc(sizeof *hm);
	hm->mask = hm->used = hm->condensed_deleted = hm->ref = 0;
	hm->chains[0] = 0;
	hm->next_dirty = next_dirty;
	m->condensed = 0;
	m->hash = hm;
	if ( (empty_mapping_load += 2) > 0)
	    remove_empty_mappings();
	return;
    }
    xfree( (char *)m );
}

#ifdef DEBUG
void check_dirty_mapping_list() {
    int i;                                                           
    struct mapping *m;                                               
                                                                     
    for (m = &dirty_mapping_head, i = num_dirty_mappings; --i >=0; ) {
	m = m->hash->next_dirty;
    }
    if (m != last_dirty_mapping)
	fatal("last_dirty_mapping not at end of dirty list\n");
    if (m->hash->next_dirty)
	fatal("dirty mapping list not terminated\n");
}
#endif

static void remove_empty_mappings() {
    struct mapping **mp, *m, *last;
    struct hash_mapping *hm;

    empty_mapping_load += empty_mapping_base - num_dirty_mappings;
    empty_mapping_base = num_dirty_mappings;
    if (empty_mapping_load <= -EMPTY_MAPPING_THRESHOLD)
	return;
#ifdef DEBUG
    /* We have stored all these superflous zeroes.
     * Now check that there is one in the proper place.
     */
    if (last_dirty_mapping->hash->next_dirty != 0)
	fatal("Dirty mapping list not terminated\n");
#endif
    last_dirty_mapping->hash->next_dirty = 0;
    last = &dirty_mapping_head;
    mp = &dirty_mapping_head_hash.next_dirty;
    m = *mp;
    do {
	hm = m->hash;
	if (!m->condensed) {
	    xfree((char *)m);
	    *mp = m = hm->next_dirty;
	    xfree( (char *)hm );
	    continue;
	}
	last = m;
	mp = &hm->next_dirty;
	m = *mp;
    } while (m);
    last_dirty_mapping = last;
    num_dirty_mappings -=
      empty_mapping_load + 2*EMPTY_MAPPING_THRESHOLD + empty_mapping_base >> 1;
    empty_mapping_load = 2*-EMPTY_MAPPING_THRESHOLD - empty_mapping_base;
#ifdef DEBUG
    check_dirty_mapping_list();
#endif
}

void free_protector_mapping(m)
    struct mapping *m;
{
    struct hash_mapping *hm;

    /* This is port of a T_PROTECTOR_MAPPING svalue, which is only
     * created for mappings with a hashed part, and has the ref of the
     * hashed part incremented at creation.
     */
#ifdef DEBUG
    if (!m->hash || m->hash->ref <= 0) {
	/* This shouldn't happen */
	printf("free_protector_mapping() : no hash %s\n",
		m->hash ? "reference" : "part");
#ifdef TRACE_CODE
	{
	    extern int last_instructions PROT((int, int));

	    last_instructions(TOTAL_TRACE_LENGTH, 1);
	}
#endif
	dump_trace(0);
	printf("free_protector_mapping() : no hash %s\n",
		m->hash ? "reference" : "part");
	free_mapping(m);
    }
#endif /* DEBUG */
    if (!--(hm = m->hash)->ref) {
	int num_values = m->num_values;
	struct map_chain *mc, *next;
	struct svalue *svp2;

	for (mc = hm->deleted; mc; mc = next) {
	    mp_int j;

	    svp2 = &mc->key;
	    j = num_values;
	    do {
		free_svalue(svp2++);
	    } while (--j >= 0);
	    next = mc->next;
	    xfree( (char *)mc );
	}
    }
    if (--m->ref)
	return;
    m->ref++;
    free_mapping(m);
}

struct svalue *get_map_lvalue(m, map_index, need_lvalue)
    struct mapping *m;
    struct svalue *map_index;
    int need_lvalue;
{
    mp_int size;
    struct condensed_mapping *cm = m->condensed;
    struct hash_mapping *hm;
    int num_values = m->num_values;
    struct svalue *svp;

    switch (map_index->type) {
      case T_STRING:
      {
	char *str;
	char *key; /* means a char **, but pointer arithmetic wants char * */
	char *keystart, *keyend;

	if (map_index->x.string_type != STRING_SHARED)
	{
	    char *tmpstr;

	    tmpstr = make_shared_string(map_index->u.string);
	    if (map_index->x.string_type == STRING_MALLOC)
		xfree(map_index->u.string);
	    map_index->x.string_type = STRING_SHARED;
	    map_index->u.string = tmpstr;
	}
	str = map_index->u.string;
	keystart = (char *)CM_STRING(cm);
	size = cm->string_size;
	if (size) {
	    p_int offset;

	    keyend = keystart + size;
	    key = keystart;
	    offset = size-1;
	    offset |= offset >> 1;
	    offset |= offset >> 2;
	    offset |= offset >> 4;
	    if (offset & ~0xff) {
		offset |= offset >> 8;
		offset |= offset >> 16;
	    }
	    if ( (offset = offset+1 >> 1) >= sizeof str) 
		do {
		    if (key + offset >= keyend) continue;
		    if ( str >= *(char **)(key+offset) ) key += offset;
		} while ( (offset >>= 1) >= sizeof str);
	    if ( str == *(char **)key ) {
		/* found it */
#ifndef FAST_MULTIPLICATION
		if (num_values == 1) /* speed up this case */
		    return (struct svalue *)
		      (keyend + (key - keystart ) *
		        (sizeof(struct svalue)/sizeof str) );
		else
#endif/*FAST_MULTIPLICATION*/
		    return (struct svalue *)
		      (keyend + (key - keystart ) *
		        ( num_values * (sizeof(struct svalue)/sizeof str) ));
	    }
	    /* not found */
	}
	/* don't search if there are no string keys */
	break;
      }
      default:
	map_index->x.generic = map_index->u.number << 1;
      case T_FLOAT:
      case T_CLOSURE:
      case T_SYMBOL:
      case T_QUOTED_ARRAY:
      {
	/* map_index->type != T_STRING */

	p_int offset;
	char *key; /* means a char **, but pointer arithmetic wants char * */
	char *keystart, *keyend;
	ph_int index_type = map_index->type;
	ph_int index_x = map_index->x.generic;
	p_int index_u = map_index->u.number, u_d;

	keyend = (char *)CM_MISC(cm);
	size = cm->misc_size;
	keystart = keyend - size;
	offset = size | size >> 1;
	offset |= offset >> 2;
	offset |= offset >> 4;
	if (offset & ~0xff) {
	    offset |= offset >> 8;
	    offset |= offset >> 16;
	}
	offset = offset+1 >> 1;
	key = keyend - offset;
	while ( (offset >>= 1) >= (sizeof svp)/2) {
	    if ( !(u_d = (((struct svalue *)key)->u.number >> 1) -
			 (index_u >> 1)) ) {
	      if ( !(u_d = ((struct svalue *)key)->x.generic - index_x) )
		if ( !(u_d = ((struct svalue *)key)->type - index_type) ) {
		    /* found */
#ifndef FAST_MULTIPLICATION
		    if (num_values == 1) /* speed up this case */
			return (struct svalue *) (key - size);
		    else
#endif/*FAST_MULTIPLICATION*/
			return (struct svalue *)
			  (keystart - ( num_values * (keyend - key) ) );
		}
	    }
	    if (u_d > 0) {
		key += offset;
	    } else {
		/* u_d < 0 */
		key -= offset;
		while (key < keystart) {
		    if ( (offset >>= 1) < (sizeof svp) )
			break;
		    key += offset;
		}
	    }
	}
	/* not found */
	break;
      }
    }
    if ( !(hm = m->hash) ) {
	struct map_chain *mc;
	mp_int i;

	if (!need_lvalue)
	    return &const0;
	hm = (struct hash_mapping *)xalloc(sizeof *hm);
	hm->mask = hm->condensed_deleted = 0;
	hm->ref = 0;
	hm->used = 1;
	last_dirty_mapping->hash->next_dirty = m;
	last_dirty_mapping = m;
#ifdef DEBUG
	hm->next_dirty = 0;
	hm->deleted = 0;
#endif
	num_dirty_mappings++;
	extra_jobs_to_do = 1;
	m->hash = hm;
	mc = (struct map_chain *)xalloc(MAP_CHAIN_SIZE(num_values));
	mc->next = 0;
	hm->chains[0] = mc;
	assign_svalue_no_free(&mc->key, map_index);
	svp = mc->data;
	for (i = num_values; --i >= 0; svp++) {
	    svp->type = T_NUMBER;
	    svp->u.number = 0;
	}
	return mc->data;
    } else {
	struct map_chain *mc;
	p_int index_type = *SVALUE_FULLTYPE(map_index);
	p_int index_u = map_index->u.number;
	mp_int i;

	i = index_u ^ index_type;
	i = i ^ i >> 16;
	i = i ^ i >> 8;
	i &= hm->mask;
	for (mc = hm->chains[i];mc; mc = mc->next){
	    if (mc->key.u.number != index_u ||
		*SVALUE_FULLTYPE(&mc->key) != index_type)
		continue;
	    return mc->data;
	}
	if (!need_lvalue)
	    return &const0;
	if (hm->used & ~hm->mask<<1) {
	    /* Avoid average map_chains lengths above 2 by reallocating the
	     * array of pointers
	     */
	    struct hash_mapping *hm2;
	    mp_int mask, j;
	    struct map_chain **mcp, **mcp2, *next;

	    hm2 = hm;
	    size = (hm->mask << 1) + 2;
	    mask = size - 1;
	    hm = (struct hash_mapping *)
	      xalloc(sizeof *hm - sizeof *mcp + sizeof *mcp * size);
	    *hm = *hm2;
	    hm->mask = mask;
	    mcp = hm->chains;
	    do *mcp++ = 0; while (--size);
	    mcp = hm->chains;
	    mcp2 = hm2->chains;
	    for (j = hm2->mask + 1; --j >= 0; ) {
		for (mc = *mcp2++; mc; mc = next) {
		    next = mc->next;
		    i = mc->key.u.number ^ *SVALUE_FULLTYPE(&mc->key);
		    i = i ^ i >> 16;
		    i = i ^ i >> 8;
		    i &= mask;
		    mc->next = mcp[i];
		    mcp[i] = mc;
		}
	    }
	    m->hash = hm;
	    xfree((char *)hm2);
	    i = map_index->u.number ^ *SVALUE_FULLTYPE(map_index);
	    i = i ^ i >> 16;
	    i = i ^ i >> 8;
	    i &= mask;
	}
	hm->used++;
	mc = (struct map_chain *)xalloc(MAP_CHAIN_SIZE(num_values));
	mc->next = hm->chains[i];
	hm->chains[i] = mc;
	assign_svalue_no_free(&mc->key, map_index);
	svp = mc->data;
	for (i = num_values; --i >= 0; svp++) {
	    svp->type = T_NUMBER;
	    svp->u.number = 0;
	}
	return mc->data;
    }
}

void check_map_for_destr(m)
    struct mapping *m;
{
    struct condensed_mapping *cm;
    struct hash_mapping *hm;
    struct svalue *svp;
    mp_int i, j;
    int num_values;

    num_values = m->num_values;
    cm = m->condensed;
    for (svp = CM_MISC(cm),i = cm->misc_size; (i -= sizeof *svp) >= 0; ) {
	--svp;
	if (svp->type == T_OBJECT && svp->u.ob->flags & O_DESTRUCTED) {
	    struct svalue *data;
	    extern void free_object_svalue PROT((struct svalue *));

	    if (j = num_values) {
		data = (struct svalue *)((char *)svp - i -
		  num_values * ((char *)CM_MISC(cm) - (char *)svp));
		do {
		    free_svalue(data);
		    data->type = T_NUMBER;
		    data->u.number = 0;
		    data++;
		} while (--j);
	    }
	    while ( &svp[1] < CM_MISC(cm) &&
	      svp[1].u.number == svp[0].u.number &&
	      svp[1].x.generic == svp[0].x.generic)
	    {
		*SVALUE_FULLTYPE(&svp[0]) =  *SVALUE_FULLTYPE(&svp[1]);
		svp++;
		i += sizeof *svp;
		for (j = num_values; --j >= 0; data++)
		    data[-num_values] = data[0];
		    data->type = T_NUMBER;
		    data->u.number = 0;
	    }
	    free_object_svalue(svp);
	    svp[0].type = T_INVALID;
	    if ( !(hm = m->hash) ) {
		hm = (struct hash_mapping *)xalloc(sizeof *hm);
		m->hash = hm;
		hm->mask = hm->used = hm->condensed_deleted = hm->ref = 0;
		hm->chains[0] = 0;
		last_dirty_mapping->hash->next_dirty = m;
		last_dirty_mapping = m;
#ifdef DEBUG
		hm->next_dirty = 0;
		hm->deleted = 0;
#endif
		num_dirty_mappings++;
		extra_jobs_to_do = 1;
	    }
	    hm->condensed_deleted++;
	}
    }
    for (i = cm->misc_size * num_values; (i -= sizeof *svp) >= 0; ) {
	svp--;
	if (svp->type == T_OBJECT && svp->u.ob->flags & O_DESTRUCTED) {
	    assign_svalue(svp, &const0);
	}
    }
    svp = (struct svalue *)( (char *)CM_STRING(cm) + cm->string_size );
    for (i = cm->string_size * num_values; (i -= sizeof(char *)) >= 0; svp++) {
	if (svp->type == T_OBJECT && svp->u.ob->flags & O_DESTRUCTED) {
	    assign_svalue(svp, &const0);
	}
    }
    if (hm = m->hash) {
	struct map_chain **mcp, **mcp2, *mc;

	for (mcp = hm->chains, i = hm->mask + 1; --i >= 0;) {
	    for(mcp2 = mcp++; mc = *mcp2; ) {
		if (mc->key.type == T_OBJECT &&
		  mc->key.u.ob->flags & O_DESTRUCTED)
		{
		    svp = &mc->key;
		    *mcp2 = mc->next;

		    if (hm->ref) {
			mc->next = hm->deleted;
			hm->deleted = mc;
		    } else {
			j = num_values;
			do {
			    free_svalue(svp++);
			} while (--j >= 0);
			xfree( (char *)mc );
		    }
		    hm->used--;
		    continue;
		}
		for (svp = mc->data, j = num_values; --j >= 0; ) {
		    if (svp->type == T_OBJECT &&
		      svp->u.ob->flags & O_DESTRUCTED)
		    {
			assign_svalue(svp, &const0);
		    }
		}
		mcp2 = &mc->next;
	    }
	}
    }
}

void remove_mapping(m, map_index)
    struct mapping *m;
    struct svalue *map_index;
{
    mp_int size;
    struct condensed_mapping *cm = m->condensed;
    struct hash_mapping *hm;
    int num_values = m->num_values;
    struct svalue *svp;

    switch (map_index->type) {
      case T_STRING:
      {
	char *str;
	char *key; /* means a char **, but pointer arithmetic wants char * */
	char *keystart, *keyend;

	if (map_index->x.string_type != STRING_SHARED)
	{
	    char *tmpstr;

	    tmpstr = findstring(map_index->u.string);
	    if (!tmpstr) {
		return;
	    }
	    if (map_index->x.string_type == STRING_MALLOC)
		xfree(map_index->u.string);
	    map_index->x.string_type = STRING_SHARED;
	    map_index->u.string = tmpstr;
	    increment_string_ref(tmpstr);
	}
	str = map_index->u.string;
	keystart = (char *)CM_STRING(cm);
	size = cm->string_size;
	if (size) {
	    p_int offset;

	    keyend = keystart + size;
	    key = keystart;
	    offset = size-1;
	    offset |= offset >> 1;
	    offset |= offset >> 2;
	    offset |= offset >> 4;
	    if (offset & ~0xff) {
		offset |= offset >> 8;
		offset |= offset >> 16;
	    }
	    if ( (offset = offset+1 >> 1) >= sizeof str) 
		do {
		    if (key + offset >= keyend) continue;
		    if ( str >= *(char **)(key+offset) ) key += offset;
		} while ( (offset >>= 1) >= sizeof str);
	    if ( str == *(char **)key ) {
		/* found it */

		int i;

		free_string(str);
		(*(char **)key)++;
		svp = (struct svalue *)
		  (keyend + (key - keystart ) *
		    ( num_values * (sizeof(struct svalue)/sizeof str) ));
		for (i = num_values; --i >= 0 ;svp++) {
		    free_svalue(svp);
		    svp->type = T_NUMBER;
		    svp->u.number = 0;
		}
		if ( !(hm = m->hash) ) {
		    hm = (struct hash_mapping *)xalloc(sizeof *hm);
		    m->hash = hm;
		    hm->mask = hm->used = hm->condensed_deleted = hm->ref = 0;
		    hm->chains[0] = 0;
		    last_dirty_mapping->hash->next_dirty = m;
		    last_dirty_mapping = m;
#ifdef DEBUG
		    hm->next_dirty = 0;
		    hm->deleted = 0;
#endif
		    num_dirty_mappings++;
		    extra_jobs_to_do = 1;
		}
		hm->condensed_deleted++;
		return;
	    }
	    /* not found */
	}
	/* don't search if there are no string keys */
	break;
      }
      default:
	map_index->x.generic = map_index->u.number << 1;
      case T_FLOAT:
      case T_CLOSURE:
      case T_SYMBOL:
      case T_QUOTED_ARRAY:
      {
	/* map_index->type != T_STRING */

	p_int offset;
	char *key; /* means a char **, but pointer arithmetic wants char * */
	char *keystart, *keyend;
	ph_int index_type = map_index->type;
	ph_int index_x = map_index->x.generic;
	p_int index_u = map_index->u.number, u_d;

	keyend = (char *)CM_MISC(cm);
	size = cm->misc_size;
	keystart = keyend - size;
	offset = size | size >> 1;
	offset |= offset >> 2;
	offset |= offset >> 4;
	if (offset & ~0xff) {
	    offset |= offset >> 8;
	    offset |= offset >> 16;
	}
	offset = offset+1 >> 1;
	key = keyend - offset;
	while ( (offset >>= 1) >= (sizeof svp)/2) {
	    if ( !(u_d = (((struct svalue *)key)->u.number >> 1) -
			 (index_u >> 1)) ) {
	      if ( !(u_d = ((struct svalue *)key)->x.generic - index_x) )
		if ( !(u_d = ((struct svalue *)key)->type - index_type) ) {
		    /* found */

		    int i;

		    free_svalue( (struct svalue *)key );
		    svp = (struct svalue *)
		      (keystart - ( num_values * (keyend - key) ) );
		    for (i = num_values; --i >= 0 ;svp++) {
			free_svalue(svp);
			svp->type = T_NUMBER;
			svp->u.number = 0;
		    }

		    /* it's harmless to read misc/string_size as an svalue */
		    while ( ((struct svalue *)key+1)->u.number == index_u &&
			    ((struct svalue *)key+1)->x.generic == index_x &&
			    key + sizeof(struct svalue) < keyend)
		    {
			struct svalue *svp2;

			*((struct svalue *)key) = *((struct svalue *)key+1);
			key += sizeof(struct svalue);
			svp2 = svp - num_values;
			for (i = num_values; --i >= 0 ;svp++, svp2++) {
			    *svp2 = *svp;
			    svp->type = T_NUMBER;
			    svp->u.number = 0;
			}
		    }
		    ((struct svalue *)key)->type = T_INVALID;
		    if ( !(hm = m->hash) ) {
		        hm = (struct hash_mapping *)xalloc(sizeof *hm);
		        m->hash = hm;
		        hm->mask = hm->used = hm->condensed_deleted = 0;
		        hm->chains[0] = 0;
			last_dirty_mapping->hash->next_dirty = m;
			last_dirty_mapping = m;
#ifdef DEBUG
			hm->next_dirty = 0;
			hm->deleted = 0;
#endif
			hm->ref = 0;
			num_dirty_mappings++;
			extra_jobs_to_do = 1;
		    }
		    hm->condensed_deleted++;
		    return;
		}
	    }
	    if (u_d > 0) {
		key += offset;
	    } else {
		/* u_d < 0 */
		key -= offset;
		while (key < keystart) {
		    if ( (offset >>= 1) < (sizeof svp) )
			break;
		    key += offset;
		}
	    }
	}
	/* not found */
	break;
      }
    }
    if (hm = m->hash) {
	struct map_chain **mcp, *mc;
	p_int index_type = *SVALUE_FULLTYPE(map_index);
	p_int index_u = map_index->u.number;
	mp_int i;

	i = index_u ^ index_type;
	i = i ^ i >> 16;
	i = i ^ i >> 8;
	i &= hm->mask;
	for(mcp = &hm->chains[i]; mc = *mcp; ) {
	    if (mc->key.u.number == index_u &&
		*SVALUE_FULLTYPE(&mc->key) == index_type)
	    {
		int j;

		*mcp = mc->next;
		if (hm->ref) {
		    mc->next = hm->deleted;
		    hm->deleted = mc;
		} else {
		    svp = &mc->key;
		    j = num_values;
		    do {
			free_svalue(svp++);
		    } while (--j >= 0);
		    xfree( (char *)mc );
		}
		hm->used--;
		return;
	    }
	    mcp = &mc->next;
	}
    }
}

struct mapping *copy_mapping(m)
    struct mapping *m;
{
    struct mapping *m2;
    struct hash_mapping *hm, *hm2 = 0;
    struct condensed_mapping *cm, *cm2;
    mp_int num_values = m->num_values;
    mp_int size;
    mp_int i;
    char **str, **str2;
    struct svalue *svp, *svp2;

    if (hm = m->hash) {
	struct map_chain **mcp, **mcp2;
	mp_int linksize;

	size = hm->mask + 1;
	hm2 = (struct hash_mapping *)
	  xalloc(sizeof *hm - sizeof *mcp + sizeof *mcp * size);
	hm2->mask = hm->mask;
	hm2->used = hm->used;
	hm2->condensed_deleted = hm->condensed_deleted;
#ifdef DEBUG
	hm2->next_dirty = 0;
	hm->deleted = 0;
#endif
	hm2->ref = 0;
	num_dirty_mappings++;
	mcp = hm->chains;
	mcp2 = hm2->chains;
	linksize = MAP_CHAIN_SIZE(num_values);
	do {
	    struct map_chain *last = 0, *mc, *mc2;

	    for(mc = *mcp++; mc; mc = mc->next) {
		mc2 = (struct map_chain *)xalloc(linksize);
		i = num_values;
		svp = &mc->key;
		svp2 = &mc2->key;
		do {
		    assign_svalue_no_free(svp2++, svp++);
		} while (--i >= 0);
		mc2->next = last;
		last = mc2;
	    }
	    *mcp2++ = last;
	} while (--size);
    }
    cm = m->condensed;
#ifdef MALLOC_smalloc
    size =
      (malloced_size(
	(char *)cm - cm->misc_size * (1 + num_values)
      ) - SMALLOC_OVERHEAD) * sizeof (p_int);
#else
    size = sizeof *cm2 +
      (cm->string_size  * (sizeof *svp/sizeof(char *)) + cm->misc_size) *
	(1 + num_values) -
      cm->string_size * (sizeof *svp/sizeof(char *) - 1);
#endif
    cm2 = (struct condensed_mapping *)
      ( (char *)xalloc(size) + cm->misc_size * (1 + num_values) );
    *cm2 = *cm;
    str = CM_STRING(cm);
    str2 = CM_STRING(cm2);
    for(i = cm->string_size; (i -= sizeof *str) >= 0; str++, str2++) {
	*str2 = *str;
	if ( !((p_int)*str & 1) )
	    increment_string_ref(*str);
    }
    svp = (struct svalue *)str;
    svp2 = (struct svalue *)str2;
    for(i = cm->string_size*num_values; (i -= sizeof *str) >= 0; ) {
	assign_svalue_no_free(svp2++, svp++);
    }
    svp = CM_MISC(cm);
    svp2 = CM_MISC(cm2);
    i = cm->misc_size*(num_values+1);
    while ( (i -= sizeof *svp) >= 0)
	assign_svalue_no_free(--svp2, --svp);
    m2 = (struct mapping *)xalloc(sizeof *m2);
    if (m2->hash = hm2) {
	last_dirty_mapping->hash->next_dirty = m2;
	last_dirty_mapping = m2;
    }
    m2->condensed = cm2;
    m2->num_values = num_values;
    m2->ref = 1;
    (m2->user =
      current_object->user ? current_object->user : &default_wizlist_entry
    )->mapping_total +=
      sizeof *m2 + sizeof(char*) + size + sizeof(char*);
    num_mappings++;
    return m2;
}

struct mapping *add_mapping(m1, m2)
    struct mapping *m1, *m2;
{
    struct mapping *m3;
    struct hash_mapping *hm;
    struct condensed_mapping *cm1, *cm2, *cm3;
    struct svalue *condensed_start, *condensed_end;
    mp_int num_values = m1->num_values;
    mp_int size, size1, size2;
    mp_int string_size, misc_size;
    mp_int i;
    char **str1, **str2, **str3;
    struct svalue *svp1, *svp2, *svp3;
    mp_int u_d;
    struct svalue *data1, *data2, *data3;
    mp_int dirty;

    cm1 = m1->condensed;
    cm2 = m2->condensed;
    if (m2->num_values != num_values) {
	if (!cm2->string_size && !cm2->misc_size && !m2->hash) {
	    m2->num_values = num_values;
	} else if (!cm1->string_size && !cm1->misc_size && !m1->hash) {
	    m1->num_values = num_values = m2->num_values;
	} else {
	    return copy_mapping(m1);
	}
    }
    string_size = cm1->string_size + cm2->string_size;
    misc_size = cm1->misc_size + cm2->misc_size;
    size = sizeof *cm3 +
      (string_size * (sizeof *svp3/sizeof *str1) + misc_size) *
	(1 + num_values) -
      string_size * (sizeof *svp3/sizeof *str1 - 1);
    condensed_start  = (struct svalue *)xalloc(size);
    condensed_end = (struct svalue *)((char *)condensed_start + size);
    cm3 = (struct condensed_mapping *)
      ( (char *)condensed_start + misc_size * (1 + num_values) );
    cm3->string_size = string_size;
    cm3->misc_size = misc_size;
    dirty = 0;
    size1 = cm1->string_size;
    size2 = cm2->string_size;
    str1 = CM_STRING(cm1);
    data1 = (struct svalue *)( (char *)str1 + size1 );
    str2 = CM_STRING(cm2);
    data2 = (struct svalue *)( (char *)str2 + size2 );
    str3 = CM_STRING(cm3);
    data3 = (struct svalue *)( (char *)str3 + string_size );
    for(;size1 && size2; str3++) {
	if (*str1 < *str2) {
	    *str3 = *str1++;
	    for (i = num_values; --i >= 0; )
		assign_svalue_no_free(data3++, data1++);
	    size1 -= sizeof *str1;
	} else {
	    if (*str1 == *str2) {
		if( (p_int)*str1 & 1 ) {
		    *str3++ = *str1++;
		} else {
		    dirty++;
		    *str3++ = *str1++  - 1;
		}
		for (i = num_values; --i >= 0; )
		    (data3++)->type = T_INVALID;
		data1 += num_values;
		size1 -= sizeof *str1;
	    }
	    *str3 = *str2++;
	    for (i = num_values; --i >= 0; )
		assign_svalue_no_free(data3++, data2++);
	    size2 -= sizeof *str2;
	}
	if ( !((p_int)*str3 & 1) )
	    increment_string_ref(*str3);
    }
    if (!size1) {
	str1 = str2;
	size1 = size2;
	data1 = data2;
    }
    for (;(size1 -= sizeof *str1) >= 0;) {
	if ( !( (p_int)(*str3 = *str1++) & 1) )
	    increment_string_ref(*str3);
	str3++;
	for (i = num_values; --i >= 0; )
	    assign_svalue_no_free(data3++, data1++);
    }
    size1 = cm1->misc_size;
    size2 = cm2->misc_size;
    svp1 = CM_MISC(cm1) - 1;
    data1 = (struct svalue *)( (char *)svp1 - size1 );
    svp2 = CM_MISC(cm2) - 1;
    data2 = (struct svalue *)( (char *)svp2 - size2 );
    svp3 = CM_MISC(cm3);
    data3 = (struct svalue *)( (char *)svp3 - misc_size );
    for(;size1 && size2; ) {
	if ( !(u_d = (svp1->u.number >> 1) - (svp2->u.number >> 1)) )
	  if ( !(u_d = svp1->x.generic - svp2->x.generic) )
	    if ( !(u_d = svp1->type - svp2->type) ) {
		dirty += svp1->type != T_INVALID;
		svp1--;
		data1 -= num_values;
		size1 -= sizeof *svp1;
	    }
	if (u_d < 0) {
	    assign_svalue_no_free(--svp3, svp1--);
	    for (i = num_values; --i >= 0; )
		assign_svalue_no_free(--data3, data1--);
	    size1 -= sizeof *svp1;
	} else {
	    assign_svalue_no_free(--svp3, svp2--);
	    for (i = num_values; --i >= 0; )
		assign_svalue_no_free(--data3, data2--);
	    size2 -= sizeof *svp2;
	}
    }
    if (!size1) {
	svp1 = svp2;
	size1 = size2;
	data1 = data2;
    }
    while ( (size1 -= sizeof *svp1) >= 0) {
	assign_svalue_no_free(--svp3, svp1--);
	for (i = num_values; --i >= 0; )
	    assign_svalue_no_free(--data3, data1--);
    }
    while (data3 > condensed_start) {
	(--svp3)->type = T_INVALID;
	svp3->x.generic = MIN_PH_INT;
	svp3->u.number = MIN_P_INT;
	for (i = num_values; --i >= 0; )
	    (--data3)->type = T_INVALID;
    }
    size1 =
      (m1->hash ? dirty += m1->hash->condensed_deleted, m1->hash->used : 0) +
      (m2->hash ? dirty += m2->hash->condensed_deleted, m2->hash->used : 0) ;
    size1 += !size1 && dirty;
    m3 = allocate_mapping(size1, num_values);
    xfree( (char *)m3->condensed );
    m3->condensed = cm3;
    if (size1)
	m3->hash->condensed_deleted = dirty;
    (m3->user =
      current_object->user ? current_object->user : &default_wizlist_entry
    )->mapping_total += size - sizeof *cm3;
      /*  allocate_mapping has already accounted most of the total size
       *  sizeof *m3 + sizeof(char*) + size + sizeof(char*);
       */

    if (hm = m1->hash) {
	struct map_chain **mcp;

	size = hm->mask + 1;
	mcp = hm->chains;
	do {
	    struct map_chain *mc;

	    for(mc = *mcp++; mc; mc = mc->next) {
		data1 = mc->data;
		data3 = get_map_lvalue(m3, &mc->key, 1);
		if (data3 < condensed_start || data3 >= condensed_end) {
		    for (i = num_values; --i >= 0; )
			assign_svalue(data3++, data1++);
		}
	    }
	} while (--size);
    }
    if (hm = m2->hash) {
	struct map_chain **mcp;

	size = hm->mask + 1;
	mcp = hm->chains;
	do {
	    struct map_chain *mc;

	    for(mc = *mcp++; mc; mc = mc->next) {
		data1 = mc->data;
		data2 = get_map_lvalue(m3, &mc->key, 1);
		for (i = num_values; --i >= 0; )
		    assign_svalue(data2++, data1++);
	    }
	} while (--size);
    }
    return m3;
}

struct svalue walk_mapping_string_svalue = { T_STRING };

void walk_mapping(m, func, extra)
    struct mapping *m;
    void (*func) PROT((struct svalue *, struct svalue *, char *));
    char *extra;
{
    char **str;
    struct svalue *svp, *data;
    mp_int size;
    mp_int num_values;
    struct hash_mapping *hm;

    num_values = m->num_values;
    str = CM_STRING(m->condensed);
    size = m->condensed->string_size;
    data = (struct svalue *)((char *)str + size);
    while ( (size -= sizeof(char *)) >= 0) {
	if ( !( (p_int)(walk_mapping_string_svalue.u.string = *str++) & 1 ) )
	    (*func)(&walk_mapping_string_svalue, data, extra);
	data += num_values;
    }
    svp = CM_MISC(m->condensed);
    size = m->condensed->misc_size;
    data = (struct svalue *)((char *)svp - size);
    while ( (size -= sizeof(struct svalue)) >= 0) {
	data -= num_values;
	if ( (--svp)->type != T_INVALID )
	    (*func)(svp, data, extra);
    }
    if (hm = m->hash) {
	struct map_chain **mcp, *mc;

	mcp = hm->chains;
	size = hm->mask;
	do {
	    if (mc = *mcp++) {
		do {
		    (*func)(&mc->key, mc->data, extra);
		} while (mc = mc->next);
	    }
	} while (--size >= 0);
    }
}

void f_walk_mapping_filter(key, data, extra)
    struct svalue *key, *data;
    char *extra;
{
    struct svalue *svp;

    svp = *(struct svalue **)extra;
    assign_svalue_no_free(svp, key);
    (++svp)->u.lvalue = data;
    *(struct svalue **)extra = ++svp;
}

void f_walk_mapping_cleanup(arg)
    struct svalue *arg;
{
    struct svalue *svp;
    struct mapping *m;
    mp_int i;

    svp = arg + 1;
    m = svp[1].u.map;
    if (svp[1].x.generic) {
	struct hash_mapping *hm;
	int num_values;

	hm = m->hash;
	num_values = m->num_values;
	if (!--hm->ref) {
	    struct map_chain *mc, *next;
	    struct svalue *svp2;

	    for (mc = hm->deleted; mc; mc = next) {
		mp_int j;

		svp2 = &mc->key;
		j = num_values;
		do {
		    free_svalue(svp2++);
		} while (--j >= 0);
		next = mc->next;
		xfree( (char *)mc );
	    }
	}
    }
    i = svp->u.number;
    if (i) do {
	svp += 2;
	free_svalue(svp);
    } while (--i > 0);
    xfree((char *)arg);
}

struct svalue *walk_mapping_prologue(m, sp)
    struct mapping *m;
    struct svalue *sp;
{
    struct hash_mapping *hm;
    struct svalue *pointers;
    struct svalue *write_pointer, *read_pointer;
    mp_int i;

    i = m->condensed->string_size/sizeof(char *) +
        m->condensed->misc_size/sizeof(struct svalue);
    if (hm = m->hash) {
	i += hm->used - hm->condensed_deleted;
	if (!m->num_values) {
	    hm = 0;
	} else if (!hm->ref++) {
	    hm->deleted = 0;
	}
    }
    pointers = (struct svalue *)xalloc( (i * 2 + 3) * sizeof(struct svalue) );
    pointers[0].type = T_ERROR_HANDLER;
    pointers[0].u.error_handler = f_walk_mapping_cleanup;
    pointers[1].u.number = i;
    pointers[2].u.map = m;
    pointers[2].x.generic = hm != 0;
    (++sp)->type = T_LVALUE;
    sp->u.lvalue = pointers;
    read_pointer = write_pointer = pointers + 3;
    walk_mapping(m, f_walk_mapping_filter, (char*)&write_pointer);
    return read_pointer;
}

#ifdef F_WALK_MAPPING
struct svalue *f_walk_mapping(sp, num_arg)
    struct svalue *sp;
    int num_arg;
{
    extern struct svalue *inter_sp;
    extern void assign_eval_cost();

    struct svalue *arg, *extra;
    int extra_num;
    struct mapping *m;
    struct object *ob;
    char *func;
    int num_values;
    struct svalue *read_pointer;
    mp_int i;

    arg = sp - num_arg + 1;
    inter_sp = sp;
    if (arg[0].type != T_MAPPING)
	bad_efun_arg(1, F_WALK_MAPPING-F_OFFSET, sp);
    if (arg[1].type == T_CLOSURE) {
	ob = 0;
	func = (char *)&arg[1];
	extra_num = num_arg - 2;
	extra = &arg[2];
    } else if (arg[1].type != T_STRING) {
	bad_efun_arg(2, F_WALK_MAPPING-F_OFFSET, sp);
    } else {
	if (num_arg >= 3 /* && arg[1].type == T_STRING */) {
	    if (arg[2].type == T_OBJECT)
		ob = arg[2].u.ob;
	    else if (arg[2].type != T_STRING ||
		     !(ob = find_object(arg[2].u.string)) )
		bad_efun_arg(3, F_WALK_MAPPING-F_OFFSET, sp);
	    extra_num = num_arg - 3;
	    extra = &arg[3];
	} else {
	    ob = current_object;
	    extra_num = 0;
	}
	func = arg[1].u.string;
    }
    m = arg[0].u.map;
    check_map_for_destr(m);
    assign_eval_cost();

    read_pointer = walk_mapping_prologue(m, sp);
    i = read_pointer[-2].u.number;
    sp++;
    num_values = m->num_values;
    while (--i >= 0) {
	int j;
	struct svalue *sp2, *data;

	assign_svalue_no_free( (sp2 = sp+1), read_pointer++ );
	for (j = num_values, data = (read_pointer++)->u.lvalue; --j >= 0; ) {
	     (++sp2)->type = T_LVALUE;
	     sp2->u.lvalue = data++;
	}
	inter_sp = sp2;
	push_svalue_block(extra_num, extra);
	if (ob) {
	    if (ob->flags & O_DESTRUCTED)
		error("Object used by walk_mapping destructed");
	    apply( func, ob, 1 + num_values + extra_num);
	} else {
	    call_lambda( (struct svalue *)func, 1 + num_values + extra_num);
	    free_svalue(inter_sp--);
	}
    }
    free_svalue(sp);
    i = num_arg;
    do
	free_svalue(--sp);
    while (--i > 0);
    return sp-1;
}
#endif /* F_WALK_MAPPING */

struct vector *m_indices(m)
    struct mapping *m;
{
    struct vector *v;
    struct svalue *svp;
    mp_int size;

    size = m->condensed->string_size / sizeof(char *) +
	   m->condensed->misc_size   / sizeof(struct svalue) +
	  (m->hash ? m->hash->used  - m->hash->condensed_deleted : 0);
    v = allocate_array(size); /* might cause error */
    svp = v->item;
    walk_mapping(m, m_indices_filter, (char *)&svp);
    return v;
}

static void add_to_mapping_filter(key, data, extra)
    struct svalue *key, *data;
    char *extra;
{
    struct svalue *data2;
    int i;

    data2 = get_map_lvalue((struct mapping *)extra, key, 1);
    for (i = ((struct mapping *)extra)->num_values; --i >= 0;) {
	if (data2->type != T_NUMBER)
	    free_svalue(data2);
	assign_svalue_no_free(data2++, data++);
    }
}

void sub_from_mapping_filter(key, data, extra)
    struct svalue *key, *data;
    char *extra;
{
    remove_mapping((struct mapping *)extra, key);
}

void add_to_mapping(m1, m2)
    struct mapping *m1, *m2;
{
    if (m2->num_values != m1->num_values) {
	struct condensed_mapping *cm1, *cm2;

	cm2 = m2->condensed;
	if (!cm2->string_size && !cm2->misc_size && !m2->hash) {
	    m2->num_values = m1->num_values;
	} else {
	    cm1 = m1->condensed;
	    if (!cm1->string_size && !cm1->misc_size && !m1->hash) {
		m1->num_values = m2->num_values;
	    } else {
		return;
	    }
	}
    }
    walk_mapping(m2, add_to_mapping_filter, (char *)m1);
}

struct mapping *subtract_mapping(minuend, subtrahend)
    struct mapping *minuend, *subtrahend;
{
    /* this could be done faster, especially if there the mappings are
     * mainly condensed. On the other hand, the priority of fast mapping
     * subtraction is unknown.
     */
    minuend = copy_mapping(minuend);
    walk_mapping(subtrahend, sub_from_mapping_filter, (char *)minuend);
    return minuend;
}

/* leave a filtered mapping on the stack */
struct svalue *filter_mapping (sp, num_arg)
    struct svalue *sp;
    int num_arg;
{
    extern struct svalue *inter_sp;
    extern void assign_eval_cost();

    struct svalue *arg;
    struct mapping *m;
    char *func;
    struct object *ob;
    struct svalue *extra;
    int num_values;
    struct svalue *v;
    int extra_num;
    int i, j;
    struct svalue *read_pointer;

    arg = sp - num_arg + 1;
    inter_sp = sp;
    if (arg[0].type != T_MAPPING)
	bad_efun_arg(1, F_FILTER_MAPPING-F_OFFSET, sp);
    if (arg[1].type == T_CLOSURE) {
	ob = 0;
	func = (char *)&arg[1];
	extra = &arg[2];
	extra_num = num_arg - 2;
    } else if (arg[1].type != T_STRING) {
	bad_efun_arg(2, F_FILTER_MAPPING-F_OFFSET, sp);
    } else {
	if (num_arg < 3) {
	    ob = current_object;
	    /* let the compiler mourn: we need no extra. */
	    extra_num = 0;
	} else {
	    if (arg[2].type == T_OBJECT)
		ob = arg[2].u.ob;
	    else if (arg[2].type != T_STRING &&
		     !(ob = find_object(arg[2].u.string)) )
		bad_efun_arg(3, F_FILTER_MAPPING-F_OFFSET, sp);
	    extra = &arg[3];
	    extra_num = num_arg - 3;
	}
	func = arg[1].u.string;
    }
    m = arg[0].u.map;
    check_map_for_destr(m);
    assign_eval_cost();

    num_values = m->num_values;
    read_pointer = walk_mapping_prologue(m, sp);
    m = allocate_mapping(read_pointer[-2].u.number , num_values);
    (sp += 2)->type = T_MAPPING;
    sp->u.map = m;
    for (i = read_pointer[-2].u.number; --i >= 0; read_pointer += 2) {
	struct svalue *data;

	if (ob) {
	    if (ob->flags & O_DESTRUCTED)
		break;
	    assign_svalue_no_free((inter_sp = sp + 1), read_pointer);
	    push_svalue_block( extra_num, extra);
	    v = apply( func, ob, 1 + extra_num);
	    if (!v || v->type == T_NUMBER && !v->u.number)
		continue;
	} else {
	    assign_svalue_no_free((inter_sp = sp + 1), read_pointer);
	    push_svalue_block( extra_num, extra);
	    call_lambda( (struct svalue *)func, 1 + extra_num);
	    v = inter_sp--;
	    if (v->type == T_NUMBER) {
		if (!v->u.number)
		    continue;
	    } else {
		free_svalue(v);
	    }
	}
	v = get_map_lvalue(m, read_pointer, 1);
	for (j = num_values, data = read_pointer[1].u.lvalue; --j >= 0; ) {
	    assign_svalue_no_free(v++, data++);
	}
    }
    i = num_arg;
    do
	free_svalue(--sp);
    while (--i >= 0);
    sp->type = T_MAPPING;
    sp->u.map = m;
    return sp;
}

/* leave result mapping on the stack */
struct svalue *map_mapping (sp, num_arg)
    struct svalue *sp;
    int num_arg;
{
    extern struct svalue *inter_sp;
    extern void assign_eval_cost();

    struct svalue *arg;
    struct mapping *m;
    char *func;
    struct object *ob;
    struct svalue *extra;
    struct vector *vec;
    int num_values;
    int extra_num;
    int i;
    struct svalue *key;

    arg = sp - num_arg + 1;
    inter_sp = sp;
    if (arg[0].type != T_MAPPING)
	bad_efun_arg(1, F_MAP_MAPPING-F_OFFSET, sp);
    if (arg[1].type == T_CLOSURE) {
	ob = 0;
	func = (char *)(arg + 1);
	extra = &arg[2];
	extra_num = num_arg - 2;
    } else if (arg[1].type != T_STRING) {
	bad_efun_arg(2, F_MAP_MAPPING-F_OFFSET, sp);
    } else {
	if (num_arg < 3) {
	    ob = current_object;
	    /* let the compiler mourn: we need no extra. */
	    extra_num = 0;
	} else {
	    if (arg[2].type == T_OBJECT)
		ob = arg[2].u.ob;
	    else if (arg[2].type != T_STRING &&
		     !(ob = find_object(arg[2].u.string)) )
		bad_efun_arg(3, F_MAP_MAPPING-F_OFFSET, sp);
	    extra = &arg[3];
	    extra_num = num_arg - 3;
	}
	func = arg[1].u.string;
    }
    m = arg[0].u.map;
    check_map_for_destr(m);
    assign_eval_cost();

    num_values = m->num_values;
    vec = m_indices(m); /* might cause error */
    (++sp)->type = T_POINTER;
    sp->u.vec = vec;
    m = allocate_mapping(vec->size, 1);
    (++sp)->type = T_MAPPING;
    sp->u.map = m;
    key = vec->item;
    for (i = vec->size; --i >= 0; key++) {
	struct svalue *v;

	assign_svalue_no_free((inter_sp = sp + 1), key);
	push_svalue_block( extra_num, extra);
	v = get_map_lvalue(m, key, 1);
	if (ob) {
	    struct svalue *data;

	    if (ob->flags & O_DESTRUCTED)
		error("Object used by map_mapping destructed");
	    data = apply( func, ob, 1 + extra_num);
	    if (data) {
		transfer_svalue_no_free(v, data);
		data->type = T_INVALID;
	    }
	} else {
	    call_lambda( (struct svalue *)func, 1 + extra_num);
	    transfer_svalue_no_free(v, inter_sp--);
	}
    }
    i = num_arg;
    do
	free_svalue(--sp);
    while (--i >= 0);
    sp->type = T_MAPPING;
    sp->u.map = m;
    return sp;
}

/* Used mergesort to sort hashed string and misc keys, respectively.
 * Portions that won't make up the current power of two are processed
 * first, to save tests.
 * When all previously hashed keys are sorted, they are merged with the
 * already condensed part.
 */
void compact_mappings(num)
    mp_int num;
{
    extern struct svalue last_indexing_protector;
    extern int malloc_privilege;

    struct mapping *m;

    malloc_privilege = MALLOC_SYSTEM;
    if (last_indexing_protector.type == T_PROTECTOR_MAPPING) {
	/* There is a slight chance that free_protector_mapping causes
	 * remove_empty_mappings(), and thus changes num_dirty_mappings.
	 */
	free_protector_mapping(last_indexing_protector.u.map);
	last_indexing_protector.type = T_NUMBER;
    }
    if (num >= num_dirty_mappings) {
	num = num_dirty_mappings;
	last_dirty_mapping = &dirty_mapping_head;
    } else {
	extra_jobs_to_do = 1;
    }
    num_dirty_mappings -= num;
    m = dirty_mapping_head_hash.next_dirty;
    while (--num >= 0) {
	mp_int count1, count2;
	struct hash_mapping *hm;
	struct condensed_mapping *cm, *cm2;
	int num_values;
	/* hooks to hang the chains on  :-) */
	struct map_chain *string_hook1, *string_hook2,
			 *misc_hook1,   *misc_hook2;
	mp_int string_used, misc_used, runlength;
	struct map_chain **mcpp, *mcp, *next;
	struct map_chain *last_string, *last_misc;

#ifdef DEBUG
	if (!m->user)
	    fatal("No wizlist pointer for mapping\n");
#endif
	m->ref++; /* prevent freeing while using in case of recursive
		   * mappings referenced by a deleted value
		   */
	cm = m->condensed;
	hm = m->hash;
#ifdef DEBUG
	if (hm->ref) {
	    struct svalue *svp;
	    int i;

	    printf("compact_mappings(): remaining ref count %d!\n", hm->ref);
#ifdef TRACE_CODE
	    {
		extern int last_instructions PROT((int, int));

		last_instructions(TOTAL_TRACE_LENGTH, 1);
	    }
#endif
	    printf("compact_mappings(): remaining ref count! %d\n", hm->ref);
	    if (hm->ref > 0) {
		for (mcp = hm->deleted; mcp; mcp = next) {
		    next = mcp->next;
		    svp = &mcp->key;
		    i = num_values;
		    do {
			free_svalue(svp++);
		    } while (--i >= 0);
		    xfree( (char *)mcp );
		}
	    }
	}
#endif /* DEBUG */
	if (!hm->used && !hm->condensed_deleted) {
	    if (!m->condensed) {
		xfree((char *)m);
		empty_mapping_load -= 2;
	    } else {
		m->hash = 0;
		/* the ref count has been incremented above; on the other
		 * hand, the last real reference might have gone with the
		 * deleted keys.
		 */
		free_mapping(m);
	    }
	    m = hm->next_dirty;
	    xfree( (char *)hm );
	    continue;
	}
	num_values = m->num_values;
	mcpp = hm->chains;
	count1 = hm->mask;
	string_hook1 = string_hook2 = 0;
	misc_hook1 = misc_hook2 = 0;
	misc_used = 0;
	last_string = last_misc = 0;
	do {
	    mcp = *mcpp++;
	    while (mcp) {
		next = mcp->next;

		if (mcp->key.type != T_STRING) {
		    if (last_misc) {
			p_int d;

			if ( !(d = (last_misc->key.u.number >> 1) -
				   (mcp->key.u.number >> 1) ) )
			  if ( !(d = last_misc->key.x.generic -
				     mcp->key.x.generic ) )
			    d = last_misc->key.type - mcp->key.type;
			if (d > 0) {
			    last_misc->next = misc_hook1;
			    mcp->next = last_misc;
			    misc_hook1 = misc_hook2;
			    misc_hook2 = mcp;
			} else {
			    mcp->next = misc_hook1;
			    last_misc->next = mcp;
			    misc_hook1 = misc_hook2;
			    misc_hook2 = last_misc;
			}
			misc_used += 2;
			last_misc = 0;
		    } else {
			last_misc = mcp;
		    }
		} else {
		    if (last_string) {
			if (last_string->key.u.string > mcp->key.u.string) {
			    last_string->next = string_hook1;
			    mcp->next = last_string;
			    string_hook1 = string_hook2;
			    string_hook2 = mcp;
			} else {
			    mcp->next = string_hook1;
			    last_string->next = mcp;
			    string_hook1 = string_hook2;
			    string_hook2 = last_string;
			}
			last_string = 0;
		    } else {
			last_string = mcp;
		    }
		}
		mcp = next;
	    }
	} while (--count1 >= 0);
	if (last_string) {
	    last_string->next = string_hook1;
	    string_hook1 = last_string;
	}
	if (last_misc) {
	    misc_used++;
	    last_misc->next = misc_hook1;
	    misc_hook1 = last_misc;
	}
	string_used = hm->used - misc_used;
	for (runlength = 2; runlength < string_used; runlength <<= 1) {
	    struct map_chain *out_hook1, *out_hook2, **out1, **out2;

	    count1 = string_used & runlength-1;
	    count2 = string_used & runlength;
	    if (!count1) {
		out2 = &out_hook1;
		*out2 = string_hook2;
		while (--count2 >= 0) {
		    out2 = &(*out2)->next;
		}
		string_hook2 = *out2;
		count1 = count2 = runlength;
		out1 = &out_hook2;
	    } else if (!count2) {
		out2 = &out_hook1;
		*out2 = string_hook1;
		do {
		    out2 = &(*out2)->next;
		} while (--count1);
		string_hook1 = *out2;
		count1 = count2 = runlength;
		out1 = &out_hook2;
	    } else {
		out1 = &out_hook1;
		out2 = &out_hook2;
	    }
	    while (string_hook1) {
		while (1) {
		    if (string_hook2->key.u.string <
			string_hook1->key.u.string)
		    {
			*out1 = string_hook2;
			out1 = &string_hook2->next;
			string_hook2 = *out1;
			if (!--count2) {
			    *out1 = string_hook1;
			    do {
				out1 = &(*out1)->next;
			    } while (--count1);
			    string_hook1 = *out1;
			    break;
			}
		    } else {
			*out1 = string_hook1;
			out1 = &string_hook1->next;
			string_hook1 = *out1;
			if (!--count1) {
			    *out1 = string_hook2;
			    do {
				out1 = &(*out1)->next;
			    } while (--count2);
			    string_hook2 = *out1;
			    break;
			}
		    }
		}
		{
		    struct map_chain **temp;

		    temp = out1;
		    out1 = out2;
		    out2 = temp;
		}
		count1 = count2 = runlength;
	    }
	    *out1 = 0;
	    *out2 = 0;
	    string_hook1 = out_hook1;
	    string_hook2 = out_hook2;
	}
	if (!string_hook1)
	    string_hook1 = string_hook2;
	for (runlength = 2; runlength < misc_used; runlength <<= 1) {
	    struct map_chain *out_hook1, *out_hook2, **out1, **out2;

	    count1 = misc_used & runlength-1;
	    count2 = misc_used & runlength;
	    if (!count1) {
		out2 = &out_hook1;
		*out2 = misc_hook2;
		while (--count2 >= 0) {
		    out2 = &(*out2)->next;
		}
		misc_hook2 = *out2;
		count1 = count2 = runlength;
		out1 = &out_hook2;
	    } else if (!count2) {
		out2 = &out_hook1;
		*out2 = misc_hook1;
		do {
		    out2 = &(*out2)->next;
		} while (--count1);
		misc_hook1 = *out2;
		count1 = count2 = runlength;
		out1 = &out_hook2;
	    } else {
		out1 = &out_hook1;
		out2 = &out_hook2;
	    }
	    while (misc_hook1) {
		while (1) {
		    p_int d;

		    if (!(d = (misc_hook2->key.u.number >> 1) -
			      (misc_hook1->key.u.number >> 1) ))
		      if (!(d = misc_hook2->key.x.generic -
				misc_hook1->key.x.generic))
			  d = misc_hook2->key.type -
			      misc_hook1->key.type;
		    if (d < 0) {
			*out1 = misc_hook2;
			out1 = &misc_hook2->next;
			misc_hook2 = *out1;
			if (!--count2) {
			    *out1 = misc_hook1;
			    do {
				out1 = &(*out1)->next;
			    } while (--count1);
			    misc_hook1 = *out1;
			    break;
			}
		    } else {
			*out1 = misc_hook1;
			out1 = &misc_hook1->next;
			misc_hook1 = *out1;
			if (!--count1) {
			    *out1 = misc_hook2;
			    do {
				out1 = &(*out1)->next;
			    } while (--count2);
			    misc_hook2 = *out1;
			    break;
			}
		    }
		}
		{
		    struct map_chain **temp;

		    temp = out1;
		    out1 = out2;
		    out2 = temp;
		}
		count1 = count2 = runlength;
	    }
	    *out1 = 0;
	    *out2 = 0;
	    misc_hook1 = out_hook1;
	    misc_hook2 = out_hook2;
	}
	if (!misc_hook1)
	    misc_hook1 = misc_hook2;
	{
	    /* merge old condensed part with sorted lists */
	    mp_int misc_deleted;
	    mp_int string_total, misc_total;
	    char *condensed_start;
	    char **str1, **str2;
	    struct svalue *key1, *key2;
	    struct svalue *data1, *data2;
	    char *cm1_end, *cm2_end;

	    misc_deleted = 0;
	    if (hm->condensed_deleted) {
		struct svalue *svp;
		mp_int size;

		svp = CM_MISC(cm);
		size = cm->misc_size;
		while ( (size -= sizeof(struct svalue)) >= 0) {
		    if ( (--svp)->type == T_INVALID )
			misc_deleted++;
		}
	    }
	    string_total = string_used + cm->string_size/sizeof(char *) -
			(hm->condensed_deleted - misc_deleted);
	    misc_total = misc_used + cm->misc_size/sizeof(struct svalue) -
			misc_deleted;
	    condensed_start = xalloc(sizeof *cm2 +
		(string_total+misc_total)*sizeof(struct svalue)*(num_values+1)-
		string_total * (sizeof(struct svalue)-sizeof(char *))
	    );
	    cm2 = (struct condensed_mapping *)
		   (condensed_start +
		    misc_total * (num_values+1) * sizeof(struct svalue) );
	    cm2->string_size = string_total * sizeof(char*);
	    cm2->misc_size = misc_total * sizeof(struct svalue);
	    str1 = CM_STRING(cm);
	    data1 = (struct svalue *)((char *)str1 + cm->string_size);
	    str2 = CM_STRING(cm2);
	    data2 = (struct svalue *)((char *)str2 + cm2->string_size);
	    count1 = cm->string_size;
	    while (count1 && (p_int)*str1 & 1) {
		int i;

		i = num_values;
		while (--i >= 0) {
		    free_svalue(data1++);
		}
		str1++;
		count1 -= sizeof(char *);
	    }
	    if (string_hook1 && count1) {
		while (1) {
		    if (string_hook1->key.u.string < *str1) {
			struct map_chain *temp;
			struct svalue *data;
			int i;

			temp = string_hook1;
			*str2++ = temp->key.u.string;
			data = temp->data;
			i = num_values;
			while (--i >= 0) {
			    *data2++ = *data++;
			}
			string_hook1 = temp->next;
			xfree( (char *)temp );
			if (!string_hook1)
			    break;
		    } else {
			int i;

			*str2++ = *str1++;
			i = num_values;
			while (--i >= 0) {
			    *data2++ = *data1++;
			}
			if ( !(count1 -= sizeof(char*)) )
			    break;
			if ((p_int)*str1 & 1) {
			    do {
				i = num_values;
				while (--i >= 0) {
				    free_svalue(data1++);
				}
				str1++;
				if ( !(count1 -= sizeof(char*)) )
				    break;
			    } while ((p_int)*str1 & 1);
			    if (!count1)
				break;
			}
		    }
		}
	    }
	    if (count1) {
		while (1) {
		    int i;

		    *str2++ = *str1++;
		    i = num_values;
		    while (--i >= 0) {
			*data2++ = *data1++;
		    }
		    if ( !(count1 -= sizeof(char*)) )
			break;
		    if ((p_int)*str1 & 1) {
			do {
			    i = num_values;
			    while (--i >= 0) {
				free_svalue(data1++);
			    }
			    str1++;
			    if ( !(count1 -= sizeof(char*)) )
				break;
			} while ((p_int)*str1 & 1);
			if (!count1)
			    break;
		    }
		}
	    } else {
		while (string_hook1) {
		    struct map_chain *temp;
		    struct svalue *data;
		    int i;

		    temp = string_hook1;
		    *str2++ = temp->key.u.string;
		    data = temp->data;
		    i = num_values;
		    while (--i >= 0) {
			*data2++ = *data++;
		    }
		    string_hook1 = temp->next;
		    xfree( (char *)temp );
		}
	    }
	    cm1_end = (char *)data1;
	    cm2_end = (char *)data2;
	    key1 = CM_MISC(cm);
	    data1 = (struct svalue *)((char *)key1 - cm->misc_size);
	    key2 = CM_MISC(cm2);
	    data2 = (struct svalue *)((char *)key2 - cm2->misc_size);
	    count1 = cm->misc_size;
	    while (count1 && key1[-1].type == T_INVALID) {
		int i;

		key1--;
		i = num_values;
		while (--i >= 0) {
		    free_svalue(--data1);
		}
		count1 -= sizeof(struct svalue);
	    }
	    if (misc_hook1 && count1) {
		while (1) {
		    p_int d;

		    if (!(d = (misc_hook1->key.u.number >> 1) -
			      (key1[-1].u.number >> 1) ))
		      if (!(d = misc_hook1->key.x.generic - key1[-1].x.generic))
			  d = misc_hook1->key.type - key1[-1].type;
		    if (d < 0) {
			struct map_chain *temp;
			struct svalue *data;
			int i;

			temp = misc_hook1;
			*--key2 = temp->key;
			data = temp->data + num_values;
			i = num_values;
			while (--i >= 0) {
			    *--data2 = *--data;
			}
			misc_hook1 = temp->next;
			xfree( (char *)temp );
			if (!misc_hook1)
			    break;
		    } else {
			int i;

			*--key2 = *--key1;
			i = num_values;
			while (--i >= 0) {
			    *--data2 = *--data1;
			}
			if (! (count1 -= sizeof(struct svalue)) )
			    break;
			if (key1[-1].type == T_INVALID) {
			    do {
				key1--;
				i = num_values;
				while (--i >= 0) {
				    free_svalue(--data1);
				}
				if (! (count1 -= sizeof(struct svalue)) )
				    break;
			    } while (key1[-1].type == T_INVALID);
			    if (!count1)
				break;
			}
		    }
		}
	    }
	    if (count1) {
		while (1) {
		    int i;

		    *--key2 = *--key1;
		    i = num_values;
		    while (--i >= 0) {
			*--data2 = *--data1;
		    }
		    if (! (count1 -= sizeof(struct svalue)) )
			break;
		    if (key1[-1].type == T_INVALID) {
			do {
			    key1--;
			    i = num_values;
			    while (--i >= 0) {
				free_svalue(--data1);
			    }
			    if (! (count1 -= sizeof(struct svalue)) )
				break;
			} while (key1[-1].type == T_INVALID);
			if (!count1)
			    break;
		    }
		}
	    } else {
		while (misc_hook1) {
		    struct map_chain *temp;
		    struct svalue *data;
		    int i;

		    temp = misc_hook1;
		    *--key2 = temp->key;
		    data = temp->data + num_values;
		    i = num_values;
		    while (--i >= 0) {
			*--data2 = *--data;
		    }
		    misc_hook1 = temp->next;
		    xfree( (char *)temp );
		}
	    }
	    m->user->mapping_total +=
		(cm2_end - (char *)data2) -
		(cm1_end - (char *)data1);
	    xfree( (char *)(data1) ); /* free old condensed mapping part */
	} /* end of merge block */
	m->condensed = cm2;
	m->hash = 0;
	free_mapping(m);
	m = hm->next_dirty;
	xfree( (char *)hm );
    }
    dirty_mapping_head_hash.next_dirty = m;
}

mp_int total_mapping_size() {
    extern struct wiz_list *all_wiz;

    struct wiz_list *wl;
    mp_int total;

    total = default_wizlist_entry.mapping_total;
    for (wl = all_wiz; wl; wl = wl->next) {
	total += wl->mapping_total;
    }
    return total;
}

#if 0
void check_dirty(avoid)
    int avoid;
{
    struct mapping *m;
    mp_int i;

    m = dirty_mapping_head_hash.next_dirty;
    for (i = num_dirty_mappings - avoid; --i >= 0; m = m->hash->next_dirty) {
	struct hash_mapping *hm = m->hash;
	mp_int j;
	struct map_chain **mcp, *mc;

	j = hm->mask;
	mcp = hm->chains;
	do {
	    mc = *mcp++;
	    while (mc) {
		if ((p_int)mc & 0xff000003) /* The mask is machine dependent. */
		    fatal("check_dirty\n");
		mc = mc->next;
	    }
	} while (--j >= 0);
    }
}
#endif

struct set_mapping_user_locals {
    int num_values;
    struct object *owner;
    struct svalue *hairy; /* changing keys */
};

void set_mapping_user_filter(key, data, extra)
    struct svalue *key, *data;
    char *extra;
{
    int i;
    struct set_mapping_user_locals *locals;
    struct object *owner;

    locals = (struct set_mapping_user_locals *)extra;
    owner = locals->owner;
    if (key->type == T_CLOSURE && !CLOSURE_MALLOCED(key->x.closure_type)) {
	*locals->hairy++ = *key;
    } else {
	set_svalue_user(key, owner);
    }
    for (i = locals->num_values; --i >= 0;) {
	set_svalue_user(data++, owner);
    }
}

void set_mapping_user(m, owner)
    struct mapping *m;
    struct object *owner;
{
    struct condensed_mapping *cm;
    int num_values;
    mp_int total;
    struct wiz_list *user;
    struct set_mapping_user_locals locals;
    struct svalue *first_hairy;
    mp_int i;

    num_values = m->num_values;
    cm = m->condensed;
    total =
      sizeof *m + 4 + sizeof *cm + 4 +
        ( cm->string_size * (sizeof(struct svalue)/sizeof(char*)) +
	  cm->misc_size) * (1 + num_values) -
	cm->string_size * (sizeof(struct svalue)/sizeof(char *) - 1);
    m->user->mapping_total -= total;
    if ( !(user = owner->user) )
	user = &default_wizlist_entry;
    m->user = user;
    m->user->mapping_total += total;
    locals.owner = owner;
    locals.num_values = num_values;
    locals.hairy = first_hairy = (struct svalue *)alloca(cm->misc_size);
    walk_mapping(m, set_mapping_user_filter, (char *)&locals);
    for (i = locals.hairy - first_hairy; --i >= 0; first_hairy++) {
	struct svalue new_key, *dest, *source;
	mp_int j;

	assign_svalue_no_free(&new_key, first_hairy);
	set_svalue_user(&new_key, owner);
	dest = get_map_lvalue(m, &new_key, 1);
	free_svalue(&new_key);
	source = get_map_lvalue(m, first_hairy, 0);
	if (num_values)
	    memcpy((char *)dest, (char *)source, num_values * sizeof *dest);
	for (j = num_values; --j >= 0; source++)
	    source->type = T_INVALID;
	remove_mapping(m, first_hairy);
    }
}

#ifdef MALLOC_smalloc
void count_ref_in_mapping(m)
    struct mapping *m;
{
    extern struct object *gc_obj_list_destructed;

    char **str;
    struct svalue *svp, *data;
    mp_int size;
    mp_int num_values;
    int any_destructed = 0;

    num_values = m->num_values;
    str = CM_STRING(m->condensed);
    size = m->condensed->string_size;
    while ( (size -= sizeof(char *)) >= 0) {
	count_ref_from_string(*str++);
    }
    data = (struct svalue *)str;
    count_ref_in_vector(
      (struct svalue *)str,
      m->condensed->string_size / sizeof *str * num_values
    );
    svp = CM_MISC(m->condensed);
    size = m->condensed->misc_size;
    while ( (size -= sizeof(struct svalue)) >= 0) {
	--svp;
	if (svp->type == T_OBJECT && svp->u.ob->flags & O_DESTRUCTED ||
	    ( svp->type == T_CLOSURE &&
	      ( CLOSURE_MALLOCED(svp->x.closure_type) ?
		  ( svp->x.closure_type != CLOSURE_UNBOUND_LAMBDA &&
		    svp->u.lambda->ob->flags & O_DESTRUCTED ) :
		  svp->u.ob->flags & O_DESTRUCTED ) ) )
	{
	    /* This key is / is bound to a destructed object. The entry has to
	     * be deleted (later).
	     */
	    if (svp->type == T_CLOSURE &&
		svp->x.closure_type == CLOSURE_BOUND_LAMBDA)
	    {
		/* We don't want changing keys, even if they are still valid
		 * unbound closures
		 */
		struct lambda *l = svp->u.lambda;

		svp->x.closure_type = CLOSURE_LAMBDA;
		svp->u.lambda = l->function.lambda;
		if (!l->ref) {
		    l->function.lambda->ob = l->ob;
		    l->ref = -1;
		    l->ob = (struct object *)stale_misc_closures;
		    stale_misc_closures = l;
		} else {
		    l->function.lambda->ob = gc_obj_list_destructed;
		}
	    }
	    count_ref_in_vector(svp, 1);
	    if (svp->type == T_CLOSURE) {
		/* *svp has been transformed into an efun closure bound
		 * to the master
		 */
		svp->u.ob->ref--;
	    }
	    svp->type = T_INVALID;
	    if (!any_destructed) {
		any_destructed = 1;
		/* Might be a small mapping. Don't malloc, it might get too
		 * much due to the global scope of garbage_collection.
		 * Since there was a previous
		 * compact_mappings(num_dirty_mappings) , the hash field is
		 * known to be 0.
		 */
		m->hash = (struct hash_mapping *)stale_mappings;
		stale_mappings = m;
		/* We are going to use free_svalue() later to get rid of the
		 * data asscoiated with the keys. This data might reference
		 * mappings with destructed keys... Thus, we must prevent
		 * free_mapping() to look at the hash field.
		 */
		m->ref++;
	    }
	} else {
	    count_ref_in_vector(svp, 1);
	}
    }
    size = m->condensed->misc_size * num_values;
    count_ref_in_vector(
      (struct svalue *)((char *)svp - size),
      size / sizeof *svp
    );
}

void clean_stale_mappings() {
    struct mapping *m, *next;

    for (m = stale_mappings; m; m = next) {
	struct condensed_mapping *cm, *cm2;
	char *cm2_start;
	mp_int size, data_size, deleted_size, preserved_size;
	mp_int i, num_deleted = 0, num_values;
	struct svalue *svp, *svp2, *data, *data2;

	next = (struct mapping *)m->hash;
	m->hash = 0;
	num_values = m->num_values;
	cm = m->condensed;
	svp = CM_MISC(cm);
	i = size = cm->misc_size;
	while ( (i -= sizeof(struct svalue)) >= 0) {
	    if ( (--svp)->type == T_INVALID)
		num_deleted++;
	}
	data_size = size * num_values;
	deleted_size = num_deleted * sizeof(struct svalue) * (num_values + 1);
	preserved_size = sizeof(*cm2) +
	  cm->string_size *
	  (1 + (sizeof(struct svalue)/sizeof(char *)) * num_values);
	m->user->mapping_total -= deleted_size;
	cm2_start = xalloc(data_size + size - deleted_size + preserved_size);
	cm2 = (struct condensed_mapping *)
	  (cm2_start + data_size + size - deleted_size);
	memcpy((char *)cm2, (char *)cm, preserved_size);
	cm2->misc_size = size - num_deleted * sizeof(struct svalue);
	data = svp;
	svp2 = CM_MISC(cm2);
	data2 = (struct svalue *)((char *)svp2 - size) + num_deleted;
	svp = CM_MISC(cm);
	i = size;
	while ( (i -= sizeof(struct svalue)) >= 0) {
	    if ( (--svp)->type == T_INVALID) {
		mp_int j;

		for (j = num_values; --j >= 0; ) {
		    free_svalue(--data);
		}
		continue;
	    }
	    *--svp2 = *svp;
	    data -= num_values;
	    data2 -= num_values;
	    memcpy(data2, data, num_values * sizeof(struct svalue));
	}
	m->condensed = cm2;
	xfree((char *)cm - data_size - size);
	free_mapping(m);
    }
}
#endif /* MALLOC_smalloc */