vim: src/eval.c comparison

comparison src/eval.c @ 371:4b9fef49d7ff v7.0095

updated for version 7.0095

author	vimboss
date	Mon, 27 Jun 2005 22:48:21 +0000
parents	5332dd13733c
children	575dacb554d8

comparison

equal deleted inserted replaced

-:3a21825ad207
+:4b9fef49d7ff
 #define FC_DICT	    4		/* Dict function, uses "self" */
 #define DEL_REFCOUNT	999999	/* list/dict is being deleted */
 /*
-* All user-defined functions are found in this hash table.
+* All user-defined functions are found in this hashtable.
 */
 static hashtab_T	func_hashtab;
+/* list heads for garbage collection */
+static dict_T		*first_dict = NULL;	/* list of all dicts */
+static list_T		*first_list = NULL;	/* list of all lists */
 /* From user function to hashitem and back. */
 static ufunc_T dumuf;
 #define UF2HIKEY(fp) ((fp)->uf_name)
 #define HIKEY2UF(p)  ((ufunc_T *)(p - (dumuf.uf_name - (char_u *)&dumuf)))
 #define MAX_FUNC_ARGS	20	/* maximum number of function arguments */
 #define VAR_SHORT_LEN	20	/* short variable name length */
 #define FIXVAR_CNT	12	/* number of fixed variables */
 /* structure to hold info for a function that is currently being executed. */
-typedef struct funccall_S
+typedef struct funccall_S funccall_T;
+struct funccall_S
 {
 ufunc_T	*func;		/* function being called */
 int		linenr;		/* next line to be executed */
 int		returned;	/* ":return" used */
 struct			/* fixed variables for arguments */
 int		dbg_tick;	/* debug_tick when breakpoint was set */
 int		level;		/* top nesting level of executed function */
 #ifdef FEAT_PROFILE
 proftime_T	prof_child;	/* time spent in a child */
 #endif
-} funccall_T;
+funccall_T	*caller;	/* calling function or NULL */
+};
 /*
 * Info used by a ":for" loop.
 */
 typedef struct
 static list_T *list_copy __ARGS((list_T *orig, int deep, int copyID));
 static void list_remove __ARGS((list_T *l, listitem_T *item, listitem_T *item2));
 static char_u *list2string __ARGS((typval_T *tv));
 static int list_join __ARGS((garray_T *gap, list_T *l, char_u *sep, int echo));
-static int count_self_ref __ARGS((void *p, int type));
+static void set_ref_in_ht __ARGS((hashtab_T *ht, int copyID));
-static int count_ref_in_dict __ARGS((dict_T *d, void *rp, int copyID, garray_T *gap));
+static void set_ref_in_list __ARGS((list_T *l, int copyID));
-static int count_ref_in_list __ARGS((list_T *l, void *rp, int copyID, garray_T *gap));
+static void set_ref_in_item __ARGS((typval_T *tv, int copyID));
-static int count_ref_item __ARGS((typval_T *tv, void *rp, int copyID, garray_T *gap));
 static void dict_unref __ARGS((dict_T *d));
 static void dict_free __ARGS((dict_T *d));
 static dictitem_T *dictitem_alloc __ARGS((char_u *key));
 static dictitem_T *dictitem_copy __ARGS((dictitem_T *org));
 static void f_foldlevel __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_foldtext __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_foldtextresult __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_foreground __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_function __ARGS((typval_T *argvars, typval_T *rettv));
+static void f_garbagecollect __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_get __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_getbufvar __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_getchar __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_getcharmod __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_getcmdline __ARGS((typval_T *argvars, typval_T *rettv));
 free_scriptnames();
 /* global variables */
 vars_clear(&globvarht);
+/* functions */
 free_all_functions();
