Differential D10618 Diff 34765 source/blender/blenlib/intern/string_search.cc

Changeset View

Standalone View

source/blender/blenlib/intern/string_search.cc

Show First 20 Lines • Show All 389 Lines • ▼ Show 20 Lines	if (is_in_word) {
r_words.append(str_copy.drop_prefix(static_cast<int>(word_start)));		r_words.append(str_copy.drop_prefix(static_cast<int>(word_start)));
}		}
}		}

} // namespace blender::string_search		} // namespace blender::string_search

struct SearchItem {		struct SearchItem {
blender::Span<blender::StringRef> normalized_words;		blender::Span<blender::StringRef> normalized_words;
		int length;
void *user_data;		void *user_data;
};		};

struct StringSearch {		struct StringSearch {
blender::LinearAllocator<> allocator;		blender::LinearAllocator<> allocator;
blender::Vector<SearchItem> items;		blender::Vector<SearchItem> items;
};		};

StringSearch *BLI_string_search_new()		StringSearch *BLI_string_search_new()
{		{
return new StringSearch();		return new StringSearch();
}		}

/**		/**
* Add a new possible result to the search.		* Add a new possible result to the search.
* The caller keeps ownership of all parameters.		* The caller keeps ownership of all parameters.
*/		*/
void BLI_string_search_add(StringSearch search, const char str, void *user_data)		void BLI_string_search_add(StringSearch search, const char str, void *user_data)
{		{
using namespace blender;		using namespace blender;
Vector<StringRef, 64> words;		Vector<StringRef, 64> words;
string_search::extract_normalized_words(str, search->allocator, words);		StringRef str_ref{str};
search->items.append({search->allocator.construct_array_copy(words.as_span()), user_data});		string_search::extract_normalized_words(str_ref, search->allocator, words);
		search->items.append(
		{search->allocator.construct_array_copy(words.as_span()), (int)str_ref.size(), user_data});
}		}

/**		/**
* Filter and sort all previously added search items.		* Filter and sort all previously added search items.
* Returns an array containing the filtered user data.		* Returns an array containing the filtered user data.
* The caller has to free the returned array.		* The caller has to free the returned array.
*/		*/
int BLI_string_search_query(StringSearch search, const char query, void ***r_data)		int BLI_string_search_query(StringSearch search, const char query, void ***r_data)
Show All 19 Lines	for (const int score : result_indices_by_score.keys()) {
found_scores.append(score);		found_scores.append(score);
}		}
std::sort(found_scores.begin(), found_scores.end(), std::greater<>());		std::sort(found_scores.begin(), found_scores.end(), std::greater<>());

/* Add results to output vector in correct order. First come the results with the best match		/* Add results to output vector in correct order. First come the results with the best match
* score. Results with the same score are in the order they have been added to the search. */		* score. Results with the same score are in the order they have been added to the search. */
Vector<int> sorted_result_indices;		Vector<int> sorted_result_indices;
for (const int score : found_scores) {		for (const int score : found_scores) {
Span<int> indices = result_indices_by_score.lookup(score);		MutableSpan<int> indices = result_indices_by_score.lookup(score);
		if (score == found_scores[0]) {
		/* Sort items with best score by length. Shorter items are more likely the ones you are
		* looking for. This also ensures that exact matches will be at the top, even if the query is
		* a substring of another item. */
		std::sort(indices.begin(), indices.end(), [&](int a, int b) {
		return search->items[a].length < search->items[b].length;
		});
		}
sorted_result_indices.extend(indices);		sorted_result_indices.extend(indices);
}		}

void sorted_data = static_cast<void >(		void sorted_data = static_cast<void >(
MEM_malloc_arrayN(static_cast<size_t>(sorted_result_indices.size()), sizeof(void *), AT));		MEM_malloc_arrayN(static_cast<size_t>(sorted_result_indices.size()), sizeof(void *), AT));
for (const int i : sorted_result_indices.index_range()) {		for (const int i : sorted_result_indices.index_range()) {
const int result_index = sorted_result_indices[i];		const int result_index = sorted_result_indices[i];
SearchItem &item = search->items[result_index];		SearchItem &item = search->items[result_index];
Show All 12 Lines