Ок, теперь другая задачка на потокобезопасную очередь...
* Очередь элементов состоящая из строк.
* Есть произвольное количество поставщиков и потребителей.
* Потребители достают строки из очереди по одному и обрабатывают.
* В редких случаях обработка может закончится неудачно — такая строка ставится опять в начало очереди.
* Строки в очереди должны быть уникальны. У поставщиков в буфере могут быть строки, которые уже есть в очереди или находятся в обработке у потребителя, такие строки должны игнорироваться и ни при каких обстоятельствах в очередь не попадать.
Идеи?
Здравствуйте, Аноним, Вы писали:
А>Ок, теперь другая задачка на потокобезопасную очередь... А>* Очередь элементов состоящая из строк. А>* Есть произвольное количество поставщиков и потребителей. А>* Потребители достают строки из очереди по одному и обрабатывают.
А>* В редких случаях обработка может закончится неудачно — такая строка ставится опять в начало очереди.
В момент между взятием строки на обработку и неудачей обработки этой строки другой поставщик может взять следующую строку или нет?
А>* Строки в очереди должны быть уникальны. У поставщиков в буфере могут быть строки, которые уже есть в очереди или находятся в обработке у потребителя, такие строки должны игнорироваться и ни при каких обстоятельствах в очередь не попадать.
Для хранения строк используем не очередь, а Dictionary. Элемент забираем через dictionary.Keys.First() с последующим удалением этого элемента из словаря. Добавляемые строки проверяем на наличие в словаре, если они уже есть, то игнорируем.
Re[2]: Thread-Safe Queue 2
От:
Аноним
Дата:
03.07.09 09:49
Оценка:
Здравствуйте, Undying, Вы писали:
U>В момент между взятием строки на обработку и неудачей обработки этой строки другой поставщик может взять следующую строку или нет?
Да, конечно.
U>Для хранения строк используем не очередь, а Dictionary. Элемент забираем через dictionary.Keys.First() с последующим удалением этого элемента из словаря. Добавляемые строки проверяем на наличие в словаре, если они уже есть, то игнорируем.
1. Как это лочить? Для очереди хорошо работают две блокировки, на хвост и начало, что обеспечивает достаточно хорошее распараллеливание, а тут как, учитывая, что нужно еще проверять на вхождение?.
Здравствуйте, <Аноним>, Вы писали:
U>>Для хранения строк используем не очередь, а Dictionary. Элемент забираем через dictionary.Keys.First() с последующим удалением этого элемента из словаря. Добавляемые строки проверяем на наличие в словаре, если они уже есть, то игнорируем. А>1. Как это лочить? Для очереди хорошо работают две блокировки, на хвост и начало, что обеспечивает достаточно хорошее распараллеливание, а тут как, учитывая, что нужно еще проверять на вхождение?.
Вроде очевидно, что надо использовать lock {} . Я из исходного поста не понимаю, что этому очевидному решению может мешать.
Здравствуйте, Аноним, Вы писали:
U>>В момент между взятием строки на обработку и неудачей обработки этой строки другой поставщик может взять следующую строку или нет? А>Да, конечно.
Тогда в словаре для каждой строки храним флажок. Забирая элемент из очереди этот флажок ставим в true, очередному потребителю отдаем первый элемент в словаре с флажком в false. При успешном завершении обработки строки вызываем Commit и удаляем строку из словаря, иначе вызываем Rollback и сбрасываем флажок у этой строки.
U>>Для хранения строк используем не очередь, а Dictionary. Элемент забираем через dictionary.Keys.First() с последующим удалением этого элемента из словаря. Добавляемые строки проверяем на наличие в словаре, если они уже есть, то игнорируем. А>1. Как это лочить? Для очереди хорошо работают две блокировки, на хвост и начало, что обеспечивает достаточно хорошее распараллеливание,
Как выглядят раздельные блокировки на хвост и начало очереди?
А>а тут как, учитывая, что нужно еще проверять на вхождение?.
Здравствуйте, Undying, Вы писали:
U>Тогда в словаре для каждой строки храним флажок. Забирая элемент из очереди этот флажок ставим в true, очередному потребителю отдаем первый элемент в словаре с флажком в false.
Первый элемент — это если откуда считать и как?
U> При успешном завершении обработки строки вызываем Commit и удаляем строку из словаря, иначе вызываем Rollback и сбрасываем флажок у этой строки.
Тогда этот элемент попадет не в конец очереди, а в начало, то есть будет обработан первым же потребителем. А тут критично, чтобы он был обработан в конце, после всех элементов, которые еще не были ни разу обработаны на данный момент.
U>Как выглядят раздельные блокировки на хвост и начало очереди? http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html http://www.ddj.com/cpp/211601363?pgno=2
U>Думаю, никак. Словарь надо лочить целиком.
Нет идей, как этого избежать?
Здравствуйте, Аноним, Вы писали:
U>>Тогда в словаре для каждой строки храним флажок. Забирая элемент из очереди этот флажок ставим в true, очередному потребителю отдаем первый элемент в словаре с флажком в false. А>Первый элемент — это если откуда считать и как?
Бежим по dictionary.Keys foreach'ем, элементы там будут как раз в порядке добавления.
U>> При успешном завершении обработки строки вызываем Commit и удаляем строку из словаря, иначе вызываем Rollback и сбрасываем флажок у этой строки. А>Тогда этот элемент попадет не в конец очереди, а в начало, то есть будет обработан первым же потребителем. А тут критично, чтобы он был обработан в конце, после всех элементов, которые еще не были ни разу обработаны на данный момент.
Не понял почему этот код является потокобезопасным?
dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
lock(&Q->H_lock) // Acquire H_lock in order to access Head
node = Q->Head // Read Head
new_head = node->next // Read next pointer
if new_head == NULL // Is queue empty?
unlock(&Q->H_lock) // Release H_lock before return
return FALSE // Queue was empty
endif
*pvalue = new_head->value // Queue not empty. Read value before release
Q->Head = new_head // Swing Head to next node
unlock(&Q->H_lock) // Release H_lock
free(node) // Free node
return} TRUE // Queue was not empty, dequeue succeeded
Вроде как если у нас в очереди был один элемент и между выделенными строками произошел вызов enqueue, то произойдет рассинхронизации — голова будет равна null, а хвост добавленному значению.
U>>Думаю, никак. Словарь надо лочить целиком. А>Нет идей, как этого избежать?
Учитывая, что нужно игнорировать дублирующиеся строки думаю избежать нельзя никак. А обработка строк предполагается настолько быстрой, что лок может стать проблемой для производительности?
Здравствуйте, Undying, Вы писали:
U>Не понял почему этот код является потокобезопасным?
U>
U> dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
U> lock(&Q->H_lock) // Acquire H_lock in order to access Head
U> node = Q->Head // Read Head
U> new_head = node->next // Read next pointer
U> if new_head == NULL // Is queue empty?
U> unlock(&Q->H_lock) // Release H_lock before return
U> return FALSE // Queue was empty
U> endif
U> *pvalue = new_head->value // Queue not empty. Read value before release
U> Q->Head = new_head // Swing Head to next node
U> unlock(&Q->H_lock) // Release H_lock
U> free(node) // Free node
U> return} TRUE // Queue was not empty, dequeue succeeded
U>
U>Вроде как если у нас в очереди был один элемент и между выделенными строками произошел вызов enqueue, то произойдет рассинхронизации — голова будет равна null, а хвост добавленному значению.
Голова (Head) же не может быть равна null?
initialize(Q: pointer to queue_t)
node = new_node() // Allocate a free node
node->next = NULL // Make it the only node in the linked list
Q->Head = Q->Tail = node // Both Head and Tail point to it
Q->H_lock = Q->T_lock = FREE // Locks are initially free
Я бы создал массив Хэш таблиц с размером например 13.
Индекс вычислял бы как хэш строки % 13
Лочился бы на нее. При всатвке в очередь проверял бы методом
uint NavigateOrInsertDefault(uint HashCode,K Key,out bool exists) используя полученный хэш.
При чтении удалял. Так можно довести вероятнось блокировки до 1/13, и нет потерь на повторный поиск при отсутствии
ключа
Пример хэш таблицы. Можно убрать из не валуе и убрать лишние методы
using System;
using System.Collections.Generic;
namespace RSDN.HashTable
{
using Generic = System.Collections.Generic;
/// <summary>
/// Summary description for Class1.
/// </summary>public struct HashItem<K,V>
{
internal bool Used;
internal uint HashCode;
internal K key;
public V Value;
internal uint Next;
}
public class HashConst
{
public static uint mdk=3;
public static uint ПростоеЧисло(uint newSize)
{
uint i;
bool Find=true;
uint Result=newSize | 1;
while (true)
{
i=3;
while (i<(uint)Math.Sqrt(Result))
{
if ((Result % i)== 0 )
{
Find=false;
break;
}
else i+=2;
}
if (Find)
return Result;
else
{
Find=true;
Result+=2;
}
}
}
}
public class HashTable<K,V>
{
public uint Count,Size,MaxDublicate, Dublicate,FirstDeleted;
public HashItem<K,V>[] Buckets;
private Generic.IEqualityComparer<K> Comparer;
K EmptyKey;
V EmptyValue;
public HashTable(Generic.IEqualityComparer<K> comparer)
: this(5, comparer)
{
}
public HashTable(uint newSize, Generic.IEqualityComparer<K> comparer)
{
if (newSize<=5)
Size=5;
else
Size=HashConst.ПростоеЧисло(newSize);
Count=0;
Dublicate=0;
MaxDublicate=Size/HashConst.mdk;
Buckets = new HashItem<K,V>[Size+MaxDublicate];
this.Comparer=comparer;
this.EmptyKey=Buckets[0].key;
this.EmptyValue=Buckets[0].Value;
}
public uint Add(K Key, V Value)
{uint HashCode=(uint) this.Comparer.GetHashCode(Key);
return Add(HashCode,Key,Value);
}
public uint Add(uint HashCode,K Key, V Value)
{
uint Hash= ((uint)HashCode) % Size;
if (Buckets[Hash].Used)
{
if (Dublicate == MaxDublicate)
{
ReHash();
return Add(HashCode,Key,Value);
}
uint NewPos;
if (FirstDeleted == 0)
NewPos=Size+Dublicate;
else
{
NewPos=FirstDeleted;
FirstDeleted=Buckets[NewPos].Next;
}
Buckets[NewPos].HashCode=HashCode;
Buckets[NewPos].key = Key;
Buckets[NewPos].Value= Value;
Buckets[NewPos].Next = Buckets[Hash].Next;
Buckets[NewPos].Used=true;
Buckets[Hash].Next= NewPos;
Dublicate++; Count++;
return NewPos;
}
else
{
Count++;
Buckets[Hash].HashCode=HashCode;
Buckets[Hash].key = Key;
Buckets[Hash].Value= Value;
Buckets[Hash].Used=true;
Buckets[Hash].Next = 0;
return Hash;
}
}
public void ReHash()
{
HashItem<K,V>[] TempBuckets;
uint Hash;
uint NewPos;
Size=HashConst.ПростоеЧисло(Size*2);
MaxDublicate=Size / HashConst.mdk;
TempBuckets=Buckets;
Buckets = new HashItem<K,V>[Size + MaxDublicate];
HashItem<K,V> Item;
Dublicate=0;
FirstDeleted=0;
for (int i=0; i<TempBuckets.Length; i++)
{
Item=TempBuckets[i];
if (Item.Used)
{
Hash= (uint)Item.HashCode % Size;
if (Buckets[Hash].Used)
{
NewPos=Size+Dublicate;
Dublicate++;
Item.Next=Buckets[Hash].Next;
Buckets[Hash].Next=NewPos;
Buckets[NewPos]=Item;
if (Dublicate == MaxDublicate )
ReHash();
}
else
{
Item.Next=0;
Buckets[Hash]=Item;
}
}
}
}
public bool KeyExists(K Key,out uint NewPos)
{uint HashCode=(uint) this.Comparer.GetHashCode(Key);
return KeyExists(HashCode,Key,out NewPos);
}
public bool KeyExists(uint HashCode,K Key,out uint NewPos)
{
NewPos = (uint) HashCode % Size;
if (Buckets[NewPos].Used)
do
{
if ((Buckets[NewPos].HashCode==HashCode) && (Comparer.Equals(Buckets[NewPos].key,Key)))
return true;
else
NewPos= Buckets[NewPos].Next;
} while (NewPos != 0);
return false;
}
public void RestructDubleBuckets()
{
int I;
uint j;
HashItem<K,V> NewItem;
uint num;
HashItem<K,V>[] TempDubleBuckets;
TempDubleBuckets = new HashItem<K,V>[MaxDublicate];
num=0;
for (I=((int)Size)-1; I>=0; I--)
{
if (Buckets[I].Used)
{
j=Buckets[I].Next;
if (j>0)
{
Buckets[I].Next=Size+num;
do
{
NewItem=Buckets[j];
j=NewItem.Next;
if (j>0)
NewItem.Next=Size+num+1;
TempDubleBuckets[num]=NewItem;
num++;
} while( j>0);
}
}
}
Array.Copy(TempDubleBuckets, 0, Buckets, Size, MaxDublicate);
}
public void RemoveKey(K Key)
{ uint HashCode=(uint) Comparer.GetHashCode(Key);
RemoveKey(HashCode, Key);
}
public void RemoveKey(uint HashCode,K Key)
{
uint Hash = (uint) HashCode % Size;
uint Pred=Hash;
if (Buckets[Hash].Used)
do
{
if ((Buckets[Hash].HashCode==HashCode) && (Comparer.Equals(Buckets[Hash].key,Key)))
{
Dublicate--;
if (Pred==Hash)
{
if (Buckets[Hash].Next>0)
{
uint di=Buckets[Hash].Next;
Buckets[Hash]=Buckets[di];
Buckets[di].Next=FirstDeleted;
Buckets[di].Used=false;
Buckets[di].Value=EmptyValue;
Buckets[di].key = EmptyKey;
FirstDeleted=di;
}
else
{
Buckets[Hash].Used=false;
Buckets[Hash].Value = EmptyValue;
Buckets[Hash].key = EmptyKey;
}
return;
}
else
{
Buckets[Pred].Next=Buckets[Hash].Next;
Buckets[Hash].Next=FirstDeleted;
Buckets[Hash].Used=false;
Buckets[Hash].Value = EmptyValue;
Buckets[Hash].key = EmptyKey;
FirstDeleted=Hash;
}
return;
}
else
{ Pred=Hash;
Hash= Buckets[Hash].Next;
}
} while (Hash != 0);
}
private bool Navigate(ref uint Pos, K Key)
{
uint HashCode = (uint) Comparer.GetHashCode(Key);
return Navigate(ref Pos,HashCode,Key);
}
private bool Navigate(ref uint Pos, uint HashCode, K Key)
{
do
{
if ((Buckets[Pos].HashCode==HashCode) && (Comparer.Equals(Buckets[Pos].key,Key)))
return true;
else
Pos= Buckets[Pos].Next;
} while (Pos != 0);
return false;
}
public uint NavigateOrInsertDefault(K Key, out bool exists)
{
uint HashCode = (uint) Comparer.GetHashCode(Key);
return NavigateOrInsertDefault(HashCode, Key, out exists);
}
public uint NavigateOrInsertDefault(uint HashCode,K Key,out bool exists)
{
exists = false;
uint Hash= ((uint)HashCode) % Size;
if (Buckets[Hash].Used)
{
uint NewPos=Hash;
do
{
if ((Buckets[NewPos].HashCode == HashCode) && (Comparer.Equals(Buckets[NewPos].key, Key)))
{
exists = true;
return NewPos;
}
else
NewPos = Buckets[NewPos].Next;
} while (NewPos != 0);
if (Dublicate == MaxDublicate)
{
ReHash();
return Add(HashCode, Key, this.EmptyValue);
}
if (FirstDeleted == 0)
NewPos=Size+Dublicate;
else
{
NewPos=FirstDeleted;
FirstDeleted=Buckets[NewPos].Next;
}
Buckets[NewPos].HashCode = HashCode;
Buckets[NewPos].key = Key;
Buckets[NewPos].Next = Buckets[Hash].Next;
Buckets[NewPos].Used=true;
Buckets[Hash].Next= NewPos;
Dublicate++; Count++;
exists=false;
return NewPos;
}
else
{
Count++;
Buckets[Hash].HashCode = HashCode;
Buckets[Hash].key = Key;
Buckets[Hash].Used=true;
Buckets[Hash].Next = 0;
exists= false;
return Hash;
}
}
public V this[K key]
{
get {
uint HashCode = (uint)this.Comparer.GetHashCode(key);
uint NewPos= ((uint)HashCode) % Size;
// if (!this.Navigate(ref NewPos,HashCode,key))
// throw new ArgumentException("Key not present in Dictionary.");
// return this.Buckets[NewPos].Value;if (!Buckets[NewPos].Used)
throw new ArgumentException("Key not present in Dictionary.");
do
{
if ((Buckets[NewPos].HashCode == HashCode) && (Comparer.Equals(Buckets[NewPos].key, key)))
return Buckets[NewPos].Value;
else
NewPos = Buckets[NewPos].Next;
} while (NewPos != 0);
throw new ArgumentException("Key not present in Dictionary.");
}
set
{
uint HashCode = (uint)this.Comparer.GetHashCode(key);
uint Hash = ((uint)HashCode) % Size;
if (Buckets[Hash].Used)
{
uint NewPos = Hash;
do
{
if ((Buckets[NewPos].HashCode == HashCode) && (Comparer.Equals(Buckets[NewPos].key, key)))
{
Buckets[NewPos].Value = value;
return;
}
else
NewPos = Buckets[NewPos].Next;
} while (NewPos != 0);
if (Dublicate == MaxDublicate)
{
ReHash();
Add(HashCode,key, this.EmptyValue);
return;
}
if (FirstDeleted == 0)
NewPos = Size + Dublicate;
else
{
NewPos = FirstDeleted;
FirstDeleted = Buckets[NewPos].Next;
}
Buckets[NewPos].HashCode = HashCode;
Buckets[NewPos].key = key;
Buckets[NewPos].Value = value;
Buckets[NewPos].Next = Buckets[Hash].Next;
Buckets[NewPos].Used = true;
Buckets[Hash].Next = NewPos;
Dublicate++; Count++;
}
else
{
Count++;
Buckets[Hash].HashCode = HashCode;
Buckets[Hash].key = key;
Buckets[Hash].Value = value;
Buckets[Hash].Used = true;
Buckets[Hash].Next = 0;
}
}
}
}
public struct Int32HashItem<V>
{
internal bool Used;
internal Int32 key;
public V Value;
internal uint Next;
}
public class Int32HashTable<V>
{
public uint Count, Size, MaxDublicate, Dublicate, FirstDeleted;
public Int32HashItem<V>[] Buckets;
private V EmptyValue;
public Int32HashTable():this(5)
{
}
public Int32HashTable(uint newSize)
{
if (newSize <= 5)
Size = 5;
else
Size = HashConst.ПростоеЧисло(newSize + (newSize >> 1));
Count = 0;
Dublicate = 0;
MaxDublicate = Size / HashConst.mdk;
Buckets = new Int32HashItem<V>[Size + MaxDublicate];
EmptyValue = Buckets[0].Value;
}
public uint Add(Int32 Key, V Value)
{
uint Hash = ((uint)Key) % Size;
if (Buckets[Hash].Used)
{
if (Dublicate == MaxDublicate)
{
ReHash();
return Add(Key, Value);
}
uint NewPos;
if (FirstDeleted == 0)
NewPos = Size + Dublicate;
else
{
NewPos = FirstDeleted;
FirstDeleted = Buckets[NewPos].Next;
}
Buckets[NewPos].key = Key;
Buckets[NewPos].Value = Value;
Buckets[NewPos].Next = Buckets[Hash].Next;
Buckets[NewPos].Used = true;
Buckets[Hash].Next = NewPos;
Dublicate++; Count++;
return NewPos;
}
else
{
Count++;
Buckets[Hash].key = Key;
Buckets[Hash].Value = Value;
Buckets[Hash].Used = true;
Buckets[Hash].Next = 0;
return Hash;
}
}
public void ReHash()
{
Int32HashItem<V>[] TempBuckets;
uint Hash;
uint NewPos;
Size = HashConst.ПростоеЧисло(Size * 2);
MaxDublicate = Size / HashConst.mdk;
TempBuckets = Buckets;
Buckets = new Int32HashItem<V>[Size + MaxDublicate];
Int32HashItem<V> Item;
Dublicate = 0;
FirstDeleted = 0;
for (int i = 0; i < TempBuckets.Length; i++)
{
Item = TempBuckets[i];
if (Item.Used)
{
Hash = (uint)Item.key % Size;
if (Buckets[Hash].Used)
{
NewPos = Size + Dublicate;
Dublicate++;
Item.Next = Buckets[Hash].Next;
Buckets[Hash].Next = NewPos;
Buckets[NewPos] = Item;
if (Dublicate == MaxDublicate)
ReHash();
}
else
{
Item.Next = 0;
Buckets[Hash] = Item;
}
}
}
}
public bool KeyExists(Int32 Key, out uint NewPos)
{
NewPos = (uint)Key % Size;
if (Buckets[NewPos].Used)
do
{
if (Buckets[NewPos].key == Key)
return true;
else
NewPos = Buckets[NewPos].Next;
} while (NewPos != 0);
return false;
}
public void RestructDubleBuckets()
{
int I;
uint j;
Int32HashItem<V> NewItem;
uint num;
Int32HashItem<V>[] TempDubleBuckets;
TempDubleBuckets = new Int32HashItem<V>[MaxDublicate];
num = 0;
for (I = ((int)Size) - 1; I >= 0; I--)
{
if (Buckets[I].Used)
{
j = Buckets[I].Next;
if (j > 0)
{
Buckets[I].Next = Size + num;
do
{
NewItem = Buckets[j];
j = NewItem.Next;
if (j > 0)
NewItem.Next = Size + num + 1;
TempDubleBuckets[num] = NewItem;
num++;
} while (j > 0);
}
}
}
Array.Copy(TempDubleBuckets, 0, Buckets, Size, MaxDublicate);
}
public void RemoveKey(Int32 Key)
{
uint Hash = (uint)Key % Size;
uint Pred = Hash;
if (Buckets[Hash].Used)
do
{
if (Buckets[Hash].key== Key)
{
Dublicate--;
if (Pred == Hash)
{
if (Buckets[Hash].Next > 0)
{
uint di = Buckets[Hash].Next;
Buckets[Hash] = Buckets[di];
Buckets[di].Next = FirstDeleted;
Buckets[di].Used = false;
Buckets[di].Value = EmptyValue;
FirstDeleted = di;
}
else
{
Buckets[Hash].Used = false;
Buckets[Hash].Value = EmptyValue;
}
return;
}
else
{
Buckets[Pred].Next = Buckets[Hash].Next;
Buckets[Hash].Next = FirstDeleted;
Buckets[Hash].Used = false;
Buckets[Hash].Value = EmptyValue;
FirstDeleted = Hash;
}
return;
}
else
{
Pred = Hash;
Hash = Buckets[Hash].Next;
}
} while (Hash != 0);
}
private bool Navigate(ref uint Pos, Int32 Key)
{
do
{
if (Buckets[Pos].key== Key)
return true;
else
Pos = Buckets[Pos].Next;
} while (Pos != 0);
return false;
}
public uint NavigateOrInsertDefault(Int32 Key, out bool exists)
{
exists = false;
uint Hash = ((uint)Key) % Size;
if (Buckets[Hash].Used)
{
uint NewPos = Hash;
do
{
if (Buckets[NewPos].key==Key)
{
exists = true;
return NewPos;
}
else
NewPos = Buckets[NewPos].Next;
} while (NewPos != 0);
if (Dublicate == MaxDublicate)
{
ReHash();
return Add(Key, this.EmptyValue);
}
if (FirstDeleted == 0)
NewPos = Size + Dublicate;
else
{
NewPos = FirstDeleted;
FirstDeleted = Buckets[NewPos].Next;
}
Buckets[NewPos].key = Key;
Buckets[NewPos].Next = Buckets[Hash].Next;
Buckets[NewPos].Used = true;
Buckets[Hash].Next = NewPos;
Dublicate++; Count++;
exists = false;
return NewPos;
}
else
{
Count++;
Buckets[Hash].key = Key;
Buckets[Hash].Used = true;
Buckets[Hash].Next = 0;
exists = false;
return Hash;
}
}
public V this[Int32 key]
{
get
{
uint HashCode = (uint)key;
uint NewPos = ((uint)HashCode) % Size;
// if (!this.Navigate(ref NewPos,HashCode,key))
// throw new ArgumentException("Key not present in Dictionary.");
// return this.Buckets[NewPos].Value;if (!Buckets[NewPos].Used)
throw new ArgumentException("Key not present in Dictionary.");
do
{
if (Buckets[NewPos].key==key)
return Buckets[NewPos].Value;
else
NewPos = Buckets[NewPos].Next;
} while (NewPos != 0);
throw new ArgumentException("Key not present in Dictionary.");
}
set
{
uint HashCode = (uint)key;
uint Hash = ((uint)HashCode) % Size;
if (Buckets[Hash].Used)
{
uint NewPos = Hash;
do
{
if (Buckets[NewPos].key== key)
{
Buckets[NewPos].Value = value;
return;
}
else
NewPos = Buckets[NewPos].Next;
} while (NewPos != 0);
if (Dublicate == MaxDublicate)
{
ReHash();
Add(key, this.EmptyValue);
return;
}
if (FirstDeleted == 0)
NewPos = Size + Dublicate;
else
{
NewPos = FirstDeleted;
FirstDeleted = Buckets[NewPos].Next;
}
Buckets[NewPos].key = key;
Buckets[NewPos].Value = value;
Buckets[NewPos].Next = Buckets[Hash].Next;
Buckets[NewPos].Used = true;
Buckets[Hash].Next = NewPos;
Dublicate++; Count++;
}
else
{
Count++;
Buckets[Hash].key = key;
Buckets[Hash].Value = value;
Buckets[Hash].Used = true;
Buckets[Hash].Next = 0;
}
}
}
}
}
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Arboz, Вы писали:
U>>Не понял почему этот код является потокобезопасным?
U>>
U>> dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
U>> lock(&Q->H_lock) // Acquire H_lock in order to access Head
U>> node = Q->Head // Read Head
U>> new_head = node->next // Read next pointer
U>> if new_head == NULL // Is queue empty?
U>> unlock(&Q->H_lock) // Release H_lock before return
U>> return FALSE // Queue was empty
U>> endif
U>> *pvalue = new_head->value // Queue not empty. Read value before release
U>> Q->Head = new_head // Swing Head to next node
U>> unlock(&Q->H_lock) // Release H_lock
U>> free(node) // Free node
U>> return} TRUE // Queue was not empty, dequeue succeeded
U>>
U>>Вроде как если у нас в очереди был один элемент и между выделенными строками произошел вызов enqueue, то произойдет рассинхронизации — голова будет равна null, а хвост добавленному значению.
A>Голова (Head) же не может быть равна null?
Да, торможу, return false я не приметил. Тогда нормально, идея интересная.