+hash_clear(&func_hashtab);
+/* unreferenced lists and dicts */
+(void)garbage_collect();
 }
 #endif
 /*
 * Return the name of the executed function.
 * Allocate an empty header for a list.
 */
 static list_T *
 list_alloc()
 {
-return (list_T *)alloc_clear(sizeof(list_T));
+list_T  *l;
+l = (list_T *)alloc_clear(sizeof(list_T));
+if (l != NULL)
+{
+	/* Prepend the list to the list of lists for garbage collection. */
+	if (first_list != NULL)
+	    first_list->lv_used_prev = l;
+	l->lv_used_prev = NULL;
+	l->lv_used_next = first_list;
+	first_list = l;
+}
+return l;
 }
 /*
 * Unreference a list: decrement the reference count and free it when it
 * becomes zero.
 */
 static void
 list_unref(l)
 list_T *l;
 {
-int		selfref;
+if (l != NULL && l->lv_refcount != DEL_REFCOUNT && --l->lv_refcount <= 0)
+	list_free(l);
-if (l != NULL && l->lv_refcount != DEL_REFCOUNT)
-{
-	if (--l->lv_refcount > 0)
-	{
-	    /* Check if the dict contains references to itself.  These need to
-	     * be subtracted from the reference count to find out if we can
-	     * delete the dict. */
-	    selfref = count_self_ref(l, VAR_LIST);
-	}
-	else
-	    selfref = 0;
-	if (l->lv_refcount - selfref == 0)
-	    /* No references to the list now, free it. */
-	    list_free(l);
-}
 }
 /*
 * Free a list, including all items it points to.
 * Ignores the reference count.
 {
 listitem_T *item;
 /* Avoid that recursive reference to the list frees us again. */
 l->lv_refcount = DEL_REFCOUNT;
+/* Remove the list from the list of lists for garbage collection. */
+if (l->lv_used_prev == NULL)
+	first_list = l->lv_used_next;
+else
+	l->lv_used_prev->lv_used_next = l->lv_used_next;
+if (l->lv_used_next != NULL)
+	l->lv_used_next->lv_used_prev = l->lv_used_prev;
 for (item = l->lv_first; item != NULL; item = l->lv_first)
 {
 	/* Remove the item before deleting it. */
 	l->lv_first = item->li_next;
 }
 return OK;
 }
 /*
-* Count the number of references for list/dict "p" inside itself.
+* Garbage collection for lists and dictionaries.
-* This is used to find out if there are no more references elsewhere.
+*
-* The tricky bit is that we must not count references in lists/dicts that are
+* We use reference counts to be able to free most items right away when they
-* used elsewhere, but we can only know by counting their references...
+* are no longer used.  But for composite items it's possible that it becomes
-* This is a bit slow, but required to avoid leaking memory.
+* unused while the reference count is > 0: When there is a recursive
-*/
+* reference.  Example:
-static int
+*	:let l = [1, 2, 3]
-count_self_ref(p, type)
+*	:let d = {9: l}
-void	*p;
+*	:let l[1] = d
-int		type;
+*
-{
+* Since this is quite unusual we handle this with garbage collection: every
-garray_T	ga;
+* once in a while find out which lists and dicts are not referenced from any
-typval_T	*tv;
+* variable.
-int		selfref;
+*
+* Here is a good reference text about garbage collection (refers to Python
+* but it applies to all reference-counting mechanisms):
+*	http://python.ca/nas/python/gc/
+*/
+/*
+* Do garbage collection for lists and dicts.
+* Return TRUE if some memory was freed.
+*/
+int
+garbage_collect()
+{
+dict_T	*dd;
+list_T	*ll;
+int		copyID = ++current_copyID;
+buf_T	*buf;
+win_T	*wp;
 int		i;
-int		n;
+funccall_T	*fc;
+int		did_free = FALSE;
-ga_init2(&ga, sizeof(typval_T *), 10);
-if (type == VAR_DICT)
+/*
-	selfref = count_ref_in_dict(p, p, ++current_copyID, &ga);
+* 1. Go through all accessible variables and mark all lists and dicts
-else
+*    with copyID.
-	selfref = count_ref_in_list(p, p, ++current_copyID, &ga);
+*/
-for (i = 0; i < ga.ga_len; ++i)
+/* script-local variables */
-{
+for (i = 1; i <= ga_scripts.ga_len; ++i)
-	tv = ((typval_T **)ga.ga_data)[i];
+	set_ref_in_ht(&SCRIPT_VARS(i), copyID);
-	if (tv->v_type == VAR_DICT)
-	{
+/* buffer-local variables */
-	    n = count_ref_in_dict(tv->vval.v_dict, tv->vval.v_dict,
+for (buf = firstbuf; buf != NULL; buf = buf->b_next)
-						      ++current_copyID, NULL);
+	set_ref_in_ht(&buf->b_vars.dv_hashtab, copyID);
-	    if (n < tv->vval.v_dict->dv_refcount)
-	    {
+/* window-local variables */
-		selfref = 0;
+FOR_ALL_WINDOWS(wp)
-		break;
+	set_ref_in_ht(&wp->w_vars.dv_hashtab, copyID);
-	    }
+/* global variables */
+set_ref_in_ht(&globvarht, copyID);
+/* function-local variables */
+for (fc = current_funccal; fc != NULL; fc = fc->caller)
+{
+	set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID);
+	set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID);
+}
+/*
+* 2. Go through the list of dicts and free items without the copyID.
+*/
+for (dd = first_dict; dd != NULL; )
+	if (dd->dv_copyID != copyID)
+	{
+	    dict_free(dd);
+	    did_free = TRUE;
+	    /* restart, next dict may also have been freed */
+	    dd = first_dict;
 	}
 	else
-	{
+	    dd = dd->dv_used_next;
-	    n = count_ref_in_list(tv->vval.v_list, tv->vval.v_list,
-						      ++current_copyID, NULL);
+/*
-	    if (n < tv->vval.v_list->lv_refcount)
+* 3. Go through the list of lists and free items without the copyID.
-	    {
+*/
-		selfref = 0;
+for (ll = first_list; ll != NULL; )
-		break;
+	if (ll->lv_copyID != copyID)
-	    }
+	{
-	}
+	    list_free(ll);
-}
+	    did_free = TRUE;
-ga_clear(&ga);
+	    /* restart, next dict may also have been freed */
-return selfref;
+	    ll = first_list;
-}
+	}
+	else
-/*
+	    ll = ll->lv_used_next;
-* Count number of references to "rp" in dictionary "d" and its members.
-* We use "copyID" to avoid recursing into the same list/dict twice.
+return did_free;
-*/
+}
-static int
-count_ref_in_dict(d, rp, copyID, gap)
+/*
-dict_T	*d;
+* Mark all lists and dicts referenced through hashtab "ht" with "copyID".
-void	*rp;
+*/
+static void
+set_ref_in_ht(ht, copyID)
+hashtab_T	*ht;
 int		copyID;
