diff options
19 files changed, 1070 insertions, 128 deletions
diff --git a/java/res/layout/radio_button_preference_widget.xml b/java/res/layout/radio_button_preference_widget.xml new file mode 100644 index 000000000..ee9cda1cc --- /dev/null +++ b/java/res/layout/radio_button_preference_widget.xml @@ -0,0 +1,23 @@ +<?xml version="1.0" encoding="utf-8"?> +<!-- Copyright (C) 2014 The Android Open Source Project + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> + +<RadioButton + xmlns:android="http://schemas.android.com/apk/res/android" + android:id="@+id/radio_button" + android:layout_width="wrap_content" + android:layout_height="wrap_content" + android:clickable="false" + android:focusable="false" /> diff --git a/java/res/xml/prefs.xml b/java/res/xml/prefs.xml index 66091a03d..ba285de09 100644 --- a/java/res/xml/prefs.xml +++ b/java/res/xml/prefs.xml @@ -22,12 +22,10 @@ android:fragment="com.android.inputmethod.latin.settings.InputSettingsFragment" android:title="@string/settings_screen_input" android:key="screen_input" /> - <ListPreference - android:key="pref_keyboard_theme" + <PreferenceScreen + android:fragment="com.android.inputmethod.latin.settings.ThemeSettingsFragment" android:title="@string/keyboard_theme" - android:entryValues="@array/keyboard_theme_ids" - android:entries="@array/keyboard_theme_names" - android:persistent="true" /> + android:key="screen_theme" /> <PreferenceScreen android:fragment="com.android.inputmethod.latin.settings.MultiLingualSettingsFragment" android:title="@string/settings_screen_multi_lingual" diff --git a/java/res/xml/prefs_screen_theme.xml b/java/res/xml/prefs_screen_theme.xml new file mode 100644 index 000000000..b49f0bea6 --- /dev/null +++ b/java/res/xml/prefs_screen_theme.xml @@ -0,0 +1,23 @@ +<?xml version="1.0" encoding="utf-8"?> +<!-- Copyright (C) 2014 The Android Open Source Project + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> + +<PreferenceScreen + xmlns:android="http://schemas.android.com/apk/res/android" + xmlns:latin="http://schemas.android.com/apk/res/com.android.inputmethod.latin" + android:title="@string/keyboard_theme" + android:key="screen_theme"> + <!-- Keyboard theme list will be populated programmatically here. --> +</PreferenceScreen> diff --git a/java/src/com/android/inputmethod/latin/settings/GestureSettingsFragment.java b/java/src/com/android/inputmethod/latin/settings/GestureSettingsFragment.java index b95c35637..832fbf65a 100644 --- a/java/src/com/android/inputmethod/latin/settings/GestureSettingsFragment.java +++ b/java/src/com/android/inputmethod/latin/settings/GestureSettingsFragment.java @@ -36,9 +36,4 @@ public final class GestureSettingsFragment extends SubScreenFragment { super.onCreate(icicle); addPreferencesFromResource(R.xml.prefs_screen_gesture); } - - @Override - public void onSharedPreferenceChanged(final SharedPreferences prefs, final String key) { - // Nothing to do here. - } } diff --git a/java/src/com/android/inputmethod/latin/settings/MultiLingualSettingsFragment.java b/java/src/com/android/inputmethod/latin/settings/MultiLingualSettingsFragment.java index f40106ba9..fcdd39316 100644 --- a/java/src/com/android/inputmethod/latin/settings/MultiLingualSettingsFragment.java +++ b/java/src/com/android/inputmethod/latin/settings/MultiLingualSettingsFragment.java @@ -63,11 +63,6 @@ public final class MultiLingualSettingsFragment extends SubScreenFragment { updateCustomInputStylesSummary(); } - @Override - public void onSharedPreferenceChanged(final SharedPreferences prefs, final String key) { - // Nothing to do here. - } - private void updateCustomInputStylesSummary() { final SharedPreferences prefs = getSharedPreferences(); final Resources res = getResources(); diff --git a/java/src/com/android/inputmethod/latin/settings/RadioButtonPreference.java b/java/src/com/android/inputmethod/latin/settings/RadioButtonPreference.java new file mode 100644 index 000000000..c173d4706 --- /dev/null +++ b/java/src/com/android/inputmethod/latin/settings/RadioButtonPreference.java @@ -0,0 +1,93 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.settings; + +import android.content.Context; +import android.preference.Preference; +import android.util.AttributeSet; +import android.view.View; +import android.widget.RadioButton; + +import com.android.inputmethod.latin.R; + +/** + * Radio Button preference + */ +public class RadioButtonPreference extends Preference { + interface OnRadioButtonClickedListener { + /** + * Called when this preference needs to be saved its state. + * + * @param preference This preference. + */ + public void onRadioButtonClicked(RadioButtonPreference preference); + } + + private boolean mIsSelected; + private RadioButton mRadioButton; + private OnRadioButtonClickedListener mListener; + private final View.OnClickListener mClickListener = new View.OnClickListener() { + @Override + public void onClick(final View v) { + if (mListener != null) { + mListener.onRadioButtonClicked(RadioButtonPreference.this); + } + } + }; + + public RadioButtonPreference(final Context context) { + this(context, null); + } + + public RadioButtonPreference(final Context context, final AttributeSet attrs) { + this(context, attrs, android.R.attr.preferenceStyle); + } + + public RadioButtonPreference(final Context context, final AttributeSet attrs, + final int defStyleAttr) { + super(context, attrs, defStyleAttr); + setWidgetLayoutResource(R.layout.radio_button_preference_widget); + } + + public void setOnRadioButtonClickedListener(final OnRadioButtonClickedListener listener) { + mListener = listener; + } + + @Override + protected void onBindView(final View view) { + super.onBindView(view); + mRadioButton = (RadioButton)view.findViewById(R.id.radio_button); + mRadioButton.setChecked(mIsSelected); + mRadioButton.setOnClickListener(mClickListener); + view.setOnClickListener(mClickListener); + } + + public boolean isSelected() { + return mIsSelected; + } + + public void setSelected(final boolean selected) { + if (selected == mIsSelected) { + return; + } + mIsSelected = selected; + if (mRadioButton != null) { + mRadioButton.setChecked(selected); + } + notifyChanged(); + } +} diff --git a/java/src/com/android/inputmethod/latin/settings/Settings.java b/java/src/com/android/inputmethod/latin/settings/Settings.java index 0e6a15a7e..90174e490 100644 --- a/java/src/com/android/inputmethod/latin/settings/Settings.java +++ b/java/src/com/android/inputmethod/latin/settings/Settings.java @@ -41,6 +41,7 @@ public final class Settings implements SharedPreferences.OnSharedPreferenceChang private static final String TAG = Settings.class.getSimpleName(); // Settings screens public static final String SCREEN_INPUT = "screen_input"; + public static final String SCREEN_THEME = "screen_theme"; public static final String SCREEN_MULTI_LINGUAL = "screen_multi_lingual"; public static final String SCREEN_GESTURE = "screen_gesture"; public static final String SCREEN_CORRECTION = "screen_correction"; diff --git a/java/src/com/android/inputmethod/latin/settings/SettingsFragment.java b/java/src/com/android/inputmethod/latin/settings/SettingsFragment.java index 93645203b..6734a9ce6 100644 --- a/java/src/com/android/inputmethod/latin/settings/SettingsFragment.java +++ b/java/src/com/android/inputmethod/latin/settings/SettingsFragment.java @@ -16,47 +16,23 @@ package com.android.inputmethod.latin.settings; -import android.app.Activity; -import android.app.backup.BackupManager; -import android.content.Context; import android.content.Intent; -import android.content.SharedPreferences; -import android.content.res.Resources; import android.os.Bundle; -import android.preference.ListPreference; import android.preference.PreferenceScreen; -import android.util.Log; import android.view.Menu; import android.view.MenuInflater; import android.view.MenuItem; -import com.android.inputmethod.keyboard.KeyboardTheme; -import com.android.inputmethod.latin.AudioAndHapticFeedbackManager; import com.android.inputmethod.latin.R; import com.android.inputmethod.latin.utils.ApplicationUtils; import com.android.inputmethod.latin.utils.FeedbackUtils; import com.android.inputmethodcommon.InputMethodSettingsFragment; -public final class SettingsFragment extends InputMethodSettingsFragment - implements SharedPreferences.OnSharedPreferenceChangeListener { - private static final String TAG = SettingsFragment.class.getSimpleName(); - +public final class SettingsFragment extends InputMethodSettingsFragment { private static final int NO_MENU_GROUP = Menu.NONE; // We don't care about menu grouping. private static final int MENU_FEEDBACK = Menu.FIRST; // The first menu item id and order. private static final int MENU_ABOUT = Menu.FIRST + 1; // The second menu item id and order. - private void updateListPreferenceSummaryToCurrentValue(final String prefKey) { - // Because the "%s" summary trick of {@link ListPreference} doesn't work properly before - // KitKat, we need to update the summary programmatically. - final ListPreference listPreference = (ListPreference)findPreference(prefKey); - if (listPreference == null) { - return; - } - final CharSequence entries[] = listPreference.getEntries(); - final int entryIndex = listPreference.findIndexOfValue(listPreference.getValue()); - listPreference.setSummary(entryIndex < 0 ? null : entries[entryIndex]); - } - @Override public void onCreate(final Bundle icicle) { super.onCreate(icicle); @@ -65,73 +41,14 @@ public final class SettingsFragment extends InputMethodSettingsFragment setSubtypeEnablerTitle(R.string.select_language); addPreferencesFromResource(R.xml.prefs); final PreferenceScreen preferenceScreen = getPreferenceScreen(); - TwoStatePreferenceHelper.replaceCheckBoxPreferencesBySwitchPreferences(preferenceScreen); preferenceScreen.setTitle( ApplicationUtils.getActivityTitleResId(getActivity(), SettingsActivity.class)); - - final Resources res = getResources(); - final Context context = getActivity(); - - // When we are called from the Settings application but we are not already running, some - // singleton and utility classes may not have been initialized. We have to call - // initialization method of these classes here. See {@link LatinIME#onCreate()}. - AudioAndHapticFeedbackManager.init(context); - - final SharedPreferences prefs = getPreferenceManager().getSharedPreferences(); - prefs.registerOnSharedPreferenceChangeListener(this); - - if (!Settings.readFromBuildConfigIfGestureInputEnabled(res)) { - getPreferenceScreen().removePreference(findPreference(Settings.SCREEN_GESTURE)); - } - - AdditionalFeaturesSettingUtils.addAdditionalFeaturesPreferences(context, this); } @Override public void onResume() { super.onResume(); - final SharedPreferences prefs = getPreferenceManager().getSharedPreferences(); - final ListPreference keyboardThemePref = (ListPreference)findPreference( - Settings.PREF_KEYBOARD_THEME); - if (keyboardThemePref != null) { - final KeyboardTheme keyboardTheme = KeyboardTheme.getKeyboardTheme(prefs); - final String value = Integer.toString(keyboardTheme.mThemeId); - final CharSequence entries[] = keyboardThemePref.getEntries(); - final int entryIndex = keyboardThemePref.findIndexOfValue(value); - keyboardThemePref.setSummary(entryIndex < 0 ? null : entries[entryIndex]); - keyboardThemePref.setValue(value); - } - } - - @Override - public void onPause() { - super.onPause(); - final SharedPreferences prefs = getPreferenceManager().getSharedPreferences(); - final ListPreference keyboardThemePref = (ListPreference)findPreference( - Settings.PREF_KEYBOARD_THEME); - if (keyboardThemePref != null) { - KeyboardTheme.saveKeyboardThemeId(keyboardThemePref.getValue(), prefs); - } - } - - @Override - public void onDestroy() { - getPreferenceManager().getSharedPreferences().unregisterOnSharedPreferenceChangeListener( - this); - super.onDestroy(); - } - - @Override - public void onSharedPreferenceChanged(final SharedPreferences prefs, final String key) { - final Activity activity = getActivity(); - if (activity == null) { - // TODO: Introduce a static function to register this class and ensure that - // onCreate must be called before "onSharedPreferenceChanged" is called. - Log.w(TAG, "onSharedPreferenceChanged called before activity starts."); - return; - } - (new BackupManager(activity)).dataChanged(); - updateListPreferenceSummaryToCurrentValue(Settings.PREF_KEYBOARD_THEME); + ThemeSettingsFragment.updateKeyboardThemeSummary(findPreference(Settings.SCREEN_THEME)); } @Override diff --git a/java/src/com/android/inputmethod/latin/settings/SubScreenFragment.java b/java/src/com/android/inputmethod/latin/settings/SubScreenFragment.java index c70bf2997..ca5b395ce 100644 --- a/java/src/com/android/inputmethod/latin/settings/SubScreenFragment.java +++ b/java/src/com/android/inputmethod/latin/settings/SubScreenFragment.java @@ -115,4 +115,9 @@ abstract class SubScreenFragment extends PreferenceFragment mSharedPreferenceChangeListener); super.onDestroy(); } + + @Override + public void onSharedPreferenceChanged(final SharedPreferences prefs, final String key) { + // This method may be overridden by an extended class. + } } diff --git a/java/src/com/android/inputmethod/latin/settings/ThemeSettingsFragment.java b/java/src/com/android/inputmethod/latin/settings/ThemeSettingsFragment.java new file mode 100644 index 000000000..5a3fc3600 --- /dev/null +++ b/java/src/com/android/inputmethod/latin/settings/ThemeSettingsFragment.java @@ -0,0 +1,114 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.settings; + +import android.content.Context; +import android.content.SharedPreferences; +import android.content.res.Resources; +import android.os.Bundle; +import android.preference.Preference; +import android.preference.PreferenceScreen; + +import com.android.inputmethod.keyboard.KeyboardTheme; +import com.android.inputmethod.latin.R; +import com.android.inputmethod.latin.settings.RadioButtonPreference.OnRadioButtonClickedListener; + +/** + * "Keyboard theme" settings sub screen. + */ +public final class ThemeSettingsFragment extends SubScreenFragment + implements OnRadioButtonClickedListener { + private String mSelectedThemeId; + + static class KeyboardThemePreference extends RadioButtonPreference { + final String mThemeId; + + KeyboardThemePreference(final Context context, final String name, final String id) { + super(context); + setTitle(name); + mThemeId = id; + } + } + + static void updateKeyboardThemeSummary(final Preference pref) { + final Resources res = pref.getContext().getResources(); + final SharedPreferences prefs = pref.getSharedPreferences(); + final KeyboardTheme keyboardTheme = KeyboardTheme.getKeyboardTheme(prefs); + final String keyboardThemeId = String.valueOf(keyboardTheme.mThemeId); + final String[] keyboardThemeNames = res.getStringArray(R.array.keyboard_theme_names); + final String[] keyboardThemeIds = res.getStringArray(R.array.keyboard_theme_ids); + for (int index = 0; index < keyboardThemeNames.length; index++) { + if (keyboardThemeId.equals(keyboardThemeIds[index])) { + pref.setSummary(keyboardThemeNames[index]); + return; + } + } + } + + @Override + public void onCreate(final Bundle icicle) { + super.onCreate(icicle); + addPreferencesFromResource(R.xml.prefs_screen_theme); + final PreferenceScreen screen = getPreferenceScreen(); + final Resources res = getResources(); + final String[] keyboardThemeNames = res.getStringArray(R.array.keyboard_theme_names); + final String[] keyboardThemeIds = res.getStringArray(R.array.keyboard_theme_ids); + for (int index = 0; index < keyboardThemeNames.length; index++) { + final KeyboardThemePreference pref = new KeyboardThemePreference( + getActivity(), keyboardThemeNames[index], keyboardThemeIds[index]); + screen.addPreference(pref); + pref.setOnRadioButtonClickedListener(this); + } + final SharedPreferences prefs = getSharedPreferences(); + final KeyboardTheme keyboardTheme = KeyboardTheme.getKeyboardTheme(prefs); + mSelectedThemeId = String.valueOf(keyboardTheme.mThemeId); + } + + @Override + public void onRadioButtonClicked(final RadioButtonPreference preference) { + if (preference instanceof KeyboardThemePreference) { + final KeyboardThemePreference pref = (KeyboardThemePreference)preference; + mSelectedThemeId = pref.mThemeId; + updateSelected(); + } + } + + @Override + public void onResume() { + super.onResume(); + updateSelected(); + } + + @Override + public void onPause() { + super.onPause(); + KeyboardTheme.saveKeyboardThemeId(mSelectedThemeId, getSharedPreferences()); + } + + private void updateSelected() { + final PreferenceScreen screen = getPreferenceScreen(); + final int count = screen.getPreferenceCount(); + for (int index = 0; index < count; index++) { + final Preference preference = screen.getPreference(index); + if (preference instanceof KeyboardThemePreference) { + final KeyboardThemePreference pref = (KeyboardThemePreference)preference; + final boolean selected = mSelectedThemeId.equals(pref.mThemeId); + pref.setSelected(selected); + } + } + } +} diff --git a/java/src/com/android/inputmethod/latin/utils/FragmentUtils.java b/java/src/com/android/inputmethod/latin/utils/FragmentUtils.java index 9858a235a..08f5b0b41 100644 --- a/java/src/com/android/inputmethod/latin/utils/FragmentUtils.java +++ b/java/src/com/android/inputmethod/latin/utils/FragmentUtils.java @@ -26,6 +26,7 @@ import com.android.inputmethod.latin.settings.GestureSettingsFragment; import com.android.inputmethod.latin.settings.InputSettingsFragment; import com.android.inputmethod.latin.settings.MultiLingualSettingsFragment; import com.android.inputmethod.latin.settings.SettingsFragment; +import com.android.inputmethod.latin.settings.ThemeSettingsFragment; import com.android.inputmethod.latin.spellcheck.SpellCheckerSettingsFragment; import com.android.inputmethod.latin.userdictionary.UserDictionaryAddWordFragment; import com.android.inputmethod.latin.userdictionary.UserDictionaryList; @@ -40,6 +41,7 @@ public class FragmentUtils { sLatinImeFragments.add(DictionarySettingsFragment.class.getName()); sLatinImeFragments.add(AboutPreferences.class.getName()); sLatinImeFragments.add(InputSettingsFragment.class.getName()); + sLatinImeFragments.add(ThemeSettingsFragment.class.getName()); sLatinImeFragments.add(MultiLingualSettingsFragment.class.getName()); sLatinImeFragments.add(CustomInputStyleSettingsFragment.class.getName()); sLatinImeFragments.add(GestureSettingsFragment.class.getName()); diff --git a/native/jni/NativeFileList.mk b/native/jni/NativeFileList.mk index 1cb61c45f..ef6f3d69e 100644 --- a/native/jni/NativeFileList.mk +++ b/native/jni/NativeFileList.mk @@ -84,7 +84,8 @@ LATIN_IME_CORE_SRC_FILES := \ forgetting_curve_utils.cpp \ format_utils.cpp \ mmapped_buffer.cpp \ - sparse_table.cpp) \ + sparse_table.cpp \ + trie_map.cpp ) \ suggest/policyimpl/gesture/gesture_suggest_policy_factory.cpp \ $(addprefix suggest/policyimpl/typing/, \ scoring_params.cpp \ @@ -125,4 +126,5 @@ LATIN_IME_CORE_TEST_FILES := \ suggest/core/layout/normal_distribution_2d_test.cpp \ suggest/core/dictionary/bloom_filter_test.cpp \ suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer_test.cpp \ + suggest/policyimpl/dictionary/utils/trie_map_test.cpp \ utils/autocorrection_threshold_utils_test.cpp diff --git a/native/jni/src/suggest/core/dictionary/dictionary.cpp b/native/jni/src/suggest/core/dictionary/dictionary.cpp index 4605409cc..bf917d69c 100644 --- a/native/jni/src/suggest/core/dictionary/dictionary.cpp +++ b/native/jni/src/suggest/core/dictionary/dictionary.cpp @@ -88,13 +88,7 @@ void Dictionary::getPredictions(const PrevWordsInfo *const prevWordsInfo, } int Dictionary::getProbability(const int *word, int length) const { - TimeKeeper::setCurrentTime(); - int pos = getDictionaryStructurePolicy()->getTerminalPtNodePositionOfWord(word, length, - false /* forceLowerCaseSearch */); - if (NOT_A_DICT_POS == pos) { - return NOT_A_PROBABILITY; - } - return getDictionaryStructurePolicy()->getProbabilityOfPtNode(nullptr /* prevWordsInfo */, pos); + return getNgramProbability(nullptr /* prevWordsInfo */, word, length); } int Dictionary::getMaxProbabilityOfExactMatches(const int *word, int length) const { @@ -109,18 +103,7 @@ int Dictionary::getNgramProbability(const PrevWordsInfo *const prevWordsInfo, co int nextWordPos = mDictionaryStructureWithBufferPolicy->getTerminalPtNodePositionOfWord(word, length, false /* forceLowerCaseSearch */); if (NOT_A_DICT_POS == nextWordPos) return NOT_A_PROBABILITY; - BinaryDictionaryBigramsIterator bigramsIt = prevWordsInfo->getBigramsIteratorForPrediction( - mDictionaryStructureWithBufferPolicy.get()); - while (bigramsIt.hasNext()) { - bigramsIt.next(); - if (bigramsIt.getBigramPos() == nextWordPos - && bigramsIt.getProbability() != NOT_A_PROBABILITY) { - return mDictionaryStructureWithBufferPolicy->getProbability( - mDictionaryStructureWithBufferPolicy->getProbabilityOfPtNode( - nullptr /* prevWordsInfo */, nextWordPos), bigramsIt.getProbability()); - } - } - return NOT_A_PROBABILITY; + return getDictionaryStructurePolicy()->getProbabilityOfPtNode(prevWordsInfo, nextWordPos); } bool Dictionary::addUnigramEntry(const int *const word, const int length, diff --git a/native/jni/src/suggest/policyimpl/dictionary/structure/backward/v402/ver4_patricia_trie_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/structure/backward/v402/ver4_patricia_trie_policy.cpp index 881994552..327741065 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/structure/backward/v402/ver4_patricia_trie_policy.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/structure/backward/v402/ver4_patricia_trie_policy.cpp @@ -140,6 +140,18 @@ int Ver4PatriciaTriePolicy::getProbabilityOfPtNode(const PrevWordsInfo *const pr if (ptNodeParams.isDeleted() || ptNodeParams.isBlacklisted() || ptNodeParams.isNotAWord()) { return NOT_A_PROBABILITY; } + if (prevWordsInfo) { + BinaryDictionaryBigramsIterator bigramsIt = + prevWordsInfo->getBigramsIteratorForPrediction(this /* dictStructurePolicy */); + while (bigramsIt.hasNext()) { + bigramsIt.next(); + if (bigramsIt.getBigramPos() == ptNodePos + && bigramsIt.getProbability() != NOT_A_PROBABILITY) { + return getProbability(ptNodeParams.getProbability(), bigramsIt.getProbability()); + } + } + return NOT_A_PROBABILITY; + } return getProbability(ptNodeParams.getProbability(), NOT_A_PROBABILITY); } diff --git a/native/jni/src/suggest/policyimpl/dictionary/structure/v2/patricia_trie_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/structure/v2/patricia_trie_policy.cpp index 53550a432..b909e8268 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/structure/v2/patricia_trie_policy.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/structure/v2/patricia_trie_policy.cpp @@ -21,6 +21,7 @@ #include "suggest/core/dicnode/dic_node.h" #include "suggest/core/dicnode/dic_node_vector.h" #include "suggest/core/dictionary/binary_dictionary_bigrams_iterator.h" +#include "suggest/core/session/prev_words_info.h" #include "suggest/policyimpl/dictionary/structure/pt_common/dynamic_pt_reading_helper.h" #include "suggest/policyimpl/dictionary/structure/pt_common/patricia_trie_reading_utils.h" #include "suggest/policyimpl/dictionary/utils/probability_utils.h" @@ -297,10 +298,6 @@ int PatriciaTriePolicy::getProbability(const int unigramProbability, int PatriciaTriePolicy::getProbabilityOfPtNode(const PrevWordsInfo *const prevWordsInfo, const int ptNodePos) const { - if (prevWordsInfo) { - // TODO: Return probability using prevWordsInfo. - return NOT_A_PROBABILITY; - } if (ptNodePos == NOT_A_DICT_POS) { return NOT_A_PROBABILITY; } @@ -312,6 +309,18 @@ int PatriciaTriePolicy::getProbabilityOfPtNode(const PrevWordsInfo *const prevWo // for shortcuts). return NOT_A_PROBABILITY; } + if (prevWordsInfo) { + BinaryDictionaryBigramsIterator bigramsIt = + prevWordsInfo->getBigramsIteratorForPrediction(this /* dictStructurePolicy */); + while (bigramsIt.hasNext()) { + bigramsIt.next(); + if (bigramsIt.getBigramPos() == ptNodePos + && bigramsIt.getProbability() != NOT_A_PROBABILITY) { + return getProbability(ptNodeParams.getProbability(), bigramsIt.getProbability()); + } + } + return NOT_A_PROBABILITY; + } return getProbability(ptNodeParams.getProbability(), NOT_A_PROBABILITY); } diff --git a/native/jni/src/suggest/policyimpl/dictionary/structure/v4/ver4_patricia_trie_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/structure/v4/ver4_patricia_trie_policy.cpp index 5197a4dd5..cada3d1f7 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/structure/v4/ver4_patricia_trie_policy.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/structure/v4/ver4_patricia_trie_policy.cpp @@ -123,10 +123,6 @@ int Ver4PatriciaTriePolicy::getProbability(const int unigramProbability, int Ver4PatriciaTriePolicy::getProbabilityOfPtNode(const PrevWordsInfo *const prevWordsInfo, const int ptNodePos) const { - if (prevWordsInfo) { - // TODO: Return probability using prevWordsInfo. - return NOT_A_PROBABILITY; - } if (ptNodePos == NOT_A_DICT_POS) { return NOT_A_PROBABILITY; } @@ -134,6 +130,18 @@ int Ver4PatriciaTriePolicy::getProbabilityOfPtNode(const PrevWordsInfo *const pr if (ptNodeParams.isDeleted() || ptNodeParams.isBlacklisted() || ptNodeParams.isNotAWord()) { return NOT_A_PROBABILITY; } + if (prevWordsInfo) { + BinaryDictionaryBigramsIterator bigramsIt = + prevWordsInfo->getBigramsIteratorForPrediction(this /* dictStructurePolicy */); + while (bigramsIt.hasNext()) { + bigramsIt.next(); + if (bigramsIt.getBigramPos() == ptNodePos + && bigramsIt.getProbability() != NOT_A_PROBABILITY) { + return getProbability(ptNodeParams.getProbability(), bigramsIt.getProbability()); + } + } + return NOT_A_PROBABILITY; + } return getProbability(ptNodeParams.getProbability(), NOT_A_PROBABILITY); } diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/trie_map.cpp b/native/jni/src/suggest/policyimpl/dictionary/utils/trie_map.cpp new file mode 100644 index 000000000..a7d86f9ae --- /dev/null +++ b/native/jni/src/suggest/policyimpl/dictionary/utils/trie_map.cpp @@ -0,0 +1,340 @@ +/* + * Copyright (C) 2014, The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "suggest/policyimpl/dictionary/utils/trie_map.h" + +namespace latinime { + +const int TrieMap::INVALID_INDEX = -1; +const int TrieMap::FIELD0_SIZE = 4; +const int TrieMap::FIELD1_SIZE = 3; +const int TrieMap::ENTRY_SIZE = FIELD0_SIZE + FIELD1_SIZE; +const uint32_t TrieMap::VALUE_FLAG = 0x400000; +const uint32_t TrieMap::VALUE_MASK = 0x3FFFFF; +const uint32_t TrieMap::TERMINAL_LINK_FLAG = 0x800000; +const uint32_t TrieMap::TERMINAL_LINK_MASK = 0x7FFFFF; +const int TrieMap::NUM_OF_BITS_USED_FOR_ONE_LEVEL = 5; +const uint32_t TrieMap::LABEL_MASK = 0x1F; +const int TrieMap::MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL = 1 << NUM_OF_BITS_USED_FOR_ONE_LEVEL; +const int TrieMap::ROOT_BITMAP_ENTRY_INDEX = 0; +const int TrieMap::ROOT_BITMAP_ENTRY_POS = MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL * FIELD0_SIZE; +const TrieMap::Entry TrieMap::EMPTY_BITMAP_ENTRY = TrieMap::Entry(0, 0); +const uint64_t TrieMap::MAX_VALUE = + (static_cast<uint64_t>(1) << ((FIELD0_SIZE + FIELD1_SIZE) * CHAR_BIT)) - 1; +const int TrieMap::MAX_BUFFER_SIZE = TERMINAL_LINK_MASK * ENTRY_SIZE; + +TrieMap::TrieMap() : mBuffer(MAX_BUFFER_SIZE) { + mBuffer.extend(ROOT_BITMAP_ENTRY_POS); + writeEntry(EMPTY_BITMAP_ENTRY, ROOT_BITMAP_ENTRY_INDEX); +} + +void TrieMap::dump(const int from, const int to) const { + AKLOGI("BufSize: %d", mBuffer.getTailPosition()); + for (int i = from; i < to; ++i) { + AKLOGI("Entry[%d]: %x, %x", i, readField0(i), readField1(i)); + } + int unusedRegionSize = 0; + for (int i = 1; i <= MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL; ++i) { + int index = readEmptyTableLink(i); + while (index != ROOT_BITMAP_ENTRY_INDEX) { + index = readField0(index); + unusedRegionSize += i; + } + } + AKLOGI("Unused Size: %d", unusedRegionSize); +} + +int TrieMap::getNextLevelBitmapEntryIndex(const int key, const int bitmapEntryIndex) { + const Entry bitmapEntry = readEntry(bitmapEntryIndex); + const uint32_t unsignedKey = static_cast<uint32_t>(key); + const int terminalEntryIndex = getTerminalEntryIndex( + unsignedKey, getBitShuffledKey(unsignedKey), bitmapEntry, 0 /* level */); + if (terminalEntryIndex == INVALID_INDEX) { + // Not found. + return INVALID_INDEX; + } + const Entry terminalEntry = readEntry(terminalEntryIndex); + if (terminalEntry.hasTerminalLink()) { + return terminalEntry.getValueEntryIndex() + 1; + } + // Create a value entry and a bitmap entry. + const int valueEntryIndex = allocateTable(2 /* entryCount */); + if (!writeEntry(Entry(0, terminalEntry.getValue()), valueEntryIndex)) { + return INVALID_INDEX; + } + if (!writeEntry(EMPTY_BITMAP_ENTRY, valueEntryIndex + 1)) { + return INVALID_INDEX; + } + if (!writeField1(valueEntryIndex | TERMINAL_LINK_FLAG, valueEntryIndex)) { + return INVALID_INDEX; + } + return valueEntryIndex + 1; +} + +const TrieMap::Result TrieMap::get(const int key, const int bitmapEntryIndex) const { + const uint32_t unsignedKey = static_cast<uint32_t>(key); + return getInternal(unsignedKey, getBitShuffledKey(unsignedKey), bitmapEntryIndex, + 0 /* level */); +} + +bool TrieMap::put(const int key, const uint64_t value, const int bitmapEntryIndex) { + if (value > MAX_VALUE) { + return false; + } + const uint32_t unsignedKey = static_cast<uint32_t>(key); + return putInternal(unsignedKey, value, getBitShuffledKey(unsignedKey), bitmapEntryIndex, + readEntry(bitmapEntryIndex), 0 /* level */); +} + +/** + * Shuffle bits of the key in the fixed order. + * + * This method is used as a hash function. This returns different values for different inputs. + */ +uint32_t TrieMap::getBitShuffledKey(const uint32_t key) const { + uint32_t shuffledKey = 0; + for (int i = 0; i < 4; ++i) { + const uint32_t keyPiece = (key >> (i * 8)) & 0xFF; + shuffledKey ^= ((keyPiece ^ (keyPiece << 7) ^ (keyPiece << 14) ^ (keyPiece << 21)) + & 0x11111111) << i; + } + return shuffledKey; +} + +bool TrieMap::writeValue(const uint64_t value, const int terminalEntryIndex) { + if (value <= VALUE_MASK) { + // Write value into the terminal entry. + return writeField1(value | VALUE_FLAG, terminalEntryIndex); + } + // Create value entry and write value. + const int valueEntryIndex = allocateTable(2 /* entryCount */); + if (!writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value), valueEntryIndex)) { + return false; + } + if (!writeEntry(EMPTY_BITMAP_ENTRY, valueEntryIndex + 1)) { + return false; + } + return writeField1(valueEntryIndex | TERMINAL_LINK_FLAG, terminalEntryIndex); +} + +bool TrieMap::updateValue(const Entry &terminalEntry, const uint64_t value, + const int terminalEntryIndex) { + if (!terminalEntry.hasTerminalLink()) { + return writeValue(value, terminalEntryIndex); + } + const int valueEntryIndex = terminalEntry.getValueEntryIndex(); + return writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value), valueEntryIndex); +} + +bool TrieMap::freeTable(const int tableIndex, const int entryCount) { + if (!writeField0(readEmptyTableLink(entryCount), tableIndex)) { + return false; + } + return writeEmptyTableLink(tableIndex, entryCount); +} + +/** + * Allocate table with entryCount-entries. Reuse freed table if possible. + */ +int TrieMap::allocateTable(const int entryCount) { + if (entryCount > 0 && entryCount <= MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL) { + const int tableIndex = readEmptyTableLink(entryCount); + if (tableIndex > 0) { + if (!writeEmptyTableLink(readField0(tableIndex), entryCount)) { + return INVALID_INDEX; + } + // Reuse the table. + return tableIndex; + } + } + // Allocate memory space at tail position of the buffer. + const int mapIndex = getTailEntryIndex(); + if (!mBuffer.extend(entryCount * ENTRY_SIZE)) { + return INVALID_INDEX; + } + return mapIndex; +} + +int TrieMap::getTerminalEntryIndex(const uint32_t key, const uint32_t hashedKey, + const Entry &bitmapEntry, const int level) const { + const int label = getLabel(hashedKey, level); + if (!exists(bitmapEntry.getBitmap(), label)) { + return INVALID_INDEX; + } + const int entryIndex = bitmapEntry.getTableIndex() + popCount(bitmapEntry.getBitmap(), label); + const Entry entry = readEntry(entryIndex); + if (entry.isBitmapEntry()) { + // Move to the next level. + return getTerminalEntryIndex(key, hashedKey, entry, level + 1); + } + if (entry.getKey() == key) { + // Terminal entry is found. + return entryIndex; + } + return INVALID_INDEX; +} + +/** + * Get Result corresponding to the key. + * + * @param key the key. + * @param hashedKey the hashed key. + * @param bitmapEntryIndex the index of bitmap entry + * @param level current level + * @return Result instance corresponding to the key. mIsValid indicates whether the key is in the + * map. + */ +const TrieMap::Result TrieMap::getInternal(const uint32_t key, const uint32_t hashedKey, + const int bitmapEntryIndex, const int level) const { + const int terminalEntryIndex = getTerminalEntryIndex(key, hashedKey, + readEntry(bitmapEntryIndex), level); + if (terminalEntryIndex == INVALID_INDEX) { + // Not found. + return Result(0, false, INVALID_INDEX); + } + const Entry terminalEntry = readEntry(terminalEntryIndex); + if (!terminalEntry.hasTerminalLink()) { + return Result(terminalEntry.getValue(), true, INVALID_INDEX); + } + const int valueEntryIndex = terminalEntry.getValueEntryIndex(); + const Entry valueEntry = readEntry(valueEntryIndex); + return Result(valueEntry.getValueOfValueEntry(), true, valueEntryIndex + 1); +} + +/** + * Put key to value mapping to the map. + * + * @param key the key. + * @param value the value + * @param hashedKey the hashed key. + * @param bitmapEntryIndex the index of bitmap entry + * @param bitmapEntry the bitmap entry + * @param level current level + * @return whether the key-value has been correctly inserted to the map or not. + */ +bool TrieMap::putInternal(const uint32_t key, const uint64_t value, const uint32_t hashedKey, + const int bitmapEntryIndex, const Entry &bitmapEntry, const int level) { + const int label = getLabel(hashedKey, level); + const uint32_t bitmap = bitmapEntry.getBitmap(); + const int mapIndex = bitmapEntry.getTableIndex(); + if (!exists(bitmap, label)) { + // Current map doesn't contain the label. + return addNewEntryByExpandingTable(key, value, mapIndex, bitmap, bitmapEntryIndex, label); + } + const int entryIndex = mapIndex + popCount(bitmap, label); + const Entry entry = readEntry(entryIndex); + if (entry.isBitmapEntry()) { + // Bitmap entry is found. Go to the next level. + return putInternal(key, value, hashedKey, entryIndex, entry, level + 1); + } + if (entry.getKey() == key) { + // Terminal entry for the key is found. Update the value. + return updateValue(entry, value, entryIndex); + } + // Conflict with the existing key. + return addNewEntryByResolvingConflict(key, value, hashedKey, entry, entryIndex, level); +} + +/** + * Resolve a conflict in the current level and add new entry. + * + * @param key the key + * @param value the value + * @param hashedKey the hashed key + * @param conflictedEntry the existing conflicted entry + * @param conflictedEntryIndex the index of existing conflicted entry + * @param level current level + * @return whether the key-value has been correctly inserted to the map or not. + */ +bool TrieMap::addNewEntryByResolvingConflict(const uint32_t key, const uint64_t value, + const uint32_t hashedKey, const Entry &conflictedEntry, const int conflictedEntryIndex, + const int level) { + const int conflictedKeyNextLabel = + getLabel(getBitShuffledKey(conflictedEntry.getKey()), level + 1); + const int nextLabel = getLabel(hashedKey, level + 1); + if (conflictedKeyNextLabel == nextLabel) { + // Conflicted again in the next level. + const int newTableIndex = allocateTable(1 /* entryCount */); + if (newTableIndex == INVALID_INDEX) { + return false; + } + if (!writeEntry(conflictedEntry, newTableIndex)) { + return false; + } + const Entry newBitmapEntry(setExist(0 /* bitmap */, nextLabel), newTableIndex); + if (!writeEntry(newBitmapEntry, conflictedEntryIndex)) { + return false; + } + return putInternal(key, value, hashedKey, conflictedEntryIndex, newBitmapEntry, level + 1); + } + // The conflict has been resolved. Create a table that contains 2 entries. + const int newTableIndex = allocateTable(2 /* entryCount */); + if (newTableIndex == INVALID_INDEX) { + return false; + } + if (nextLabel < conflictedKeyNextLabel) { + if (!writeTerminalEntry(key, value, newTableIndex)) { + return false; + } + if (!writeEntry(conflictedEntry, newTableIndex + 1)) { + return false; + } + } else { // nextLabel > conflictedKeyNextLabel + if (!writeEntry(conflictedEntry, newTableIndex)) { + return false; + } + if (!writeTerminalEntry(key, value, newTableIndex + 1)) { + return false; + } + } + const uint32_t updatedBitmap = + setExist(setExist(0 /* bitmap */, nextLabel), conflictedKeyNextLabel); + return writeEntry(Entry(updatedBitmap, newTableIndex), conflictedEntryIndex); +} + +/** + * Add new entry to the existing table. + */ +bool TrieMap::addNewEntryByExpandingTable(const uint32_t key, const uint64_t value, + const int tableIndex, const uint32_t bitmap, const int bitmapEntryIndex, const int label) { + // Current map doesn't contain the label. + const int entryCount = popCount(bitmap); + const int newTableIndex = allocateTable(entryCount + 1); + if (newTableIndex == INVALID_INDEX) { + return false; + } + const int newEntryIndexInTable = popCount(bitmap, label); + // Copy from existing table to the new table. + for (int i = 0; i < entryCount; ++i) { + if (!copyEntry(tableIndex + i, newTableIndex + i + (i >= newEntryIndexInTable ? 1 : 0))) { + return false; + } + } + // Write new terminal entry. + if (!writeTerminalEntry(key, value, newTableIndex + newEntryIndexInTable)) { + return false; + } + // Update bitmap. + if (!writeEntry(Entry(setExist(bitmap, label), newTableIndex), bitmapEntryIndex)) { + return false; + } + if (entryCount > 0) { + return freeTable(tableIndex, entryCount); + } + return true; +} + +} // namespace latinime diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/trie_map.h b/native/jni/src/suggest/policyimpl/dictionary/utils/trie_map.h new file mode 100644 index 000000000..2a9051f98 --- /dev/null +++ b/native/jni/src/suggest/policyimpl/dictionary/utils/trie_map.h @@ -0,0 +1,253 @@ +/* + * Copyright (C) 2014, The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef LATINIME_TRIE_MAP_H +#define LATINIME_TRIE_MAP_H + +#include <climits> +#include <cstdint> +#include <vector> + +#include "defines.h" +#include "suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h" + +namespace latinime { + +/** + * Trie map derived from Phil Bagwell's Hash Array Mapped Trie. + * key is int and value is uint64_t. + * This supports multiple level map. Terminal entries can have a bitmap for the next level map. + * This doesn't support root map resizing. + */ +class TrieMap { + public: + struct Result { + const uint64_t mValue; + const bool mIsValid; + const int mNextLevelBitmapEntryIndex; + + Result(const uint64_t value, const bool isValid, const int nextLevelBitmapEntryIndex) + : mValue(value), mIsValid(isValid), + mNextLevelBitmapEntryIndex(nextLevelBitmapEntryIndex) {} + }; + + static const int INVALID_INDEX; + static const uint64_t MAX_VALUE; + + TrieMap(); + void dump(const int from = 0, const int to = 0) const; + + bool isNearSizeLimit() const { + return mBuffer.isNearSizeLimit(); + } + + // Returns bitmapEntryIndex. Create the next level map if it doesn't exist. + int getNextLevelBitmapEntryIndex(const int key) { + return getNextLevelBitmapEntryIndex(key, ROOT_BITMAP_ENTRY_INDEX); + } + + int getNextLevelBitmapEntryIndex(const int key, const int bitmapEntryIndex); + + const Result getRoot(const int key) const { + return get(key, ROOT_BITMAP_ENTRY_INDEX); + } + + const Result get(const int key, const int bitmapEntryIndex) const; + + bool putRoot(const int key, const uint64_t value) { + return put(key, value, ROOT_BITMAP_ENTRY_INDEX); + } + + bool put(const int key, const uint64_t value, const int bitmapEntryIndex); + + private: + DISALLOW_COPY_AND_ASSIGN(TrieMap); + + /** + * Struct represents an entry. + * + * Entry is one of these entry types. All entries are fixed size and have 2 fields FIELD_0 and + * FIELD_1. + * 1. bitmap entry. bitmap entry contains bitmap and the link to hash table. + * FIELD_0(bitmap) FIELD_1(LINK_TO_HASH_TABLE) + * 2. terminal entry. terminal entry contains hashed key and value or terminal link. terminal + * entry have terminal link when the value is not fit to FIELD_1 or there is a next level map + * for the key. + * FIELD_0(hashed key) (FIELD_1(VALUE_FLAG VALUE) | FIELD_1(TERMINAL_LINK_FLAG TERMINAL_LINK)) + * 3. value entry. value entry represents a value. Upper order bytes are stored in FIELD_0 and + * lower order bytes are stored in FIELD_1. + * FIELD_0(value (upper order bytes)) FIELD_1(value (lower order bytes)) + */ + struct Entry { + const uint32_t mData0; + const uint32_t mData1; + + Entry(const uint32_t data0, const uint32_t data1) : mData0(data0), mData1(data1) {} + + AK_FORCE_INLINE bool isBitmapEntry() const { + return (mData1 & VALUE_FLAG) == 0 && (mData1 & TERMINAL_LINK_FLAG) == 0; + } + + AK_FORCE_INLINE bool hasTerminalLink() const { + return (mData1 & TERMINAL_LINK_FLAG) != 0; + } + + // For terminal entry. + AK_FORCE_INLINE uint32_t getKey() const { + return mData0; + } + + // For terminal entry. + AK_FORCE_INLINE uint32_t getValue() const { + return mData1 & VALUE_MASK; + } + + // For terminal entry. + AK_FORCE_INLINE uint32_t getValueEntryIndex() const { + return mData1 & TERMINAL_LINK_MASK; + } + + // For bitmap entry. + AK_FORCE_INLINE uint32_t getBitmap() const { + return mData0; + } + + // For bitmap entry. + AK_FORCE_INLINE int getTableIndex() const { + return static_cast<int>(mData1); + } + + // For value entry. + AK_FORCE_INLINE uint64_t getValueOfValueEntry() const { + return ((static_cast<uint64_t>(mData0) << (FIELD1_SIZE * CHAR_BIT)) ^ mData1); + } + }; + + BufferWithExtendableBuffer mBuffer; + + static const int FIELD0_SIZE; + static const int FIELD1_SIZE; + static const int ENTRY_SIZE; + static const uint32_t VALUE_FLAG; + static const uint32_t VALUE_MASK; + static const uint32_t TERMINAL_LINK_FLAG; + static const uint32_t TERMINAL_LINK_MASK; + static const int NUM_OF_BITS_USED_FOR_ONE_LEVEL; + static const uint32_t LABEL_MASK; + static const int MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL; + static const int ROOT_BITMAP_ENTRY_INDEX; + static const int ROOT_BITMAP_ENTRY_POS; + static const Entry EMPTY_BITMAP_ENTRY; + static const int MAX_BUFFER_SIZE; + + uint32_t getBitShuffledKey(const uint32_t key) const; + bool writeValue(const uint64_t value, const int terminalEntryIndex); + bool updateValue(const Entry &terminalEntry, const uint64_t value, + const int terminalEntryIndex); + bool freeTable(const int tableIndex, const int entryCount); + int allocateTable(const int entryCount); + int getTerminalEntryIndex(const uint32_t key, const uint32_t hashedKey, + const Entry &bitmapEntry, const int level) const; + const Result getInternal(const uint32_t key, const uint32_t hashedKey, + const int bitmapEntryIndex, const int level) const; + bool putInternal(const uint32_t key, const uint64_t value, const uint32_t hashedKey, + const int bitmapEntryIndex, const Entry &bitmapEntry, const int level); + bool addNewEntryByResolvingConflict(const uint32_t key, const uint64_t value, + const uint32_t hashedKey, const Entry &conflictedEntry, const int conflictedEntryIndex, + const int level); + bool addNewEntryByExpandingTable(const uint32_t key, const uint64_t value, + const int tableIndex, const uint32_t bitmap, const int bitmapEntryIndex, + const int label); + + AK_FORCE_INLINE const Entry readEntry(const int entryIndex) const { + return Entry(readField0(entryIndex), readField1(entryIndex)); + } + + // Returns whether an entry for the index is existing by testing if the index-th bit in the + // bitmap is set or not. + AK_FORCE_INLINE bool exists(const uint32_t bitmap, const int index) const { + return (bitmap & (1 << index)) != 0; + } + + // Set index-th bit in the bitmap. + AK_FORCE_INLINE uint32_t setExist(const uint32_t bitmap, const int index) const { + return bitmap | (1 << index); + } + + // Count set bits before index in the bitmap. + AK_FORCE_INLINE int popCount(const uint32_t bitmap, const int index) const { + return popCount(bitmap & ((1 << index) - 1)); + } + + // Count set bits in the bitmap. + AK_FORCE_INLINE int popCount(const uint32_t bitmap) const { + return __builtin_popcount(bitmap); + // int v = bitmap - ((bitmap >> 1) & 0x55555555); + // v = (v & 0x33333333) + ((v >> 2) & 0x33333333); + // return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; + } + + AK_FORCE_INLINE int getLabel(const uint32_t hashedKey, const int level) const { + return (hashedKey >> (level * NUM_OF_BITS_USED_FOR_ONE_LEVEL)) & LABEL_MASK; + } + + AK_FORCE_INLINE uint32_t readField0(const int entryIndex) const { + return mBuffer.readUint(FIELD0_SIZE, ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE); + } + + AK_FORCE_INLINE uint32_t readField1(const int entryIndex) const { + return mBuffer.readUint(FIELD1_SIZE, + ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE + FIELD0_SIZE); + } + + AK_FORCE_INLINE int readEmptyTableLink(const int entryCount) const { + return mBuffer.readUint(FIELD1_SIZE, (entryCount - 1) * FIELD1_SIZE); + } + + AK_FORCE_INLINE bool writeEmptyTableLink(const int tableIndex, const int entryCount) { + return mBuffer.writeUint(tableIndex, FIELD1_SIZE, (entryCount - 1) * FIELD1_SIZE); + } + + AK_FORCE_INLINE bool writeField0(const uint32_t data, const int entryIndex) { + return mBuffer.writeUint(data, FIELD0_SIZE, + ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE); + } + + AK_FORCE_INLINE bool writeField1(const uint32_t data, const int entryIndex) { + return mBuffer.writeUint(data, FIELD1_SIZE, + ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE + FIELD0_SIZE); + } + + AK_FORCE_INLINE bool writeEntry(const Entry &entry, const int entryIndex) { + return writeField0(entry.mData0, entryIndex) && writeField1(entry.mData1, entryIndex); + } + + AK_FORCE_INLINE bool writeTerminalEntry(const uint32_t key, const uint64_t value, + const int entryIndex) { + return writeField0(key, entryIndex) && writeValue(value, entryIndex); + } + + AK_FORCE_INLINE bool copyEntry(const int originalEntryIndex, const int newEntryIndex) { + return writeEntry(readEntry(originalEntryIndex), newEntryIndex); + } + + AK_FORCE_INLINE int getTailEntryIndex() const { + return (mBuffer.getTailPosition() - ROOT_BITMAP_ENTRY_POS) / ENTRY_SIZE; + } +}; + +} // namespace latinime +#endif /* LATINIME_TRIE_MAP_H */ diff --git a/native/jni/tests/suggest/policyimpl/dictionary/utils/trie_map_test.cpp b/native/jni/tests/suggest/policyimpl/dictionary/utils/trie_map_test.cpp new file mode 100644 index 000000000..5dd782277 --- /dev/null +++ b/native/jni/tests/suggest/policyimpl/dictionary/utils/trie_map_test.cpp @@ -0,0 +1,169 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "suggest/policyimpl/dictionary/utils/trie_map.h" + +#include <gtest/gtest.h> + +#include <algorithm> +#include <cstdlib> +#include <functional> +#include <map> +#include <random> +#include <unordered_map> + +namespace latinime { +namespace { + +TEST(TrieMapTest, TestSetAndGet) { + TrieMap trieMap; + trieMap.putRoot(10, 10); + EXPECT_EQ(10ull, trieMap.getRoot(10).mValue); + trieMap.putRoot(0x10A, 10); + EXPECT_EQ(10ull, trieMap.getRoot(10).mValue); + EXPECT_EQ(10ull, trieMap.getRoot(0x10A).mValue); + trieMap.putRoot(10, 1000); + EXPECT_EQ(1000ull, trieMap.getRoot(10).mValue); + trieMap.putRoot(11, 1000); + EXPECT_EQ(1000ull, trieMap.getRoot(11).mValue); + const int next = trieMap.getNextLevelBitmapEntryIndex(10); + trieMap.put(9, 9, next); + EXPECT_EQ(9ull, trieMap.get(9, next).mValue); + EXPECT_FALSE(trieMap.get(11, next).mIsValid); + trieMap.putRoot(0, 0xFFFFFFFFFull); + EXPECT_EQ(0xFFFFFFFFFull, trieMap.getRoot(0).mValue); +} + +TEST(TrieMapTest, TestSetAndGetLarge) { + static const int ELEMENT_COUNT = 200000; + TrieMap trieMap; + for (int i = 0; i < ELEMENT_COUNT; ++i) { + EXPECT_TRUE(trieMap.putRoot(i, i)); + } + for (int i = 0; i < ELEMENT_COUNT; ++i) { + EXPECT_EQ(trieMap.getRoot(i).mValue, static_cast<uint64_t>(i)); + } +} + +TEST(TrieMapTest, TestRandSetAndGetLarge) { + static const int ELEMENT_COUNT = 100000; + TrieMap trieMap; + std::unordered_map<int, uint64_t> testKeyValuePairs; + + // Use the uniform integer distribution [S_INT_MIN, S_INT_MAX]. + std::uniform_int_distribution<int> keyDistribution(S_INT_MIN, S_INT_MAX); + auto keyRandomNumberGenerator = std::bind(keyDistribution, std::mt19937()); + + // Use the uniform distribution [0, TrieMap::MAX_VALUE]. + std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE); + auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937()); + + for (int i = 0; i < ELEMENT_COUNT; ++i) { + const int key = keyRandomNumberGenerator(); + const uint64_t value = valueRandomNumberGenerator(); + EXPECT_TRUE(trieMap.putRoot(key, value)) << key << " " << value; + testKeyValuePairs[key] = value; + } + for (const auto &v : testKeyValuePairs) { + EXPECT_EQ(trieMap.getRoot(v.first).mValue, v.second); + } +} + +TEST(TrieMapTest, TestMultiLevel) { + static const int FIRST_LEVEL_ENTRY_COUNT = 10000; + static const int SECOND_LEVEL_ENTRY_COUNT = 20000; + static const int THIRD_LEVEL_ENTRY_COUNT = 40000; + + TrieMap trieMap; + std::vector<int> firstLevelKeys; + std::map<int, uint64_t> firstLevelEntries; + std::vector<std::pair<int, int>> secondLevelKeys; + std::map<int, std::map<int, uint64_t>> twoLevelMap; + std::map<int, std::map<int, std::map<int, uint64_t>>> threeLevelMap; + + // Use the uniform integer distribution [0, S_INT_MAX]. + std::uniform_int_distribution<int> distribution(0, S_INT_MAX); + auto keyRandomNumberGenerator = std::bind(distribution, std::mt19937()); + auto randomNumberGeneratorForKeySelection = std::bind(distribution, std::mt19937()); + + // Use the uniform distribution [0, TrieMap::MAX_VALUE]. + std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE); + auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937()); + + for (int i = 0; i < FIRST_LEVEL_ENTRY_COUNT; ++i) { + const int key = keyRandomNumberGenerator(); + const uint64_t value = valueRandomNumberGenerator(); + EXPECT_TRUE(trieMap.putRoot(key, value)); + firstLevelKeys.push_back(key); + firstLevelEntries[key] = value; + } + + for (int i = 0; i < SECOND_LEVEL_ENTRY_COUNT; ++i) { + const int key = keyRandomNumberGenerator(); + const uint64_t value = valueRandomNumberGenerator(); + const int firstLevelKey = + firstLevelKeys[randomNumberGeneratorForKeySelection() % FIRST_LEVEL_ENTRY_COUNT]; + const int nextLevelBitmapEntryIndex = trieMap.getNextLevelBitmapEntryIndex(firstLevelKey); + EXPECT_NE(TrieMap::INVALID_INDEX, nextLevelBitmapEntryIndex); + EXPECT_TRUE(trieMap.put(key, value, nextLevelBitmapEntryIndex)); + secondLevelKeys.push_back(std::make_pair(firstLevelKey, key)); + twoLevelMap[firstLevelKey][key] = value; + } + + for (int i = 0; i < THIRD_LEVEL_ENTRY_COUNT; ++i) { + const int key = keyRandomNumberGenerator(); + const uint64_t value = valueRandomNumberGenerator(); + const std::pair<int, int> secondLevelKey = + secondLevelKeys[randomNumberGeneratorForKeySelection() % SECOND_LEVEL_ENTRY_COUNT]; + const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(secondLevelKey.first); + EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel); + const int thirdLevel = trieMap.getNextLevelBitmapEntryIndex( + secondLevelKey.second, secondLevel); + EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel); + EXPECT_TRUE(trieMap.put(key, value, thirdLevel)); + threeLevelMap[secondLevelKey.first][secondLevelKey.second][key] = value; + } + + for (const auto &firstLevelEntry : firstLevelEntries) { + EXPECT_EQ(firstLevelEntry.second, trieMap.getRoot(firstLevelEntry.first).mValue); + } + + for (const auto &firstLevelEntry : twoLevelMap) { + const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first); + EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel); + for (const auto &secondLevelEntry : firstLevelEntry.second) { + EXPECT_EQ(secondLevelEntry.second, + trieMap.get(secondLevelEntry.first, secondLevel).mValue); + } + } + + for (const auto &firstLevelEntry : threeLevelMap) { + const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first); + EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel); + for (const auto &secondLevelEntry : firstLevelEntry.second) { + const int thirdLevel = + trieMap.getNextLevelBitmapEntryIndex(secondLevelEntry.first, secondLevel); + EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel); + for (const auto &thirdLevelEntry : secondLevelEntry.second) { + EXPECT_EQ(thirdLevelEntry.second, + trieMap.get(thirdLevelEntry.first, thirdLevel).mValue); + } + } + } +} + +} // namespace +} // namespace latinime |