[Перевод] Реализация Swift словаря26.01.2016 13:49

internal var _bucketMask: Int {
  // The capacity is not negative, therefore subtracting 1 will not overflow.
  return capacity &- 1
}

@warn_unused_result
internal func _next(bucket: Int) -> Int {
  // Bucket is within 0 and capacity. Therefore adding 1 does not overflow.
  return (bucket &+ 1) & _bucketMask
}

@warn_unused_result
internal func _prev(bucket: Int) -> Int {
  // Bucket is not negative. Therefore subtracting 1 does not overflow.
  return (bucket &- 1) & _bucketMask
}

Для добавления нового элемента нам понадобится узнать, к какому сегменту он будет принадлежать и затем вызвать функцию, вставляющую соответствующий ключ и значение в выбранный сегмент, а также задающую действительные параметры для записи bitmap.

@_transparent
internal func initializeKey(k: Key, value v: Value, at i: Int) {
  _sanityCheck(!isInitializedEntry(i))

  (keys + i).initialize(k)
  (values + i).initialize(v)
  initializedEntries[i] = true
  _fixLifetime(self)
}

Функция _find

• Функция _find позволяет выяснить, какой сегмент будет задействован при работе с ключом (вставка или выборка);
• Запрашивает исходный сегмент для ключа, чтобы вызвать _bucket(key);
• В случае, если ключ в параметре совпадает с ключом сегмента, возвращает на исходную позицию объекта;
• Если объект не найден, расположение первого пробела определяется возможным участком для вставки ключа;
• Bitmap позволяет проверять сегменты, отделяя заполненные участки от пробелов;
• Это и есть линейное пробирование (linear probing);

/// Поиск для данного ключа начинается с указанного сегмента.
///
///Если ключ не обнаружен, возврат к месту его возможной
/// вставки.
@warn_unused_result
internal
func _find(key: Key, _ startBucket: Int) -> (pos: Index, found: Bool) {
  var bucket = startBucket

  // The invariant guarantees there's always a hole, so we just loop
  // until we find one
  while true {
    let isHole = !isInitializedEntry(bucket)
    if isHole {
      return (Index(nativeStorage: self, offset: bucket), false)
    }
    if keyAt(bucket) == key {
      return (Index(nativeStorage: self, offset: bucket), true)
    }
    bucket = _next(bucket)
  }
}

• Фактически, squeezeHashValue — индикатор того, что ключ присутствует в массиве сегмента, но возможны, коллизии. Например, у двух ключей могут быть одинаковые значения хеш;
• В таком случае выберите функцию, которая выявит ближайший сегмент для вставки ключа.

Именно поэтому при анализе значений хеш Hashable выступает в роли, едва ли не идеальной функции, гарантирующей высокую производительность.

• squeezeHashValue действительно пытается создать отличный хеш с помощью нескольких опций;
• Похоже, для того, чтобы при исполнении программы сохранить различные значения хеш, ядро запуска было привязано к hashValue, указанному в типе ключа. Правда, мы говорим о постоянном значении заполнителя;
• _BitMap struct используется в качестве оболочки, позволяющей читать и делать записи в bitmap.

Наглядно получаем, примерно, следующее:

_NativeDictionaryStorageOwner (class)

Этот класс создан для отслеживания правильного подсчета сносок для копий, сделанных в процессе записи. Так как сохранение данных осуществляется с помощью опций Dictionary и DictionaryIndex, счетчик ссылок будет присваивать вводимой информации значение 2, но, если словарь относится к вышеупомянутому классу и количество ссылок для него отслеживается, вам не о чем беспокоиться.

/// Данный класс — идентификатор запуска COW. Он
/// необходим исключительно для разделения уникальных счетчиков ссылок для:
/// — `Dictionary` и `NSDictionary`,
/// — `DictionaryIndex`.
///
/// Это важно, поскольку проверка на уникальность для COW проводится исключительно
/// для выявления счетчиков первого вида.

Так это выглядит не очень приятно:

_VariantDictionaryStorage (перечисляемый тип)

Этот перечисляемый тип работает с двумя операторами Native/Cocoa в зависимости от сохраняемых в них данных.

case Native(_NativeDictionaryStorageOwner)
case Cocoa(_CocoaDictionaryStorage)

Основные характеристики:

• Перечисляемый тип, основанный на Native или Cocoa, задает функции корректировки в процессе сохранения информации в словаре для таких операций, как, как вставка, выборка, удаления и т.д;
• Расширяет объем памяти для хранения данных по мере ее заполнения;
• Обновляет или задает связку ключ-значение.
• Если необходимо удалить Значение из массива сегмента, может появиться пробел, который вызовет побочные эффекты в процессе пробирования, что приведет к его преждевременному прерыванию. Для предотвращения подобных негативных явлений важно учитывать позиции всех элементов словаря.

/// - параметр idealBucket: идеальный сегмент, предполагающий возможность удаления элемента.
/// - параметр offset: офсет элемента, который будет удален.
///Необходима инициализация записи на смещение.
internal mutating func nativeDeleteImpl(
  nativeStorage: NativeStorage, idealBucket: Int, offset: Int
) {
  _sanityCheck(
      nativeStorage.isInitializedEntry(offset), "expected initialized entry")

  // удалить элемент
  nativeStorage.destroyEntryAt(offset)
  nativeStorage.count -= 1

 // Если в ряду смежных элементов появляется пробел,
 // некоторые элементы после пробела могут заполнить промежуток нового пробела.
  var hole = offset

  // Определите первый сегмент смежного ряда
  var start = idealBucket
  while nativeStorage.isInitializedEntry(nativeStorage._prev(start)) {
    start = nativeStorage._prev(start)
  }

  // Определите последний сегмент смежного ряда
  var lastInChain = hole
  var b = nativeStorage._next(lastInChain)
  while nativeStorage.isInitializedEntry(b) {
    lastInChain = b
    b = nativeStorage._next(b)
  }

  // Перемещайте элементы, перенесенные на новые места в ряду, повторяя процедуру до тех пор,
  // пока все элементы не окажутся на соответствующих позициях.
  while hole != lastInChain {
    // Повторите проверку в обратном направлении, с конца ряда смежных сегментов в поиске
    // элементов, оставшихся не на своих местах.
    var b = lastInChain
    while b != hole {
      let idealBucket = nativeStorage._bucket(nativeStorage.keyAt(b))

      // Элемент оказался между началом и пробелом? Нам необходимо
       // два отдельных теста с учетом возможного появления упаковщиков [начало, пробел]
      // в конце буфера
      let c0 = idealBucket >= start
      let c1 = idealBucket <= hole
      if start <= hole ? (c0 && c1) : (c0 || c1) {
        break // Found it
      }
      b = nativeStorage._prev(b)
    }

    if b == hole { // No out-of-place elements found; we're done adjusting
      break
    }

    // Переместите найденный элемент на место пробела
    nativeStorage.moveInitializeFrom(nativeStorage, at: b, toEntryAt: hole)
    hole = b
  }
}

И вот как выглядит наш словарь

(всего лишь один из видов перечисляемых данных)

© Habrahabr.ru