Diff | Source/Git

Download diff

	4b825dc642cb6eb9a060e54bf8d69288fbee4904		cfad47cfa334b206c65f22086bcc5d63e6f70944
		1	#ifdef RCSID
		2	static char RCSid[] =
		3	"$Header$";
		4	#endif
		5
		6	/*
		7	* Copyright (c) 2001, 2002 Michael J. Roberts. All Rights Reserved.
		8	*
		9	* Please see the accompanying license file, LICENSE.TXT, for information
		10	* on using and copying this software.
		11	*/
		12	/*
		13	Name
		14	vmlookup.cpp - LookupTable metaclass implementation
		15	Function
		16
		17	Notes
		18
		19	Modified
		20	02/06/01 MJRoberts - Creation
		21	*/
		22
		23	#include <stdlib.h>
		24	#include <string.h>
		25	#include <assert.h>
		26
		27	#include "t3std.h"
		28	#include "vmlookup.h"
		29	#include "vmerr.h"
		30	#include "vmerrnum.h"
		31	#include "vmtype.h"
		32	#include "vmglob.h"
		33	#include "vmobj.h"
		34	#include "vmundo.h"
		35	#include "vmmcreg.h"
		36	#include "vmfile.h"
		37	#include "vmbif.h"
		38	#include "vmmeta.h"
		39	#include "vmstack.h"
		40	#include "vmiter.h"
		41	#include "vmrun.h"
		42	#include "vmlst.h"
		43
		44
		45
		46	/* ------------------------------------------------------------------------ */
		47	/*
		48	* LookupTable undo record. We attach this record to the standard undo
		49	* record via the 'ptrval' field.
		50	*/
		51	struct lookuptab_undo_rec
		52	{
		53	/* action type */
		54	enum lookuptab_undo_action action;
		55
		56	/* key value */
		57	vm_val_t key;
		58	};
		59
		60
		61	/* ------------------------------------------------------------------------ */
		62	/*
		63	* Allocate a new extension structure
		64	*/
		65	vm_lookup_ext vm_lookup_ext::alloc_ext(VMG_ CVmObjLookupTable self,
		66	uint bucket_cnt, uint value_cnt)
		67	{
		68	size_t siz;
		69	vm_lookup_ext *ext;
		70
		71	/* calculate how much space we need */
		72	siz = sizeof(vm_lookup_ext)
		73	+ (bucket_cnt - 1) * sizeof(ext->buckets[0])
		74	+ value_cnt * sizeof(vm_lookup_val);
		75
		76	/* allocate the memory */
		77	ext = (vm_lookup_ext *)G_mem->get_var_heap()->alloc_mem(siz, self);
		78
		79	/* remember the table sizes */
		80	ext->bucket_cnt = bucket_cnt;
		81	ext->value_cnt = value_cnt;
		82
		83	/* return the new extension */
		84	return ext;
		85	}
		86
		87	/*
		88	* initialize the buckets and free list
		89	*/
		90	void vm_lookup_ext::init_ext()
		91	{
		92	uint i;
		93	vm_lookup_val **bucketp;
		94	vm_lookup_val *valp;
		95
		96	/* all of the buckets are initially empty */
		97	for (i = bucket_cnt, bucketp = buckets ; i != 0 ; --i, ++bucketp)
		98	*bucketp = 0;
		99
		100	/*
		101	* Initialize the value free list. We suballocate the value entry
		102	* structures out of our main allocation block; the available memory
		103	* for the structures comes immediately after the last bucket, so
		104	* bucketp points to the first value entry.
		105	*/
		106	valp = (vm_lookup_val )(void )bucketp;
		107	first_free = valp;
		108	for (first_free = valp, i = value_cnt ; i != 0 ; --i, ++valp)
		109	{
		110	/* link it into the free list */
		111	valp->nxt = valp + 1;
		112
		113	/* mark it as empty */
		114	valp->key.set_empty();
		115	valp->val.set_empty();
		116	}
		117
		118	/* terminate the free list at the last element */
		119	(valp - 1)->nxt = 0;
		120	}
		121
		122	/*
		123	* Reallocate an extension structure, adding more value entries.
		124	*/
		125	vm_lookup_ext vm_lookup_ext::expand_ext(VMG_ CVmObjLookupTable self,
		126	vm_lookup_ext *old_ext,
		127	uint new_value_cnt)
		128	{
		129	vm_lookup_ext *new_ext;
		130
		131	/* allocate a new extension structure of the requested size */
		132	new_ext = alloc_ext(vmg_ self, old_ext->bucket_cnt, new_value_cnt);
		133
		134	/* copy the old extension data into the new extension */
		135	new_ext->copy_ext_from(old_ext);
		136
		137	/* delete the old memory */
		138	G_mem->get_var_heap()->free_mem(old_ext);
		139
		140	/* return the new extension */
		141	return new_ext;
		142	}
		143
		144	/*
		145	* Copy extension data
		146	*/
		147	void vm_lookup_ext::copy_ext_from(vm_lookup_ext *old_ext)
		148	{
		149	vm_lookup_val **oldbp;
		150	vm_lookup_val **newbp;
		151	vm_lookup_val *oldval;
		152	vm_lookup_val *newval;
		153	char *oldbase;
		154	char *newbase;
		155	uint i;
		156
		157	/* the bucket counts must be the same in both extensions */
		158	assert(bucket_cnt == old_ext->bucket_cnt);
		159
		160	/* we must have at least as many entries as the old one had */
		161	assert(value_cnt >= old_ext->value_cnt);
		162
		163	/* get the new and old base values for faster pointer arithmetic */
		164	oldbase = (char *)old_ext->idx_to_val(0);
		165	newbase = (char *)idx_to_val(0);
		166
		167	/* copy the hash buckets from the old extension to the new extension */
		168	for (i = old_ext->bucket_cnt, oldbp = old_ext->buckets, newbp = buckets ;
		169	i != 0 ; --i, ++newbp, ++oldbp)
		170	{
		171	/* copy the bucket pointer, adjusting to our local pointer scheme */
		172	newbp = (oldbp == 0
		173	? 0
		174	: (vm_lookup_val )(((char )*oldbp - oldbase) + newbase));
		175	}
		176
		177	/* copy the values from the old extension to the new extension */
		178	for (i = old_ext->value_cnt, oldval = old_ext->idx_to_val(0),
		179	newval = idx_to_val(0) ;
		180	i != 0 ;
		181	--i, ++oldval, ++newval)
		182	{
		183	/* copy this entry */
		184	newval->key = oldval->key;
		185	newval->val = oldval->val;
		186	newval->nxt = (oldval->nxt == 0
		187	? 0
		188	: (vm_lookup_val )(((char )oldval->nxt - oldbase)
		189	+ newbase));
		190	}
		191
		192	/* link all of the remaining free values into the free list */
		193	first_free = newval;
		194	for (i = value_cnt - old_ext->value_cnt ; i != 0 ; --i, ++newval)
		195	{
		196	/* link this value into the free list */
		197	newval->nxt = newval + 1;
		198
		199	/* mark this free value as empty */
		200	newval->key.set_empty();
		201	newval->val.set_empty();
		202	}
		203
		204	/* terminate the free list */
		205	(newval - 1)->nxt = 0;
		206	}
		207
		208
		209	/* ------------------------------------------------------------------------ */
		210	/*
		211	* LookupTable object statics
		212	*/
		213
		214	/* metaclass registration object */
		215	static CVmMetaclassLookupTable metaclass_reg_obj;
		216	CVmMetaclass *CVmObjLookupTable::metaclass_reg_ = &metaclass_reg_obj;
		217
		218	/* function table */
		219	int (CVmObjLookupTable::
		220	*CVmObjLookupTable::func_table_[])(VMG_ vm_obj_id_t self,
		221	vm_val_t retval, uint argc) =
		222	{
		223	&CVmObjLookupTable::getp_undef,
		224	&CVmObjLookupTable::getp_key_present,
		225	&CVmObjLookupTable::getp_remove_entry,
		226	&CVmObjLookupTable::getp_apply_all,
		227	&CVmObjLookupTable::getp_for_each,
		228	&CVmObjLookupTable::getp_count_buckets,
		229	&CVmObjLookupTable::getp_count_entries,
		230	&CVmObjLookupTable::getp_for_each_assoc,
		231	&CVmObjLookupTable::getp_keys_to_list,
		232	&CVmObjLookupTable::getp_vals_to_list
		233	};
		234
		235
		236	/* ------------------------------------------------------------------------ */
		237	/*
		238	* Lookup Table metaclass implementation
		239	*/
		240
		241	/*
		242	* create a lookup table with a given hash table size and the given
		243	* initial entry table size
		244	*/
		245	CVmObjLookupTable::CVmObjLookupTable(VMG_ size_t bucket_cnt, size_t val_cnt)
		246	{
		247	vm_val_t empty;
		248
		249	/* set up an empty value */
		250	empty.set_empty();
		251
		252	/* allocate our extension structure from the variable heap */
		253	ext_ = (char *)vm_lookup_ext::alloc_ext(vmg_ this, bucket_cnt, val_cnt);
		254
		255	/* initialize the extension */
		256	get_ext()->init_ext();
		257	}
		258
		259
		260	/*
		261	* create
		262	*/
		263	vm_obj_id_t CVmObjLookupTable::create(VMG_ int in_root_set,
		264	uint bucket_count, uint init_capacity)
		265	{
		266	vm_obj_id_t id;
		267
		268	/* allocate the object ID */
		269	id = vm_new_id(vmg_ in_root_set, TRUE, FALSE);
		270
		271	/* create the object */
		272	new (vmg_ id) CVmObjLookupTable(vmg_ bucket_count, init_capacity);
		273
		274	/* return the new ID */
		275	return id;
		276	}
		277
		278	/*
		279	* create dynamically using stack arguments
		280	*/
		281	vm_obj_id_t CVmObjLookupTable::create_from_stack(
		282	VMG_ const uchar **pc_ptr, uint argc)
		283	{
		284	vm_obj_id_t id;
		285	size_t bucket_count;
		286	size_t init_capacity;
		287
		288	/* parse the arguments */
		289	get_constructor_args(vmg_ argc, &bucket_count, &init_capacity);
		290
		291	/*
		292	* allocate the object ID - this type of construction never creates a
		293	* root object
		294	*/
		295	id = vm_new_id(vmg_ FALSE, TRUE, FALSE);
		296
		297	/* create the object */
		298	new (vmg_ id) CVmObjLookupTable(vmg_ bucket_count, init_capacity);
		299
		300	/* return the new ID */
		301	return id;
		302	}
		303
		304	/*
		305	* get and check constructor arguments
		306	*/
		307	void CVmObjLookupTable::get_constructor_args(VMG_ uint argc,
		308	size_t *bucket_count,
		309	size_t *init_capacity)
		310	{
		311	/* check arguments */
		312	if (argc == 0)
		313	{
		314	/* no arguments - they want default parameters */
		315	*bucket_count = 32;
		316	*init_capacity = 64;
		317	}
		318	else if (argc == 2)
		319	{
		320	/*
		321	* two arguments - they specified the bucket count and initial
		322	* capacity; pop the parameters
		323	*/
		324	*bucket_count = (size_t)CVmBif::pop_long_val(vmg0_);
		325	*init_capacity = (size_t)CVmBif::pop_long_val(vmg0_);
		326	}
		327	else
		328	{
		329	/* invalid arguments */
		330	err_throw(VMERR_WRONG_NUM_OF_ARGS);
		331	}
		332
		333
		334	/* make sure both are positive */
		335	if (bucket_count <= 0 \|\| init_capacity <= 0)
		336	err_throw(VMERR_BAD_VAL_BIF);
		337	}
		338
		339	/*
		340	* Create a copy of this object
		341	*/
		342	vm_obj_id_t CVmObjLookupTable::create_copy(VMG0_)
		343	{
		344	vm_obj_id_t id;
		345	CVmObjLookupTable *new_obj;
		346
		347	/* allocate the object ID */
		348	id = vm_new_id(vmg_ FALSE, TRUE, FALSE);
		349
		350	/* allocate a new object */
		351	new_obj = new (vmg_ id) CVmObjLookupTable();
		352
		353	/*
		354	* set up the new object with our same sizes, but don't initialize it
		355	* - we're going to blast all of our data directly into the new
		356	* extension, so we don't need to waste time setting up an empty
		357	* initial state
		358	*/
		359	new_obj->ext_ = (char *)vm_lookup_ext::alloc_ext(
		360	vmg_ new_obj, get_bucket_count(), get_entry_count());
		361
		362	/* copy my data to the next object */
		363	new_obj->get_ext()->copy_ext_from(get_ext());
		364
		365	/* return the new object's id */
		366	return id;
		367	}
		368
		369	/*
		370	* notify of deletion
		371	*/
		372	void CVmObjLookupTable::notify_delete(VMG_ int /in_root_set/)
		373	{
		374	/* free our additional data, if we have any */
		375	if (ext_ != 0)
		376	G_mem->get_var_heap()->free_mem(ext_);
		377	}
		378
		379	/*
		380	* set a property
		381	*/
		382	void CVmObjLookupTable::set_prop(VMG_ class CVmUndo *undo,
		383	vm_obj_id_t self, vm_prop_id_t prop,
		384	const vm_val_t *val)
		385	{
		386	/* no settable properties - throw an error */
		387	err_throw(VMERR_INVALID_SETPROP);
		388	}
		389
		390	/*
		391	* get a property
		392	*/
		393	int CVmObjLookupTable::get_prop(VMG_ vm_prop_id_t prop, vm_val_t *retval,
		394	vm_obj_id_t self, vm_obj_id_t *source_obj,
		395	uint *argc)
		396	{
		397	uint func_idx;
		398
		399	/* translate the property into a function vector index */
		400	func_idx = G_meta_table
		401	->prop_to_vector_idx(metaclass_reg_->get_reg_idx(), prop);
		402
		403	/* call the appropriate function */
		404	if ((this->*func_table_[func_idx])(vmg_ self, retval, argc))
		405	{
		406	*source_obj = metaclass_reg_->get_class_obj(vmg0_);
		407	return TRUE;
		408	}
		409
		410	/* inherit default handling from our base class */
		411	return CVmObjCollection::
		412	get_prop(vmg_ prop, retval, self, source_obj, argc);
		413	}
		414
		415	/*
		416	* apply an undo record
		417	*/
		418	void CVmObjLookupTable::apply_undo(VMG_ struct CVmUndoRecord *undo_rec)
		419	{
		420	if (undo_rec->id.ptrval != 0)
		421	{
		422	lookuptab_undo_rec *rec;
		423
		424	/* get our private record from the standard undo record */
		425	rec = (lookuptab_undo_rec *)undo_rec->id.ptrval;
		426
		427	/* check the action in the record */
		428	switch(rec->action)
		429	{
		430	case LOOKUPTAB_UNDO_NULL:
		431	/*
		432	* null record, which means that it had a weak reference to an
		433	* object that has been deleted - there's no way to reinstate
		434	* such records, so ignore it
		435	*/
		436	break;
		437
		438	case LOOKUPTAB_UNDO_ADD:
		439	/* we added the entry, so we must now delete it */
		440	del_entry(vmg_ &rec->key);
		441	break;
		442
		443	case LOOKUPTAB_UNDO_DEL:
		444	/* we deleted the entry, so we must now add it */
		445	add_entry(vmg_ &rec->key, &undo_rec->oldval);
		446	break;
		447
		448	case LOOKUPTAB_UNDO_MOD:
		449	/* we modified the entry, so we must change it back */
		450	mod_entry(vmg_ &rec->key, &undo_rec->oldval);
		451	break;
		452	}
		453
		454	/* discard the private record */
		455	t3free(rec);
		456
		457	/* clear the pointer in the main record so we know it's gone */
		458	undo_rec->id.ptrval = 0;
		459	}
		460	}
		461
		462	/*
		463	* discard extra undo information
		464	*/
		465	void CVmObjLookupTable::discard_undo(VMG_ CVmUndoRecord *rec)
		466	{
		467	/* delete our extra information record */
		468	if (rec->id.ptrval != 0)
		469	{
		470	/* free the record */
		471	t3free((lookuptab_undo_rec *)rec->id.ptrval);
		472
		473	/* clear the pointer so we know it's gone */
		474	rec->id.ptrval = 0;
		475	}
		476	}
		477
		478	/*
		479	* Mark undo references.
		480	*/
		481	void CVmObjLookupTable::
		482	mark_undo_ref(VMG_ struct CVmUndoRecord *undo_rec)
		483	{
		484	lookuptab_undo_rec *rec;
		485
		486	/* get our private record from the standard undo record */
		487	rec = (lookuptab_undo_rec *)undo_rec->id.ptrval;
		488
		489	/* if the key in the record is an object, mark it referenced */
		490	if (rec->key.typ == VM_OBJ)
		491	G_obj_table->mark_all_refs(rec->key.val.obj, VMOBJ_REACHABLE);
		492
		493	/* if the value in the record is an object, mark it as well */
		494	if (undo_rec->oldval.typ == VM_OBJ)
		495	G_obj_table->mark_all_refs(undo_rec->oldval.val.obj,
		496	VMOBJ_REACHABLE);
		497	}
		498
		499	/*
		500	* Mark references. Keys (but not values) are strongly referenced.
		501	*/
		502	void CVmObjLookupTable::mark_refs(VMG_ uint state)
		503	{
		504	vm_lookup_val **bp;
		505	uint i;
		506
		507	/* run through my buckets */
		508	for (i = get_ext()->bucket_cnt, bp = get_ext()->buckets ;
		509	i != 0 ; --i, ++bp)
		510	{
		511	const vm_lookup_val *entry;
		512
		513	/* run through all entries attached to this bucket */
		514	for (entry = *bp ; entry != 0 ; entry = entry->nxt)
		515	{
		516	/* if the key is an object, mark it as referenced */
		517	if (entry->key.typ == VM_OBJ)
		518	G_obj_table->mark_all_refs(entry->key.val.obj, state);
		519
		520	/* if the entry is an object, mark it as referenced */
		521	if (entry->val.typ == VM_OBJ)
		522	G_obj_table->mark_all_refs(entry->val.val.obj, state);
		523	}
		524	}
		525	}
		526
		527	/*
		528	* load from an image file
		529	*/
		530	void CVmObjLookupTable::load_from_image(VMG_ vm_obj_id_t self,
		531	const char *ptr, size_t siz)
		532	{
		533	/* load our image data */
		534	load_image_data(vmg_ ptr, siz);
		535
		536	/*
		537	* save our image data pointer in the object table, so that we can
		538	* access it (without storing it ourselves) during a reload
		539	*/
		540	G_obj_table->save_image_pointer(self, ptr, siz);
		541	}
		542
		543	/*
		544	* reload from the image file
		545	*/
		546	void CVmObjLookupTable::reload_from_image(VMG_ vm_obj_id_t self,
		547	const char *ptr, size_t siz)
		548	{
		549	/* load our image data */
		550	load_image_data(vmg_ ptr, siz);
		551	}
		552
		553	/*
		554	* load or reload data from the image
		555	*/
		556	void CVmObjLookupTable::load_image_data(VMG_ const char *ptr, size_t siz)
		557	{
		558	uint bucket_cnt;
		559	uint val_cnt;
		560	uint i;
		561	const char *ibp;
		562	const char *ival;
		563	vm_lookup_val **ebp;
		564	vm_lookup_val *eval;
		565	vm_lookup_ext *ext;
		566
		567	/* free our existing extension, if we have one */
		568	if (ext_ != 0)
		569	G_mem->get_var_heap()->free_mem(ext_);
		570
		571	/* read the bucket and value counts from the header */
		572	bucket_cnt = osrp2(ptr);
		573	val_cnt = osrp2(ptr + 2);
		574
		575	/* allocate space for a copy of the image data */
		576	ext = vm_lookup_ext::alloc_ext(vmg_ this, bucket_cnt, val_cnt);
		577	ext_ = (char *)ext;
		578
		579	/* initialize the free list pointer, given as a 1-based entry index */
		580	ext->first_free = ext->img_idx_to_val(osrp2(ptr + 4));
		581
		582	/* initialize the table from the load image data */
		583	for (i = bucket_cnt, ibp = ptr + 6, ebp = ext->buckets ;
		584	i != 0 ; --i, ibp += 2, ++ebp)
		585	{
		586	/* translate the image file index to a value pointer */
		587	*ebp = ext->img_idx_to_val(osrp2(ibp));
		588	}
		589
		590	/* initialize the value entries */
		591	for (i = val_cnt, ival = ibp, eval = ext->idx_to_val(0) ;
		592	i != 0 ; --i, ival += VMLOOKUP_VALUE_SIZE, ++eval)
		593	{
		594	/* read the key and value */
		595	vmb_get_dh(ival, &eval->key);
		596	vmb_get_dh(ival + VMB_DATAHOLDER, &eval->val);
		597
		598	/* remember the next pointer, which is given as a 1-based index */
		599	eval->nxt = ext->img_idx_to_val(osrp2(ival + VMB_DATAHOLDER*2));
		600	}
		601	}
		602
		603	/*
		604	* save to a file
		605	*/
		606	void CVmObjLookupTable::save_to_file(VMG_ class CVmFile *fp)
		607	{
		608	vm_lookup_ext *ext = get_ext();
		609	uint i;
		610	vm_lookup_val **bp;
		611	vm_lookup_val *val;
		612
		613	/* write our bucket count, value count, and first-free index */
		614	fp->write_int2(ext->bucket_cnt);
		615	fp->write_int2(ext->value_cnt);
		616	fp->write_int2(ext->val_to_img_idx(ext->first_free));
		617
		618	/* write the buckets */
		619	for (i = ext->bucket_cnt, bp = ext->buckets ; i != 0 ; --i, ++bp)
		620	fp->write_int2(ext->val_to_img_idx(*bp));
		621
		622	/* write the values */
		623	for (i = ext->value_cnt, val = ext->idx_to_val(0) ; i != 0 ; --i, ++val)
		624	{
		625	char buf[VMLOOKUP_VALUE_SIZE];
		626	uint idx;
		627
		628	/* store the key, value, and index */
		629	vmb_put_dh(buf, &val->key);
		630	vmb_put_dh(buf + VMB_DATAHOLDER, &val->val);
		631	idx = ext->val_to_img_idx(val->nxt);
		632	oswp2(buf + VMB_DATAHOLDER*2, idx);
		633
		634	/* write the data */
		635	fp->write_bytes(buf, VMLOOKUP_VALUE_SIZE);
		636	}
		637	}
		638
		639	/*
		640	* restore from a file
		641	*/
		642	void CVmObjLookupTable::restore_from_file(VMG_ vm_obj_id_t self,
		643	CVmFile fp, CVmObjFixup fixups)
		644	{
		645	vm_lookup_ext *ext;
		646	char buf[64];
		647	size_t bucket_cnt;
		648	size_t val_cnt;
		649	size_t i;
		650	vm_lookup_val **bp;
		651	vm_lookup_val *entry;
		652	uint idx;
		653
		654	/* free our existing extension, if we have one */
		655	if (ext_ != 0)
		656	G_mem->get_var_heap()->free_mem(ext_);
		657
		658	/* read the fixed fields */
		659	fp->read_bytes(buf, 6);
		660	bucket_cnt = vmb_get_uint2(buf);
		661	val_cnt = vmb_get_uint2(buf + 2);
		662
		663	/* allocate the extension structure */
		664	ext = vm_lookup_ext::alloc_ext(vmg_ this, bucket_cnt, val_cnt);
		665	ext_ = (char *)ext;
		666
		667	/* store the free pointer */
		668	ext->first_free = ext->img_idx_to_val(vmb_get_uint2(buf + 4));
		669
		670	/* read the buckets */
		671	for (i = bucket_cnt, bp = ext->buckets ; i != 0 ; ++bp, --i)
		672	{
		673	/* read this bucket pointer and store it */
		674	idx = fp->read_uint2();
		675	*bp = ext->img_idx_to_val(idx);
		676	}
		677
		678	/* read the value entries */
		679	for (i = val_cnt, entry = ext->idx_to_val(0) ; i != 0 ; --i, ++entry)
		680	{
		681	/* read this value entry */
		682	fp->read_bytes(buf, VMLOOKUP_VALUE_SIZE);
		683
		684	/* fix up the key and value dataholders */
		685	fixups->fix_dh_array(vmg_ buf, 2);
		686
		687	/* store the key and value */
		688	vmb_get_dh(buf, &entry->key);
		689	vmb_get_dh(buf + VMB_DATAHOLDER, &entry->val);
		690
		691	/* store the next pointer */
		692	idx = osrp2(buf + VMB_DATAHOLDER*2);
		693	entry->nxt = ext->img_idx_to_val(idx);
		694	}
		695	}
		696
		697	/*
		698	* create an iterator
		699	*/
		700	void CVmObjLookupTable::new_iterator(VMG_ vm_val_t *retval,
		701	const vm_val_t *self_val)
		702	{
		703	vm_val_t copy_val;
		704
		705	/* save a copy of myself for protection against garbage collection */
		706	G_stk->push(self_val);
		707
		708	/*
		709	* create a copy of my object, so that we can iterate over a snapshot
		710	* of our state even if we subsequently change our state
		711	*/
		712	copy_val.set_obj(create_copy(vmg0_));
		713
		714	/* set up a new lookup table iterator object on the copy */
		715	retval->set_obj(CVmObjIterLookupTable::create_for_coll(vmg_ &copy_val));
		716
		717	/* done with the gc protection */
		718	G_stk->discard();
		719	}
		720
		721	/*
		722	* create a live iterator
		723	*/
		724	void CVmObjLookupTable::new_live_iterator(VMG_ vm_val_t *retval,
		725	const vm_val_t *self_val)
		726	{
		727	/* set up a new lookup table iterator directly on myself */
		728	retval->set_obj(CVmObjIterLookupTable::create_for_coll(vmg_ self_val));
		729	}
		730
		731	/*
		732	* add an undo record
		733	*/
		734	void CVmObjLookupTable::add_undo_rec(VMG_ vm_obj_id_t self,
		735	lookuptab_undo_action action,
		736	const vm_val_t *key,
		737	const vm_val_t *old_entry_val)
		738	{
		739	lookuptab_undo_rec *rec;
		740	vm_val_t nil_val;
		741
		742	/* allocate our record extension */
		743	rec = (lookuptab_undo_rec *)t3malloc(sizeof(lookuptab_undo_rec));
		744
		745	/* if either the key or old value are null pointers, use a nil value */
		746	nil_val.set_nil();
		747	if (key == 0)
		748	key = &nil_val;
		749	if (old_entry_val == 0)
		750	old_entry_val = &nil_val;
		751
		752	/* set up the record */
		753	rec->action = action;
		754	rec->key = *key;
		755
		756	/* add the record to the global undo stream */
		757	if (!G_undo->add_new_record_ptr_key(vmg_ self, rec, old_entry_val))
		758	{
		759	/*
		760	* we didn't add an undo record, so our extra undo information
		761	* isn't actually going to be stored in the undo system - hence we
		762	* must delete our extra information
		763	*/
		764	t3free(rec);
		765	}
		766	}
		767
		768	/*
		769	* Add an entry; does not generate undo.
		770	*/
		771	void CVmObjLookupTable::add_entry(VMG_
		772	const vm_val_t key, const vm_val_t val)
		773	{
		774	uint hashval;
		775	vm_lookup_val *entry;
		776
		777	/* push the key and value as gc protection for a moment */
		778	G_stk->push(key);
		779	G_stk->push(val);
		780
		781	/* calculate the hash value for the key */
		782	hashval = calc_key_hash(vmg_ key);
		783
		784	/* allocate an entry */
		785	entry = alloc_new_entry(vmg0_);
		786
		787	/* link this entry into the chain at this hash value */
		788	entry->nxt = get_ext()->buckets[hashval];
		789	get_ext()->buckets[hashval] = entry;
		790
		791	/* set the key and value for this entry */
		792	entry->key = *key;
		793	entry->val = *val;
		794
		795	/* discard the gc protection */
		796	G_stk->discard(2);
		797	}
		798
		799	/*
		800	* Add an entry, generating undo
		801	*/
		802	void CVmObjLookupTable::add_entry_undo(VMG_ vm_obj_id_t self,
		803	const vm_val_t *key,
		804	const vm_val_t *val)
		805	{
		806	/*
		807	* Add undo for the change. Since we're adding a new record, there's
		808	* no old value for the record.
		809	*/
		810	add_undo_rec(vmg_ self, LOOKUPTAB_UNDO_ADD, key, 0);
		811
		812	/* add the entry */
		813	add_entry(vmg_ key, val);
		814	}
		815
		816
		817	/*
		818	* Delete an entry; does not generate undo.
		819	*/
		820	void CVmObjLookupTable::del_entry(VMG_ const vm_val_t *key)
		821	{
		822	uint hashval;
		823	vm_lookup_val *entry;
		824	vm_lookup_val *prv_entry;
		825
		826	/* find the entry for the key */
		827	entry = find_entry(vmg_ key, &hashval, &prv_entry);
		828
		829	/* if we found it, unlink it */
		830	if (entry != 0)
		831	unlink_entry(vmg_ entry, hashval, prv_entry);
		832	}
		833
		834	/*
		835	* Unlink an entry
		836	*/
		837	void CVmObjLookupTable::unlink_entry(VMG_ vm_lookup_val *entry, uint hashval,
		838	vm_lookup_val *prv_entry)
		839	{
		840	vm_lookup_ext *ext = get_ext();
		841
		842	/*
		843	* set the previous item's next pointer, or the head of the chain, as
		844	* appropriate
		845	*/
		846	if (prv_entry == 0)
		847	ext->buckets[hashval] = entry->nxt;
		848	else
		849	prv_entry->nxt = entry->nxt;
		850
		851	/* link the entry into the free list */
		852	entry->nxt = ext->first_free;
		853	ext->first_free = entry;
		854
		855	/* set this entry's key and value to 'empty' to indicate that it's free */
		856	entry->key.set_empty();
		857	entry->val.set_empty();
		858	}
		859
		860	/*
		861	* Modify an entry; does not generate undo.
		862	*/
		863	void CVmObjLookupTable::mod_entry(VMG_ const vm_val_t *key,
		864	const vm_val_t *val)
		865	{
		866	vm_lookup_val *entry;
		867
		868	/* find the entry for the key */
		869	entry = find_entry(vmg_ key, 0, 0);
		870
		871	/* if we found it, change the value to the given value */
		872	if (entry != 0)
		873	entry->val = *val;
		874	}
		875
		876	/*
		877	* Set an entry's value, generating undo
		878	*/
		879	void CVmObjLookupTable::set_entry_val_undo(VMG_ vm_obj_id_t self,
		880	vm_lookup_val *entry,
		881	const vm_val_t *val)
		882	{
		883	/* generate undo for the change */
		884	add_undo_rec(vmg_ self, LOOKUPTAB_UNDO_MOD, &entry->key, &entry->val);
		885
		886	/* update the entry */
		887	entry->val = *val;
		888	}
		889
		890	/*
		891	* Find an entry for a given key. Returns the entry index, and fills in
		892	* the hash value and previous-entry output variables if provided.
		893	* Returns zero if there is no such key.
		894	*/
		895	vm_lookup_val CVmObjLookupTable::find_entry(VMG_ const vm_val_t key,
		896	uint *hashval_p,
		897	vm_lookup_val **prv_entry_p)
		898	{
		899	vm_lookup_ext *ext = get_ext();
		900	uint hashval;
		901	vm_lookup_val *entry;
		902	vm_lookup_val *prv_entry;
		903
		904	/* compute the hash value (and return it to the caller if desired) */
		905	hashval = calc_key_hash(vmg_ key);
		906	if (hashval_p != 0)
		907	*hashval_p = hashval;
		908
		909	/* scan the hash chain for this entry */
		910	for (prv_entry = 0, entry = ext->buckets[hashval] ; entry != 0 ;
		911	prv_entry = entry, entry = entry->nxt)
		912	{
		913	/* if it matches the key we're looking for, this is the one */
		914	if (entry->key.equals(vmg_ key))
		915	break;
		916	}
		917
		918	/* if the caller wanted to know the previous entry, tell them */
		919	if (prv_entry_p != 0)
		920	*prv_entry_p = prv_entry;
		921
		922	/* return the entry where we found the key, if indeed we found it */
		923	return entry;
		924	}
		925
		926
		927	/*
		928	* Calculate a hash value for a key
		929	*/
		930	uint CVmObjLookupTable::calc_key_hash(VMG_ const vm_val_t *key)
		931	{
		932	uint hash;
		933
		934	/* calculate the raw hash for the value */
		935	hash = key->calc_hash(vmg0_);
		936
		937	/* reduce the hash value modulo the hash table size */
		938	hash %= get_bucket_count();
		939
		940	/* return the hash value */
		941	return hash;
		942	}
		943
		944	/*
		945	* Allocate a new entry
		946	*/
		947	vm_lookup_val *CVmObjLookupTable::alloc_new_entry(VMG0_)
		948	{
		949	vm_lookup_val *entry;
		950
		951	/* if necessary, add more entry slots to the table */
		952	expand_if_needed(vmg0_);
		953
		954	/* get the first entry from the free list */
		955	entry = get_first_free();
		956
		957	/* unlink this entry from the free list */
		958	set_first_free(entry->nxt);
		959	entry->nxt = 0;
		960
		961	/* return the free entry */
		962	return entry;
		963	}
		964
		965	/*
		966	* Check for free space, and expand the table if necessary.
		967	*/
		968	void CVmObjLookupTable::expand_if_needed(VMG0_)
		969	{
		970	uint new_entry_cnt;
		971
		972	/* if we have any free entries left, we need do nothing */
		973	if (get_first_free() != 0)
		974	return;
		975
		976	/* increase the entry count by 50%, or 16 slots, whichever is more */
		977	new_entry_cnt = get_entry_count() + (get_entry_count() >> 1);
		978	if (new_entry_cnt < get_entry_count() + 16)
		979	new_entry_cnt = get_entry_count() + 16;
		980
		981	/* reallocate the extension at the new size */
		982	ext_ = (char *)vm_lookup_ext::expand_ext(
		983	vmg_ this, get_ext(), new_entry_cnt);
		984	}
		985
		986	/* ------------------------------------------------------------------------ */
		987	/*
		988	* Get a value by index
		989	*/
		990	void CVmObjLookupTable::index_val(VMG_ vm_val_t *result,
		991	vm_obj_id_t self,
		992	const vm_val_t *index_val)
		993	{
		994	vm_lookup_val *entry;
		995
		996	/* find the entry */
		997	entry = find_entry(vmg_ index_val, 0, 0);
		998
		999	/* if we found it, return it; otherwise, return nil */
		1000	if (entry != 0)
		1001	{
		1002	/* get the value from the entry and hand it back as the result */
		1003	*result = entry->val;
		1004	}
		1005	else
		1006	{
		1007	/* not found - return nil */
		1008	result->set_nil();
		1009	}
		1010	}
		1011
		1012
		1013	/*
		1014	* Set a value by index
		1015	*/
		1016	void CVmObjLookupTable::set_index_val(VMG_ vm_val_t *new_container,
		1017	vm_obj_id_t self,
		1018	const vm_val_t *index_val,
		1019	const vm_val_t *new_val)
		1020	{
		1021	vm_lookup_val *entry;
		1022
		1023	/* look for an existing entry with this key */
		1024	entry = find_entry(vmg_ index_val, 0, 0);
		1025
		1026	/* if we found an existing entry, modify it; otherwise, add a new one */
		1027	if (entry != 0)
		1028	{
		1029	/* set the new value for this entry */
		1030	set_entry_val_undo(vmg_ self, entry, new_val);
		1031	}
		1032	else
		1033	{
		1034	/* add a new entry with the given key */
		1035	add_entry_undo(vmg_ self, index_val, new_val);
		1036	}
		1037
		1038	/* we can be modified, hence the new container is the original one */
		1039	new_container->set_obj(self);
		1040	}
		1041
		1042
		1043	/* ------------------------------------------------------------------------ */
		1044	/*
		1045	* Property evaluator - determine if the given key is in the table
		1046	*/
		1047	int CVmObjLookupTable::getp_key_present(VMG_ vm_obj_id_t self,
		1048	vm_val_t retval, uint argc)
		1049	{
		1050	vm_lookup_val *entry;
		1051	vm_val_t key;
		1052	static CVmNativeCodeDesc desc(1);
		1053
		1054	/* check arguments */
		1055	if (get_prop_check_argc(retval, argc, &desc))
		1056	return TRUE;
		1057
		1058	/* get the key */
		1059	G_stk->pop(&key);
		1060
		1061	/* find the entry for this key */
		1062	entry = find_entry(vmg_ &key, 0, 0);
		1063
		1064	/* return true if we found it, nil if not */
		1065	retval->set_logical(entry != 0);
		1066
		1067	/* handled */
		1068	return TRUE;
		1069	}
		1070
		1071	/*
		1072	* Property evaluator - remove an entry given a key
		1073	*/
		1074	int CVmObjLookupTable::getp_remove_entry(VMG_ vm_obj_id_t self,
		1075	vm_val_t retval, uint argc)
		1076	{
		1077	vm_lookup_val *entry;
		1078	vm_val_t key;
		1079	uint hashval;
		1080	vm_lookup_val *prv_entry;
		1081	static CVmNativeCodeDesc desc(1);
		1082
		1083	/* check arguments */
		1084	if (get_prop_check_argc(retval, argc, &desc))
		1085	return TRUE;
		1086
		1087	/* get the key */
		1088	G_stk->pop(&key);
		1089
		1090	/* find the entry for this key */
		1091	entry = find_entry(vmg_ &key, &hashval, &prv_entry);
		1092
		1093	/* if we found the entry, delete it */
		1094	if (entry != 0)
		1095	{
		1096	/* the return value is the value stored at this key */
		1097	*retval = entry->val;
		1098
		1099	/* generate undo for the change */
		1100	add_undo_rec(vmg_ self, LOOKUPTAB_UNDO_DEL, &key, retval);
		1101
		1102	/* unlink the entry */
		1103	unlink_entry(vmg_ entry, hashval, prv_entry);
		1104	}
		1105	else
		1106	{
		1107	/* not found - the return value is nil */
		1108	retval->set_nil();
		1109	}
		1110
		1111	/* handled */
		1112	return TRUE;
		1113	}
		1114
		1115	/*
		1116	* Property evaluator - apply a callback to each entry in the table
		1117	*/
		1118	int CVmObjLookupTable::getp_apply_all(VMG_ vm_obj_id_t self,
		1119	vm_val_t retval, uint argc)
		1120	{
		1121	vm_val_t *fn;
		1122	vm_lookup_val *entry;
		1123	static CVmNativeCodeDesc desc(1);
		1124	uint i;
		1125
		1126	/* check arguments */
		1127	if (get_prop_check_argc(retval, argc, &desc))
		1128	return TRUE;
		1129
		1130	/* the function to invoke is the top argument */
		1131	fn = G_stk->get(0);
		1132
		1133	/* push a self-reference for gc protection */
		1134	G_stk->push()->set_obj(self);
		1135
		1136	/* iterate over each entry */
		1137	for (i = get_entry_count(), entry = get_ext()->idx_to_val(0) ;
		1138	i != 0 ; ++entry, --i)
		1139	{
		1140	/*
		1141	* if the entry is in use (it is if the key is non-empty), invoke
		1142	* the callback on it
		1143	*/
		1144	if (entry->key.typ != VM_EMPTY)
		1145	{
		1146	/* push the arguments - (key, val) - push in reverse order */
		1147	G_stk->push(&entry->val);
		1148	G_stk->push(&entry->key);
		1149
		1150	/* invoke the callback */
		1151	G_interpreter->call_func_ptr(vmg_ fn, 2,
		1152	"LookupTable.applyAll", 0);
		1153
		1154	/* replace this element with the result */
		1155	set_entry_val_undo(vmg_ self, entry, G_interpreter->get_r0());
		1156	}
		1157	}
		1158
		1159	/* discard the arguments and gc protection */
		1160	G_stk->discard(2);
		1161
		1162	/* no return value */
		1163	retval->set_nil();
		1164
		1165	/* handled */
		1166	return TRUE;
		1167	}
		1168
		1169	/*
		1170	* Property evaluator - invoke a callback for each entry in the table
		1171	*/
		1172	int CVmObjLookupTable::getp_for_each(VMG_ vm_obj_id_t self,
		1173	vm_val_t retval, uint argc)
		1174	{
		1175	/* call the general processor */
		1176	return for_each_gen(vmg_ self, retval, argc, FALSE);
		1177	}
		1178
		1179	/*
		1180	* Property evaluator - invoke a callback for each entry in the table
		1181	*/
		1182	int CVmObjLookupTable::getp_for_each_assoc(VMG_ vm_obj_id_t self,
		1183	vm_val_t retval, uint argc)
		1184	{
		1185	/* call the general processor */
		1186	return for_each_gen(vmg_ self, retval, argc, TRUE);
		1187	}
		1188
		1189	/*
		1190	* general processor for forEach/forEachAssoc
		1191	*/
		1192	int CVmObjLookupTable::for_each_gen(VMG_ vm_obj_id_t self,
		1193	vm_val_t retval, uint argc,
		1194	int pass_key_to_cb)
		1195	{
		1196	vm_val_t *fn;
		1197	vm_lookup_val *entry;
		1198	static CVmNativeCodeDesc desc(1);
		1199	uint i;
		1200
		1201	/* check arguments */
		1202	if (get_prop_check_argc(retval, argc, &desc))
		1203	return TRUE;
		1204
		1205	/* the function to invoke is the top argument */
		1206	fn = G_stk->get(0);
		1207
		1208	/* push a self-reference for gc protection */
		1209	G_stk->push()->set_obj(self);
		1210
		1211	/* iterate over each bucket */
		1212	for (i = get_entry_count(), entry = get_ext()->idx_to_val(0) ;
		1213	i != 0 ; --i, ++entry)
		1214	{
		1215	/*
		1216	* if it's in use (i.e., if the key is non-empty), invoke the
		1217	* callback for the entry
		1218	*/
		1219	if (entry->key.typ != VM_EMPTY)
		1220	{
		1221	/* push the current value argument */
		1222	G_stk->push(&entry->val);
		1223
		1224	/* push the key if desired */
		1225	if (pass_key_to_cb)
		1226	G_stk->push(&entry->key);
		1227
		1228	/* invoke the callback */
		1229	G_interpreter->call_func_ptr(vmg_ fn, pass_key_to_cb ? 2 : 1,
		1230	"LookupTable.forEach", 0);
		1231	}
		1232	}
		1233
		1234	/* discard the arguments and gc protection */
		1235	G_stk->discard(2);
		1236
		1237	/* no return value */
		1238	retval->set_nil();
		1239
		1240	/* handled */
		1241	return TRUE;
		1242	}
		1243
		1244	/*
		1245	* Property evaluator - get the number of buckets
		1246	*/
		1247	int CVmObjLookupTable::getp_count_buckets(VMG_ vm_obj_id_t self,
		1248	vm_val_t retval, uint argc)
		1249	{
		1250	static CVmNativeCodeDesc desc(0);
		1251
		1252	/* check arguments */
		1253	if (get_prop_check_argc(retval, argc, &desc))
		1254	return TRUE;
		1255
		1256	/* return the number of buckets */
		1257	retval->set_int(get_bucket_count());
		1258
		1259	/* handled */
		1260	return TRUE;
		1261	}
		1262
		1263	/*
		1264	* Property evaluator - get the number of entries in use
		1265	*/
		1266	int CVmObjLookupTable::getp_count_entries(VMG_ vm_obj_id_t self,
		1267	vm_val_t retval, uint argc)
		1268	{
		1269	static CVmNativeCodeDesc desc(0);
		1270	uint i;
		1271	int cnt;
		1272	vm_lookup_val *entry;
		1273
		1274	/* check arguments */
		1275	if (get_prop_check_argc(retval, argc, &desc))
		1276	return TRUE;
		1277
		1278	/* run through the table and count in-use entries */
		1279	for (cnt = 0, i = get_entry_count(), entry = get_ext()->idx_to_val(0) ;
		1280	i != 0 ; --i, ++entry)
		1281	{
		1282	/* if the entry is not marked as free, count it as used */
		1283	if (entry->key.typ != VM_EMPTY)
		1284	++cnt;
		1285	}
		1286
		1287	/* return the number of in-use entries we counted */
		1288	retval->set_int(cnt);
		1289
		1290	/* handled */
		1291	return TRUE;
		1292	}
		1293
		1294
		1295	/*
		1296	* Property evaluator - make a list of all of the keys in the table
		1297	*/
		1298	int CVmObjLookupTable::getp_keys_to_list(VMG_ vm_obj_id_t self,
		1299	vm_val_t retval, uint argc)
		1300	{
		1301	/* use the general list maker, listing only the keys */
		1302	return make_list(vmg_ self, retval, argc, TRUE);
		1303	}
		1304
		1305	/*
		1306	* Property evaluator - make a list of all of the values in the table
		1307	*/
		1308	int CVmObjLookupTable::getp_vals_to_list(VMG_ vm_obj_id_t self,
		1309	vm_val_t retval, uint argc)
		1310	{
		1311	/* use the general list maker, listing only the values */
		1312	return make_list(vmg_ self, retval, argc, FALSE);
		1313	}
		1314
		1315	/*
		1316	* General handler for keys_to_list and vals_to_list
		1317	*/
		1318	int CVmObjLookupTable::make_list(VMG_ vm_obj_id_t self,
		1319	vm_val_t retval, uint argc,
		1320	int store_keys)
		1321	{
		1322	static CVmNativeCodeDesc desc(0);
		1323	vm_lookup_val *entry;
		1324	uint i;
		1325	int cnt;
		1326	CVmObjList *lst;
		1327
		1328	/* check arguments */
		1329	if (get_prop_check_argc(retval, argc, &desc))
		1330	return TRUE;
		1331
		1332	/* push self while we're working, for gc protection */
		1333	G_stk->push()->set_obj(self);
		1334
		1335	/* run through the table and count in-use entries */
		1336	for (cnt = 0, i = get_entry_count(), entry = get_ext()->idx_to_val(0) ;
		1337	i != 0 ; ++entry, --i)
		1338	{
		1339	/* if the entry is not marked as free, count it as used */
		1340	if (entry->key.typ != VM_EMPTY)
		1341	++cnt;
		1342	}
		1343
		1344	/* allocate a list to store the results */
		1345	retval->set_obj(CVmObjList::create(vmg_ FALSE, cnt));
		1346
		1347	/* get the list object */
		1348	lst = (CVmObjList *)vm_objp(vmg_ retval->val.obj);
		1349
		1350	/* populate the list */
		1351	for (cnt = 0, i = get_entry_count(), entry = get_ext()->idx_to_val(0) ;
		1352	i != 0 ; ++entry, --i)
		1353	{
		1354	/* if the entry is not marked as free, count it as used */
		1355	if (entry->key.typ != VM_EMPTY)
		1356	{
		1357	/* store the key or value, as appropriate */
		1358	if (store_keys)
		1359	{
		1360	/* store the key */
		1361	lst->cons_set_element(cnt, &entry->key);
		1362	}
		1363	else
		1364	{
		1365	/* store the value */
		1366	lst->cons_set_element(cnt, &entry->val);
		1367	}
		1368
		1369	/* update the destination index */
		1370	++cnt;
		1371	}
		1372	}
		1373
		1374	/* discard our gc protection */
		1375	G_stk->discard();
		1376
		1377	/* handled */
		1378	return TRUE;
		1379	}
		1380
		1381	/* ------------------------------------------------------------------------ */
		1382	/*
		1383	* WeakRefLookupTable
		1384	*/
		1385
		1386
		1387	/*
		1388	* statics
		1389	*/
		1390
		1391	/* metaclass registration object */
		1392	static CVmMetaclassWeakRefLookupTable weak_metaclass_reg_obj;
		1393	CVmMetaclass *CVmObjWeakRefLookupTable::metaclass_reg_ =
		1394	&weak_metaclass_reg_obj;
		1395
		1396	/*
		1397	* create
		1398	*/
		1399	vm_obj_id_t CVmObjWeakRefLookupTable::
		1400	create(VMG_ int in_root_set, uint bucket_count, uint init_capacity)
		1401	{
		1402	vm_obj_id_t id;
		1403
		1404	/* allocate the object ID */
		1405	id = vm_new_id(vmg_ in_root_set, TRUE, TRUE);
		1406
		1407	/* create the object */
		1408	new (vmg_ id) CVmObjWeakRefLookupTable(vmg_ bucket_count, init_capacity);
		1409
		1410	/* return the new ID */
		1411	return id;
		1412	}
		1413
		1414	/*
		1415	* create dynamically using stack arguments
		1416	*/
		1417	vm_obj_id_t CVmObjWeakRefLookupTable::create_from_stack(
		1418	VMG_ const uchar **pc_ptr, uint argc)
		1419	{
		1420	vm_obj_id_t id;
		1421	size_t bucket_count;
		1422	size_t init_capacity;
		1423
		1424	/* parse the arguments */
		1425	get_constructor_args(vmg_ argc, &bucket_count, &init_capacity);
		1426
		1427	/*
		1428	* allocate the object ID - this type of construction never creates a
		1429	* root object
		1430	*/
		1431	id = vm_new_id(vmg_ FALSE, TRUE, TRUE);
		1432
		1433	/* create the object */
		1434	new (vmg_ id) CVmObjWeakRefLookupTable(vmg_ bucket_count, init_capacity);
		1435
		1436	/* return the new ID */
		1437	return id;
		1438	}
		1439
		1440
		1441	/*
		1442	* Mark undo references. Keys are strongly referenced, so mark the key in
		1443	* the record, if present.
		1444	*/
		1445	void CVmObjWeakRefLookupTable::
		1446	mark_undo_ref(VMG_ struct CVmUndoRecord *undo_rec)
		1447	{
		1448	lookuptab_undo_rec *rec;
		1449
		1450	/* get our private record from the standard undo record */
		1451	rec = (lookuptab_undo_rec *)undo_rec->id.ptrval;
		1452
		1453	/* if the key in the record is an object, mark it referenced */
		1454	if (rec->key.typ == VM_OBJ)
		1455	G_obj_table->mark_all_refs(rec->key.val.obj, VMOBJ_REACHABLE);
		1456	}
		1457
		1458	/*
		1459	* Mark references. Keys (but not values) are strongly referenced.
		1460	*/
		1461	void CVmObjWeakRefLookupTable::mark_refs(VMG_ uint state)
		1462	{
		1463	vm_lookup_val **bp;
		1464	uint i;
		1465
		1466	/* run through my buckets */
		1467	for (i = get_ext()->bucket_cnt, bp = get_ext()->buckets ;
		1468	i != 0 ; --i, ++bp)
		1469	{
		1470	const vm_lookup_val *entry;
		1471
		1472	/* run through all entries attached to this bucket */
		1473	for (entry = *bp ; entry != 0 ; entry = entry->nxt)
		1474	{
		1475	/* if the key is an object, mark it as referenced */
		1476	if (entry->key.typ == VM_OBJ)
		1477	G_obj_table->mark_all_refs(entry->key.val.obj, state);
		1478
		1479	/*
		1480	* note that we only reference our value weakly, so do not
		1481	* mark it here
		1482	*/
		1483	}
		1484	}
		1485	}
		1486
		1487	/*
		1488	* Remove stale weak references from an undo record. Value entries are
		1489	* weakly referenced.
		1490	*/
		1491	void CVmObjWeakRefLookupTable::
		1492	remove_stale_undo_weak_ref(VMG_ struct CVmUndoRecord *undo_rec)
		1493	{
		1494	int forget_record;
		1495
		1496	/* presume we won't want to forget the record */
		1497	forget_record = FALSE;
		1498
		1499	/*
		1500	* if the old value in the undo record refers to an object, forget
		1501	* about it
		1502	*/
		1503	if (G_obj_table->is_obj_deletable(&undo_rec->oldval))
		1504	{
		1505	/*
		1506	* the object is being deleted - since we only weakly reference
		1507	* our objects, we must forget about this object now; this also
		1508	* means we can forget about the record entirely, since there is
		1509	* no need to apply it in the future now that it doesn't do
		1510	* anything
		1511	*/
		1512	undo_rec->oldval.set_nil();
		1513	forget_record = TRUE;
		1514	}
		1515
		1516	/* delete our extended record if we're forgetting the record */
		1517	if (undo_rec->id.ptrval != 0 && forget_record)
		1518	{
		1519	lookuptab_undo_rec *rec;
		1520
		1521	/* get our private record from the standard undo record */
		1522	rec = (lookuptab_undo_rec *)undo_rec->id.ptrval;
		1523
		1524	/* we don't care about the key value in this record any more */
		1525	rec->key.set_nil();
		1526
		1527	/* mark the record as forgotten */
		1528	rec->action = LOOKUPTAB_UNDO_NULL;
		1529	}
		1530	}
		1531
		1532	/*
		1533	* Remove stale weak references. Our values are weak references, so
		1534	* remove any entries that have values that are about to be deleted.
		1535	*/
		1536	void CVmObjWeakRefLookupTable::remove_stale_weak_refs(VMG0_)
		1537	{
		1538	vm_lookup_val **bucket;
		1539	uint i;
		1540	uint hashval;
		1541
		1542	/* run through each bucket */
		1543	for (hashval = 0, bucket = get_ext()->buckets, i = get_bucket_count() ;
		1544	i != 0 ; ++bucket, --i, ++hashval)
		1545	{
		1546	vm_lookup_val *entry;
		1547	vm_lookup_val *prv;
		1548	vm_lookup_val *nxt;
		1549
		1550	/* run through all entries attached to this bucket */
		1551	for (prv = 0, entry = *bucket ; entry != 0 ; entry = nxt)
		1552	{
		1553	/* remember the next entry, in case we delete this one */
		1554	nxt = entry->nxt;
		1555
		1556	/*
		1557	* if the value has an object reference that has become stale,
		1558	* delete the entry
		1559	*/
		1560	if (G_obj_table->is_obj_deletable(&entry->val))
		1561	{
		1562	/* it's deletable, so delete the entire record */
		1563	unlink_entry(vmg_ entry, hashval, prv);
		1564
		1565	/*
		1566	* note that we do NOT advance the prv pointer - we've
		1567	* deleted this entry, so the one preceding it is now the
		1568	* previous for the one following this one
		1569	*/
		1570	}
		1571	else
		1572	{
		1573	/* we're keeping this entry - make it the new previous */
		1574	prv = entry;
		1575	}
		1576	}
		1577	}
		1578	}
		1579
		1580
		1581	/* ------------------------------------------------------------------------ */
		1582	/*
		1583	* LookupTable Iterator metaclass
		1584	*/
		1585
		1586	/*
		1587	* statics
		1588	*/
		1589
		1590	/* metaclass registration object */
		1591	static CVmMetaclassIterLookupTable iter_metaclass_reg_obj;
		1592	CVmMetaclass *CVmObjIterLookupTable::metaclass_reg_ = &iter_metaclass_reg_obj;
		1593
		1594
		1595	/* create a list with no initial contents */
		1596	vm_obj_id_t CVmObjIterLookupTable::create_for_coll(VMG_ const vm_val_t *coll)
		1597	{
		1598	vm_obj_id_t id;
		1599
		1600	/* push the collection object reference for gc protection */
		1601	G_stk->push(coll);
		1602
		1603	/* create a non-root-set object */
		1604	id = vm_new_id(vmg_ FALSE, TRUE, TRUE);
		1605
		1606	/* instantiate the iterator */
		1607	new (vmg_ id) CVmObjIterLookupTable(vmg_ coll);
		1608
		1609	/* done with the gc protection */
		1610	G_stk->discard();
		1611
		1612	/* return the new object's ID */
		1613	return id;
		1614	}
		1615
		1616	/*
		1617	* constructor
		1618	*/
		1619	CVmObjIterLookupTable::CVmObjIterLookupTable(VMG_ const vm_val_t *coll)
		1620	{
		1621	/* allocate space for our extension data */
		1622	ext_ = (char *)G_mem->get_var_heap()
		1623	->alloc_mem(VMOBJITERLOOKUPTABLE_EXT_SIZE, this);
		1624
		1625	/* save the collection value */
		1626	vmb_put_dh(ext_, coll);
		1627
		1628	/* clear the flags */
		1629	set_flags(0);
		1630
		1631	/*
		1632	* set up at index zero - we're not at a valid entry until initialized
		1633	* with getNext
		1634	*/
		1635	set_entry_index(0);
		1636	}
		1637
		1638	/*
		1639	* Find the first valid entry, starting at the given entry index. If the
		1640	* given index refers to a valid entry, we return it. If there is no
		1641	* valid next entry, we return zero.
		1642	*/
		1643	uint CVmObjIterLookupTable::find_first_valid_entry(VMG_ uint entry) const
		1644	{
		1645	CVmObjLookupTable *ltab;
		1646	vm_val_t coll;
		1647
		1648	/* get my lookup table object */
		1649	get_coll_val(&coll);
		1650	ltab = (CVmObjLookupTable *)vm_objp(vmg_ coll.val.obj);
		1651
		1652	/* if we're already past the last item, we have nothing to find */
		1653	if (entry > ltab->get_entry_count())
		1654	return 0;
		1655
		1656	/*
		1657	* scan entries until we find one with a non-empty key (an empty key
		1658	* value indicates that the entry is free)
		1659	*/
		1660	for ( ; entry <= ltab->get_entry_count() ; ++entry)
		1661	{
		1662	vm_lookup_val *entryp;
		1663
		1664	/* translate the 1-based index to an entry pointer */
		1665	entryp = ltab->get_ext()->idx_to_val(entry - 1);
		1666
		1667	/* if it's non-empty, this is the one we want */
		1668	if (entryp->key.typ != VM_EMPTY)
		1669	return entry;
		1670	}
		1671
		1672	/* we didn't find a valid entry */
		1673	return 0;
		1674	}
		1675
		1676	/*
		1677	* notify of deletion
		1678	*/
		1679	void CVmObjIterLookupTable::notify_delete(VMG_ int)
		1680	{
		1681	/* free our extension */
		1682	if (ext_ != 0)
		1683	G_mem->get_var_heap()->free_mem(ext_);
		1684	}
		1685
		1686	/*
		1687	* property evaluator - get the next item
		1688	*/
		1689	int CVmObjIterLookupTable::getp_get_next(VMG_ vm_obj_id_t self,
		1690	vm_val_t retval, uint argc)
		1691	{
		1692	uint entry;
		1693	static CVmNativeCodeDesc desc(0);
		1694	CVmObjLookupTable *ltab;
		1695	vm_val_t coll;
		1696
		1697	/* check arguments */
		1698	if (get_prop_check_argc(retval, argc, &desc))
		1699	return TRUE;
		1700
		1701	/* get my collection object */
		1702	get_coll_val(&coll);
		1703	ltab = (CVmObjLookupTable *)vm_objp(vmg_ coll.val.obj);
		1704
		1705	/* advance to the next valid index after the current one */
		1706	entry = find_first_valid_entry(vmg_ get_entry_index() + 1);
		1707
		1708	/*
		1709	* if we're past the end of the table, set the index to zero to
		1710	* indicate that we're done
		1711	*/
		1712	if (entry == 0)
		1713	err_throw(VMERR_OUT_OF_RANGE);
		1714
		1715	/* retrieve the current entry */
		1716	*retval = ltab->get_ext()->idx_to_val(entry - 1)->val;
		1717
		1718	/* update our internal state, saving undo */
		1719	set_entry_index_undo(vmg_ self, entry);
		1720
		1721	/* handled */
		1722	return TRUE;
		1723	}
		1724
		1725	/*
		1726	* property evaluator - get current value
		1727	*/
		1728	int CVmObjIterLookupTable::getp_get_cur_val(VMG_ vm_obj_id_t self,
		1729	vm_val_t retval, uint argc)
		1730	{
		1731	static CVmNativeCodeDesc desc(0);
		1732
		1733	/* check arguments */
		1734	if (get_prop_check_argc(retval, argc, &desc))
		1735	return TRUE;
		1736
		1737	/* get the entry's value */
		1738	get_cur_entry(vmg_ retval, 0);
		1739
		1740	/* handled */
		1741	return TRUE;
		1742	}
		1743
		1744	/*
		1745	* property evaluator - get current key
		1746	*/
		1747	int CVmObjIterLookupTable::getp_get_cur_key(VMG_ vm_obj_id_t self,
		1748	vm_val_t retval, uint argc)
		1749	{
		1750	static CVmNativeCodeDesc desc(0);
		1751
		1752	/* check arguments */
		1753	if (get_prop_check_argc(retval, argc, &desc))
		1754	return TRUE;
		1755
		1756	/* get the entry's key */
		1757	get_cur_entry(vmg_ 0, retval);
		1758
		1759	/* handled */
		1760	return TRUE;
		1761	}
		1762
		1763	/*
		1764	* Get the current entry index, value, and key for the current entry. Any
		1765	* of the output pointers can be null if the corresponding value is not
		1766	* needed by the caller.
		1767	*/
		1768	void CVmObjIterLookupTable::get_cur_entry(VMG_ vm_val_t *valp,
		1769	vm_val_t *keyp) const
		1770	{
		1771	uint entry;
		1772	vm_val_t coll;
		1773	CVmObjLookupTable *ltab;
		1774	vm_lookup_val *entryp;
		1775
		1776	/* get my collection object */
		1777	get_coll_val(&coll);
		1778	ltab = (CVmObjLookupTable *)vm_objp(vmg_ coll.val.obj);
		1779
		1780	/* make sure the index is in range */
		1781	entry = get_entry_index();
		1782	if (entry < 1 \|\| entry > ltab->get_entry_count())
		1783	err_throw(VMERR_OUT_OF_RANGE);
		1784
		1785	/* translate our 1-based index to an entry pointer */
		1786	entryp = ltab->get_ext()->idx_to_val(entry - 1);
		1787
		1788	/* if the current entry has been deleted, we have no valid current item */
		1789	if (entryp->key.typ == VM_EMPTY)
		1790	err_throw(VMERR_OUT_OF_RANGE);
		1791
		1792	/* retrieve this entry's value and key for the caller, as desired */
		1793	if (valp != 0)
		1794	*valp = entryp->val;
		1795	if (keyp != 0)
		1796	*keyp = entryp->key;
		1797	}
		1798
		1799	/*
		1800	* property evaluator - is next value available?
		1801	*/
		1802	int CVmObjIterLookupTable::getp_is_next_avail(VMG_ vm_obj_id_t self,
		1803	vm_val_t retval, uint argc)
		1804	{
		1805	uint entry;
		1806	static CVmNativeCodeDesc desc(0);
		1807
		1808	/* check arguments */
		1809	if (get_prop_check_argc(retval, argc, &desc))
		1810	return TRUE;
		1811
		1812	/* find the index of the next valid entry */
		1813	entry = find_first_valid_entry(vmg_ get_entry_index() + 1);
		1814
		1815	/* return true if we have a valid index, false if not */
		1816	retval->set_logical(entry != 0);
		1817
		1818	/* handled */
		1819	return TRUE;
		1820	}
		1821
		1822	/*
		1823	* property evaluator - reset to first item
		1824	*/
		1825	int CVmObjIterLookupTable::getp_reset_iter(VMG_ vm_obj_id_t self,
		1826	vm_val_t retval, uint argc)
		1827	{
		1828	static CVmNativeCodeDesc desc(0);
		1829
		1830	/* check arguments */
		1831	if (get_prop_check_argc(retval, argc, &desc))
		1832	return TRUE;
		1833
		1834	/* set our entry index back to zero, saving undo */
		1835	set_entry_index_undo(vmg_ self, 0);
		1836
		1837	/* no return value */
		1838	retval->set_nil();
		1839
		1840	/* handled */
		1841	return TRUE;
		1842	}
		1843
		1844	/*
		1845	* Set the next index value, saving undo if necessary
		1846	*/
		1847	void CVmObjIterLookupTable::set_entry_index_undo(
		1848	VMG_ vm_obj_id_t self, uint entry_idx)
		1849
		1850	{
		1851	/* save undo if necessary */
		1852	if (G_undo != 0 && !(get_flags() & VMOBJITERLOOKUPTABLE_UNDO))
		1853	{
		1854	vm_val_t val;
		1855
		1856	/*
		1857	* Add the undo record. Store the entry index as the key (it's
		1858	* not really a key, but it'll do as a place to store the data).
		1859	* We don't need anything in the payload, so store a dummy nil
		1860	* value.
		1861	*/
		1862	val.set_nil();
		1863	G_undo->add_new_record_int_key(vmg_ self, get_entry_index(), &val);
		1864
		1865	/*
		1866	* set the undo bit so we don't save redundant undo for this
		1867	* savepoint
		1868	*/
		1869	set_flags(get_flags() \| VMOBJITERLOOKUPTABLE_UNDO);
		1870	}
		1871
		1872	/* set the index */
		1873	set_entry_index(entry_idx);
		1874	}
		1875
		1876	/*
		1877	* apply undo
		1878	*/
		1879	void CVmObjIterLookupTable::apply_undo(VMG_ CVmUndoRecord *rec)
		1880	{
		1881	/*
		1882	* the integer key in the undo record is my saved index value (and is
		1883	* the only thing in our state that can ever change)
		1884	*/
		1885	set_entry_index((uint)rec->id.intval);
		1886	}
		1887
		1888	/*
		1889	* mark references
		1890	*/
		1891	void CVmObjIterLookupTable::mark_refs(VMG_ uint state)
		1892	{
		1893	vm_val_t coll;
		1894
		1895	/* my collection is always an object - mark it as referenced */
		1896	get_coll_val(&coll);
		1897	G_obj_table->mark_all_refs(coll.val.obj, state);
		1898	}
		1899
		1900	/*
		1901	* load from an image file
		1902	*/
		1903	void CVmObjIterLookupTable::load_from_image(VMG_ vm_obj_id_t self,
		1904	const char *ptr, size_t siz)
		1905	{
		1906	/* if we already have memory allocated, free it */
		1907	if (ext_ != 0)
		1908	{
		1909	G_mem->get_var_heap()->free_mem(ext_);
		1910	ext_ = 0;
		1911	}
		1912
		1913	/*
		1914	* Allocate a new extension. Make sure it's at least as large as the
		1915	* current standard extension size.
		1916	*/
		1917	ext_ = (char *)G_mem->get_var_heap()
		1918	->alloc_mem(siz < VMOBJITERLOOKUPTABLE_EXT_SIZE
		1919	? VMOBJITERLOOKUPTABLE_EXT_SIZE : siz, this);
		1920
		1921	/* copy the image data to our extension */
		1922	memcpy(ext_, ptr, siz);
		1923
		1924	/*
		1925	* save our image data pointer in the object table, so that we can
		1926	* access it (without storing it ourselves) during a reload
		1927	*/
		1928	G_obj_table->save_image_pointer(self, ptr, siz);
		1929
		1930	/* clear the undo flag */
		1931	set_flags(get_flags() & ~VMOBJITERLOOKUPTABLE_UNDO);
		1932	}
		1933
		1934	/*
		1935	* re-load from an image file
		1936	*/
		1937	void CVmObjIterLookupTable::reload_from_image(VMG_ vm_obj_id_t,
		1938	const char *ptr, size_t siz)
		1939	{
		1940	/* re-copy the image data */
		1941	memcpy(ext_, ptr, siz);
		1942
		1943	/* clear the undo flag */
		1944	set_flags(get_flags() & ~VMOBJITERLOOKUPTABLE_UNDO);
		1945	}
		1946
		1947	/*
		1948	* save
		1949	*/
		1950	void CVmObjIterLookupTable::save_to_file(VMG_ CVmFile *fp)
		1951	{
		1952	/* write my extension */
		1953	fp->write_bytes(ext_, VMOBJITERLOOKUPTABLE_EXT_SIZE);
		1954	}
		1955
		1956	/*
		1957	* restore
		1958	*/
		1959	void CVmObjIterLookupTable::restore_from_file(VMG_ vm_obj_id_t,
		1960	CVmFile *fp,
		1961	CVmObjFixup *fixups)
		1962	{
		1963	/* free any existing extension */
		1964	if (ext_ != 0)
		1965	{
		1966	G_mem->get_var_heap()->free_mem(ext_);
		1967	ext_ = 0;
		1968	}
		1969
		1970	/* allocate a new extension */
		1971	ext_ = (char *)G_mem->get_var_heap()
		1972	->alloc_mem(VMOBJITERLOOKUPTABLE_EXT_SIZE, this);
		1973
		1974	/* read my extension */
		1975	fp->read_bytes(ext_, VMOBJITERLOOKUPTABLE_EXT_SIZE);
		1976
		1977	/* fix up my collection object reference */
		1978	fixups->fix_dh(vmg_ ext_);
		1979	}
		1980

FrobTADS

cfad47cfa3/tads3/vmlookup.cpp