-garray_T	*gap;
 {
 int		todo;
 hashitem_T	*hi;
-int		n = 0;
+todo = ht->ht_used;
-todo = d->dv_hashtab.ht_used;
+for (hi = ht->ht_array; todo > 0; ++hi)
-for (hi = d->dv_hashtab.ht_array; todo > 0; ++hi)
 	if (!HASHITEM_EMPTY(hi))
 	{
 	    --todo;
-	    n += count_ref_item(&HI2DI(hi)->di_tv, rp, copyID, gap);
+	    set_ref_in_item(&HI2DI(hi)->di_tv, copyID);
 	}
-return n;
+}
-}
+/*
-/*
+* Mark all lists and dicts referenced through list "l" with "copyID".
-* Count number of references to "rp" in list "l" and its members.
+*/
-* We use "copyID" to avoid recursing into the same list/dict twice.
+static void
-*/
+set_ref_in_list(l, copyID)
-static int
-count_ref_in_list(l, rp, copyID, gap)
 list_T	*l;
-void	*rp;
 int		copyID;
-garray_T	*gap;
 {
 listitem_T *li;
-int		n = 0;
 for (li = l->lv_first; li != NULL; li = li->li_next)
-	n += count_ref_item(&li->li_tv, rp, copyID, gap);
+	set_ref_in_item(&li->li_tv, copyID);
-return n;
+}
-}
+/*
-/*
+* Mark all lists and dicts referenced through typval "tv" with "copyID".
-* Count number of references to "rp" in item "tv" and any members.
+*/
-* We use "copyID" to avoid recursing into the same list/dict twice.
+static void
-* When "gap" is not NULL store items that require checking for only
+set_ref_in_item(tv, copyID)
-* references inside the structure.
-*/
-static int
-count_ref_item(tv, rp, copyID, gap)
 typval_T	*tv;
-void	*rp;
 int		copyID;
