Select Git revision
-
Henrik (Grubba) Grubbström authored
Ensure that there are at least as many keypairs as buckets in created mappings. Fixes fatal "Pretty mean hashtable there buster!".
Henrik (Grubba) Grubbström authoredEnsure that there are at least as many keypairs as buckets in created mappings. Fixes fatal "Pretty mean hashtable there buster!".
mapping.c 70.57 KiB
/*
|| 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.
*/
#include "global.h"
#include "main.h"
#include "object.h"
#include "mapping.h"
#include "svalue.h"
#include "array.h"
#include "pike_macros.h"
#include "pike_error.h"
#include "pike_memory.h"
#include "pike_types.h"
#include "dynamic_buffer.h"
#include "interpret.h"
#include "las.h"
#include "gc.h"
#include "stralloc.h"
#include "pike_security.h"
#include "block_allocator.h"
#include "opcodes.h"
#include "stuff.h"
#define AVG_LINK_LENGTH 4
#define MIN_LINK_LENGTH 1
#define MAP_SLOTS(X) ((X)?((X)+((X)>>4)+8):0)
struct mapping *first_mapping;
struct mapping *gc_internal_mapping = 0;
static struct mapping *gc_mark_mapping_pos = 0;
#define unlink_mapping_data(M) do{ \
struct mapping_data *md_=(M); \
if(md_->hardlinks) { md_->hardlinks--; md_->valrefs--; } \
free_mapping_data(M); \
}while(0)
#define MAPPING_DATA_SIZE(HSIZE, KEYPAIRS) \
PTR_TO_INT(MD_KEYPAIRS(0, HSIZE) + KEYPAIRS)
static struct block_allocator mapping_allocator = BA_INIT_PAGES(sizeof(struct mapping), 2);
void count_memory_in_mappings(size_t * num, size_t * size) {
struct mapping *m;
double datasize = 0.0;
ba_count_all(&mapping_allocator, num, size);
for(m=first_mapping;m;m=m->next) {
datasize+=MAPPING_DATA_SIZE(m->data->hashsize, m->data->num_keypairs) / (double) m->data->refs;
}
*size += (size_t) datasize;
}
void really_free_mapping(struct mapping * m) {
#ifdef PIKE_DEBUG
if (m->refs) {
# ifdef DEBUG_MALLOC
describe_something(m, T_MAPPING, 0,2,0, NULL);
# endif
Pike_fatal("really free mapping on mapping with %d refs.\n", m->refs);
}
#endif
FREE_PROT(m);
unlink_mapping_data(m->data);
DOUBLEUNLINK(first_mapping, m);
GC_FREE(m);
ba_free(&mapping_allocator, m);
}
ATTRIBUTE((malloc))
static struct mapping * alloc_mapping() {
return ba_alloc(&mapping_allocator);
}
void free_all_mapping_blocks() {
ba_destroy(&mapping_allocator);
}
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
#define IF_ELSE_KEYPAIR_LOOP(X, Y) Y
#define FREE_KEYPAIR(md, k) do { \
k->next = md->free_list; \
md->free_list = k; \
} while(0)
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
#define IF_ELSE_KEYPAIR_LOOP(X, Y) X
#define FREE_KEYPAIR(md, k) do { \
md->free_list--; \
if (k != md->free_list) { \
struct keypair **prev_; \
unsigned INT32 h_; \
INT32 e; \
/* Move the last keypair to the new hole. */ \
*k = *(md->free_list); \
h_ = k->hval & ( md->hashsize - 1); \
prev_ = md->hash + h_; \
DO_IF_DEBUG( \
if (!*prev_) { \
Pike_fatal("Node to move not found!\n"); \
} \
); \
while (*prev_ != md->free_list) { \
prev_ = &((*prev_)->next); \
DO_IF_DEBUG( \
if (!*prev_) { \
Pike_fatal("Node to move not found!\n"); \
} \
); \
} \
*prev_ = k; \
} \
} while(0)
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
void mapping_free_keypair(struct mapping_data *md, struct keypair *k)
{
FREE_KEYPAIR(md, k);
}
static INLINE int check_type_contains(TYPE_FIELD types, const struct svalue * s) {
return (TYPEOF(*s) == PIKE_T_OBJECT || types & (BIT_OBJECT|(1 << TYPEOF(*s))));
}
static INLINE int check_type_overlaps(TYPE_FIELD t1, TYPE_FIELD t2) {
return (!t1 && !t2) || t1 & t2 || (t1|t2) & BIT_OBJECT;
}
#ifdef PIKE_DEBUG
/** This function checks that the type field isn't lacking any bits.
* It is used for debugging purposes only.
*/
static void check_mapping_type_fields(const struct mapping *m)
{
INT32 e;
const struct keypair *k=0;
const struct mapping_data *md;
TYPE_FIELD ind_types, val_types;
ind_types=val_types=0;
md = m->data;
NEW_MAPPING_LOOP(md)
{
if (TYPEOF(k->val) > MAX_TYPE)
Pike_fatal("Invalid mapping keypair value type: %s\n",
get_name_of_type(TYPEOF(k->val)));
val_types |= 1 << TYPEOF(k->val);
if (TYPEOF(k->ind) > MAX_TYPE)
Pike_fatal("Invalid maping keypair index type: %s\n",
get_name_of_type(TYPEOF(k->ind)));
ind_types |= 1 << TYPEOF(k->ind);
}
if(val_types & ~(m->data->val_types))
Pike_fatal("Mapping value types out of order!\n");
if(ind_types & ~(m->data->ind_types))
Pike_fatal("Mapping indices types out of order!\n");
}
#endif
static struct mapping_data empty_data =
{ PIKE_CONSTANT_MEMOBJ_INIT(1, T_MAPPING_DATA), 1, 0,0,0,0,0,0, 0,
IF_ELSE_KEYPAIR_LOOP((struct keypair *)&empty_data.hash, 0), {0}};
static struct mapping_data weak_ind_empty_data =
{ PIKE_CONSTANT_MEMOBJ_INIT(1, T_MAPPING_DATA), 1, 0,0,0,0,0,0, MAPPING_WEAK_INDICES,
IF_ELSE_KEYPAIR_LOOP((struct keypair *)&weak_ind_empty_data.hash, 0), {0}};
static struct mapping_data weak_val_empty_data =
{ PIKE_CONSTANT_MEMOBJ_INIT(1, T_MAPPING_DATA), 1, 0,0,0,0,0,0, MAPPING_WEAK_VALUES,
IF_ELSE_KEYPAIR_LOOP((struct keypair *)&weak_val_empty_data.hash, 0), {0}};
static struct mapping_data weak_both_empty_data =
{ PIKE_CONSTANT_MEMOBJ_INIT(1, T_MAPPING_DATA), 1, 0,0,0,0,0,0, MAPPING_WEAK,
IF_ELSE_KEYPAIR_LOOP((struct keypair *)&weak_both_empty_data.hash, 0), {0}};
/** This function allocates the hash table and svalue space for a mapping
* struct. The size is the max number of indices that can fit in the
* allocated space.
*/
static void init_mapping(struct mapping *m,
INT32 size,
INT16 flags)
{
struct mapping_data *md;
ptrdiff_t e;
INT32 hashsize;
debug_malloc_touch(m);
#ifdef PIKE_DEBUG
if (Pike_in_gc > GC_PASS_PREPARE && Pike_in_gc < GC_PASS_ZAP_WEAK)
Pike_fatal("Can't allocate a new mapping_data inside gc.\n");
if(size < 0) Pike_fatal("init_mapping with negative value.\n");
#endif
if(size)
{
hashsize=find_next_power(size / AVG_LINK_LENGTH + 1);
if (size < hashsize) size = hashsize;
e=MAPPING_DATA_SIZE(hashsize, size);
md=xcalloc(1,e);
m->data=md;
md->hashsize=hashsize;
md->free_list=MD_KEYPAIRS(md, hashsize);
#ifndef PIKE_MAPPING_KEYPAIR_LOOP for(e=1;e<size;e++)
{
md->free_list[e-1].next = md->free_list + e;
mark_free_svalue (&md->free_list[e-1].ind);
mark_free_svalue (&md->free_list[e-1].val);
}
/* md->free_list[e-1].next=0; */
mark_free_svalue (&md->free_list[e-1].ind);
mark_free_svalue (&md->free_list[e-1].val);
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
/* md->ind_types = 0; */
/* md->val_types = 0; */
md->flags = flags;
/* md->size = 0; */
/* md->refs=0; */
/* md->valrefs=0; */
/* md->hardlinks=0; */
md->num_keypairs=size;
}else{
switch (flags & MAPPING_WEAK) {
case 0: md = &empty_data; break;
case MAPPING_WEAK_INDICES: md = &weak_ind_empty_data; break;
case MAPPING_WEAK_VALUES: md = &weak_val_empty_data; break;
default: md = &weak_both_empty_data; break;
}
}
add_ref(md);
m->data=md;
#ifdef MAPPING_SIZE_DEBUG
m->debug_size = md->size;
#endif
}
/** This function allocates an empty mapping with initial room
* for 'size' values.
*
* @param size initial number of values
* @return the newly allocated mapping
* @see do_free_mapping
* @see free_mapping
*/
PMOD_EXPORT struct mapping *debug_allocate_mapping(int size)
{
struct mapping *m;
m=alloc_mapping();
GC_ALLOC(m);
INITIALIZE_PROT(m);
init_mapping(m,size,0);
m->refs = 0;
add_ref(m); /* For DMALLOC... */
DOUBLELINK(first_mapping, m);
return m;
}
PMOD_EXPORT void really_free_mapping_data(struct mapping_data *md)
{
INT32 e;
struct keypair *k;
debug_malloc_touch(md);
#ifdef PIKE_DEBUG
if (md->refs) {
Pike_fatal("really_free_mapping_data(): md has non-zero refs: %d\n", md->refs);
}
#endif /* PIKE_DEBUG */
NEW_MAPPING_LOOP(md)
{
free_svalue(& k->val);
free_svalue(& k->ind);
}
free(md);
GC_FREE_BLOCK(md);
}
PMOD_EXPORT void do_free_mapping(struct mapping *m)
{
if (m)
inl_free_mapping(m);
}
/* This function is used to rehash a mapping without losing the internal
* order in each hash chain. This is to prevent mappings from becoming
* inefficient just after being rehashed.
*/
/* Evil: Steal the svalues from the old md. */
static void mapping_rehash_backwards_evil(struct mapping_data *md,
struct keypair *from)
{
unsigned INT32 h;
struct keypair *k, *prev = NULL, *next;
if(!(k = from)) return;
/* Reverse the hash chain. */
while ((next = k->next)) {
k->next = prev;
prev = k;
k = next;
}
k->next = prev;
prev = k;
/* Rehash and reverse the hash chain. */
while ((from = prev)) {
/* Reverse */
prev = from->next;
from->next = next;
next = from;
if (md->flags & MAPPING_WEAK) {
switch(md->flags & MAPPING_WEAK) {
default:
Pike_fatal("Instable mapping data flags.\n");
case MAPPING_WEAK_INDICES:
if (!REFCOUNTED_TYPE(TYPEOF(from->ind)) ||
(*from->ind.u.refs > 1)) {
goto keep_keypair;
}
break;
case MAPPING_WEAK_VALUES:
if (!REFCOUNTED_TYPE(TYPEOF(from->val)) ||
(*from->val.u.refs > 1)) {
goto keep_keypair;
}
break;
case MAPPING_WEAK:
/* NB: Compat: Unreference counted values are counted
* as multi-referenced here. */
if ((!REFCOUNTED_TYPE(TYPEOF(from->ind)) ||
(*from->ind.u.refs > 1)) &&
(!REFCOUNTED_TYPE(TYPEOF(from->val)) ||
(*from->val.u.refs > 1))) {
goto keep_keypair;
}
break;
}
/* Free.
* Note that we don't need to free or unlink the keypair,
* since that will be done by the caller anyway. */
free_svalue(&from->ind);
free_svalue(&from->val);
continue;
}
keep_keypair:
/* unlink */
k=md->free_list;
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
#ifdef PIKE_DEBUG
if(!k) Pike_fatal("Error in rehash: not enough keypairs.\n");
#endif
md->free_list=k->next;
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
md->free_list++;
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
/* initialize */
*k=*from;
/* link */
h=k->hval;
h&=md->hashsize - 1;
k->next=md->hash[h];
md->hash[h]=k;
/* update */
md->ind_types |= 1<< (TYPEOF(k->ind));
md->val_types |= 1<< (TYPEOF(k->val));
md->size++;
}
}
/* Good: Copy the svalues from the old md. */
static void mapping_rehash_backwards_good(struct mapping_data *md,
struct keypair *from)
{
unsigned INT32 h;
struct keypair *k, *prev = NULL, *next;
if(!(k = from)) return;
/* Reverse the hash chain. */
while ((next = k->next)) {
k->next = prev;
prev = k;
k = next;
}
k->next = prev;
prev = k;
/* Rehash and reverse the hash chain. */
while ((from = prev)) {
/* Reverse */
prev = from->next; from->next = next;
next = from;
if (md->flags & MAPPING_WEAK) {
switch(md->flags & MAPPING_WEAK) {
default:
Pike_fatal("Instable mapping data flags.\n");
case MAPPING_WEAK_INDICES:
if (REFCOUNTED_TYPE(TYPEOF(from->ind)) &&
(*from->ind.u.refs > 1)) {
goto keep_keypair;
}
break;
case MAPPING_WEAK_VALUES:
if (REFCOUNTED_TYPE(TYPEOF(from->val)) &&
(*from->val.u.refs > 1)) {
goto keep_keypair;
}
break;
case MAPPING_WEAK:
/* NB: Compat: Unreference counted values are counted
* as multi-referenced here.
*/
if ((!REFCOUNTED_TYPE(TYPEOF(from->ind)) ||
(*from->ind.u.refs > 1)) &&
(!REFCOUNTED_TYPE(TYPEOF(from->val)) ||
(*from->val.u.refs > 1))) {
goto keep_keypair;
}
break;
}
/* Skip copying of this keypair.
*
* NB: We can't mess with the original md here,
* since it might be in use by an iterator
* or similar.
*/
continue;
}
keep_keypair:
/* unlink */
k=md->free_list;
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
#ifdef PIKE_DEBUG
if(!k) Pike_fatal("Error in rehash: not enough keypairs.\n");
#endif
md->free_list=k->next;
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
md->free_list++;
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
/* initialize */
k->hval=from->hval;
assign_svalue_no_free(&k->ind, &from->ind);
assign_svalue_no_free(&k->val, &from->val);
/* link */
h=k->hval;
h&=md->hashsize - 1;
k->next=md->hash[h];
md->hash[h]=k;
/* update */
md->ind_types |= 1<< (TYPEOF(k->ind));
md->val_types |= 1<< (TYPEOF(k->val));
md->size++; }
}
/** This function re-allocates a mapping. It adjusts the max no. of
* values can be fitted into the mapping. It takes a bit of time to
* run, but is used seldom enough not to degrade preformance significantly.
*
* @param m the mapping to be rehashed
* @param new_size new mappingsize
* @return the rehashed mapping
*/
static struct mapping *rehash(struct mapping *m, int new_size)
{
struct mapping_data *md, *new_md;
#ifdef PIKE_DEBUG
INT32 tmp=m->data->size;
#endif
INT32 e;
md=m->data;
debug_malloc_touch(md);
#ifdef PIKE_DEBUG
if(md->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
if(d_flag>1) check_mapping(m);
#endif
/* FIXME: The special case below seems suspect.
* /grubba 2011-09-04
*/
if ((md->hashsize == new_size) && (md->refs == 1)) return m;
init_mapping(m, new_size, md->flags);
debug_malloc_touch(m);
new_md=m->data;
/* This operation is now 100% atomic - no locking required */
if(md->refs>1)
{
/* good */
/* More than one reference to the md ==> We need to
* keep it afterwards.
*/
for(e=0;e<md->hashsize;e++)
mapping_rehash_backwards_good(new_md, md->hash[e]);
unlink_mapping_data(md);
}else{
/* evil */
/* We have the only reference to the md,
* so we can just copy the svalues without
* bothering about type checking.
*/
for(e=0;e<md->hashsize;e++)
mapping_rehash_backwards_evil(new_md, md->hash[e]);
free(md);
GC_FREE_BLOCK(md);
}
#ifdef PIKE_DEBUG
if((m->data->size != tmp) &&
((m->data->size > tmp) || !(m->data->flags & MAPPING_WEAK)))
Pike_fatal("Rehash failed, size not same any more (%ld != %ld).\n",
(long)m->data->size, (long)tmp);
#endif
#ifdef MAPPING_SIZE_DEBUG
m->debug_size = m->data->size;
#endif
#ifdef PIKE_DEBUG
if(d_flag>1) check_mapping(m);
#endif
return m;
}
/*
* No need for super efficiency, should not be called very often
* -Hubbe
*/
#define LOW_RELOC(X) X= (void *) ((char *)(X) + off);
#define RELOC(X) if(X) LOW_RELOC(X)
struct mapping_data *copy_mapping_data(struct mapping_data *md)
{
long e;
ptrdiff_t size, off;
struct mapping_data *nmd;
struct keypair *keypairs;
#ifdef PIKE_DEBUG
if (Pike_in_gc > GC_PASS_PREPARE && Pike_in_gc < GC_PASS_ZAP_WEAK)
Pike_fatal("Can't allocate a new mapping_data inside gc.\n");
#endif
debug_malloc_touch(md);
size=MAPPING_DATA_SIZE(md->hashsize, md->num_keypairs);
nmd=(struct mapping_data *)xalloc(size);
MEMCPY(nmd, md, size);
off=((char *)nmd) - ((char *)md);
RELOC(nmd->free_list);
for(e=0;e<nmd->hashsize;e++) RELOC(nmd->hash[e]);
keypairs=MD_KEYPAIRS(nmd, nmd->hashsize);
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
for(e=0;e<nmd->num_keypairs;e++)
{
RELOC(keypairs[e].next);
add_ref_svalue(& keypairs[e].ind);
add_ref_svalue(& keypairs[e].val);
}
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
for(e=0;e<nmd->size;e++)
{
RELOC(keypairs[e].next);
add_ref_svalue(& keypairs[e].ind);
add_ref_svalue(& keypairs[e].val);
}
#endif /* PIKE_MAPPING_KEYPAIR_LOOP */
nmd->refs=0;
add_ref(nmd); /* For DMALLOC... */
nmd->valrefs=0;
nmd->hardlinks=0;
/* FIXME: What about nmd->flags? */
if(md->hardlinks)
{
#ifdef PIKE_DEBUG
if(md->refs <= 0 || md->valrefs<=0)
Pike_fatal("Hardlink without refs/valrefs!\n");
#endif
md->hardlinks--;
md->valrefs--; }
sub_ref(md);
return nmd;
}
#define MAPPING_DATA_IN_USE(MD) ((MD)->refs != (MD)->hardlinks + 1)
#define LOW_FIND(FUN, KEY, FOUND, NOT_FOUND) do { \
md=m->data; \
add_ref(md); \
if(md->hashsize) \
{ \
h=h2 & (md->hashsize - 1); \
DO_IF_DEBUG( if(d_flag > 1) check_mapping_type_fields(m); ) \
if(check_type_contains(md->ind_types, key)) \
{ \
for(prev= md->hash + h;(k=*prev);prev=&k->next) \
{ \
if(h2 == k->hval && FUN(& k->ind, KEY)) \
{ \
FOUND; \
} \
} \
} \
} \
NOT_FOUND; \
}while(0)
#define LOW_FIND2(FUN, KEY, FOUND, NOT_FOUND) do { \
struct keypair *k2; \
md=m->data; \
add_ref(md); \
if(md->hashsize) \
{ \
h=h2 & (md->hashsize-1); \
DO_IF_DEBUG( if(d_flag > 1) check_mapping_type_fields(m); ) \
if(check_type_contains(md->ind_types, key)) \
{ \
k2=omd->hash[h2 & (omd->hashsize - 1)]; \
prev= md->hash + h; \
for(;(k=*prev) && k2;(prev=&k->next),(k2=k2->next)) \
if(!(h2 == k->hval && is_identical(&k2->ind, &k->ind))) \
break; \
for(;(k=*prev);prev=&k->next) \
{ \
if(FUN(& k->ind, KEY)) \
{ \
FOUND; \
} \
} \
} \
} \
NOT_FOUND; \
}while(0)
#define SAME_DATA(SAME,NOT_SAME) \
if(m->data == md) \
{ \
SAME; \
}else{ \
NOT_SAME; \
}
/* FIXME: the 'no action' might need to be fixed.... */
#define FIND() do{ \
LOW_FIND(is_eq, key, \ omd=md; \
SAME_DATA( break, \
struct svalue *tmp=&k->ind; \
LOW_FIND(is_identical, tmp, break, ;); \
free_mapping_data(omd)), \
break); \
free_mapping_data(md); \
}while(0)
/* Assumes md is *NOT* locked */
#define COPYMAP2() do { \
ptrdiff_t off; \
m->data=copy_mapping_data(m->data); \
debug_malloc_touch(m->data); \
DO_IF_DEBUG( if(d_flag>1) check_mapping(m); ) \
off=((char *)m->data)-((char *)md); \
LOW_RELOC(k); \
LOW_RELOC(prev); \
md=m->data; \
}while(0)
#define PREPARE_FOR_DATA_CHANGE2() \
if(md->valrefs) COPYMAP2()
#define PREPARE_FOR_INDEX_CHANGE2() \
if(md->refs>1) COPYMAP2()
#define PROPAGATE() do { \
if(md->refs==1) \
{ \
h=h2 & (md->hashsize - 1); \
*prev=k->next; \
k->next=md->hash[h]; \
md->hash[h]=k; \
} \
}while(0)
/* Assumes md is locked */
#define COPYMAP() do { \
ptrdiff_t off; \
m->data=copy_mapping_data(m->data); \
debug_malloc_touch(m->data); \
off=((char *)m->data)-((char *)md); \
LOW_RELOC(k); \
free_mapping_data(md); \
md=m->data; \
add_ref(md); \
}while(0)
#define PREPARE_FOR_DATA_CHANGE() \
if(md->valrefs) COPYMAP()
#define PREPARE_FOR_INDEX_CHANGE() \
if(md->refs>1) COPYMAP()
/** This function brings the type fields in the mapping up to speed.
* It should be used only when the type fields MUST be correct, which is not
* very often.
*/
PMOD_EXPORT void mapping_fix_type_field(struct mapping *m)
{
INT32 e;
struct keypair *k;
TYPE_FIELD ind_types, val_types;
val_types = ind_types = 0;
NEW_MAPPING_LOOP(m->data) {
val_types |= 1 << TYPEOF(k->val);
ind_types |= 1 << TYPEOF(k->ind);
}
#ifdef PIKE_DEBUG
if(val_types & ~(m->data->val_types))
Pike_fatal("Mapping value types out of order!\n");
if(ind_types & ~(m->data->ind_types))
Pike_fatal("Mapping indices types out of order!\n");
#endif
m->data->val_types = val_types;
m->data->ind_types = ind_types;
}
PMOD_EXPORT void mapping_set_flags(struct mapping *m, int flags)
{
struct mapping_data *md = m->data;
if ((md->flags != flags) && (md->refs > 1)) {
struct keypair *k = NULL, *prev = NULL;
COPYMAP2();
md = m->data;
}
#ifdef PIKE_DEBUG
if(flags & MAPPING_WEAK)
{
debug_malloc_touch(m);
debug_malloc_touch(md);
}
else
{
debug_malloc_touch(m);
debug_malloc_touch(md);
}
#endif
md->flags = flags;
}
PMOD_EXPORT void low_mapping_insert(struct mapping *m,
const struct svalue *key,
const struct svalue *val,
int overwrite)
{
unsigned INT32 h,h2;
struct keypair *k, **prev;
struct mapping_data *md, *omd;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
h2=hash_svalue(key);
#ifdef PIKE_DEBUG
if(d_flag>1) check_mapping(m);
#endif
LOW_FIND(is_eq, key,
struct svalue *tmp=&k->ind;
SAME_DATA(goto mi_set_value,
omd=md;
LOW_FIND(is_identical, tmp,
free_mapping_data(omd);
goto mi_set_value,
free_mapping_data(omd);
goto mi_do_nothing)),
Z: SAME_DATA(goto mi_insert,
omd=md;
LOW_FIND2(is_eq, key,
free_mapping_data(omd);
goto mi_do_nothing,
free_mapping_data(omd);
goto Z)));
mi_do_nothing:
free_mapping_data(md);
return;
mi_set_value:
#ifdef PIKE_DEBUG
if(m->data != md)
Pike_fatal("Wrong dataset in mapping_insert!\n");
if(d_flag>1) check_mapping(m);
#endif
free_mapping_data(md);
if(!overwrite) return;
PREPARE_FOR_DATA_CHANGE2();
PROPAGATE(); /* propagate after preparing */
md->val_types |= 1 << TYPEOF(*val);
if (overwrite == 2 && TYPEOF(*key) == T_OBJECT)
/* Should replace the index too. It's only for objects that it's
* possible to tell the difference. */
assign_svalue (&k->ind, key);
assign_svalue(& k->val, val);
#ifdef PIKE_DEBUG
if(d_flag>1) check_mapping(m);
#endif
return;
mi_insert:
#ifdef PIKE_DEBUG
if(m->data != md)
Pike_fatal("Wrong dataset in mapping_insert!\n");
if(d_flag>1) check_mapping(m);
#endif
free_mapping_data(md);
/* We do a re-hash here instead of copying the mapping. */
if(
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
(!md->free_list) ||
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
(md->size >= md->num_keypairs) ||
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
md->refs>1)
{
debug_malloc_touch(m);
rehash(m, md->size * 2 + 2);
md=m->data;
}
h=h2 & ( md->hashsize - 1);
/* no need to lock here since we are not calling is_eq - Hubbe */
k=md->free_list;
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
md->free_list=k->next;
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
md->free_list++;
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
k->next=md->hash[h];
md->hash[h]=k;
md->ind_types |= 1 << TYPEOF(*key);
md->val_types |= 1 << TYPEOF(*val);
assign_svalue_no_free(& k->ind, key);
assign_svalue_no_free(& k->val, val);
k->hval = h2; md->size++;
#ifdef MAPPING_SIZE_DEBUG
if(m->data ==md)
m->debug_size++;
#endif
#ifdef PIKE_DEBUG
if(d_flag>1) check_mapping(m);
#endif
}
PMOD_EXPORT void mapping_insert(struct mapping *m,
const struct svalue *key,
const struct svalue *val)
{
low_mapping_insert(m,key,val,1);
}
/* Inline the above in this file. */
#define mapping_insert(M, KEY, VAL) low_mapping_insert ((M), (KEY), (VAL), 1)
PMOD_EXPORT union anything *mapping_get_item_ptr(struct mapping *m,
const struct svalue *key,
TYPE_T t)
{
unsigned INT32 h, h2;
struct keypair *k, **prev;
struct mapping_data *md,*omd;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
if(d_flag>1) check_mapping(m);
debug_malloc_touch(m);
debug_malloc_touch(m->data);
#endif
h2=hash_svalue(key);
LOW_FIND(is_eq, key,
struct svalue *tmp=&k->ind;
SAME_DATA(goto mg_set_value,
omd=md;
LOW_FIND(is_identical, tmp,
free_mapping_data(omd);
goto mg_set_value,
free_mapping_data(omd);
goto mg_do_nothing)),
Z:
SAME_DATA(goto mg_insert,
omd=md;
LOW_FIND2(is_eq, key,
free_mapping_data(omd);
goto mg_do_nothing,
free_mapping_data(omd);
goto Z)));
mg_do_nothing:
free_mapping_data(md);
return 0;
mg_set_value:
#ifdef PIKE_DEBUG
if(m->data != md)
Pike_fatal("Wrong dataset in mapping_get_item_ptr!\n");
if(d_flag) check_mapping(m);
#endif
free_mapping_data(md);
if(TYPEOF(k->val) == t)
{
PREPARE_FOR_DATA_CHANGE2();
PROPAGATE(); /* prepare then propagate */
return & ( k->val.u );
}
return 0;
mg_insert:
#ifdef PIKE_DEBUG
if(m->data != md)
Pike_fatal("Wrong dataset in mapping_get_item_ptr!\n");
if(d_flag)
check_mapping(m);
#endif
free_mapping_data(md);
if(t != T_INT) return 0;
/* no need to call PREPARE_* because we re-hash instead */
if(
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
!(md->free_list) ||
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
(md->size >= md->num_keypairs) ||
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
md->refs>1)
{
debug_malloc_touch(m);
rehash(m, md->size * 2 + 2);
md=m->data;
}
h=h2 & ( md->hashsize - 1);
k=md->free_list;
#ifndef PIKE_MAPPING_KEYPAIR_LOOP
md->free_list=k->next;
#else /* PIKE_MAPPING_KEYPAIR_LOOP */
md->free_list++;
#endif /* !PIKE_MAPPING_KEYPAIR_LOOP */
k->next=md->hash[h];
md->hash[h]=k;
assign_svalue_no_free(& k->ind, key);
SET_SVAL(k->val, T_INT, NUMBER_NUMBER, integer, 0);
k->hval = h2;
md->ind_types |= 1 << TYPEOF(*key);
md->val_types |= BIT_INT;
md->size++;
#ifdef MAPPING_SIZE_DEBUG
if(m->data ==md)
m->debug_size++;
#endif
#ifdef PIKE_DEBUG
if(d_flag > 1) check_mapping_type_fields(m);
#endif
return & ( k->val.u );
}
PMOD_EXPORT void map_delete_no_free(struct mapping *m,
const struct svalue *key,
struct svalue *to)
{
unsigned INT32 h,h2; struct keypair *k, **prev;
struct mapping_data *md,*omd;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
if(d_flag>1) check_mapping(m);
debug_malloc_touch(m);
#endif
h2=hash_svalue(key);
LOW_FIND(is_eq, key,
struct svalue *tmp=&k->ind;
SAME_DATA(goto md_remove_value,
omd=md;
LOW_FIND(is_identical, tmp,
free_mapping_data(omd);
goto md_remove_value,
free_mapping_data(omd);
goto md_do_nothing)),
goto md_do_nothing);
md_do_nothing:
debug_malloc_touch(m);
free_mapping_data(md);
if(to)
{
SET_SVAL(*to, T_INT, NUMBER_UNDEFINED, integer, 0);
}
return;
md_remove_value:
#ifdef PIKE_DEBUG
if(md->refs <= 1)
Pike_fatal("Too few refs i mapping->data\n");
if(m->data != md)
Pike_fatal("Wrong dataset in mapping_delete!\n");
if(d_flag>1) check_mapping(m);
debug_malloc_touch(m);
#endif
free_mapping_data(md);
PREPARE_FOR_INDEX_CHANGE2();
/* No need to propagate */
*prev=k->next;
free_svalue(& k->ind);
if(to)
move_svalue (to, &k->val);
else
free_svalue(& k->val);
FREE_KEYPAIR(md, k);
mark_free_svalue (&md->free_list->ind);
mark_free_svalue (&md->free_list->val);
md->size--;
#ifdef MAPPING_SIZE_DEBUG
if(m->data ==md)
m->debug_size--;
#endif
if(md->size < (md->hashsize + 1) * MIN_LINK_LENGTH)
{
debug_malloc_touch(m);
rehash(m, MAP_SLOTS(m->data->size));
}
#ifdef PIKE_DEBUG
if(d_flag>1) check_mapping(m);#endif
return;
}
PMOD_EXPORT void check_mapping_for_destruct(struct mapping *m)
{
INT32 e;
struct keypair *k, **prev;
TYPE_FIELD ind_types, val_types;
struct mapping_data *md=m->data;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
if(d_flag>1) check_mapping(m);
debug_malloc_touch(m);
if (Pike_in_gc > GC_PASS_PREPARE && Pike_in_gc < GC_PASS_FREE)
Pike_fatal("check_mapping_for_destruct called in invalid pass inside gc.\n");
#endif
/* no is_eq -> no locking */
if(!md->size) return;
if((md->ind_types | md->val_types) & (BIT_OBJECT | BIT_FUNCTION))
{
val_types = ind_types = 0;
md->val_types |= BIT_INT;
for(e=0;e<md->hashsize;e++)
{
for(prev= md->hash + e;(k=*prev);)
{
check_destructed(& k->val);
if((TYPEOF(k->ind) == T_OBJECT || TYPEOF(k->ind) == T_FUNCTION) &&
!k->ind.u.object->prog)
{
debug_malloc_touch(m);
debug_malloc_touch(md);
PREPARE_FOR_INDEX_CHANGE2();
*prev=k->next;
free_svalue(& k->ind);
free_svalue(& k->val);
FREE_KEYPAIR(md, k);
mark_free_svalue (&md->free_list->ind);
mark_free_svalue (&md->free_list->val);
md->size--;
#ifdef MAPPING_SIZE_DEBUG
if(m->data ==md)
{
m->debug_size++;
debug_malloc_touch(m);
}
#endif
debug_malloc_touch(md);
}else{
val_types |= 1 << TYPEOF(k->val);
ind_types |= 1 << TYPEOF(k->ind);
prev=&k->next;
}
}
}
md->val_types = val_types;
md->ind_types = ind_types;
if(MAP_SLOTS(md->size) < md->hashsize * MIN_LINK_LENGTH)
{
debug_malloc_touch(m); rehash(m, MAP_SLOTS(md->size));
}
#ifdef PIKE_DEBUG
if(d_flag>1) check_mapping(m);
#endif
}
}
PMOD_EXPORT struct svalue *low_mapping_lookup(struct mapping *m,
const struct svalue *key)
{
unsigned INT32 h,h2;
struct keypair *k=0, **prev=0;
struct mapping_data *md, *omd;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
if(d_flag>1) check_mapping(m);
#endif
h2=hash_svalue(key);
#ifdef PIKE_DEBUG
if(d_flag > 1) check_mapping_type_fields(m);
#endif
FIND();
if(k)
{
PROPAGATE();
return &k->val;
}
return 0;
}
PMOD_EXPORT struct svalue *low_mapping_string_lookup(struct mapping *m,
struct pike_string *p)
{
struct svalue tmp;
SET_SVAL(tmp, T_STRING, 0, string, p);
return low_mapping_lookup(m, &tmp);
}
PMOD_EXPORT void mapping_string_insert(struct mapping *m,
struct pike_string *p,
const struct svalue *val)
{
struct svalue tmp;
SET_SVAL(tmp, T_STRING, 0, string, p);
mapping_insert(m, &tmp, val);
}
PMOD_EXPORT void mapping_string_insert_string(struct mapping *m,
struct pike_string *p,
struct pike_string *val)
{
struct svalue tmp;
SET_SVAL(tmp, T_STRING, 0, string, val);
mapping_string_insert(m, p, &tmp);
}
PMOD_EXPORT struct svalue *simple_mapping_string_lookup(struct mapping *m,
const char *p)
{
struct pike_string *tmp;
if((tmp=findstring(p)))
return low_mapping_string_lookup(m,tmp);
return 0;
}
/* Lookup in a mapping of mappings */
PMOD_EXPORT struct svalue *mapping_mapping_lookup(struct mapping *m,
const struct svalue *key1,
const struct svalue *key2,
int create)
{
struct svalue tmp;
struct mapping *m2;
struct svalue *s=low_mapping_lookup(m, key1);
debug_malloc_touch(m);
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
if(!s || TYPEOF(*s) != T_MAPPING)
{
if(!create) return 0;
SET_SVAL(tmp, T_MAPPING, 0, mapping, allocate_mapping(5));
mapping_insert(m, key1, &tmp);
debug_malloc_touch(m);
debug_malloc_touch(tmp.u.mapping);
free_mapping(tmp.u.mapping); /* There is one ref in 'm' */
s=&tmp;
}
m2=s->u.mapping;
debug_malloc_touch(m2);
s=low_mapping_lookup(m2, key2);
if(s) return s;
if(!create) return 0;
SET_SVAL(tmp, T_INT, NUMBER_UNDEFINED, integer, 0);
mapping_insert(m2, key2, &tmp);
debug_malloc_touch(m2);
return low_mapping_lookup(m2, key2);
}
PMOD_EXPORT struct svalue *mapping_mapping_string_lookup(struct mapping *m,
struct pike_string *key1,
struct pike_string *key2,
int create)
{
struct svalue k1,k2;
SET_SVAL(k1, T_STRING, 0, string, key1);
SET_SVAL(k2, T_STRING, 0, string, key2);
return mapping_mapping_lookup(m,&k1,&k2,create);
}
PMOD_EXPORT void mapping_index_no_free(struct svalue *dest,
struct mapping *m,
const struct svalue *key)
{
struct svalue *p;
if(!IS_DESTRUCTED (key) && (p=low_mapping_lookup(m,key)))
{
assign_svalue_no_free(dest, p);
/* Never return NUMBER_UNDEFINED for existing entries. */
/* Note: There is code that counts on storing UNDEFINED in mapping
* values (using e.g. low_mapping_lookup to get them), so we have
* to fix the subtype here rather than in mapping_insert. */
if(TYPEOF(*p) == T_INT) SET_SVAL_SUBTYPE(*dest, NUMBER_NUMBER);
}else{
SET_SVAL(*dest, T_INT, NUMBER_UNDEFINED, integer, 0);
}
}
PMOD_EXPORT struct array *mapping_indices(struct mapping *m)
{
INT32 e;
struct array *a;
struct svalue *s;
struct keypair *k;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
check_mapping_for_destruct(m);
a=allocate_array(m->data->size);
s=ITEM(a);
/* no locking required */
NEW_MAPPING_LOOP(m->data) assign_svalue(s++, & k->ind);
a->type_field = m->data->ind_types;
#ifdef PIKE_DEBUG
if(d_flag > 1) check_mapping_type_fields(m);
#endif
return a;
}
PMOD_EXPORT struct array *mapping_values(struct mapping *m)
{
INT32 e;
struct keypair *k;
struct array *a;
struct svalue *s;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
check_mapping_for_destruct(m);
a=allocate_array(m->data->size);
s=ITEM(a);
/* no locking required */
NEW_MAPPING_LOOP(m->data) assign_svalue(s++, & k->val);
a->type_field = m->data->val_types;
#ifdef PIKE_DEBUG
if(d_flag > 1) check_mapping_type_fields(m);
#endif
return a;
}
PMOD_EXPORT struct array *mapping_to_array(struct mapping *m)
{
INT32 e;
struct keypair *k;
struct array *a;
struct svalue *s;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
a=allocate_array(m->data->size);
s=ITEM(a);
/* no locking required */
NEW_MAPPING_LOOP(m->data)
{
struct array *b=allocate_array(2);
assign_svalue(b->item+0, & k->ind);
assign_svalue(b->item+1, & k->val);
b->type_field = (1 << TYPEOF(k->ind)) | (1 << TYPEOF(k->val));
SET_SVAL(*s, T_ARRAY, 0, array, b);
s++;
}
a->type_field = BIT_ARRAY;
return a;
}
PMOD_EXPORT void mapping_replace(struct mapping *m,struct svalue *from, struct svalue *to)
{
INT32 e;
struct keypair *k;
struct mapping_data *md;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
md=m->data;
if(md->size)
{
add_ref(md);
NEW_MAPPING_LOOP(md)
{
if(is_eq(& k->val, from))
{
PREPARE_FOR_DATA_CHANGE();
assign_svalue(& k->val, to);
md->val_types |= 1<<TYPEOF(*to);
}
}
free_mapping_data(md);
}
#ifdef PIKE_DEBUG
if(d_flag > 1) check_mapping_type_fields(m);
#endif
}
PMOD_EXPORT struct mapping *mkmapping(struct array *ind, struct array *val)
{
struct mapping *m;
struct svalue *i,*v;
INT32 e;
#ifdef PIKE_DEBUG
if(ind->size != val->size)
Pike_fatal("mkmapping on different sized arrays.\n");
#endif
m=allocate_mapping(MAP_SLOTS(ind->size));
i=ITEM(ind);
v=ITEM(val); for(e=0;e<ind->size;e++) low_mapping_insert(m, i++, v++, 2);
return m;
}
/* deferred mapping copy! */
PMOD_EXPORT struct mapping *copy_mapping(struct mapping *m)
{
struct mapping *n;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
n=allocate_mapping(0);
debug_malloc_touch(n->data);
free_mapping_data(n->data);
n->data=m->data;
#ifdef MAPPING_SIZE_DEBUG
n->debug_size=n->data->size;
#endif
add_ref(n->data);
n->data->valrefs++;
n->data->hardlinks++;
debug_malloc_touch(n->data);
return n;
}
/* copy_mapping() for when destructive operations are ok.
*
* Note: It destructive operations on the resulting mapping *will*
* affect eg NEW_MAPPING_LOOP() on the original mapping.
*/
static struct mapping *destructive_copy_mapping(struct mapping *m)
{
if ((m->refs == 1) && !m->data->hardlinks &&
!(m->data->flags & MAPPING_WEAK)) {
/* We may perform destructive operations on the mapping. */
add_ref(m);
return m;
}
return copy_mapping(m);
}
/* NOTE: May perform destructive operations on either of the arguments
* if it has only a single reference.
*/
static struct mapping *subtract_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e;
ONERROR err;
/* First some special cases. */
if (!a_md->size || !b_md->size || !a_md->hashsize || !b_md->hashsize) {
return destructive_copy_mapping(a);
}
if (a_md == b_md) {
return allocate_mapping(0);
}
/* FIXME: The break-even point should probably be researched. */
if (a_md->size < b_md->size) {
/* Add the elements in a that aren't in b. */
res = allocate_mapping(a_md->size);
SET_ONERROR(err, do_free_mapping, res);
NEW_MAPPING_LOOP(a_md) { size_t h = k->hval & ( b_md->hashsize - 1);
struct keypair *k2;
for (k2 = b_md->hash[h]; k2; k2 = k2->next) {
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) {
break;
}
}
if (!k2) {
mapping_insert(res, &k->ind, &k->val);
}
}
} else {
/* Remove the elements in a that are in b. */
res = destructive_copy_mapping(a);
SET_ONERROR(err, do_free_mapping, res);
NEW_MAPPING_LOOP(b_md) {
map_delete(res, &k->ind);
}
}
UNSET_ONERROR(err);
return res;
}
/* NOTE: May perform destructive operations on either of the arguments
* if it has only a single reference.
*/
static struct mapping *and_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e;
ONERROR err;
/* First some special cases. */
if (!a_md->size || !b_md->size) return allocate_mapping(0);
if (a_md == b_md) return destructive_copy_mapping(a);
/* Copy the second mapping. */
res = copy_mapping(b);
SET_ONERROR(err, do_free_mapping, res);
/* Remove elements in res that aren't in a. */
NEW_MAPPING_LOOP(b_md) {
size_t h = k->hval & ( a_md->hashsize - 1);
struct keypair *k2;
for (k2 = a_md->hash[h]; k2; k2 = k2->next) {
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) {
break;
}
}
if (!k2) {
map_delete(res, &k->ind);
}
}
UNSET_ONERROR(err);
return res;
}
/* NOTE: May perform destructive operations on either of the arguments
* if it has only a single reference.
*/
static struct mapping *or_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e; ONERROR err;
/* First some special cases. */
if (!a_md->size) return destructive_copy_mapping(b);
if (!b_md->size) return destructive_copy_mapping(a);
if (a_md == b_md) return destructive_copy_mapping(a);
if (a_md->size <= b_md->size) {
/* Copy the second mapping. */
res = destructive_copy_mapping(b);
SET_ONERROR(err, do_free_mapping, res);
if (!b_md->hashsize) {
Pike_fatal("Invalid hashsize.\n");
}
/* Add elements in a that aren't in b. */
NEW_MAPPING_LOOP(a_md) {
size_t h = k->hval & ( b_md->hashsize - 1);
struct keypair *k2;
for (k2 = b_md->hash[h]; k2; k2 = k2->next) {
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) {
break;
}
}
if (!k2) {
mapping_insert(res, &k->ind, &k->val);
b_md = b->data;
}
}
UNSET_ONERROR(err);
} else {
/* Copy the first mapping. */
res = destructive_copy_mapping(a);
SET_ONERROR(err, do_free_mapping, res);
/* Add all elements in b. */
NEW_MAPPING_LOOP(b_md) {
mapping_insert(res, &k->ind, &k->val);
}
UNSET_ONERROR(err);
}
return res;
}
/* NOTE: May perform destructive operations on either of the arguments
* if it has only a single reference.
*/
static struct mapping *xor_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e;
ONERROR err;
/* First some special cases. */
if (!a_md->size) return destructive_copy_mapping(b);
if (!b_md->size) return destructive_copy_mapping(a);
if (a_md == b_md) return allocate_mapping(0);
/* Copy the largest mapping. */
if (a_md->size > b_md->size) {
struct mapping *tmp = a;
a = b;
b = tmp;
a_md = b_md;
b_md = b->data;
} res = destructive_copy_mapping(b);
SET_ONERROR(err, do_free_mapping, res);
/* Add elements in a that aren't in b, and remove those that are. */
NEW_MAPPING_LOOP(a_md) {
size_t h = k->hval & ( b_md->hashsize - 1);
struct keypair *k2;
for (k2 = b_md->hash[h]; k2; k2 = k2->next) {
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) {
break;
}
}
if (!k2) {
mapping_insert(res, &k->ind, &k->val);
} else {
map_delete(res, &k2->ind);
}
b_md = b->data;
}
UNSET_ONERROR(err);
return res;
}
/* NOTE: May perform destructive operations on either of the arguments
* if it has only a single reference.
*/
PMOD_EXPORT struct mapping *merge_mappings(struct mapping *a, struct mapping *b, INT32 op)
{
ONERROR r1,r2,r3,r4;
struct array *ai, *av;
struct array *bi, *bv;
struct array *ci, *cv;
INT32 *zipper;
struct mapping *m;
#ifdef PIKE_DEBUG
if(a->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
if(b->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
switch (op) {
case PIKE_ARRAY_OP_SUB:
return subtract_mappings(a, b);
case PIKE_ARRAY_OP_AND:
return and_mappings(a, b);
case PIKE_ARRAY_OP_OR:
return or_mappings(a, b);
case PIKE_ARRAY_OP_XOR:
return xor_mappings(a, b);
}
ai=mapping_indices(a);
SET_ONERROR(r1,do_free_array,ai);
av=mapping_values(a);
SET_ONERROR(r2,do_free_array,av);
if(ai->size > 1)
{
zipper=get_set_order(ai);
order_array(ai, zipper);
order_array(av, zipper);
free(zipper);
}
bi=mapping_indices(b);
SET_ONERROR(r3,do_free_array,bi);
bv=mapping_values(b);
SET_ONERROR(r4,do_free_array,bv);
if(bi->size > 1)
{
zipper=get_set_order(bi);
order_array(bi, zipper);
order_array(bv, zipper);
free(zipper);
}
zipper=merge(ai,bi,op);
ci=array_zip(ai,bi,zipper);
UNSET_ONERROR(r4); free_array(bi);
UNSET_ONERROR(r3); free_array(ai);
cv=array_zip(av,bv,zipper);
UNSET_ONERROR(r2); free_array(bv);
UNSET_ONERROR(r1); free_array(av);
free(zipper);
m=mkmapping(ci, cv);
free_array(ci);
free_array(cv);
return m;
}
/* FIXME: What are the semantics for this function?
* FIXME: It ought to be optimized just like the unordered variant.
* /grubba 2003-11-12
*/
PMOD_EXPORT struct mapping *merge_mapping_array_ordered(struct mapping *a,
struct array *b, INT32 op)
{
ONERROR r1,r2;
struct array *ai, *av;
struct array *ci = NULL, *cv = NULL;
INT32 *zipper = NULL;
struct mapping *m;
ai=mapping_indices(a);
SET_ONERROR(r1,do_free_array,ai);
av=mapping_values(a);
SET_ONERROR(r2,do_free_array,av);
if(ai->size > 1)
{
zipper=get_set_order(ai);
order_array(ai, zipper);
order_array(av, zipper);
free(zipper);
}
switch (op) /* no elements from b may be selected */
{
case PIKE_ARRAY_OP_AND:
zipper=merge(b,ai,op);
ci=array_zip(b,ai,zipper); /* b must not be used */
cv=array_zip(b,av,zipper); /* b must not be used */
break;
case PIKE_ARRAY_OP_SUB:
zipper=merge(ai,b,op);
ci=array_zip(ai,b,zipper); /* b must not be used */
cv=array_zip(av,b,zipper); /* b must not be used */
break;
default: Pike_fatal("merge_mapping_array on other than AND or SUB\n");
}
UNSET_ONERROR(r2); free_array(av);
UNSET_ONERROR(r1); free_array(ai);
free(zipper);
m=mkmapping(ci, cv);
free_array(ci);
free_array(cv);
return m;
}
PMOD_EXPORT struct mapping *merge_mapping_array_unordered(struct mapping *a,
struct array *b, INT32 op)
{
ONERROR r1;
struct array *b_temp;
INT32 *zipper;
struct mapping *m;
if (b->size>1)
{
zipper=get_set_order(b);
b_temp=reorder_and_copy_array(b,zipper);
free (zipper);
SET_ONERROR(r1,do_free_array,b_temp);
m=merge_mapping_array_ordered(a,b_temp,op);
UNSET_ONERROR(r1); free_array(b_temp);
}
else
m=merge_mapping_array_ordered(a,b,op);
return m;
}
/* NOTE: May perform destructive operations on either of the arguments
* if it has only a single reference.
*/
PMOD_EXPORT struct mapping *add_mappings(struct svalue *argp, INT32 args)
{
INT32 e,d;
struct mapping *ret=0;
struct keypair *k;
for(e=d=0;d<args;d++)
{
struct mapping *m = argp[d].u.mapping;
#ifdef PIKE_DEBUG
if(d_flag>1) check_mapping(m);
#endif
e += m->data->size;
}
if(!e) return allocate_mapping(0);
d=0;
for(;d<args;d++)
{
struct mapping *m=argp[d].u.mapping;
struct mapping_data *md=m->data;
if(md->size == 0) continue;
if(!(md->flags & MAPPING_WEAK))
{
#if 1 /* major optimization */ if(e==md->size)
return copy_mapping(m);
#endif
if(m->refs == 1 && !md->hardlinks)
{
add_ref( ret=m );
d++;
break;
}
}
ret=allocate_mapping(MAP_SLOTS(e));
break;
}
for(;d<args;d++)
{
struct mapping *m=argp[d].u.mapping;
struct mapping_data *md=m->data;
add_ref(md);
NEW_MAPPING_LOOP(md)
low_mapping_insert(ret, &k->ind, &k->val, 2);
free_mapping_data(md);
}
#ifdef PIKE_DEBUG
if(!ret)
Pike_fatal("add_mappings is confused!\n");
#endif
return ret;
}
PMOD_EXPORT int mapping_equal_p(struct mapping *a, struct mapping *b, struct processing *p)
{
struct processing curr;
struct keypair *k;
struct mapping_data *md;
INT32 e,eq=1;
#ifdef PIKE_DEBUG
if(a->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
if(b->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
if(a==b) return 1;
if (a->data == b->data) return 1;
/* If either is weak, they're different. */
if ((a->data->flags | b->data->flags) & MAPPING_WEAK) return 0;
check_mapping_for_destruct(a);
check_mapping_for_destruct(b);
if(m_sizeof(a) != m_sizeof(b)) return 0;
if (!check_type_overlaps(a->data->ind_types, b->data->ind_types) ||
!check_type_overlaps(a->data->val_types, b->data->val_types)) return 0;
curr.pointer_a = a;
curr.pointer_b = b;
curr.next = p;
for( ;p ;p=p->next)
if(p->pointer_a == (void *)a && p->pointer_b == (void *)b)
return 1;
md=a->data;
md->valrefs++;
add_ref(md);
NEW_MAPPING_LOOP(md)
{
struct svalue *s;
if((s=low_mapping_lookup(b, & k->ind)))
{
if(!low_is_equal(s, &k->val, &curr))
{
eq=0;
break;
}
}else{
INT32 d;
struct mapping_data *bmd = b->data;
struct keypair *kp;
/* This is neither pretty nor fast, but it should
* perform a bit more like expected... -Hubbe
*/
bmd->valrefs++;
add_ref(bmd);
eq=0;
for(d=0;d<(bmd)->hashsize;d++)
{
for(kp=bmd->hash[d];kp;kp=kp->next)
{
if(low_is_equal(&k->ind, &kp->ind, &curr) &&
low_is_equal(&k->val, &kp->val, &curr))
{
eq=1;
break;
}
}
}
bmd->valrefs--;
free_mapping_data(bmd);
if(!eq) break;
}
}
md->valrefs--;
free_mapping_data(md);
return eq;
}
void describe_mapping(struct mapping *m,struct processing *p,int indent)
{
struct processing doing;
struct array *a;
JMP_BUF catch;
ONERROR err;
INT32 e,d;
char buf[40];
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
if(! m->data->size)
{
my_strcat("([ ])");
return;
}
doing.next=p;
doing.pointer_a=(void *)m;
for(e=0;p;e++,p=p->next)
{
if(p->pointer_a == (void *)m)
{
sprintf(buf,"@%ld",(long)e);
my_strcat(buf);
return;
}
}
if (Pike_in_gc > GC_PASS_PREPARE && Pike_in_gc < GC_PASS_FREE) {
/* Have to do without any temporary allocations. */
struct keypair *k;
int notfirst = 0;
if (m->data->size == 1) {
my_strcat("([ /* 1 element */\n");
} else {
sprintf(buf, "([ /* %ld elements */\n", (long)m->data->size);
my_strcat(buf);
}
NEW_MAPPING_LOOP(m->data) {
if (notfirst) my_strcat(",\n");
else notfirst = 1;
for(d = 0; d < indent; d++)
my_putchar(' ');
describe_svalue(&k->ind, indent+2, &doing);
my_strcat (": ");
describe_svalue(&k->val, indent+2, &doing);
}
my_putchar('\n');
for(e=2; e<indent; e++) my_putchar(' ');
my_strcat("])");
return;
}
a = mapping_indices(m);
SET_ONERROR(err, do_free_array, a);
if(! m->data->size) { /* mapping_indices may remove elements */
my_strcat("([ ])");
}
else {
int save_t_flag = Pike_interpreter.trace_level;
dynamic_buffer save_buf;
if (m->data->size == 1) {
my_strcat("([ /* 1 element */\n");
} else {
sprintf(buf, "([ /* %ld elements */\n", (long)m->data->size);
my_strcat(buf);
}
save_buffer (&save_buf);
Pike_interpreter.trace_level = 0;
if(SETJMP(catch)) {
free_svalue(&throw_value);
mark_free_svalue (&throw_value);
}
else
sort_array_destructively(a);
UNSETJMP(catch);
Pike_interpreter.trace_level = save_t_flag;
restore_buffer (&save_buf);
for(e = 0; e < a->size; e++)
{
struct svalue *tmp;
if(e)
my_strcat(",\n");
for(d = 0; d < indent; d++)
my_putchar(' ');
describe_svalue(ITEM(a)+e, indent+2, &doing);
my_strcat (": ");
{
int save_t_flag=Pike_interpreter.trace_level;
Pike_interpreter.trace_level=0;
tmp=low_mapping_lookup(m, ITEM(a)+e);
Pike_interpreter.trace_level=save_t_flag;
}
if(tmp)
describe_svalue(tmp, indent+2, &doing);
else
my_strcat("** gone **");
}
my_putchar('\n');
for(e=2; e<indent; e++) my_putchar(' ');
my_strcat("])");
}
UNSET_ONERROR(err);
free_array(a);
}
node *make_node_from_mapping(struct mapping *m)
{
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
mapping_fix_type_field(m);
if(!mapping_is_constant(m,0))
{
struct array *ind, *val;
node *n;
ind=mapping_indices(m);
val=mapping_values(m);
n=mkefuncallnode("mkmapping",
mknode(F_ARG_LIST,
make_node_from_array(ind),
make_node_from_array(val)));
free_array(ind);
free_array(val);
return n;
}else{
struct svalue s;
if(!m->data->size)
return mkefuncallnode("aggregate_mapping",0);
SET_SVAL(s, T_MAPPING, 0, mapping, m);
return mkconstantsvaluenode(&s);
}
}
/*! @decl mapping aggregate_mapping(mixed ... elems)
*! *! Construct a mapping.
*!
*! Groups the arguments together two and two in key-index pairs and
*! creates a mapping of those pairs. Generally, the mapping literal
*! syntax is handier: @expr{([ key1:val1, key2:val2, ... ])@}
*!
*! @seealso
*! @[sizeof()], @[mappingp()], @[mkmapping()]
*/
PMOD_EXPORT void f_aggregate_mapping(INT32 args)
{
INT32 e;
struct mapping *m;
if(args & 1)
Pike_error("Uneven number of arguments to aggregate_mapping.\n");
m=allocate_mapping(MAP_SLOTS(args / 2));
for(e=-args;e<0;e+=2) {
STACK_LEVEL_START(-e);
low_mapping_insert(m, Pike_sp+e, Pike_sp+e+1, 2);
STACK_LEVEL_DONE(-e);
}
pop_n_elems(args);
#ifdef PIKE_DEBUG
if(d_flag)
check_mapping(m);
#endif
push_mapping(m);
}
PMOD_EXPORT struct mapping *copy_mapping_recursively(struct mapping *m,
struct mapping *p)
{
int not_complex;
struct mapping *ret;
INT32 e;
struct keypair *k;
struct mapping_data *md;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
#ifdef PIKE_DEBUG
if(d_flag > 1) check_mapping_type_fields(m);
#endif
if((m->data->val_types | m->data->ind_types) & BIT_COMPLEX) {
not_complex = 0;
ret=allocate_mapping(MAP_SLOTS(m->data->size));
}
else {
not_complex = 1;
ret = copy_mapping(m);
}
if (p) {
struct svalue aa, bb;
SET_SVAL(aa, T_MAPPING, 0, mapping, m);
SET_SVAL(bb, T_MAPPING, 0, mapping, ret);
mapping_insert(p, &aa, &bb);
}
if (not_complex)
return ret;
ret->data->flags = m->data->flags;
check_stack(2);
md=m->data;
md->valrefs++;
add_ref(md);
NEW_MAPPING_LOOP(md)
{
/* Place holders.
*
* NOTE: copy_svalues_recursively_no_free() may store stuff in
* the destination svalue, and then call stuff that uses
* the stack (eg itself).
*/
push_int(0);
push_int(0);
copy_svalues_recursively_no_free(Pike_sp-2,&k->ind, 1, p);
copy_svalues_recursively_no_free(Pike_sp-1,&k->val, 1, p);
low_mapping_insert(ret, Pike_sp-2, Pike_sp-1, 2);
pop_n_elems(2);
}
md->valrefs--;
free_mapping_data(md);
return ret;
}
PMOD_EXPORT void mapping_search_no_free(struct svalue *to,
struct mapping *m,
const struct svalue *look_for,
const struct svalue *key /* start */)
{
struct mapping_data *md, *omd;
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");
#endif
md=m->data;
if(md->size)
{
unsigned INT32 h2,h=0;
struct keypair *k=md->hash[0], **prev;
if(key)
{
h2=hash_svalue(key);
FIND();
if(!k)
{
SET_SVAL(*to, T_INT, NUMBER_UNDEFINED, integer, 0);
return;
}
k=k->next;
}
md=m->data;
if(md->size)
{
md->valrefs++;
add_ref(md);
if(h < (unsigned INT32)md->hashsize)
{ while(1)
{
while(k)
{
if(is_eq(look_for, &k->val))
{
assign_svalue_no_free(to,&k->ind);
md->valrefs--;
free_mapping_data(md);
return;
}
k=k->next;
}
h++;
if(h>= (unsigned INT32)md->hashsize)
break;
k=md->hash[h];
}
}
}
md->valrefs--;
free_mapping_data(md);
}
SET_SVAL(*to, T_INT, NUMBER_UNDEFINED, integer, 0);
}
#ifdef PIKE_DEBUG
void check_mapping(const struct mapping *m)
{
int e,num;
struct keypair *k;
const struct mapping_data *md;
static int in_check_mapping;
if(in_check_mapping) return;
in_check_mapping=1;
md=m->data;
if(m->refs <=0)
Pike_fatal("Mapping has zero refs.\n");
if(!m->data)
Pike_fatal("Mapping has no data block.\n");
if (!m->data->refs)
Pike_fatal("Mapping data block has zero refs.\n");
if(m->next && m->next->prev != m)
Pike_fatal("Mapping ->next->prev != mapping.\n");
#ifdef MAPPING_SIZE_DEBUG
if(m->debug_size != md->size)
{
if(Pike_in_gc)
{
fprintf(stderr,"Pike was in GC stage %d when this fatal occurred:\n",Pike_in_gc);
Pike_in_gc=0;
}
fprintf(stderr,"--MAPPING ZAPPING (%d!=%d), mapping:\n",m->debug_size,md->size);
describe(m);
fprintf(stderr,"--MAPPING ZAPPING (%d!=%d), mapping data:\n",m->debug_size,md->size);
describe(md);
Pike_fatal("Mapping zapping detected (%d != %d)!\n",m->debug_size,md->size);
}#endif
if(m->prev)
{
if(m->prev->next != m)
Pike_fatal("Mapping ->prev->next != mapping.\n");
}else{
if(first_mapping != m)
Pike_fatal("Mapping ->prev == 0 but first_mapping != mapping.\n");
}
if(md->valrefs <0)
Pike_fatal("md->valrefs < 0\n");
if(md->hardlinks <0)
Pike_fatal("md->valrefs < 0\n");
if(md->refs < md->valrefs+1)
Pike_fatal("md->refs < md->valrefs+1\n");
if(md->valrefs < md->hardlinks)
Pike_fatal("md->refs < md->valrefs+1\n");
if(md->hashsize < 0)
Pike_fatal("Assert: I don't think he's going to make it Jim.\n");
if(md->size < 0)
Pike_fatal("Core breach, evacuate ship!\n");
if(md->num_keypairs < 0)
Pike_fatal("Starboard necell on fire!\n");
if(md->size > md->num_keypairs)
Pike_fatal("Pretty mean hashtable there buster!\n");
if(md->hashsize & (md->hashsize - 1))
Pike_fatal("Invalid hashtable size: 0x%08lx\n", (long)md->hashsize);
if(md->hashsize > md->num_keypairs)
Pike_fatal("Pretty mean hashtable there buster %d > %d (2)!\n",md->hashsize,md->num_keypairs);
if(md->num_keypairs > (md->hashsize + 3) * AVG_LINK_LENGTH)
Pike_fatal("Mapping from hell detected, attempting to send it back...\n");
if(md->size > 0 && (!md->ind_types || !md->val_types))
Pike_fatal("Mapping type fields are... wrong.\n");
num=0;
NEW_MAPPING_LOOP(md)
{
num++;
if (TYPEOF(k->ind) > MAX_TYPE)
Pike_fatal("Invalid maping keypair index type: %s\n",
get_name_of_type(TYPEOF(k->ind)));
if(! ( (1 << TYPEOF(k->ind)) & (md->ind_types) ))
Pike_fatal("Mapping indices type field lies.\n");
if (TYPEOF(k->val) > MAX_TYPE)
Pike_fatal("Invalid mapping keypair value type: %s\n",
get_name_of_type(TYPEOF(k->val)));
if(! ( (1 << TYPEOF(k->val)) & (md->val_types) ))
Pike_fatal("Mapping values type field lies.\n");
check_svalue(& k->ind);
check_svalue(& k->val);
/* FIXME add check for k->hval
* beware that hash_svalue may be threaded and locking
* is required!! */
}
if(md->size != num)
Pike_fatal("Shields are failing, hull integrity down to 20%%\n");
in_check_mapping=0;
}
void check_all_mappings(void)
{
struct mapping *m;
for(m=first_mapping;m;m=m->next)
check_mapping(m);
}
#endif
static void visit_mapping_data (struct mapping_data *md, int action,
void *extra)
{
visit_enter(md, T_MAPPING_DATA, extra);
switch (action) {
#ifdef PIKE_DEBUG
default:
Pike_fatal ("Unknown visit action %d.\n", action);
case VISIT_NORMAL:
case VISIT_COMPLEX_ONLY:
break;
#endif
case VISIT_COUNT_BYTES:
mc_counted_bytes += MAPPING_DATA_SIZE (md->hashsize, md->num_keypairs);
break;
}
if ((md->ind_types | md->val_types) &
(action & VISIT_COMPLEX_ONLY ? BIT_COMPLEX : BIT_REF_TYPES)) {
int ind_ref_type =
md->flags & MAPPING_WEAK_INDICES ? REF_TYPE_WEAK : REF_TYPE_NORMAL;
int val_ref_type =
md->flags & MAPPING_WEAK_VALUES ? REF_TYPE_WEAK : REF_TYPE_NORMAL;
INT32 e;
struct keypair *k;
NEW_MAPPING_LOOP (md) {
visit_svalue (&k->ind, ind_ref_type, extra);
visit_svalue (&k->val, val_ref_type, extra);
}
}
visit_leave(md, T_MAPPING_DATA, extra);
}
PMOD_EXPORT void visit_mapping (struct mapping *m, int action, void *extra)
{
visit_enter(m, T_MAPPING, extra);
switch (action) {
#ifdef PIKE_DEBUG
default:
Pike_fatal ("Unknown visit action %d.\n", action);
case VISIT_NORMAL:
case VISIT_COMPLEX_ONLY:
break;
#endif
case VISIT_COUNT_BYTES:
mc_counted_bytes += sizeof (struct mapping);
break;
}
visit_ref (m->data, REF_TYPE_INTERNAL,
(visit_thing_fn *) &visit_mapping_data, extra);
visit_leave(m, T_MAPPING, extra);
}
#ifdef MAPPING_SIZE_DEBUG
#define DO_IF_MAPPING_SIZE_DEBUG(x) x
#else
#define DO_IF_MAPPING_SIZE_DEBUG(x)
#endif
#define GC_RECURSE_MD_IN_USE(MD, RECURSE_FN, IND_TYPES, VAL_TYPES) do { \
INT32 e; \
struct keypair *k; \
IND_TYPES = MD->ind_types; \
NEW_MAPPING_LOOP(MD) { \
if (!IS_DESTRUCTED(&k->ind) && RECURSE_FN(&k->ind, 1)) { \
DO_IF_DEBUG(Pike_fatal("Didn't expect an svalue zapping now.\n")); \
} \
RECURSE_FN(&k->val, 1); \
VAL_TYPES |= 1 << TYPEOF(k->val); \
} \
} while (0)
#ifdef PIKE_MAPPING_KEYPAIR_LOOP
#error Broken code below!
#define GC_RECURSE(M, MD, REC_KEYPAIR, TYPE, IND_TYPES, VAL_TYPES) do { \
int remove; \
struct keypair *k,**prev_; \
/* no locking required (no is_eq) */ \
for(k = MD_KEYPAIRS(md, md->hashsize);k < MD->free_list;) \
{ \
REC_KEYPAIR(remove, \
PIKE_CONCAT(TYPE, _svalues), \
PIKE_CONCAT(TYPE, _weak_svalues), \
PIKE_CONCAT(TYPE, _without_recurse), \
PIKE_CONCAT(TYPE, _weak_without_recurse)); \
if (remove) { \
/* Find and unlink k. */ \
unsigned INT32 h_; \
h_ = k->hval & ( md->hashsize - 1); \
prev_ = md->hash + h_; \
DO_IF_DEBUG( \
if (!*prev_) { \
Pike_fatal("Node to unlink not found!\n"); \
} \
); \
while (*prev_ != k) { \
prev_ = &((*prev_)->next); \
DO_IF_DEBUG( \
if (!*prev_) { \
Pike_fatal("Node to unlink not found!\n"); \
} \
); \
} \
(*prev_)->next = k->next; \
FREE_KEYPAIR(MD, k); \
mark_free_svalue (&MD->free_list->ind); \
mark_free_svalue (&MD->free_list->val); \
MD->size--; \
DO_IF_MAPPING_SIZE_DEBUG( \
if(M->data ==MD) \
M->debug_size--; \
); \
} else { \
VAL_TYPES |= 1 << TYPEOF(k->val); \
IND_TYPES |= 1 << TYPEOF(k->ind); \
k++; \
} \
} \
} while (0)
#else /* !PIKE_MAPPING_KEYPAIR_LOOP */
#define GC_RECURSE(M, MD, REC_KEYPAIR, TYPE, IND_TYPES, VAL_TYPES) do { \
INT32 e; \ int remove; \
struct keypair *k,**prev; \
/* no locking required (no is_eq) */ \
for(e=0;e<MD->hashsize;e++) \
{ \
for(prev= MD->hash + e;(k=*prev);) \
{ \
REC_KEYPAIR(remove, \
PIKE_CONCAT(TYPE, _svalues), \
PIKE_CONCAT(TYPE, _weak_svalues), \
PIKE_CONCAT(TYPE, _without_recurse), \
PIKE_CONCAT(TYPE, _weak_without_recurse)); \
if (remove) \
{ \
*prev=k->next; \
FREE_KEYPAIR(MD, k); \
mark_free_svalue (&MD->free_list->ind); \
mark_free_svalue (&MD->free_list->val); \
MD->size--; \
DO_IF_MAPPING_SIZE_DEBUG( \
if(M->data ==MD) \
M->debug_size--; \
); \
}else{ \
VAL_TYPES |= 1 << TYPEOF(k->val); \
IND_TYPES |= 1 << TYPEOF(k->ind); \
prev=&k->next; \
} \
} \
} \
} while (0)
#endif /* PIKE_MAPPING_KEYPAIR_LOOP */
#define GC_REC_KP(REMOVE, N_REC, W_REC, N_TST, W_TST) do { \
if ((REMOVE = N_REC(&k->ind, 1))) \
gc_free_svalue(&k->val); \
else \
N_REC(&k->val, 1); \
} while (0)
#define GC_REC_KP_IND(REMOVE, N_REC, W_REC, N_TST, W_TST) do { \
if ((REMOVE = W_REC(&k->ind, 1))) \
gc_free_svalue(&k->val); \
else \
N_REC(&k->val, 1); \
} while (0)
#define GC_REC_KP_VAL(REMOVE, N_REC, W_REC, N_TST, W_TST) do { \
if ((REMOVE = N_TST(&k->ind))) /* Don't recurse now. */ \
gc_free_svalue(&k->val); \
else if ((REMOVE = W_REC(&k->val, 1))) \
gc_free_svalue(&k->ind); \
else \
N_REC(&k->ind, 1); /* Now we can recurse the index. */ \
} while (0)
#define GC_REC_KP_BOTH(REMOVE, N_REC, W_REC, N_TST, W_TST) do { \
if ((REMOVE = W_TST(&k->ind))) /* Don't recurse now. */ \
gc_free_svalue(&k->val); \
else if ((REMOVE = W_REC(&k->val, 1))) \
gc_free_svalue(&k->ind); \
else \
W_REC(&k->ind, 1); /* Now we can recurse the index. */ \
} while (0)
void gc_mark_mapping_as_referenced(struct mapping *m)
{
#ifdef PIKE_DEBUG
if(m->data->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");#endif
debug_malloc_touch(m);
debug_malloc_touch(m->data);
if(gc_mark(m, T_MAPPING))
GC_ENTER (m, T_MAPPING) {
struct mapping_data *md = m->data;
if (m == gc_mark_mapping_pos)
gc_mark_mapping_pos = m->next;
if (m == gc_internal_mapping)
gc_internal_mapping = m->next;
else {
DOUBLEUNLINK(first_mapping, m);
DOUBLELINK(first_mapping, m); /* Linked in first. */
}
if(gc_mark(md, T_MAPPING_DATA) &&
((md->ind_types | md->val_types) & BIT_COMPLEX)) {
TYPE_FIELD ind_types = 0, val_types = 0;
if (MAPPING_DATA_IN_USE(md)) {
/* Must leave the mapping data untouched if it's busy. */
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE_MD_IN_USE(md, gc_mark_svalues, ind_types, val_types);
gc_assert_checked_as_nonweak(md);
}
else
switch (md->flags & MAPPING_WEAK) {
case 0:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP, gc_mark, ind_types, val_types);
gc_assert_checked_as_nonweak(md);
break;
case MAPPING_WEAK_INDICES:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP_IND, gc_mark, ind_types, val_types);
gc_assert_checked_as_weak(md);
break;
case MAPPING_WEAK_VALUES:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP_VAL, gc_mark, ind_types, val_types);
gc_assert_checked_as_weak(md);
break;
default:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP_BOTH, gc_mark, ind_types, val_types);
gc_assert_checked_as_weak(md);
break;
}
md->val_types = val_types;
md->ind_types = ind_types;
}
} GC_LEAVE;
}
void real_gc_cycle_check_mapping(struct mapping *m, int weak)
{
GC_CYCLE_ENTER(m, T_MAPPING, weak) {
struct mapping_data *md = m->data;
debug_malloc_touch(m);
debug_malloc_touch(md);
#ifdef PIKE_DEBUG
if(md->refs <=0)
Pike_fatal("Zero refs in mapping->data\n");#endif
if ((md->ind_types | md->val_types) & BIT_COMPLEX) {
TYPE_FIELD ind_types = 0, val_types = 0;
if (MAPPING_DATA_IN_USE(md)) {
/* Must leave the mapping data untouched if it's busy. */
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE_MD_IN_USE(md, gc_cycle_check_svalues, ind_types, val_types);
gc_assert_checked_as_nonweak(md);
}
else
switch (md->flags & MAPPING_WEAK) {
case 0:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP, gc_cycle_check, ind_types, val_types);
gc_assert_checked_as_nonweak(md);
break;
case MAPPING_WEAK_INDICES:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP_IND, gc_cycle_check, ind_types, val_types);
gc_assert_checked_as_weak(md);
break;
case MAPPING_WEAK_VALUES:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP_VAL, gc_cycle_check, ind_types, val_types);
gc_assert_checked_as_weak(md);
break;
default:
debug_malloc_touch(m);
debug_malloc_touch(md);
GC_RECURSE(m, md, GC_REC_KP_BOTH, gc_cycle_check, ind_types, val_types);
gc_assert_checked_as_weak(md);
break;
}
md->val_types = val_types;
md->ind_types = ind_types;
}
} GC_CYCLE_LEAVE;
}
static void gc_check_mapping(struct mapping *m)
{
struct mapping_data *md = m->data;
if((md->ind_types | md->val_types) & BIT_COMPLEX)
GC_ENTER (m, T_MAPPING) {
INT32 e;
struct keypair *k;
if(!debug_gc_check (md, " as mapping data block of a mapping")) {
if (!(md->flags & MAPPING_WEAK) || MAPPING_DATA_IN_USE(md))
/* Disregard the weak flag if the mapping data is busy; we must
* leave it untouched in that case anyway. */
NEW_MAPPING_LOOP(md)
{
debug_gc_check_svalues(&k->ind, 1, " as mapping index");
debug_gc_check_svalues(&k->val, 1, " as mapping value");
}
else {
switch (md->flags & MAPPING_WEAK) {
case MAPPING_WEAK_INDICES:
NEW_MAPPING_LOOP(md)
{
debug_gc_check_weak_svalues(&k->ind, 1, " as mapping index");
debug_gc_check_svalues(&k->val, 1, " as mapping value");
} break;
case MAPPING_WEAK_VALUES:
NEW_MAPPING_LOOP(md)
{
debug_gc_check_svalues(&k->ind, 1, " as mapping index");
debug_gc_check_weak_svalues(&k->val, 1, " as mapping value");
}
break;
default:
NEW_MAPPING_LOOP(md)
{
debug_gc_check_weak_svalues(&k->ind, 1, " as mapping index");
debug_gc_check_weak_svalues(&k->val, 1, " as mapping value");
}
break;
}
gc_checked_as_weak(md);
}
}
} GC_LEAVE;
}
unsigned gc_touch_all_mappings(void)
{
unsigned n = 0;
struct mapping *m;
if (first_mapping && first_mapping->prev)
Pike_fatal("Error in mapping link list.\n");
for (m = first_mapping; m; m = m->next) {
debug_gc_touch(m);
n++;
if (m->next && m->next->prev != m)
Pike_fatal("Error in mapping link list.\n");
}
return n;
}
void gc_check_all_mappings(void)
{
struct mapping *m;
for(m=first_mapping;m;m=m->next)
{
#ifdef DEBUG_MALLOC
if (((int) PTR_TO_INT (m->data)) == 0x55555555) {
fprintf(stderr, "** Zapped mapping in list of active mappings!\n");
describe_something(m, T_MAPPING, 0,2,0, NULL);
Pike_fatal("Zapped mapping in list of active mappings!\n");
}
#endif /* DEBUG_MALLOC */
gc_check_mapping(m);
#ifdef PIKE_DEBUG
if(d_flag > 1) check_mapping_type_fields(m);
#endif
}
}
void gc_mark_all_mappings(void)
{
gc_mark_mapping_pos = gc_internal_mapping;
while (gc_mark_mapping_pos) {
struct mapping *m = gc_mark_mapping_pos;
gc_mark_mapping_pos = m->next;
debug_malloc_touch(m);
debug_malloc_touch(m->data);
if(gc_is_referenced(m))
gc_mark_mapping_as_referenced(m); }
}
void gc_cycle_check_all_mappings(void)
{
struct mapping *m;
for (m = gc_internal_mapping; m; m = m->next) {
real_gc_cycle_check_mapping(m, 0);
gc_cycle_run_queue();
}
}
void gc_zap_ext_weak_refs_in_mappings(void)
{
gc_mark_mapping_pos = first_mapping;
while (gc_mark_mapping_pos != gc_internal_mapping && gc_ext_weak_refs) {
struct mapping *m = gc_mark_mapping_pos;
gc_mark_mapping_pos = m->next;
gc_mark_mapping_as_referenced(m);
}
gc_mark_discard_queue();
}
size_t gc_free_all_unreferenced_mappings(void)
{
struct mapping *m,*next;
struct mapping_data *md;
size_t unreferenced = 0;
for(m=gc_internal_mapping;m;m=next)
{
debug_malloc_touch(m);
debug_malloc_touch(m->data);
if(gc_do_free(m))
{
/* Got an extra ref from gc_cycle_pop(). */
md = m->data;
debug_malloc_touch(m);
debug_malloc_touch(md);
/* Protect against unlink_mapping_data() recursing too far. */
m->data=&empty_data;
add_ref(m->data);
unlink_mapping_data(md);
#ifdef MAPPING_SIZE_DEBUG
m->debug_size=0;
#endif
gc_free_extra_ref(m);
SET_NEXT_AND_FREE(m, free_mapping);
}
else
{
next=m->next;
}
unreferenced++;
}
return unreferenced;
}
#ifdef PIKE_DEBUG
void simple_describe_mapping(struct mapping *m)
{
dynamic_buffer save_buf;
char *s;
init_buf(&save_buf); describe_mapping(m,0,2);
s=simple_free_buf(&save_buf);
fprintf(stderr,"%s\n",s);
free(s);
}
void debug_dump_mapping(struct mapping *m)
{
fprintf(stderr, "Refs=%d, next=%p, prev=%p",
m->refs, m->next, m->prev);
if (((ptrdiff_t)m->data) & 3) {
fprintf(stderr, ", data=%p (unaligned)\n", m->data);
} else {
fprintf(stderr, ", flags=0x%x, size=%d, hashsize=%d\n",
m->data->flags, m->data->size, m->data->hashsize);
fprintf(stderr, "Indices type field =");
debug_dump_type_field(m->data->ind_types);
fprintf(stderr, "\n");
fprintf(stderr, "Values type field =");
debug_dump_type_field(m->data->val_types);
fprintf(stderr, "\n");
simple_describe_mapping(m);
}
}
#endif
int mapping_is_constant(struct mapping *m,
struct processing *p)
{
int ret=1;
INT32 e;
struct keypair *k;
struct mapping_data *md=m->data;
if( (md->ind_types | md->val_types) & ~(BIT_INT|BIT_FLOAT|BIT_STRING))
{
md->valrefs++;
add_ref(md);
NEW_MAPPING_LOOP(md)
{
if(!svalues_are_constant(&k->ind, 1, md->ind_types, p) ||
!svalues_are_constant(&k->val, 1, md->val_types, p))
{
ret=0;
e=md->hashsize;
break;
}
}
md->valrefs--;
free_mapping_data(md);
}
return ret;
}