C Create Secure Dictionary of Dictionary Storage Structure
- 2021-11-14 06:45:34
- OfStack
The storage structure of the stack (Stack) was introduced above, and another storage structure dictionary (Dictionary) was introduced next. Every element in the dictionary (Dictionary) is a key-value pair (consisting of two elements: key and value). The key must be 1-only, but the value does not need to be 1-only. The key and value can be of any type. A dictionary (Dictionary) is a list that is commonly used to find and sort.
Next, look at the underlying implementation code of some methods and classes of Dictionary under 1:
1. Add: Adds the specified key and value to the dictionary.
public void Add(TKey key, TValue value) {
Insert(key, value, true);
}
private void Insert(TKey key, TValue value, bool add) {
if( key == null ) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets == null) Initialize(0);
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int targetBucket = hashCode % buckets.Length;
#if FEATURE_RANDOMIZED_STRING_HASHING
int collisionCount = 0;
#endif
for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
if (add) {
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
entries[i].value = value;
version++;
return;
}
#if FEATURE_RANDOMIZED_STRING_HASHING
collisionCount++;
#endif
}
int index;
if (freeCount > 0) {
index = freeList;
freeList = entries[index].next;
freeCount--;
}
else {
if (count == entries.Length)
{
Resize();
targetBucket = hashCode % buckets.Length;
}
index = count;
count++;
}
entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;
version++;
#if FEATURE_RANDOMIZED_STRING_HASHING
if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer))
{
comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
Resize(entries.Length, true);
}
#endif
}
2. Clear (): From Dictionary < TKey, TValue > Removes all keys and values from the.
public void Clear() {
if (count > 0) {
for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
Array.Clear(entries, 0, count);
freeList = -1;
count = 0;
freeCount = 0;
version++;
}
}
3. Remove (): From Dictionary < TKey, TValue > Removes the value of the specified key from the.
public bool Remove(TKey key) {
if(key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int bucket = hashCode % buckets.Length;
int last = -1;
for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
if (last < 0) {
buckets[bucket] = entries[i].next;
}
else {
entries[last].next = entries[i].next;
}
entries[i].hashCode = -1;
entries[i].next = freeList;
entries[i].key = default(TKey);
entries[i].value = default(TValue);
freeList = i;
freeCount++;
version++;
return true;
}
}
}
return false;
}
4. GetEnumerator (): Returns iterative access to Dictionary < TKey, TValue > Gets or sets the enumerator of.
public Enumerator GetEnumerator() {
return new Enumerator(this, Enumerator.KeyValuePair);
}
[Serializable]
public struct Enumerator: IEnumerator<KeyValuePair<TKey,TValue>>,
IDictionaryEnumerator
{
private Dictionary<TKey,TValue> dictionary;
private int version;
private int index;
private KeyValuePair<TKey,TValue> current;
private int getEnumeratorRetType; // What should Enumerator.Current return?
internal const int DictEntry = 1;
internal const int KeyValuePair = 2;
internal Enumerator(Dictionary<TKey,TValue> dictionary, int getEnumeratorRetType) {
this.dictionary = dictionary;
version = dictionary.version;
index = 0;
this.getEnumeratorRetType = getEnumeratorRetType;
current = new KeyValuePair<TKey, TValue>();
}
public bool MoveNext() {
if (version != dictionary.version) {
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
}
// Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends.
// dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue
while ((uint)index < (uint)dictionary.count) {
if (dictionary.entries[index].hashCode >= 0) {
current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value);
index++;
return true;
}
index++;
}
index = dictionary.count + 1;
current = new KeyValuePair<TKey, TValue>();
return false;
}
public KeyValuePair<TKey,TValue> Current {
get { return current; }
}
public void Dispose() {
}
object IEnumerator.Current {
get {
if( index == 0 || (index == dictionary.count + 1)) {
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
}
if (getEnumeratorRetType == DictEntry) {
return new System.Collections.DictionaryEntry(current.Key, current.Value);
} else {
return new KeyValuePair<TKey, TValue>(current.Key, current.Value);
}
}
}
void IEnumerator.Reset() {
if (version != dictionary.version) {
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
}
index = 0;
current = new KeyValuePair<TKey, TValue>();
}
DictionaryEntry IDictionaryEnumerator.Entry {
get {
if( index == 0 || (index == dictionary.count + 1)) {
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
}
return new DictionaryEntry(current.Key, current.Value);
}
}
object IDictionaryEnumerator.Key {
get {
if( index == 0 || (index == dictionary.count + 1)) {
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
}
return current.Key;
}
}
object IDictionaryEnumerator.Value {
get {
if( index == 0 || (index == dictionary.count + 1)) {
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
}
return current.Value;
}
}
}
The above is mainly on the dictionary (Dictionary) of a number of common methods for a simple description. Next, we mainly explain how to create a secure dictionary (Dictionary) storage structure. The part about thread safety will not be repeated here.
/// <summary>
/// Thread-safe general dictionary
/// </summary>
/// <typeparam name="TKey"></typeparam>
/// <typeparam name="TValue"></typeparam>
public class TDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
/// <summary>
/// Lock dictionary
/// </summary>
private readonly ReaderWriterLockSlim _lockDictionary = new ReaderWriterLockSlim();
/// <summary>
/// Basic dictionary
/// </summary>
private readonly Dictionary<TKey, TValue> _mDictionary;
// Variables
/// <summary>
/// Initialize a dictionary object
/// </summary>
public TDictionary()
{
_mDictionary = new Dictionary<TKey, TValue>();
}
/// <summary>
/// Initialize a dictionary object
/// </summary>
/// <param name="capacity"> Initial capacity of dictionary </param>
public TDictionary(int capacity)
{
_mDictionary = new Dictionary<TKey, TValue>(capacity);
}
/// <summary>
/// Initialize a dictionary object
/// </summary>
/// <param name="comparer"> The comparator is used when comparing keys </param>
public TDictionary(IEqualityComparer<TKey> comparer)
{
_mDictionary = new Dictionary<TKey, TValue>(comparer);
}
/// <summary>
/// Initialize a dictionary object
/// </summary>
/// <param name="dictionary"> Its keys and values are copied to the dictionary of this object </param>
public TDictionary(IDictionary<TKey, TValue> dictionary)
{
_mDictionary = new Dictionary<TKey, TValue>(dictionary);
}
/// <summary>
/// Initialize a dictionary object
/// </summary>
/// <param name="capacity"> Initial capacity of dictionary </param>
/// <param name="comparer"> The comparator is used when comparing keys </param>
public TDictionary(int capacity, IEqualityComparer<TKey> comparer)
{
_mDictionary = new Dictionary<TKey, TValue>(capacity, comparer);
}
/// <summary>
/// Initialize a dictionary object
/// </summary>
/// <param name="dictionary"> Its keys and values are copied to the dictionary of this object </param>
/// <param name="comparer"> The comparator is used when comparing keys </param>
public TDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer)
{
_mDictionary = new Dictionary<TKey, TValue>(dictionary, comparer);
}
public TValue GetValueAddIfNotExist(TKey key, Func<TValue> func)
{
return _lockDictionary.PerformUsingUpgradeableReadLock(() =>
{
TValue rVal;
// If we have a value, get it and exit
if (_mDictionary.TryGetValue(key, out rVal))
return rVal;
// Not found, so do the value of the function
_lockDictionary.PerformUsingWriteLock(() =>
{
rVal = func.Invoke();
// Add to Dictionary
_mDictionary.Add(key, rVal);
return rVal;
});
return rVal;
});
}
/// <summary>
/// Add an item to the dictionary
/// </summary>
/// <param name="key"> Key to Adding </param>
/// <param name="value"> Value to add </param>
public void Add(TKey key, TValue value)
{
_lockDictionary.PerformUsingWriteLock(() => _mDictionary.Add(key, value));
}
/// <summary>
/// Add an item to the dictionary
/// </summary>
/// <param name="item"> The key to add / Value </param>
public void Add(KeyValuePair<TKey, TValue> item)
{
var key = item.Key;
var value = item.Value;
_lockDictionary.PerformUsingWriteLock(() => _mDictionary.Add(key, value));
}
/// <summary>
/// If the value does not exist, the value is added. If the value has been added; Otherwise true
/// </summary>
/// <param name="key"> Check the key, add </param>
/// <param name="value"> If the key does not exist, the added value </param>
public bool AddIfNotExists(TKey key, TValue value)
{
bool rVal = false;
_lockDictionary.PerformUsingWriteLock(() =>
{
// If it does not exist, add it
if (!_mDictionary.ContainsKey(key))
{
// Add the value and set the flag
_mDictionary.Add(key, value);
rVal = true;
}
});
return rVal;
}
/// <summary>
/// If the key does not exist, add a list of values.
/// </summary>
/// <param name="keys"> The key to check, add </param>
/// <param name="defaultValue"> If the key does not exist, the added value </param>
public void AddIfNotExists(IEnumerable<TKey> keys, TValue defaultValue)
{
_lockDictionary.PerformUsingWriteLock(() =>
{
foreach (TKey key in keys)
{
// If it does not exist, add it
if (!_mDictionary.ContainsKey(key))
_mDictionary.Add(key, defaultValue);
}
});
}
public bool AddIfNotExistsElseUpdate(TKey key, TValue value)
{
var rVal = false;
_lockDictionary.PerformUsingWriteLock(() =>
{
// If it does not exist, add it
if (!_mDictionary.ContainsKey(key))
{
// Add the value and set the flag
_mDictionary.Add(key, value);
rVal = true;
}
else
_mDictionary[key] = value;
});
return rVal;
}
/// <summary>
/// If the key exists, the value of the key is updated.
/// </summary>
/// <param name="key"></param>
/// <param name="newValue"></param>
public bool UpdateValueIfKeyExists(TKey key, TValue newValue)
{
bool rVal = false;
_lockDictionary.PerformUsingWriteLock(() =>
{
// If we have the key, then update it
if (!_mDictionary.ContainsKey(key)) return;
_mDictionary[key] = newValue;
rVal = true;
});
return rVal;
}
/// <summary>
/// Returns if the key-value pair exists in the dictionary true
/// </summary>
/// <param name="item"> Key-value pair lookup </param>
public bool Contains(KeyValuePair<TKey, TValue> item)
{
return _lockDictionary.PerformUsingReadLock(() => ((_mDictionary.ContainsKey(item.Key)) &&
(_mDictionary.ContainsValue(item.Value))));
}
public bool ContainsKey(TKey key)
{
return _lockDictionary.PerformUsingReadLock(() => _mDictionary.ContainsKey(key));
}
/// <summary>
/// If the dictionary contains this value, returns true
/// </summary>
/// <param name="value"> Values found </param>
public bool ContainsValue(TValue value)
{
return _lockDictionary.PerformUsingReadLock(() => _mDictionary.ContainsValue(value));
}
public ICollection<TKey> Keys
{
get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary.Keys); }
}
public bool Remove(TKey key)
{
return _lockDictionary.PerformUsingWriteLock(() => (!_mDictionary.ContainsKey(key)) || _mDictionary.Remove(key));
}
public bool Remove(KeyValuePair<TKey, TValue> item)
{
return _lockDictionary.PerformUsingWriteLock(() =>
{
// Skip if the key does not exist
TValue tempVal;
if (!_mDictionary.TryGetValue(item.Key, out tempVal))
return false;
// If the values do not match, skip
return tempVal.Equals(item.Value) && _mDictionary.Remove(item.Key);
});
}
/// <summary>
/// Delete items that match patterns from the dictionary
/// </summary>
/// <param name="predKey"> Optional expression based on key </param>
/// <param name="predValue"> Value-based option expression </param>
public bool Remove(Predicate<TKey> predKey, Predicate<TValue> predValue)
{
return _lockDictionary.PerformUsingWriteLock(() =>
{
// If there is no key to exit
if (_mDictionary.Keys.Count == 0)
return true;
// Save the list of items to delete
var deleteList = new List<TKey>();
// Process key
foreach (var key in _mDictionary.Keys)
{
var isMatch = false;
if (predKey != null)
isMatch = (predKey(key));
// If the values of this item match, add it
if ((!isMatch) && (predValue != null) && (predValue(_mDictionary[key])))
isMatch = true;
// If we have a match, add it to the list
if (isMatch)
deleteList.Add(key);
}
// Delete all items from the list
foreach (var item in deleteList)
_mDictionary.Remove(item);
return true;
});
}
public bool TryGetValue(TKey key, out TValue value)
{
_lockDictionary.EnterReadLock();
try
{
return _mDictionary.TryGetValue(key, out value);
}
finally
{
_lockDictionary.ExitReadLock();
}
}
public ICollection<TValue> Values
{
get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary.Values); }
}
public TValue this[TKey key]
{
get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary[key]); }
set { _lockDictionary.PerformUsingWriteLock(() => _mDictionary[key] = value); }
}
/// <summary>
/// Clear the dictionary
/// </summary>
public void Clear()
{
_lockDictionary.PerformUsingWriteLock(() => _mDictionary.Clear());
}
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
_lockDictionary.PerformUsingReadLock(() => _mDictionary.ToArray().CopyTo(array, arrayIndex));
}
/// <summary>
/// Returns the number of items in the dictionary
/// </summary>
public int Count
{
get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary.Count); }
}
public bool IsReadOnly
{
get { return false; }
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
Dictionary<TKey, TValue> localDict = null;
_lockDictionary.PerformUsingReadLock(() => localDict = new Dictionary<TKey, TValue>(_mDictionary));
return ((IEnumerable<KeyValuePair<TKey, TValue>>)localDict).GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
Dictionary<TKey, TValue> localDict = null;
_lockDictionary.PerformUsingReadLock(() => localDict = new Dictionary<TKey, TValue>(_mDictionary));
return localDict.GetEnumerator();
}
}
In the above methods of creating a safe dictionary, we mainly rewrite some methods and attributes of the dictionary, and set locks for some methods.