-garray_T	*gap;
 {
 dict_T	*dd;
 list_T	*ll;
-int		n;
 switch (tv->v_type)
 {
 	case VAR_DICT:
 	    dd = tv->vval.v_dict;
-	    if (dd == rp)
+	    if (dd->dv_copyID != copyID)
-		return 1;	/* match, count it */
-	    if (dd->dv_copyID == copyID)
-		return 0;	/* already inspected this dict */
-	    dd->dv_copyID = copyID;
-	    n = count_ref_in_dict(dd, rp, copyID, gap);
-	    if (n > 0 && gap != NULL && dd->dv_refcount > 1)
 	    {
-		/* We must later check that the references to this dict are
+		/* Didn't see this dict yet. */
-		 * all in the structure we are freeing. */
+		dd->dv_copyID = copyID;
-		if (ga_grow(gap, 1) == FAIL)
+		set_ref_in_ht(&dd->dv_hashtab, copyID);
-		    return 0;
-		((typval_T **)gap->ga_data)[gap->ga_len++] = tv;
 	    }
-	    return n;
+	    break;
 	case VAR_LIST:
 	    ll = tv->vval.v_list;
-	    if (ll == rp)
+	    if (ll->lv_copyID != copyID)
-		return 1;	/* match, count it */
-	    if (ll->lv_copyID == copyID)
-		return 0;	/* already inspected this list */
-	    ll->lv_copyID = copyID;
-	    n = count_ref_in_list(ll, rp, copyID, gap);
-	    if (n > 0 && gap != NULL && ll->lv_refcount > 1)
 	    {
-		/* We must later check that the references to this list are
+		/* Didn't see this list yet. */
-		 * all in the structure we are freeing. */
+		ll->lv_copyID = copyID;
-		if (ga_grow(gap, 1) == FAIL)
+		set_ref_in_list(ll, copyID);
-		    return 0;
-		((typval_T **)gap->ga_data)[gap->ga_len++] = tv;
 	    }
-	    return n;
+	    break;
 }
-return 0;
+return;
 }
 /*
 * Allocate an empty header for a dictionary.
 */
 dict_T *d;
 d = (dict_T *)alloc(sizeof(dict_T));
 if (d != NULL)
 {
+	/* Add the list to the hashtable for garbage collection. */
+	if (first_dict != NULL)
+	    first_dict->dv_used_prev = d;
+	d->dv_used_next = first_dict;
+	d->dv_used_prev = NULL;
 	hash_init(&d->dv_hashtab);
 	d->dv_lock = 0;
 	d->dv_refcount = 0;
 	d->dv_copyID = 0;
 }
 */
 static void
 dict_unref(d)
 dict_T *d;
 {
-int		selfref;
+if (d != NULL && d->dv_refcount != DEL_REFCOUNT && --d->dv_refcount <= 0)
+	dict_free(d);
-if (d != NULL && d->dv_refcount != DEL_REFCOUNT)
-{
-	if (--d->dv_refcount > 0)
-	{
-	    /* Check if the dict contains references to itself.  These need to
-	     * be subtracted from the reference count to find out if we can
-	     * delete the dict. */
-	    selfref = count_self_ref(d, VAR_DICT);
-	}
-	else
-	    selfref = 0;
-	if (d->dv_refcount - selfref == 0)
-	    /* No references to the dict now, free it. */
-	    dict_free(d);
-}
 }
 /*
 * Free a Dictionary, including all items it contains.
 * Ignores the reference count.
 dictitem_T	*di;
 /* Avoid that recursive reference to the dict frees us again. */
 d->dv_refcount = DEL_REFCOUNT;
-/* Lock the hashtab, we don't want it to resize while looping through it.
+/* Remove the dict from the list of dicts for garbage collection. */
-* */
+if (d->dv_used_prev == NULL)
+	first_dict = d->dv_used_next;
+else
+	d->dv_used_prev->dv_used_next = d->dv_used_next;
+if (d->dv_used_next != NULL)
+	d->dv_used_next->dv_used_prev = d->dv_used_prev;
+/* Lock the hashtab, we don't want it to resize while freeing items. */
 hash_lock(&d->dv_hashtab);
 todo = d->dv_hashtab.ht_used;
 for (hi = d->dv_hashtab.ht_array; todo > 0; ++hi)
 {
 	if (!HASHITEM_EMPTY(hi))
 {"foldlevel",	1, 1, f_foldlevel},
 {"foldtext",	0, 0, f_foldtext},
 {"foldtextresult",	1, 1, f_foldtextresult},
 {"foreground",	0, 0, f_foreground},
 {"function",	1, 1, f_function},
+{"garbagecollect",	0, 0, f_garbagecollect},
 {"get",		2, 3, f_get},
 {"getbufvar",	2, 2, f_getbufvar},
 {"getchar",		0, 1, f_getchar},
 {"getcharmod",	0, 0, f_getcharmod},
 {"getcmdline",	0, 0, f_getcmdline},
 	rettv->v_type = VAR_FUNC;
 }
 }
 /*
+* "garbagecollect()" function
+*/
+/*ARGSUSED*/
+static void
+f_garbagecollect(argvars, rettv)
+typval_T	*argvars;
+typval_T	*rettv;
+{
+garbage_collect();
+}
+/*
 * "get()" function
 */
 static void
 f_get(argvars, rettv)
 typval_T	*argvars;
 	    case 's': return &SCRIPT_SV(current_SID).sv_var;
 	    case 'g': return &globvars_var;
 	    case 'v': return &vimvars_var;
 	    case 'b': return &curbuf->b_bufvar;
 	    case 'w': return &curwin->w_winvar;
