/* Copyright J"orn Rennecke 1993 - 1997 */ #include <stdio.h> #include "config.h" #include "common.h" #include "interpret.h" #include "object.h" #include "uid.h" #include "regexp.h" #include "alloc.h" #include "schedule.h" #include "exec.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 wiz_list default_wizlist_entry; struct hmap_x dirty_mapping_head_hash; struct mapping dirty_mapping_head = { T_MAPPING, /* ref */ 1, /* num_values */ 0, /* hash/user */ { (struct uid *)&dirty_mapping_head_hash }, /* condensed */ 0, }; /* get_map_lvalue likes to read the first value */ p_int empty_cmap[2] = { COMBINE8_24(T_CONDENSED_MAP, 0), 0 }; mp_int num_mappings = 0; union svalue last_dirty_mapping = TO_SVALUE(&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; svalue allocate_mapping(mp_int size, int num_values, svalue ob) { union svalue sv; union svalue m; /* * we want to use alloc_gen() / free_gen for the map_chains, thus we * restrict num_values accordingly (approx. 16k) */ if (num_values > (0xffff - sizeof(struct map_chain))/ sizeof(union svalue)) return SV_NULL; m = ALLOC(T_MAPPING, 1, sizeof(struct mapping)); if (m.i) { SV_MAPPING(m).condensed = EMPTY_CMAP; SV_MAPPING(m).num_values = num_values; (SV_MAPPING(m).x.uid = SV_OBJECT(ob).x.uid->self)->total_mapping += sizeof SV_MAPPING(m); if (size) { struct hmap_x *hm; struct map_chain **mcp; size |= size >> 1; size |= size >> 2; size |= size >> 4; size |= size >> 8; size |= size >> 16; size >>= 1; /* This is now actually the mask, which is one lower */ if (size > ((MAXINT - sizeof *hm - 0x100000) / sizeof *mcp) || !(sv = ALLOC_TTS(T_INTERNAL, IT_X_HMAP, 1, sizeof (char *) + sizeof *hm + sizeof *mcp * size) ).i ) { free_block(m.p, sizeof(struct mapping)); return SV_NULL; } hm = (struct hmap_x *)&sv.p[sizeof (char *) -1]; hm->mask = size; hm->used = hm->condensed_deleted = hm->ref = 0; SV_MAPPING(last_dirty_mapping).x.hash->next_dirty = m; last_dirty_mapping = m; #ifdef DEBUG hm->next_dirty = 0; hm->deleted = 0; #endif num_dirty_mappings++; SET_JOB(do_compact_mappings); mcp = hm->chains; do *mcp++ = 0; while (--size >= 0); hm->uid = SV_MAPPING(m).x.uid; SV_MAPPING(m).x.hash = hm; } num_mappings++; } return m; } static void remove_empty_mappings(); void _free_mapping(union svalue m) { struct hmap_x *hm; union svalue *cm; mp_int i, total; int j, num_values; #ifdef DEBUG if (!SV_MAPPING(m).x.uid) fatal("No uid for mapping"); #endif num_mappings--; num_values = SV_MAPPING(m).num_values; cm = SV_MAPPING(m).condensed; total = CMAP_SIZE(cm); if (total) { if (!num_values) { union svalue old = SV_NULL; i = total - 1; do { union svalue sv = cm[i]; if ((sv.i & 3) == 1 && sv.p != old.p) { FREE_ALLOCED_SVALUE(sv); old = sv; } } while (--i >= 0); } else { /* FIXME: don't free multiple mentioned keys (from deletion) multiple times */ total = total * (1 + num_values); i = total - 1; do { union svalue sv = cm[i]; if ((sv.i & 3) == 1) /* deleted members are equiv. 3 mod 4. */ FREE_ALLOCED_SVALUE(sv); } while (--i >= 0); } total = total * sizeof m + sizeof m; free_block((uint8 *)cm - sizeof(char *) + 1, total); } SV_MAPPING(m).x.uid->self->total_mapping -= sizeof SV_MAPPING(m) + total; hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) >= IT_X_MAP) { if (MAPX_TYPE(hm) > IT_X_MAP) { struct map_chain **mcp, *mc, *next; union svalue next_dirty; union svalue sv; #ifdef DEBUG if (hm->ref) fatal("Ref count in freed hash mapping: %ld\n", hm->ref); #endif mcp = hm->chains; i = hm->mask + 1; do { for (next = *mcp++; mc = next; ) { j = num_values; do { union svalue sv2 = (&mc->key)[j]; FREE_SVALUE(sv2); } while (--j >= 0); next = mc->next; free_gen( (char *)mc ); } } while (--i); next_dirty = hm->next_dirty; sv = ALLOC_TTS(T_INTERNAL, IT_X_HMAP, 1, sizeof (char *) + sizeof *hm); if (!sv.i) { i = hm->mask; do { hm->chains[i] = 0; } while (--i); } else { free_block((char *)hm - sizeof (char *) + 1, sizeof (char *) + sizeof *hm + sizeof *mcp * hm->mask); hm = (struct hmap_x *)&sv.p[sizeof (char *) -1]; hm->mask = 0; } hm->chains[0] = 0; hm->used = hm->condensed_deleted = hm->ref = 0; hm->next_dirty = next_dirty; SV_MAPPING(m).condensed = 0; SV_MAPPING(m).x.hash = hm; if ( (empty_mapping_load += 2) > 0) remove_empty_mappings(); return; } else { free_block((uint8 *)hm - sizeof (char *) + 1, sizeof(char *)+ sizeof(struct map_x)); } } free_block((uint8 *)&SV_MAPPING(m), sizeof SV_MAPPING(m)); } void free_empty_mapping(union svalue m) { struct hmap_x *hm; union svalue *cm; mp_int num_values; mp_int total; #ifdef DEBUG if (!SV_MAPPING(m).x.uid) fatal("No wizlist pointer for mapping"); #endif num_mappings--; num_values = SV_MAPPING(m).num_values; cm = SV_MAPPING(m).condensed; total = CMAP_SIZE(cm); if (total) { total = sizeof (char *) + total * (1 + num_values) * sizeof(union svalue); free_block((uint8 *)cm - sizeof(char *) + 1, total); } SV_MAPPING(m).x.uid->self->total_mapping -= sizeof SV_MAPPING(m) + total; hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) >= IT_X_MAP) { if (MAPX_TYPE(hm) > IT_X_MAP) { struct map_chain **mcp, *mc, *next; union svalue next_dirty; mp_int i; union svalue sv; #ifdef DEBUG if (hm->ref) fatal("Ref count in freed hash mapping: %ld\n", hm->ref); #endif mcp = hm->chains; i = hm->mask + 1; do { for (next = *mcp++; mc = next; ) { next = mc->next; free_gen( (char *)mc ); } } while (--i); next_dirty = hm->next_dirty; sv = ALLOC_TTS(T_INTERNAL, IT_X_HMAP, 1, sizeof (char *) + sizeof *hm); if (!sv.i) { i = hm->mask; do { hm->chains[i] = 0; } while (--i); } else { free_block((uint8 *)hm - sizeof (char *) + 1, sizeof (char *) + sizeof *hm + sizeof *mcp * hm->mask); hm = (struct hmap_x *)&sv.p[sizeof (char *) -1]; hm->mask = 0; } hm->chains[0] = 0; hm->used = hm->condensed_deleted = hm->ref = 0; hm->next_dirty = next_dirty; SV_MAPPING(m).condensed = 0; SV_MAPPING(m).x.hash = hm; if ( (empty_mapping_load += 2) > 0) remove_empty_mappings(); return; } else { free_block((uint8 *)hm - sizeof (char *) + 1, sizeof(char *)+ sizeof(struct map_x)); } } free_block((uint8 *)&SV_MAPPING(m), sizeof SV_MAPPING(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() { union svalue *mp, m, last; /* mapping svalues */ struct hmap_x *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 SV_MAPPING(last_dirty_mapping).x.hash->next_dirty = SV_NULL; last = TO_SVALUE(&dirty_mapping_head); mp = &dirty_mapping_head_hash.next_dirty; m = *mp; do { hm = SV_MAPPING(m).x.hash; if (!SV_MAPPING(m).condensed) { free_block((uint8 *)&SV_MAPPING(m), sizeof SV_MAPPING(m)); *mp = m = hm->next_dirty; free_block((uint8 *)hm -sizeof(char *) + 1, sizeof (char *) + sizeof *hm + sizeof hm->chains[0] * hm->mask); continue; } last = m; mp = &hm->next_dirty; m = *mp; } while (m.i); 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(union svalue m) { struct hmap_x *hm; /* This is part 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 (!SV_MAPPING(m).x.hash || SV_MAPPING(m).x.hash->ref <= 0) { /* This shouldn't happen */ printf("free_protector_mapping() : no hash %s\n", SV_MAPPING(m).x.hash ? "reference" : "part"); #ifdef TRACE_CODE { extern int last_instructions(int, int, struct svalue **); last_instructions(TOTAL_TRACE_LENGTH, 1, 0); } #endif printf("free_protector_mapping() : no hash %s\n", SV_MAPPING(m).x.hash ? "reference" : "part"); free_mapping(m); } #endif /* DEBUG */ hm = SV_MAPPING(m).x.hash; if (!--hm->ref) { int num_values = SV_MAPPING(m).num_values; struct map_chain *mc, *next; for (mc = hm->deleted; mc; mc = next) { mp_int j; j = num_values; do { union svalue sv = (&mc->key)[j]; FREE_SVALUE(sv); } while (--j >= 0); next = mc->next; free_gen(mc); } } FREE_ALLOCED_SVALUE(m); } static struct hmap_x *add_hash(svalue m) { union svalue sv; struct hmap_x *hm; sv = ALLOC_TTS(T_INTERNAL, IT_X_HMAP, 1, sizeof (char *) + sizeof *hm); if (!sv.i) { return 0; } hm->uid = SV_MAPPING(m).x.uid->self; if (MAPX_TYPE(hm) == IT_X_MAP) { MAPX_REF(hm) = MAPX_REF(SV_MAPPING(m).x.x); free_block( (uint8 *)SV_MAPPING(m).x.hash-sizeof(char *)+1, sizeof(char *)+ sizeof(struct map_x)); } SV_MAPPING(m).x.hash = hm; hm->mask = hm->used = hm->condensed_deleted = 0; hm->chains[0] = 0; SV_MAPPING(last_dirty_mapping).x.hash->next_dirty = m; last_dirty_mapping = m; #ifdef DEBUG hm->next_dirty = 0; hm->deleted = 0; #endif hm->ref = 0; num_dirty_mappings++; SET_JOB(do_compact_mappings); return hm; } struct lvalue m_delete_marker; union svalue *get_map_lvalue(union svalue m, union svalue map_index, int insert) { mp_int size; svalue *cm = SV_MAPPING(m).condensed; struct hmap_x *hm; int num_values = SV_MAPPING(m).num_values; p_int hash; if (SV_IS_NUMBER(map_index)) { goto got_number; } else switch(SV_TYPE(map_index)) { case T_DESTRUCTED: map_index.i = 0; case T_STRING: case T_LSTRING: map_index = findstring(map_index); goto got_pointer; case T_ISTRING: case T_ILSTRING: map_index = SV_ISTRING(map_index); case T_GSTRING: case T_GLSTRING: case T_ARRAY: case T_MAPPING: case T_OBJECT: got_pointer: got_number: /* We can test equality and order on the svalue itself */ { svalue first, *key; mp_int offset, orig_size; cm = SV_MAPPING(m).condensed; size = CMAP_SIZE(cm); key = cm; orig_size = size; first = *cm; if (!SV_IS_NUMBER(first) && !SV_STRONG_EQUALITY(SV_TYPE(first))) { /* size >= 1, since the empty cmap has a number first */ mp_int o = size; do { o++; o>>= 1; if (o <= size && !SV_IS_NUMBER(first = key[o-1]) || !SV_STRONG_EQUALITY(SV_TYPE(first)) ) { key += o; size -= o; } } while (o > 1); } if (size) { offset = size-1; offset |= offset >> 1; offset |= offset >> 2; offset |= offset >> 4; offset |= offset >> 8; offset |= offset >> 16; if ( (offset = offset+1 >> 1) ) { svalue search = map_index; do { if (offset >= size) continue; if ( search.i >= key[offset].i ) { key += offset; size -= offset; } } while ( (offset >>= 1) ); } if ( map_index.i == key->i ) { /* found it */ if (insert >= 0) { #ifndef FAST_MULTIPLICATION if (num_values == 1) /* speed up this case */ return key + orig_size; else #endif/*FAST_MULTIPLICATION*/ return key + orig_size * num_values; } else { svalue sv; hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) != IT_X_HMAP) { hm = add_hash(m); if (!hm) return 0; } hm->condensed_deleted++; sv = *key; if (SV_IS_NUMBER(sv)) { sv.i = sv.i-1 | 2; } else { FREE_ALLOCED_SVALUE(sv); sv.i |= 2; if (sv.i > key[1].i && size > 1) { int i; *key = key[1]; key[1] = sv; key += orig_size; for (i = num_values; --i >= 0; key++) { sv = *key; FREE_SVALUE(sv); *key = key[num_values]; key[num_values].i = 0; } return 0; } } *key = sv; return 0; } } /* not found */ } hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) != IT_X_HMAP) { struct map_chain *mc; mp_int i; svalue sv; insert_first: if (insert <= 0) return EMPTY_CMAP; sv = ALLOC_TTS(T_INTERNAL, IT_X_HMAP, 1, sizeof (char *) + sizeof *hm); if (!sv.i) return 0; hm = (struct hmap_x *)(sv.p - 1 + sizeof(p_int)); hm->mask = hm->condensed_deleted = 0; hm->ref = 0; hm->used = 1; hm->uid = SV_MAPPING(m).x.uid->self; SV_MAPPING(last_dirty_mapping).x.hash->next_dirty = m; if (MAP_HAS_X(&SV_MAPPING(m))) { ((uint16 *)hm)[-1] = MAP_REF(&SV_MAPPING(m)); free_block((uint8 *)SV_MAPPING(m).x.hash - sizeof (char *) + 1, sizeof(char *)+ sizeof(struct map_x)); } last_dirty_mapping = m; #ifdef DEBUG hm->next_dirty = 0; hm->deleted = 0; #endif num_dirty_mappings++; SET_JOB(do_compact_mappings); SV_MAPPING(m).x.hash = hm; mc = (struct map_chain *)alloc_gen(MAP_CHAIN_SIZE(num_values)); hm->chains[0] = mc; if (!mc) return 0; mc->next = 0; mc->key = COPY_SVALUE(map_index); i = num_values; if (i) do { mc->data[i-1].i = 0; } while (--i); return mc->data; } else { struct map_chain **mcp, *mc; mp_int i; hash = map_index.i; hash = hash ^ hash >> 16; hash = hash ^ hash >> 8; i = hash & hm->mask; mcp = &hm->chains[i]; if ((mc = *mcp)) for (;;) { if (mc->key.i != map_index.i) { mcp = &mc->next; if ((mc = *mcp)) continue; break; } if (insert >= 0) { return mc->data; } else { *mcp = mc->next; if (hm->ref) { mc->next = hm->deleted; hm->deleted = mc; } else { int j; svalue sv; j = num_values; do { sv = (&mc->key)[j]; FREE_SVALUE(sv); } while (--j >= 0); free_gen(mc); } hm->used--; return 0; } } insert_another: if (insert <= 0) return EMPTY_CMAP; if (hm->used & ~hm->mask<<1) { /* Avoid average map_chains lengths above 2 by reallocating the * array of pointers */ struct hmap_x *hm2; mp_int mask, j; struct map_chain **mcp, **mcp2, *next; svalue sv; hm2 = hm; size = (hm->mask << 1) + 2; mask = size - 1; sv = ALLOC_TTS(T_INTERNAL, IT_X_HMAP, 1, sizeof (char *) + sizeof *hm + sizeof hm->chains[0] * mask); if (!sv.i) return 0; hm = (struct hmap_x *)&sv.p[sizeof (char *) -1]; MAPX_REF(hm) = MAPX_REF(hm2); *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.i; i = i ^ i >> 16; i = i ^ i >> 8; i &= mask; mc->next = mcp[i]; mcp[i] = mc; } } SV_MAPPING(m).x.hash = hm; free_block((uint8 *)hm2 - sizeof(char *) + 1, sizeof(char *) + sizeof *hm2 + sizeof hm2->chains[0] * hm2->mask); } mc = (struct map_chain *)alloc_gen(MAP_CHAIN_SIZE(num_values)); if (!mc) return 0; hm->used++; i = hash & hm->mask; mc->next = hm->chains[i]; hm->chains[i] = mc; mc->key = COPY_SVALUE(map_index); i = num_values; if (i) do { mc->data[i-1].i = 0; } while (--i); return mc->data; } break; } { /* Simular code in f_member() . */ svalue *min, *med, *lub, medv; p_int size; p_int mk0, mk1, m2, mk2, m3, mk3; default: m2 = 0; m3 = 0; goto search_value; case T_FLOAT: m2 = ~0; mk2 = SV_KEY(map_index)[2]; m3 = 0; goto search_value; case T_CLOSURE: switch(SV_CLOSURE(map_index).g.closure_type) { case CLOSURE_BOUND_LAMBDA: m2 = ~0; mk2 = SV_KEY(map_index)[2]; m3 = 0; break; case CLOSURE_ALIEN_LFUN: m2 = S2I32(0, 0xffff); mk2 = SV_KEY(map_index)[2]; m3 = ~0; mk3 = SV_KEY(map_index)[3]; break; case CLOSURE_LFUN: case CLOSURE_IDENTIFIER: m2 = S2I32(0, 0xffff); mk2 = SV_KEY(map_index)[2]; m3 = 0; break; default: m2 = 0; m3 = 0; break; } goto search_value; case T_QUOTED: /* byte 4..7:sv byte 2..3:quotes byte 0:type */ m2 = 0; m3 = 0; search_value: /* we exploit the fact that types with SV_STRONG_EQUALITY sort lower */ min = cm; lub = cm + (size = CMAP_SIZE(cm)); mk0 = SV_KEY(map_index)[0]; EXTRACT_T_WORD(mk0); mk1 = SV_KEY(map_index)[1]; mk2 &= m2; mk3 &= m3; while (min < lub) { p_int tmp; med = (svalue *)((((p_int)min + (p_int)lub) >> 1) & -sizeof *med); medv = *med; if ((medv.i & 3) != 1) goto raise_min; tmp = SV_KEY(medv)[0]; EXTRACT_T_WORD(tmp); if (mk0 == tmp) { tmp = SV_KEY(medv)[1]; if (mk1 == tmp) { tmp = SV_KEY(medv)[2] & m2; if (mk2 == tmp) { tmp = SV_KEY(medv)[3] & m3; if (mk3 == tmp) { goto found_value; } else if (mk3 <= tmp) { goto lower_lub; } else { goto raise_min; } } else if (mk2 <= tmp) { goto lower_lub; } else { goto raise_min; } } else if (mk1 <= tmp) { goto lower_lub; } else { goto raise_min; } } else if (mk0 > tmp) { raise_min: min = med + 1; } else { lower_lub: lub = med; } } /* not found in cmap */ hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) != IT_X_HMAP) { goto insert_first; } else { struct map_chain **mcp, *mc; mp_int i; #ifndef WORDS_BIGENDIAN mk0 = (p_uint)mk0 << 8 | (p_uint)mk0 >> 24; #endif hash = mk0 ^ mk1 ^ (mk2 & m2) ^ (mk3 & m3); hash = hash ^ hash >> 16; hash = hash ^ hash >> 8; i = hash & hm->mask; mcp = &hm->chains[i]; if ((mc = *mcp)) for (;;) { if (((*SV_KEY(mc->key) & COMBINE8_8_16(T_MASK,0,0xffff)) ^ mk0) | (SV_KEY(mc->key)[1] ^ mk1) || ((SV_KEY(mc->key)[2] & m2) ^ mk2) | ((SV_KEY(mc->key)[3] & m3) ^ mk3) ) { mcp = &mc->next; if ((mc = *mcp)) continue; break; } if (insert >= 0) { return mc->data; } else { *mcp = mc->next; if (hm->ref) { mc->next = hm->deleted; hm->deleted = mc; } else { int j; svalue sv; j = num_values; do { sv = (&mc->key)[j]; FREE_SVALUE(sv); } while (--j >= 0); free_gen(mc); } hm->used--; return 0; } } /* not found in hash table either */ goto insert_another; } found_value: if (insert >= 0) { med += size * num_values; if (med->p == TO_SVALUE(&m_delete_marker).p) { if (insert) { svalue *svp = med, sv; int i; med->i = 0; for (i = num_values; --i; ) { sv = svp[i]; FREE_SVALUE(sv); svp[i].i = 0; } } else { return EMPTY_CMAP; } } return med; } else { hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) != IT_X_HMAP) { hm = add_hash(m); if (!hm) return 0; } hm->condensed_deleted++; if (num_values) { svalue sv; med += size * num_values; sv = *med; FREE_SVALUE(sv); *med = TO_SVALUE(&m_delete_marker); return 0; } else { svalue sv; map_index = *med; FREE_ALLOCED_SVALUE(map_index); while (med > cm && med[-1].p == map_index.p) med--; if (med == cm || ((sv = med[-1]).i & 3) != 1 || SV_STRONG_EQUALITY(SV_TYPE(sv))) { sv.i = (p_uint)~0 >> 1; } do { *med = sv; med++; } while (med->p == map_index.p); return 0; } } break; } } } svalue copy_mapping(svalue m, svalue ob) { union svalue m2; struct hmap_x *hm, *hm2; union svalue *cm, *cm2; mp_int num_values = SV_MAPPING(m).num_values; mp_int size; mp_int i; svalue sv; cm = SV_MAPPING(m).condensed; size = CMAP_SIZE(cm); if (!size) { cm2 = EMPTY_CMAP; } else { union svalue *svp, *svp2; size = size * (num_values+1); sv = alloc(CMAP_HEADER(size), sizeof(char *) + size * sizeof(char *)); size *= sizeof(union svalue); if (!sv.i) return 0; cm2 = (union svalue *)(sv.p - 1 + sizeof(char *)); *cm2 = *cm; for (svp = cm, svp2 = cm2, i = size; i -= sizeof *svp >= 0;) { sv = *(union svalue *)((char *)svp + i); if ((sv.i & 3) == 1) REF_INC_IN_VAR(sv); *(union svalue *)((char *)svp2 + i) = sv; } } m2 = ALLOC(T_MAPPING, 1, sizeof SV_MAPPING(m2)); if (!m2.i) return 0; SV_MAPPING(m2).condensed = cm2; SV_MAPPING(m2).num_values = num_values; (SV_MAPPING(m2).x.uid = SV_OBJECT(ob).x.uid->self)->total_mapping += sizeof SV_MAPPING(m2) + sizeof(char*) + size; num_mappings++; hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) == IT_X_HMAP) { struct map_chain **mcp, **mcp2; mp_int linksize; size = hm->mask + 1; sv = ALLOC_TTS(T_INTERNAL, IT_X_HMAP, 1, GEN_ALLOCED_LEN(hm)); if (!sv.i) return 0; hm2 = (struct hmap_x *)&sv.p[sizeof (char *) -1]; hm2->uid = SV_MAPPING(m2).x.uid; SV_MAPPING(m2).x.hash = hm2; SV_MAPPING(last_dirty_mapping).x.hash->next_dirty = m2; last_dirty_mapping = m2; 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) { union svalue *svp, *svp2; mc2 = (struct map_chain *)alloc_gen(linksize); i = num_values; svp = &mc->key; svp2 = &mc2->key; do { union svalue sv2 = *svp; COPY_SVALUE_IN_VAR(sv2); *svp2 = sv2; } while (--i >= 0); mc2->next = last; last = mc2; } *mcp2++ = last; } while (--size); } return m2; } svalue add_mapping(svalue m1, svalue m2, svalue ob) { svalue m3; #if 1 m3 = copy_mapping(m1, ob); if (m3.i) add_to_mapping(m3, m2); #else struct hmap_x *hm; svalue *cm1, *cm2, *cm3; struct svalue *condensed_start, *condensed_end; mp_int num_values = SV_MAPPING(m1).num_values; mp_int size, size1, size2; mp_int 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 = SV_MAPPING(m1).condensed; cm2 = SV_MAPPING(m2).condensed; if (SV_MAPPING(m2).num_values != num_values) { if (!CMAP_SIZE(cm1) && MAP_X_TYPE(&SV_MAPPING(m1)) != IT_X_HMAP) { return copy_mapping(m2, ob); } else { return copy_mapping(m1, ob); } } misc_size = CMAP_SIZE(cm1) + CMAP_SIZE(cm2); if (!misc_size) { cm3 = EMPTY_CMAP; } else { union svalue csv; size = sizeof *cm3 + misc_size * (1+num_values); csv = alloc(CMAP_HEADER(size), sizeof(char *) + size * sizeof(char *)); size *= sizeof(union svalue); if (!csv.i) return SV_NULL; cm3 = (union svalue *)(csv.p - 1 + sizeof(char *)); } condensed_end = (struct svalue *)((char *)cm + 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 ); sv1 = *svp1; sv2 = *svp2; for(;size1 && size2; svp3++) { if (sv1.i < sv2.i) { sv3 = sv1; for (i = num_values; --i >= 0; ) *data3++ = COPY_SVALUE(*data1++); sv1 = *++svp1; size1 -= sizeof *svp1; } else { if (sv1.i == sv2.i) { if((*sv1.i & 3) != 3) { dirty++; } data1 += num_values; size1 -= sizeof *svp1; } sv3 = sv2; for (i = num_values; --i >= 0; ) *data3++ = COPY_SVALUE(*data2++); sv2 = *++svp2; size2 -= sizeof *svp2; } if ((sv3.i & 3) == 1) COPY_SVALUE_IN_VAR(sv3); *svp3 = sv3; } for (j = dirty; --j >= 0; svp++) { svp->i = ~(p_uint)0 >> 1; for (i = num_values; --i >= 0; data3++) data3->i = 0; } for(;size1 && size2; svp3++) { if (sv1.i < sv2.i) { sv3 = sv1; for (i = num_values; --i >= 0; ) *data3++ = COPY_SVALUE(*data1++); sv1 = *++svp1; size1 -= sizeof *svp1; } else { if (sv1.i == sv2.i) { if( *sv1.i & 2 ) { *str3++ = sv1; } else { dirty++; *str3++ = sv1 - 1; } sv1 = *++svp1; for (i = num_values; --i >= 0; ) *data3++ = TO_SVALUE(&m_delete_marker); data1 += num_values; size1 -= sizeof *svp1; } sv3 = sv2; for (i = num_values; --i >= 0; ) *data3++ = COPY_SVALUE(*data2++); sv2 = *++svp2; size2 -= sizeof *svp2; } if ((sv3.i & 3) == 1) COPY_SVALUE_IN_VAR(sv3); *svp3 = sv3; } 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; if ( !(m3 = allocate_mapping(size1, num_values)) ) { xfree((char *)condensed_start); /* There's a value leak here, well, gcollect will take care of this */ return 0; } xfree( (char *)m3->condensed ); m3->condensed = cm3; if (size1) m3->hash->condensed_deleted = dirty; (m3->user = current_object->user)->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); } #endif return m3; } void m_indices_filter(svalue key, svalue *data, uint8 *extra) { svalue **svpp = (svalue **)extra; *(*svpp)++ = COPY_SVALUE(key); } void walk_mapping( union svalue m, void (*func)(union svalue, union svalue *, uint8 *), char *extra) { union svalue *keyp, key, *data; mp_int size; mp_int num_values; struct hmap_x *hm; num_values = SV_MAPPING(m).num_values; keyp = SV_MAPPING(m).condensed; size = CMAP_SIZE(keyp); data = keyp + size; while (--size >= 0) { key = keyp; if (key.i & 3 != 3) (*func)(key, data, extra); data += num_values; } hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) == IT_X_HMAP) { 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) svalue key, *data; uint8 *extra; { svalue *svp; if (!SV_IS_NUMBER(key)) { if (SV_TYPE(key) == T_DESTRUCTED) return; REF_INC_IN_VAR(key); } svp = *(svalue **)extra; *svp = key; (++svp)->lvalue = data; *(svalue **)extra = ++svp; } void f_walk_mapping_cleanup(svalue m, svalue *arg) { svalue *svp; mp_int i; if (arg[-1].i) { struct hmap_x *hm; int num_values; hm = SV_MAPPING(m).x.hash; num_values = SV_MAPPING(m).num_values; if (!--hm->ref) { struct map_chain *mc, *next; svalue *svp2; for (mc = hm->deleted; mc; mc = next) { mp_int j; svp2 = &mc->key; j = num_values; do { svalue sv = *svp2++; FREE_SVALUE(sv); } while (--j >= 0); next = mc->next; free_gen(mc); } } } svp = arg; i = arg[-2].i; if (i) do { svalue sv = *svp; FREE_SVALUE(sv); svp += 2; } while (--i > 0); x_free((char *)(arg - 2)); } struct walk_mapping_descriptor { svalue *start, *end, *extra; p_int num_values, num_extra; struct lvalue *lvalues; struct hmap_x *hm; svalue result; }; static struct control_ret f_walk_mapping_callback(svalue, struct frame *); struct control_ret walk_mapping_dispatch(struct frame *fp, svalue *sp, int num_arg, inter_callback cb[4], int kind) { extern svalue *inter_sp; svalue *arg, sv, *extra; int extra_num; svalue m, ob, fp_object, func; struct call_cache_entry *centry; uint8 * funstart; struct walk_mapping_descriptor *wmd; struct hmap_x *hm; svalue *pointers, *data; mp_int i, num_values; struct lvalue *lvp; arg = sp - num_arg + 1; m = arg[0]; if (SV_IS_NUMBER(m) || SV_TYPE(m) != T_MAPPING) { struct control_ret cntret; bad_efun_arg(1); cntret.sp = sp; cntret.fp = fp; return cntret; } if (!SV_MAPPING(m).num_values) { struct control_ret cntret; cntret.sp = sp; cntret.fp = fp; (*cb[3])(m, fp); return cntret; } ASSIGN_EVAL_COST(&SV_OBJECT(fp_object = fp->object)); func = arg[1]; if (SV_IS_NUMBER(func)) { bad_efun_arg(2); } else if (SV_TYPE(func) == T_CLOSURE) { ob = 0; extra_num = num_arg - 2; extra = &arg[2]; } else if (!SV_IS_STRING(func)) { bad_efun_arg(2); } else { struct cache_call_ret ccret; if (num_arg >= 3) { sv = arg[2]; if (SV_IS_NUMBER(sv)) bad_efun_arg(3); else if (SV_TYPE(sv) == T_OBJECT) ob = sv; else if (!SV_IS_STRING(sv) || !(inter_sp = sp, inter_fp = fp, ob = find_object(sv, MAX_INHERIT_DEPTH)).p ) bad_efun_arg(3); extra_num = num_arg - 3; extra = &arg[3]; } else { ob = fp_object; extra_num = 0; } ccret = cache_call(ob, func, fp); ob = ccret.u.ob; centry = ccret.entry; if (!centry) { struct control_ret cntret; cntret.sp = sp; cntret.fp = fp; (*cb[3])(m, fp); return cntret; } funstart = centry->funstart; } wmd = (struct walk_mapping_descriptor *)sp; wmd->extra = extra; wmd->num_extra = extra_num; num_values = SV_MAPPING(m).num_values; wmd->num_values = num_values; i = CMAP_SIZE(SV_MAPPING(m).condensed); hm = SV_MAPPING(m).x.hash; if (MAPX_TYPE(hm) == IT_X_HMAP) { i += hm->used - hm->condensed_deleted; if (!num_values) { hm = 0; } else if (!hm->ref++) { hm->deleted = 0; } } else { hm = 0; } wmd->hm = hm; wmd->result = kind < 0 ? SV_NULL : allocate_mapping(i, kind ? kind : num_values, fp_object); if (!FUNSTART2NARGS(funstart)) cb++; if (!FUNSTART2NARGS(funstart) && kind < 0) { wmd->num_extra = i; } else { /* allocate lvalue space: svalue[2*num_values] */ pointers = (svalue *)x_alloc( ((i + num_values) * 2) * sizeof(svalue) ); if (!pointers) { struct control_ret cntret; cntret.sp = sp; cntret.fp = fp; return cntret; } wmd->start = wmd->end = pointers; walk_mapping(m, f_walk_mapping_filter, (uint8 *)&wmd->end); wmd->lvalues = lvp = (struct lvalue *)wmd->end; data = pointers->lvalue; while (--num_values >= 0) { lvp->type = T_LVALUE; lvp->ref = 255; lvp->type = LVALUE_SIMPLE; lvp->pad = 0; lvp->lvalue = data++; lvp++; } } /* FIXME: prune num_extra / num_values */ /* FIXME: push key & data for first element */ /* FIXME: push extra */ if (SV_TYPE(func) == T_CLOSURE) { sp = (svalue *)(wmd+1); } else { struct control_ret cntret; struct program *prog; cntret = make_frame((svalue *)(wmd+1), num_arg, centry->funstart); cntret.fp->previous = fp; fp = cntret.fp; fp->object = ob; fp->variable = SV_OBJECT(ob).variable + centry->cache_variable_index_offset; prog = centry->program; fp->program = prog; fp->shared = prog->shared; fp->virtual.function_8 = prog->virtual.function_8 + centry->cache_virtual_index_offset; fp->return_mode.fun = *cb; return cntret; } } /* * Simple case: no VARARGS triggered, the key argument is accepted. * Ignored mapping values / extra arguments can be handled here * (or rather need no longer be bothered about) * after previous pruning of num_values / num_extra. */ struct control_ret f_walk_mapping_callback(svalue result, struct frame *fp) { int nargs; struct walk_mapping_descriptor *wmd; svalue *argp, *vp, *end; struct control_ret ret; int i; struct lvalue *lvp; FREE_SVALUE(result); nargs = FUNSTART2NARGS(fp->funstart); argp = fp->arguments - nargs; wmd = (struct walk_mapping_descriptor *)&argp[1] - 1; ++argp; FREE_SVALUE(*argp); end = wmd->end; end -= 2; if (end == wmd->start) { fp->return_mode.i = fp >= inter_stack.external ? IR_EXTERN_XF : IR_EXTERN; } *argp = *end; vp = end[1].lvalue; lvp = wmd->lvalues; for (i = wmd->num_values; --i >= 0;) { (lvp++)->lvalue = vp++; } for (i = wmd->num_extra; --i >= 0;) { } i = FUNSTART2NLOCAL(fp->funstart); ret.sp = CONTROL_LOCALS(ret.fp) - 1; if (i) do { (++ret.sp)->i = 0; } while (--i); ret.fp = fp; return ret; } /* special case: no arguments accepted */ struct control_ret f_walk_mapping_zcallback(svalue result, struct frame *fp) { struct walk_mapping_descriptor *wmd; struct control_ret ret; int i; FREE_SVALUE(result); wmd = (struct walk_mapping_descriptor *)&fp->arguments[1] - 1; if (!--wmd->num_extra) { fp->return_mode.i = fp >= inter_stack.external ? IR_EXTERN_XF : IR_EXTERN; } i = FUNSTART2NLOCAL(fp->funstart); ret.sp = CONTROL_LOCALS(fp) - 1; if (i) do { (++ret.sp)->i = 0; } while (--i); ret.fp = fp; return ret; } struct control_ret f_walk_mapping_vcallback(svalue result, struct frame *fp) { } struct control_ret f_walk_mapping_nilcallback(svalue m, struct frame *fp) { } struct control_ret f_walk_mapping(struct frame *fp, svalue *sp, int num_arg) { static inter_callback cb[] = { f_walk_mapping_callback, f_walk_mapping_zcallback, f_walk_mapping_vcallback, f_walk_mapping_nilcallback }; return walk_mapping_dispatch(fp, sp, num_arg, cb, -1); } svalue *f_m_indices(svalue *sp, struct frame *fp) { svalue m, a, *svp; struct hmap_x *hm; mp_int size; m = *sp; if (SV_TYPE(m) != T_MAPPING) { bad_efun_arg(1); } else { hm = SV_MAPPING(m).x.hash; size = CMAP_SIZE(SV_MAPPING(m).condensed) + (MAPX_TYPE(hm) == IT_X_HMAP ? hm->used - hm->condensed_deleted : 0); if ((a = allocate_array(size, SV_OBJECT(fp->object).x.uid->self)).p) { svp = SV_ARRAY(a).member; walk_mapping(m, m_indices_filter, (uint8 *)&svp); *sp = a; } } return sp; } static void add_to_mapping_filter( svalue key, register svalue *data, uint8 *extra) { register volatile union svalue (*data2); register int i; data2 = get_map_lvalue((union svalue)extra, key, 1); for (i = (SV_MAPPING((union svalue)extra)).num_values; --i >= 0;) { register union svalue sv; sv = data2[i]; FREE_SVALUE(sv); sv = data[i]; COPY_SVALUE_IN_VAR(sv); data2[i] = sv; } } void sub_from_mapping_filter(svalue key, svalue *data, uint8 *extra) { remove_mapping((/* mapping */ svalue)extra, key); } void add_to_mapping(svalue m1, svalue m2) { if (SV_MAPPING(m2).num_values != SV_MAPPING(m1).num_values) { svalue *cm1, *cm2; cm2 = SV_MAPPING(m2).condensed; if (!CMAP_SIZE(cm2) && !MAP_X_TYPE(&SV_MAPPING(m2)) == IT_X_HMAP) { SV_MAPPING(m2).num_values = SV_MAPPING(m1).num_values; } else { cm1 = SV_MAPPING(m1).condensed; if (!CMAP_SIZE(cm1) && !MAP_X_TYPE(&SV_MAPPING(m1)) == IT_X_HMAP) { SV_MAPPING(m1).num_values = SV_MAPPING(m2).num_values; } else { return; } } } walk_mapping(m2, add_to_mapping_filter, m1.p); } svalue subtract_mapping(svalue minuend, svalue subtrahend, svalue ob) { /* 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, ob); walk_mapping(subtrahend, sub_from_mapping_filter, minuend.p); return minuend; } /* * Simple case: no VARARGS triggered, the key argument is accepted. * Ignored mapping values / extra arguments can be handled here * (or rather need no longer be bothered about) * after previous pruning of num_values / num_extra. */ struct control_ret f_filter_mapping_callback(svalue result, struct frame *fp) { int nargs; struct walk_mapping_descriptor *wmd; svalue *argp, *end; struct control_ret ret; int i; nargs = fp->funstart[-2]; argp = fp->arguments - nargs; wmd = (struct walk_mapping_descriptor *)&argp[1] - 1; ++argp; end = wmd->end; do { svalue m, *svp, *vp; if (!SV_IS_NUMBER(result)) FREE_ALLOCED_SVALUE(result); else if (!result.i) break; m = wmd->result; svp = get_map_lvalue(m, end[0], 1); vp = end[1].lvalue; for (i = wmd->num_values; --i >= 0;) { svalue sv = *vp++; COPY_SVALUE_IN_VAR(sv); *svp++ = sv; } } while (0); FREE_SVALUE(*argp); end -= 2; if (end == wmd->start) { fp->return_mode.i = fp >= inter_stack.external ? IR_EXTERN_XF : IR_EXTERN; } *argp = *end; for (i = wmd->num_extra; --i >= 0;) { } i = FUNSTART2NLOCAL(fp->funstart); ret.sp = CONTROL_LOCALS(ret.fp) - 1; if (i) do { (++ret.sp)->i = 0; } while (--i); ret.fp = fp; return ret; } /* special case: no arguments accepted */ struct control_ret f_filter_mapping_zcallback(svalue result, struct frame *fp) { struct walk_mapping_descriptor *wmd; struct control_ret ret; int i; wmd = (struct walk_mapping_descriptor *)&fp->arguments[1] - 1; /*FIXME:filter!*/ if (0/*FIXME*/) { fp->return_mode.i = fp >= inter_stack.external ? IR_EXTERN_XF : IR_EXTERN; } i = FUNSTART2NLOCAL(fp->funstart); ret.sp = CONTROL_LOCALS(fp) - 1; if (i) do { (++ret.sp)->i = 0; } while (--i); ret.fp = fp; return ret; } struct control_ret f_filter_mapping_vcallback(svalue result, struct frame *fp) { } struct control_ret f_filter_mapping_nilcallback(svalue m, struct frame *fp) { } /* leave a filtered mapping on the stack */ struct control_ret f_filter_mapping(struct frame *fp, svalue *sp, int num_arg) { static inter_callback cb[] = { f_filter_mapping_callback, f_filter_mapping_zcallback, f_filter_mapping_vcallback, f_filter_mapping_nilcallback }; return walk_mapping_dispatch(fp, sp, num_arg, cb, 1); } #if 0 /* leave result mapping on the stack */ struct control_ret f_map_mapping(struct frame *fp, svalue *sp, int num_arg) { static inter_callback cb[] = { f_map_mapping_callback, f_map_mapping_zcallback, f_map_mapping_vcallback, f_map_mapping_nilcallback }; return walk_mapping_dispatch(fp, sp, num_arg, cb, 0); } struct svalue *map_mapping (sp, num_arg) struct svalue *sp; int num_arg; { extern struct svalue *inter_sp; 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_xefun_vararg(1, 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_xefun_vararg(2, 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 || !(inter_sp = sp, ob = find_object(arg[2].u.string)) ) bad_xefun_vararg(3, 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((i = VEC_SIZE(vec)), 1); if (!m) { inter_sp = sp; error("Out of memory\n"); } (++sp)->type = T_MAPPING; sp->u.map = m; key = vec->item; for (; --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; } #endif #if 0 /* 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; CLEAR_JOB(do_compact_mappings); } 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) { #if 1 fatal("compact_mappings(): remaining ref count %ld!\n", hm->ref); #else struct svalue *svp; int i; printf("compact_mappings(): remaining ref count %ld!\n", hm->ref); #ifdef TRACE_CODE { extern int last_instructions(int, int, struct svalue **); last_instructions(TOTAL_TRACE_LENGTH, 1, 0); } #endif printf("compact_mappings(): remaining ref count! %ld\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 } #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; } #endif void do_compact_mappings() { malloc_privilege = MALLOC_SYSTEM; compact_mappings(num_dirty_mappings+80 >> 5); malloc_privilege = MALLOC_USER; /* no EXTRA_JOBS() call here because we want lazy mapping compacting */ } #if 0 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; user = owner->user; 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 #endif /* MALLOC_smalloc */