vim_findfile(void *search_ctx_arg)
{
    char_u	*file_path;
#ifdef FEAT_PATH_EXTRA
    char_u	*rest_of_wildcards;
    char_u	*path_end = NULL;
#endif
    ff_stack_T	*stackp;
#if defined(FEAT_SEARCHPATH) || defined(FEAT_PATH_EXTRA)
    int		len;
#endif
    int		i;
    char_u	*p;
#ifdef FEAT_SEARCHPATH
    char_u	*suf;
#endif
    ff_search_ctx_T *search_ctx;

    if (search_ctx_arg == NULL)
	return NULL;

    search_ctx = (ff_search_ctx_T *)search_ctx_arg;

    /*
     * filepath is used as buffer for various actions and as the storage to
     * return a found filename.
     */
    if ((file_path = alloc(MAXPATHL)) == NULL)
	return NULL;

#ifdef FEAT_PATH_EXTRA
    // store the end of the start dir -- needed for upward search
    if (search_ctx->ffsc_start_dir != NULL)
	path_end = &search_ctx->ffsc_start_dir[
					  STRLEN(search_ctx->ffsc_start_dir)];
#endif

#ifdef FEAT_PATH_EXTRA
    // upward search loop
    for (;;)
    {
#endif
	// downward search loop
	for (;;)
	{
	    // check if user user wants to stop the search
	    ui_breakcheck();
	    if (got_int)
		break;

	    // get directory to work on from stack
	    stackp = ff_pop(search_ctx);
	    if (stackp == NULL)
		break;

	    /*
	     * TODO: decide if we leave this test in
	     *
	     * GOOD: don't search a directory(-tree) twice.
	     * BAD:  - check linked list for every new directory entered.
	     *       - check for double files also done below
	     *
	     * Here we check if we already searched this directory.
	     * We already searched a directory if:
	     * 1) The directory is the same.
	     * 2) We would use the same wildcard string.
	     *
	     * Good if you have links on same directory via several ways
	     *  or you have selfreferences in directories (e.g. SuSE Linux 6.3:
	     *  /etc/rc.d/init.d is linked to /etc/rc.d -> endless loop)
	     *
	     * This check is only needed for directories we work on for the
	     * first time (hence stackp->ff_filearray == NULL)
	     */
	    if (stackp->ffs_filearray == NULL
		    && ff_check_visited(&search_ctx->ffsc_dir_visited_list
							  ->ffvl_visited_list,
			stackp->ffs_fix_path
#ifdef FEAT_PATH_EXTRA
			, stackp->ffs_wc_path
#endif
			) == FAIL)
	    {
#ifdef FF_VERBOSE
		if (p_verbose >= 5)
		{
		    verbose_enter_scroll();
		    smsg("Already Searched: %s (%s)",
				   stackp->ffs_fix_path, stackp->ffs_wc_path);
		    // don't overwrite this either
		    msg_puts("\n");
		    verbose_leave_scroll();
		}
#endif
		ff_free_stack_element(stackp);
		continue;
	    }
#ifdef FF_VERBOSE
	    else if (p_verbose >= 5)
	    {
		verbose_enter_scroll();
		smsg("Searching: %s (%s)",
				   stackp->ffs_fix_path, stackp->ffs_wc_path);
		// don't overwrite this either
		msg_puts("\n");
		verbose_leave_scroll();
	    }
#endif

	    // check depth
	    if (stackp->ffs_level <= 0)
	    {
		ff_free_stack_element(stackp);
		continue;
	    }

	    file_path[0] = NUL;

	    /*
	     * If no filearray till now expand wildcards
	     * The function expand_wildcards() can handle an array of paths
	     * and all possible expands are returned in one array. We use this
	     * to handle the expansion of '**' into an empty string.
	     */
	    if (stackp->ffs_filearray == NULL)
	    {
		char_u *dirptrs[2];

		// we use filepath to build the path expand_wildcards() should
		// expand.
		dirptrs[0] = file_path;
		dirptrs[1] = NULL;

		// if we have a start dir copy it in
		if (!vim_isAbsName(stackp->ffs_fix_path)
						&& search_ctx->ffsc_start_dir)
		{
		    if (STRLEN(search_ctx->ffsc_start_dir) + 1 < MAXPATHL)
		    {
			STRCPY(file_path, search_ctx->ffsc_start_dir);
			add_pathsep(file_path);
		    }
		    else
		    {
			ff_free_stack_element(stackp);
			goto fail;
		    }
		}

		// append the fix part of the search path
		if (STRLEN(file_path) + STRLEN(stackp->ffs_fix_path) + 1
								    < MAXPATHL)
		{
		    STRCAT(file_path, stackp->ffs_fix_path);
		    add_pathsep(file_path);
		}
		else
		{
		    ff_free_stack_element(stackp);
		    goto fail;
		}

#ifdef FEAT_PATH_EXTRA
		rest_of_wildcards = stackp->ffs_wc_path;
		if (*rest_of_wildcards != NUL)
		{
		    len = (int)STRLEN(file_path);
		    if (STRNCMP(rest_of_wildcards, "**", 2) == 0)
		    {
			// pointer to the restrict byte
			// The restrict byte is not a character!
			p = rest_of_wildcards + 2;

			if (*p > 0)
			{
			    (*p)--;
			    if (len + 1 < MAXPATHL)
				file_path[len++] = '*';
			    else
			    {
				ff_free_stack_element(stackp);
				goto fail;
			    }
			}

			if (*p == 0)
			{
			    // remove '**<numb> from wildcards
			    STRMOVE(rest_of_wildcards, rest_of_wildcards + 3);
			}
			else
			    rest_of_wildcards += 3;

			if (stackp->ffs_star_star_empty == 0)
			{
			    // if not done before, expand '**' to empty
			    stackp->ffs_star_star_empty = 1;
			    dirptrs[1] = stackp->ffs_fix_path;
			}
		    }

		    /*
		     * Here we copy until the next path separator or the end of
		     * the path. If we stop at a path separator, there is
		     * still something else left. This is handled below by
		     * pushing every directory returned from expand_wildcards()
		     * on the stack again for further search.
		     */
		    while (*rest_of_wildcards
			    && !vim_ispathsep(*rest_of_wildcards))
			if (len + 1 < MAXPATHL)
			    file_path[len++] = *rest_of_wildcards++;
			else
			{
			    ff_free_stack_element(stackp);
			    goto fail;
			}

		    file_path[len] = NUL;
		    if (vim_ispathsep(*rest_of_wildcards))
			rest_of_wildcards++;
		}
#endif

		/*
		 * Expand wildcards like "*" and "$VAR".
		 * If the path is a URL don't try this.
		 */
		if (path_with_url(dirptrs[0]))
		{
		    stackp->ffs_filearray = ALLOC_ONE(char_u *);
		    if (stackp->ffs_filearray != NULL
			    && (stackp->ffs_filearray[0]
				= vim_strsave(dirptrs[0])) != NULL)
			stackp->ffs_filearray_size = 1;
		    else
			stackp->ffs_filearray_size = 0;
		}
		else
		    // Add EW_NOTWILD because the expanded path may contain
		    // wildcard characters that are to be taken literally.
		    // This is a bit of a hack.
		    expand_wildcards((dirptrs[1] == NULL) ? 1 : 2, dirptrs,
			    &stackp->ffs_filearray_size,
			    &stackp->ffs_filearray,
			    EW_DIR|EW_ADDSLASH|EW_SILENT|EW_NOTWILD);

		stackp->ffs_filearray_cur = 0;
		stackp->ffs_stage = 0;
	    }
#ifdef FEAT_PATH_EXTRA
	    else
		rest_of_wildcards = &stackp->ffs_wc_path[
						 STRLEN(stackp->ffs_wc_path)];
#endif

	    if (stackp->ffs_stage == 0)
	    {
		// this is the first time we work on this directory
#ifdef FEAT_PATH_EXTRA
		if (*rest_of_wildcards == NUL)
#endif
		{
		    /*
		     * We don't have further wildcards to expand, so we have to
		     * check for the final file now.
		     */
		    for (i = stackp->ffs_filearray_cur;
					  i < stackp->ffs_filearray_size; ++i)
		    {
			if (!path_with_url(stackp->ffs_filearray[i])
				      && !mch_isdir(stackp->ffs_filearray[i]))
			    continue;   // not a directory

			// prepare the filename to be checked for existence
			// below
			if (STRLEN(stackp->ffs_filearray[i]) + 1
				+ STRLEN(search_ctx->ffsc_file_to_search)
								    < MAXPATHL)
			{
			    STRCPY(file_path, stackp->ffs_filearray[i]);
			    add_pathsep(file_path);
			    STRCAT(file_path, search_ctx->ffsc_file_to_search);
			}
			else
			{
			    ff_free_stack_element(stackp);
			    goto fail;
			}

			/*
			 * Try without extra suffix and then with suffixes
			 * from 'suffixesadd'.
			 */
#ifdef FEAT_SEARCHPATH
			len = (int)STRLEN(file_path);
			if (search_ctx->ffsc_tagfile)
			    suf = (char_u *)"";
			else
			    suf = curbuf->b_p_sua;
			for (;;)
#endif
			{
			    // if file exists and we didn't already find it
			    if ((path_with_url(file_path)
				  || (mch_getperm(file_path) >= 0
				      && (search_ctx->ffsc_find_what
							      == FINDFILE_BOTH
					  || ((search_ctx->ffsc_find_what
							      == FINDFILE_DIR)
						   == mch_isdir(file_path)))))
#ifndef FF_VERBOSE
				    && (ff_check_visited(
					    &search_ctx->ffsc_visited_list->ffvl_visited_list,
					    file_path
#ifdef FEAT_PATH_EXTRA
					    , (char_u *)""
#endif
					    ) == OK)
#endif
			       )
			    {
#ifdef FF_VERBOSE
				if (ff_check_visited(
					    &search_ctx->ffsc_visited_list->ffvl_visited_list,
					    file_path
#ifdef FEAT_PATH_EXTRA
					    , (char_u *)""
#endif
						    ) == FAIL)
				{
				    if (p_verbose >= 5)
				    {
					verbose_enter_scroll();
					smsg("Already: %s",
								   file_path);
					// don't overwrite this either
					msg_puts("\n");
					verbose_leave_scroll();
				    }
				    continue;
				}
#endif

				// push dir to examine rest of subdirs later
				stackp->ffs_filearray_cur = i + 1;
				ff_push(search_ctx, stackp);

				if (!path_with_url(file_path))
				    simplify_filename(file_path);
				if (mch_dirname(ff_expand_buffer, MAXPATHL)
									== OK)
				{
				    p = shorten_fname(file_path,
							    ff_expand_buffer);
				    if (p != NULL)
					STRMOVE(file_path, p);
				}
#ifdef FF_VERBOSE
				if (p_verbose >= 5)
				{
				    verbose_enter_scroll();
				    smsg("HIT: %s", file_path);
				    // don't overwrite this either
				    msg_puts("\n");
				    verbose_leave_scroll();
				}
#endif
				return file_path;
			    }

#ifdef FEAT_SEARCHPATH
			    // Not found or found already, try next suffix.
			    if (*suf == NUL)
				break;
			    copy_option_part(&suf, file_path + len,
							 MAXPATHL - len, ",");
#endif
			}
		    }
		}
#ifdef FEAT_PATH_EXTRA
		else
		{
		    /*
		     * still wildcards left, push the directories for further
		     * search
		     */
		    for (i = stackp->ffs_filearray_cur;
					  i < stackp->ffs_filearray_size; ++i)
		    {
			if (!mch_isdir(stackp->ffs_filearray[i]))
			    continue;	// not a directory

			ff_push(search_ctx,
				ff_create_stack_element(
						     stackp->ffs_filearray[i],
						     rest_of_wildcards,
						     stackp->ffs_level - 1, 0));
		    }
		}
#endif
		stackp->ffs_filearray_cur = 0;
		stackp->ffs_stage = 1;
	    }

#ifdef FEAT_PATH_EXTRA
	    /*
	     * if wildcards contains '**' we have to descent till we reach the
	     * leaves of the directory tree.
	     */
	    if (STRNCMP(stackp->ffs_wc_path, "**", 2) == 0)
	    {
		for (i = stackp->ffs_filearray_cur;
					  i < stackp->ffs_filearray_size; ++i)
		{
		    if (fnamecmp(stackp->ffs_filearray[i],
						   stackp->ffs_fix_path) == 0)
			continue; // don't repush same directory
		    if (!mch_isdir(stackp->ffs_filearray[i]))
			continue;   // not a directory
		    ff_push(search_ctx,
			    ff_create_stack_element(stackp->ffs_filearray[i],
				stackp->ffs_wc_path, stackp->ffs_level - 1, 1));
		}
	    }
#endif

	    // we are done with the current directory
	    ff_free_stack_element(stackp);

	}

#ifdef FEAT_PATH_EXTRA
	// If we reached this, we didn't find anything downwards.
	// Let's check if we should do an upward search.
	if (search_ctx->ffsc_start_dir
		&& search_ctx->ffsc_stopdirs_v != NULL && !got_int)
	{
	    ff_stack_T  *sptr;

	    // is the last starting directory in the stop list?
	    if (ff_path_in_stoplist(search_ctx->ffsc_start_dir,
		       (int)(path_end - search_ctx->ffsc_start_dir),
		       search_ctx->ffsc_stopdirs_v) == TRUE)
		break;

	    // cut of last dir
	    while (path_end > search_ctx->ffsc_start_dir
						  && vim_ispathsep(*path_end))
		path_end--;
	    while (path_end > search_ctx->ffsc_start_dir
					      && !vim_ispathsep(path_end[-1]))
		path_end--;
	    *path_end = 0;
	    path_end--;

	    if (*search_ctx->ffsc_start_dir == 0)
		break;

	    if (STRLEN(search_ctx->ffsc_start_dir) + 1
		    + STRLEN(search_ctx->ffsc_fix_path) < MAXPATHL)
	    {
		STRCPY(file_path, search_ctx->ffsc_start_dir);
		add_pathsep(file_path);
		STRCAT(file_path, search_ctx->ffsc_fix_path);
	    }
	    else
		goto fail;

	    // create a new stack entry
	    sptr = ff_create_stack_element(file_path,
		    search_ctx->ffsc_wc_path, search_ctx->ffsc_level, 0);
	    if (sptr == NULL)
		break;
	    ff_push(search_ctx, sptr);
	}
	else
	    break;
    }
#endif

fail:
    vim_free(file_path);
    return NULL;
}