-	    case 'l': return &current_funccal->l_vars_var;
+	    case 'l': return current_funccal == NULL
-	    case 'a': return &current_funccal->l_avars_var;
+					? NULL : &current_funccal->l_vars_var;
+	    case 'a': return current_funccal == NULL
+				       ? NULL : &current_funccal->l_avars_var;
 	}
 	return NULL;
 }
 hi = hash_find(ht, varname);
 	    if ((v->di_flags & DI_FLAGS_FIX) == 0)
 		vim_free(v);
 	}
 }
 hash_clear(ht);
+ht->ht_used = 0;
 }
 /*
 * Delete a variable from hashtab "ht" at item "hi".
 * Clear the variable value and free the dictitem.
 	    EMSG2(_("E704: Funcref variable name must start with a capital: %s"), name);
 	    return;
 	}
 	if (function_exists(name))
 	{
-	    EMSG2(_("705: Variable name conflicts with existing function: %s"),
+	    EMSG2(_("E705: Variable name conflicts with existing function: %s"),
 									name);
 	    return;
 	}
 }
 {
 char_u	*save_sourcing_name;
 linenr_T	save_sourcing_lnum;
 scid_T	save_current_SID;
 funccall_T	fc;
-funccall_T	*save_fcp = current_funccal;
 int		save_did_emsg;
 static int	depth = 0;
 dictitem_T	*v;
 int		fixvar_idx = 0;	/* index in fixvar[] */
 int		i;
 }
 ++depth;
 line_breakcheck();		/* check for CTRL-C hit */
+fc.caller = current_funccal;
 current_funccal = &fc;
 fc.func = fp;
 fc.rettv = rettv;
 rettv->vval.v_number = 0;
 fc.linenr = 0;
 if (do_profiling)
 {
 	if (!fp->uf_profiling && has_profiling(FALSE, fp->uf_name, NULL))
 	    func_do_profile(fp);
 	if (fp->uf_profiling
-		       || (save_fcp != NULL && &save_fcp->func->uf_profiling))
+		       || (fc.caller != NULL && &fc.caller->func->uf_profiling))
 	{
 	    ++fp->uf_tm_count;
 	    profile_start(&fp->uf_tm_start);
 	    profile_zero(&fp->uf_tm_children);
 	}
 	rettv->v_type = VAR_NUMBER;
 	rettv->vval.v_number = -1;
 }
 #ifdef FEAT_PROFILE
-if (fp->uf_profiling || (save_fcp != NULL && &save_fcp->func->uf_profiling))
+if (fp->uf_profiling || (fc.caller != NULL && &fc.caller->func->uf_profiling))
 {
 	profile_end(&fp->uf_tm_start);
 	profile_sub_wait(&wait_start, &fp->uf_tm_start);
 	profile_add(&fp->uf_tm_total, &fp->uf_tm_start);
 	profile_add(&fp->uf_tm_self, &fp->uf_tm_start);
 	profile_sub(&fp->uf_tm_self, &fp->uf_tm_children);
-	if (save_fcp != NULL && &save_fcp->func->uf_profiling)
+	if (fc.caller != NULL && &fc.caller->func->uf_profiling)
 	{
-	    profile_add(&save_fcp->func->uf_tm_children, &fp->uf_tm_start);
+	    profile_add(&fc.caller->func->uf_tm_children, &fp->uf_tm_start);
-	    profile_add(&save_fcp->func->uf_tml_children, &fp->uf_tm_start);
+	    profile_add(&fc.caller->func->uf_tml_children, &fp->uf_tm_start);
 	}
 }
 #endif
 /* when being verbose, mention the return value */
 	verbose_leave_scroll();
 	--no_wait_return;
 }
 did_emsg |= save_did_emsg;
-current_funccal = save_fcp;
+current_funccal = fc.caller;
 /* The a: variables typevals were not alloced, only free the allocated
 * variables. */
 vars_clear_ext(&fc.l_avars.dv_hashtab, FALSE);

Mercurial > vim

comparison src/eval.c @ 371:4b9fef49d7ff v7.0095