×
10.04.2016
216.015.3284

ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ

Вид РИД

Изобретение

Юридическая информация Свернуть Развернуть
№ охранного документа
0002581011
Дата охранного документа
10.04.2016
Краткое описание РИД Свернуть Развернуть
Аннотация: Изобретение относится к вычислительной технике. Технический результат заключается в повышении скорости обработки данных. Способ содержит этапы, на которых: предоставляют неактивное представление документа, исполняют с помощью вычислительной системы поток-конструктор для ввода или изменения элемента в документе, предоставляют доступ к неактивному представлению для использования потоком-считывателем, обновляют неактивное представление документа с помощью активного представления документа и после обновления неактивного представления предоставляют доступ к неактивному представлению документа, включающему в себя упомянутые изменения в отношении упомянутого элемента. 3 н. и 17 з.п. ф-лы, 20 ил.
Реферат Свернуть Развернуть

УРОВЕНЬ ТЕХНИКИ

[0001] Электронные документы в сегодняшней рабочей обстановке повсеместны. Например, миллионы людей каждый день используют и формируют документы текстового процессора, документы электронной таблицы и другие виды документов. При увеличивающейся важности электронных документов люди предполагают, что программные приложения предоставят еще более мощные инструменты для обращения с электронными документами. Например, люди предполагают, что приложения для обработки текстов предоставят инструменты безошибочной проверки грамматики и орфографии.

[0002] Однако такие инструменты часто требуют больших объемов вычислений. Поскольку такие инструменты требуют больших объемов вычислений, использование таких инструментов может привести к задержкам, которые заметны пользователям. Такие задержки могут вызывать неудовлетворенность пользователя, и поэтому их следует минимизировать.

[0003] Производительность компьютеров в последние годы увеличилась. Однако значительная часть того увеличения обусловлена тем, что отдельные компьютеры теперь могут использовать несколько блоков обработки. Например, более старые компьютеры имели только один блок обработки и поэтому могли выполнять только одну программу единовременно. Новые компьютеры могут иметь несколько блоков обработки и поэтому могут выполнять одновременно несколько программ.

[0004] В некоторых обстоятельствах несколько программ, выполняющихся на нескольких блоках обработки, должны взаимодействовать с одними и теми же данными в электронном документе. Например, если первая программа должна была писать в некоторые данные в электронном документе, тогда как вторая программа пыталась считать те данные, то вторая программа могла считать искаженные данные. Типичным решением этой проблемы для программ является блокировка данных в электронном документе до того, как программы считают данные. Когда программа блокирует данные, никакая другая программа не может писать в те данные. Поэтому, если другой поток хочет писать в данные, пока данные заблокированы, другой поток вынужден ожидать, пока данные не разблокируют. Вынуждение другого потока ждать может привести к задержкам, которые заметны пользователям.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[0005] Вычислительная система одновременно выполняет поток-конструктор и по меньшей мере один поток-считыватель. Поток-конструктор изменяет документ путем изменения активного представления документа. Поток-считыватель выполняет операции в отношении документа, используя неактивное представление документа. Активное представление документа и неактивное представление документа сохраняются в запоминающем устройстве вычислительной системы. Активное представление документа и неактивное представление документа не включают в себя разные копии одних и тех же данных в запоминающем устройстве. При считывании данных в любом неактивном представлении документа логическая связность обеспечивается без блокирования каких-либо данных в любом неактивном представлении документа.

[0006] Данная сущность изобретения предоставляется для знакомства с набором идей. Эти идеи дополнительно описываются ниже в Подробном описании. Данная сущность изобретения не предназначена для определения ключевых признаков или существенных признаков заявленного предмета изобретения, и также данная сущность не предназначена в качестве содействия при определении объема заявленного предмета изобретения.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0007] Фиг. 1 - блок-схема, иллюстрирующая примерную вычислительную систему.

[0008] Фиг. 2 иллюстрирует примерное дерево документа и массив элементов, который представляет дерево документа.

[0009] Фиг. 3 иллюстрирует примерное представление документа.

[0010] Фиг. 4 иллюстрирует примерное представление документа, когда вставляются элементы.

[0011] Фиг. 5 иллюстрирует примерное представление документа, когда удаляются элементы.

[0012] Фиг. 6 иллюстрирует примерное представление документа, когда дополнительные элементы вставляются в существующий фрагмент.

[0013] Фиг. 7 иллюстрирует примерное дерево индексов.

[0014] Фиг. 8 иллюстрирует примерное дерево индексов с наложенными узлами замены, принадлежащими поздней версии дерева индексов.

[0015] Фиг. 9 - блок-схема алгоритма, иллюстрирующая примерную операцию, выполненную приложением, когда приложение запускается.

[0016] Фиг. 10 - блок-схема алгоритма, иллюстрирующая примерную операцию вставки элемента.

[0017] Фиг. 11 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции вставки элемента.

[0018] Фиг. 12 - блок-схема алгоритма, иллюстрирующая дальнейшее продолжение примерной операции вставки элемента.

[0019] Фиг. 13 - блок-схема алгоритма, иллюстрирующая дальнейшее продолжение примерной операции вставки элемента.

[0020] Фиг. 14 - блок-схема алгоритма, иллюстрирующая примерную операцию удаления элемента.

[0021] Фиг. 15 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции удаления элемента.

[0022] Фиг. 16 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции удаления элемента.

[0023] Фиг. 17 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции удаления элемента.

[0024] Фиг. 18 - блок-схема алгоритма, иллюстрирующая примерную операцию потока-считывателя.

[0025] Фиг. 19 - блок-схема алгоритма, иллюстрирующая примерную операцию потока-считывателя.

[0026] Фиг. 20 - блок-схема, иллюстрирующая примерное вычислительное устройство.

ПОДРОБНОЕ ОПИСАНИЕ

[0027] Фиг. 1 - блок-схема, иллюстрирующая примерную вычислительную систему 100. Как проиллюстрировано в примере из фиг. 1, пользователь 102 использует вычислительную систему 100 для доступа к приложению 104. Приложение 104 позволяет пользователю 102 взаимодействовать с документом 106. В различных вариантах осуществления приложение 104 может быть различными типами приложений. Например, приложение 104 может быть приложением обработки текстов MICROSOFT® WORD®, системой связи MICROSOFT® OUTLOOK®, приложением электронной таблицы MICROSOFT® EXCEL®, приложением создания заметок MICROSOFT® ONENOTE® или другими типами приложений обработки текстов, приложений связи/электронной почты, приложений электронной таблицы, приложений создания заметок или другими типами приложений, которые позволяют пользователям взаимодействовать с документами. Соответственно, документ 106 может быть различными типами документов. Например, документ 106 может быть документом текстового процессора, веб-страницей, сообщением электронной почты, документом электронной таблицы или другим типом документа. В различных вариантах осуществления пользователь 102 может взаимодействовать с документом 106 различными способами. Например, в некоторых вариантах осуществления пользователь 102 может просматривать или редактировать содержимое документа 106.

[0028] Чтобы отобразить документ 106 пользователю 102, приложение 104 преобразует внутреннее представление документа 106 в документ, показанный пользователю 102. Например, представление документа 106 может включать в себя значительное количество данных, которые дают указание приложению 104, как отображать документ 106. Приложение 104 интерпретирует эти данные для отображения документа 106 пользователю 102. Однако эти данные обычно не отображаются пользователю 102.

[0029] Приложение 104 использует множество потоков, выполняемых вычислительной системой 100, чтобы дать пользователю 102 возможность взаимодействовать с документом 106. Поток является частью программы, которая может выполняться независимо от других частей программы. Потоки, используемые приложением 104, могут выполняться одновременно на разных блоках обработки вычислительной системы 100. Следовательно, два или более потоков могут попробовать одновременно обратиться к одним и тем же данным в представлении документа 106. Для двух или более потоков не желательно обращаться к одним и тем же данным одновременно, потому что могут возникнуть неожиданные результаты. Например, когда пользователь 102 предоставляет ввод в вычислительную систему 100 для замены старого слова (например, "tiger") в документе 106 новым словом (например, "leopard"), один поток обновляет подходящие данные в представлении документа 106 для замены старого слова новым словом. Одновременно другой поток проверяет орфографию в документе. Если бы проверяющий орфографию поток считывал подходящие данные, в то время как обновляющий поток обновлял подходящие данные, то проверяющий орфографию поток мог бы считать данные, представляющие некоторую часть нового слова (например, "leop"), и данные, представляющие некоторую часть старого слова (например, "ger"). Проверяющий орфографию поток мог бы увидеть слово "leopger" и указать, что новое слово написано неверно, даже если новое слово "leopard" написано правильно и выглядит правильным для пользователя 102. Это не является логически непротиворечивым.

[0030] Чтобы избежать этой ситуации, приложение 104 использует несколько представлений документа 106. Как проиллюстрировано в примере из фиг. 1, потоки включают в себя поток-конструктор 108. Как описано где-то в другом месте этого описания изобретения, поток-конструктор 108 изменяет документ 106 путем изменения активного представления документа 106. Активное представление документа 106 хранится в запоминающем устройстве вычислительной системы 100. После того, как поток-конструктор 108 завершает изменение активного представления документа 106, активное представление документа 106 становится неактивным представлением документа 106.

[0031] В дополнение к потоку-конструктору 108 приложение 104 использует один или несколько потоков-считывателей 110A-110N (вместе - "потоки-считыватели 110"). Потоки-считыватели 110 выполняют операции в отношении документа 106, используя одно или несколько неактивных представлений документа 106. Такие операции помогают приложению 104 предоставлять различные типы функциональных возможностей. Например, документ 106 может быть документом обработки текстов, например документом MICROSOFT® WORD®. В этом примере один из потоков-считывателей 110 выполняет операцию проверки орфографии над текстом в документе 106. В другом примере один из потоков-считывателей 110 получает документ 106, готовый для печати. В еще одном примере один из потоков-считывателей 110 сохраняет документ 106 в локальную или удаленную систему хранения данных. В еще одном примере один из потоков-считывателей 110 использует неактивное представление документа 106 для отображения документа 106 пользователю 102. В еще одном примере один из потоков-считывателей 110 изменяет нумерацию страниц документа 106, когда пользователь 102 набирает на клавиатуре данные в документ 106. В еще одном примере один из потоков-считывателей 110 идентифицирует места для вставки переносов, когда слова охватывают несколько строк.

[0032] Поток-конструктор 108 является единственным потоком, который изменяет данные в любом представлении документа 106. То есть потоки-считыватели 110 не изменяют активное представление документа 106 или любое неактивное представление документа 106. Точнее, потоки-считыватели 110 могут дать потоку-конструктору 108 указание изменить документ 106. Поток-конструктор 108 не изменяет никакие данные ни в одном неактивном представлении документа 106.

[0033] После того, как поток-конструктор 108 завершает операцию по изменению активного представления документа 106, активное представление документа 106 становится неактивным представлением документа 106. Это неактивное представление документа 106 доступно для использования потоками-считывателями 110. Чтобы снова изменить документ 106, поток-конструктор 108 формирует новое активное представление документа 106, изменяет то новое активное представление документа 106 и превращает это новое активное представление документа 106 в неактивное представление документа 106.

[0034] Поскольку никакой поток не изменяет никакое неактивное представление документа 106, то когда потоки-считыватели 110 считывают данные в неактивном представлении документа 106, логическая связность обеспечивается без блокирования каких-либо данных в неактивном представлении документа 106. Другими словами, отсутствует опасность, что другой одновременно выполняющийся поток мог бы записать в данные, пока один из потоков-считывателей 110 пытается считать те же данные.

[0035] Формирование полностью отдельных представлений документа 106 каждый раз, когда изменяется документ 106, могло бы потреблять огромное пространство в памяти вычислительной системы 100. Кроме того, формирование полностью отдельных представлений документа каждый раз, когда изменяется документ 106, могло бы потребовать больших объемов вычислений. Следовательно, активное представление документа 106 и неактивные представления документа 106 не включают в себя разные копии одних и тех же данных в запоминающем устройстве. Например, активное представление документа 106 и неактивное представление документа 106 могут оба включать в себя данные, которые представляет одну и ту же часть документа 106. В этом примере нет двух отдельных копий тех данных в запоминающем устройстве. Скорее, активное представление документа 106 и неактивное представления документа 106 ссылаются на одну и ту же копию тех данных в запоминающем устройстве.

[0036] Фиг. 2 иллюстрирует примерное дерево 200 документа и массив 202 элементов. Внутри документ 106 представляется в виде дерева документа, например дерева 200 документа. Дерево 200 документа является иерархией элементов документа. Эти элементы документа обычно не отображаются пользователю 102, а скорее используются приложением 104 для определения, как отобразить документ 106 пользователю 102.

[0037] Элементы документа в дереве 200 документа включают в себя элементы, которые представляют структуры внутри документа 106. Например, в примере из фиг. 2 дерево 200 документа включает в себя элемент 204 документа, который представляет документ 106 в целом. В этом примере дерево 200 документа включает в себя элемент 206 документа и элемент 208 документа, которые представляют абзацы в документе 106. Поскольку элемент 206 документа (то есть абзац) и элемент 208 документа (то есть другой абзац) представляют сущности внутри документа 106, элемент 206 документа и элемент 208 документа находятся ниже элемента 204 документа в дереве 200 документа.

[0038] Кроме того, в примере из фиг. 2 дерево 200 документа включает в себя элемент 210 документа, элемент 212 документа и элемент 214 документа. Элемент 210 документа и элемент 212 документа представляют последовательности текста в абзаце, представленном элементом 206 документа. Например, элементы 210 и 212 документа могут представлять предложения в абзаце, представленном элементом 206 документа. Поскольку элемент 210 документа и элемент 212 документа представляют сущности в абзаце, представленном элементом 206 документа, элемент 210 документа и элемент 212 документа находятся ниже элемента 206 документа в дереве 200 документа. Элемент 214 документа представляет последовательность текста в абзаце, представленном элементом 208 документа. Поскольку элемент 214 документа представляет сущность в абзаце, представленном элементом 208 документа, элемент 214 документа находится ниже элемента 208 документа в дереве 200 документа.

[0039] Элементы документа в дереве 200 документа могут обладать различными атрибутами. В примере из фиг. 2 элемент 204 документа может включать в себя атрибут, который устанавливает "Times New Roman" в качестве шрифта по умолчанию для документа 106. В этом примере элемент 208 документа может включать в себя атрибут, который переопределяет шрифт по умолчанию и устанавливает "Arial" в качестве шрифта для абзаца, представленного элементом 208 документа. Кроме того, в этом примере элемент 214 документа может включать в себя атрибут, который делает подчеркнутой последовательность текста, представленную элементом 214 документа.

[0040] На понятийном уровне память компьютера подобна строке сегментов. Каждый из сегментов в строке имеет разный адрес. Например, один сегмент в строке может иметь адрес "37", а следующий сегмент в строке может иметь адрес "38", и так далее. Каждый из сегментов может хранить данные. Поскольку память компьютера подобна строке сегментов, память компьютера на понятийном уровне является одномерной структурой. В отличие от этого, дерево 200 документа является двумерной структурой (то есть дерево 200 документа обладает высотой и шириной). Чтобы хранить дерево 200 документа (двумерную структуру) в памяти компьютера (одномерной структуре), необходимо представить дерево 200 документа как одномерную структуру.

[0041] Массив 202 элементов является примерной одномерной структурой, которая представляет дерево 200 документа. Массив 202 элементов содержит элементы 216A, 216B, 218A, 218B, 220A, 220B, 222A, 222B, 224A, 224B, 226A и 226B. Элементы 216A и 216B соответствуют элементу 204 документа в дереве 200 документа. Элемент 216A является открывающим элементом, а элемент 216B является закрывающим элементом, соответствующим элементу 216A. Элементы в массиве между открывающим элементом и соответствующим закрывающим элементом представляют элементы документа ниже элемента документа, представленного открывающим элементом и соответствующим закрывающим элементом.

[0042] Элементы в массиве 202 элементов между элементами 216A и 216B соответствуют элементам документа в дереве 200 документа ниже элемента 204 документа. Элементы 218A и 218B соответствуют элементу 206 документа в дереве 200 документа. Элементы в массиве 202 элементов между элементами 218A и 218B соответствуют элементам документа в дереве 200 документа ниже элемента 206 документа. Элементы 220A и 220B соответствуют элементу 210 документа в дереве 200 документа. Поскольку отсутствуют элементы документа в дереве 200 документа ниже элемента 210 документа, отсутствуют элементы в массиве 202 элементов между элементами 220A и 220B. Элементы 222A и 222B соответствуют элементу 212 документа в дереве 200 документа. Поскольку отсутствуют элементы документа в дереве 200 документа ниже элемента 210 документа, отсутствуют элементы в массиве 202 элементов между элементами 222A и 222B. Элементы 224A и 224B соответствуют элементу 208 документа в дереве 200 документа. Элементы в массиве 202 элементов между элементами 224A и 224B соответствуют элементам документа в дереве 200 документа ниже элемента 208 документа. Элементы 226A и 226B соответствуют элементу 214 документа в дереве 200 документа. Поскольку отсутствуют элементы документа в дереве 200 документа ниже элемента 214 документа, отсутствуют элементы в массиве 202 элементов между элементами 226A и 226B.

[0043] Когда пользователь 102 работает с документом 106, пользователь 102 может захотеть добавить новый абзац между абзацем, представленным элементом 206 документа, и абзацем, представленным элементом 208 документа. Следовательно, дерево 200 документа обновилось бы для включения в него нового элемента документа ниже элемента 204 документа. Новый элемент документа представляет новый абзац. Чтобы представить обновленное дерево 200 документа, потребовалось бы добавить новую пару элементов между элементами 218B и 224A в массиве 202 элементов. Новая пара элементов соответствует новому элементу документа.

[0044] Как упоминалось ранее, память компьютера на понятийном уровне является строкой сегментов. Данные, представляющие массив 202 элементов, сохраняются в таких сегментах в памяти компьютера. Чтобы вставить новые элементы между двумя элементами в массиве 202 элементов, поток-конструктор 108 мог бы освободить сегменты для новых элементов путем копирования всех элементов в массиве 202 элементов после новых элементов в сегменты еще ниже по строке сегментов, а затем сохранения новых элементов в освободившиеся сегменты. Например, элемент 218B можно сохранить в сегменте "37", элемент 224A можно сохранить в сегменте "38", элемент 226A можно сохранить в сегменте "39", элемент 226B можно сохранить в сегменте "40", элемент 224B можно сохранить в сегменте "41", а элемент 216B можно сохранить в сегменте "41". В этом примере, чтобы вставить элементы между элементом 218B и элементом 224A, вычислительная система 100 могла бы скопировать элемент 216B в сегмент "43", элемент 224B в сегмент "42", элемент 226B в сегмент "41", элемент 226A в сегмент "40" и элемент 224A в сегмент "39". В этом примере поток-конструктор 108 затем мог бы сохранить новые элементы в сегментах "37" и "38". Как демонстрирует этот пример, если бы поток-конструктор 108 должен был использовать этот подход, то потоку-конструктору 108 могло бы потребоваться выполнить большое количество операций копирования, чтобы вставить элементы в массив 202 элементов. Аналогичным образом, если бы поток-конструктор 108 должен был сдвинуть элементы в массиве 202 элементов, когда элементы удаляются из массива 202 элементов, то потоку-конструктору 108 могло бы потребоваться выполнить большое количество операций копирования, чтобы удалить элементы из массива 202 элементов.

[0045] Вместо копирования элементов, когда в массив 202 элементов вставляется новый элемент, поток-конструктор 108 добавляет новый элемент в один конец реального массива элементов. Следовательно, элементы в реальном массиве элементов не обязательно упорядочены так, что элементы, соответствующие элементу документа ниже другого элемента документа, находятся между элементами, соответствующими другому элементу документа. Как описано в этом описании изобретения, представление документа 106 содержит дерево индексов, таблицу дескрипторов фрагментов и такой реальный массив элементов. Дерево индексов и таблица дескрипторов фрагментов указывают, где элементы в реальном массиве элементов находятся в виртуальном массиве элементов. Виртуальный массив элементов является одномерным представлением дерева 200 документа. Элементы в виртуальном массиве элементов упорядочены так, что элементы, соответствующие элементу документа ниже другого элемента документа, находятся между элементами, соответствующими другому элементу документа.

[0046] Фиг. 3 - блок-схема, иллюстрирующая примерное представление документа 106. Представление документа 106 включает в себя дерево 300 индексов, таблицу 302 дескрипторов фрагментов и реальный массив 304 элементов. Дерево 300 индексов и таблица 302 дескрипторов фрагментов являются структурами данных, которые указывают, где элементы в реальном массиве 304 элементов находятся в виртуальном массиве 306 элементов.

[0047] Как проиллюстрировано в примере из фиг. 3, реальный массив 304 элементов содержит элементы 308A, 308B, 310A, 310B, 312A и 312B. Элементы 308A, 308B, 310A, 310B, 312A и 312B соответствуют каждому элементу документа в дереве документа 106. Для каждого заданного элемента в виртуальном массиве 306 элементов, если заданный элемент находится между открывающим элементом и закрывающим элементом в виртуальном массиве 306 элементов, то заданный элемент представляет элемент документа в дереве документа, который находится ниже элемента документа в дереве документа, представленном открывающим элементом и закрывающим элементом. Виртуальный массив 306 элементов также содержит элементы 308A, 308B, 310A, 310B, 312A и 312B. Однако виртуальный массив 306 элементов фактически не существует в памяти компьютера.

[0048] В некоторых вариантах осуществления, например, проиллюстрированных в примере из фиг. 3, элементы в реальном массиве 304 элементов упорядочены должным образом, когда приложение 104 первоначально загружает документ 106. Другими словами, каждый элемент в реальном массиве 304 элементов, соответствующий элементу документа ниже другого элемента документа, находится между элементами, соответствующими другому элементу документа. Следовательно, когда приложение 104 первоначально загружает документ 106, реальный массив 304 элементов может быть таким же, как и виртуальный массив 306 элементов.

[0049] Таблица 302 дескрипторов фрагментов содержит набор из одного или нескольких дескрипторов фрагментов. Каждый из дескрипторов фрагментов в таблице 302 дескрипторов фрагментов является структурой данных, которая идентифицирует разный фрагмент реального массива 304 элементов. Фрагмент реального массива 304 элементов является набором из одного или нескольких последовательных элементов в реальном массиве 304 элементов. Например, элементы 308A, 310A и 310B могли бы быть фрагментом реального массива 304 элементов, а элементы 312B и 308B могли бы быть другим фрагментом реального массива 304 элементов.

[0050] В различных вариантах осуществления дескрипторы фрагментов реализуются различными способами. Например, в некоторых вариантах осуществления дескрипторы фрагментов задают реальное смещение крайнего левого элемента фрагмента и реальное смещение крайнего правого элемента фрагмента. В этом описании изобретения элемент в массиве считается находящимся слева от другого элемента в массиве, когда элемент находится ближе к началу массива, нежели другой элемент. Аналогичным образом элемент в массиве считается находящимся справа от другого элемента в массиве, когда элемент находится дальше от начала массива, нежели другой элемент. В других вариантах осуществления дескрипторы фрагментов реализуются в виде структур данных, имеющих атрибут реального смещения и атрибут длины. Реальное смещение элемента указывает расстояние от начала реального массива 304 элементов до этого элемента. Атрибут реального смещения у дескриптора фрагмента указывает реальное смещение крайнего левого элемента во фрагменте. Атрибут длины у дескриптора фрагмента указывает длину фрагмента. Эта реализация дескрипторов фрагментов используется по всему описанию изобретения. Однако следует понимать, что в других вариантах осуществления могут использоваться другие реализации дескрипторов фрагментов.

[0051] Атрибут реального смещения у дескриптора фрагмента может указывать реальное смещение различными способами. Например, в некоторых вариантах осуществления атрибут реального смещения может указывать количество байтов от начала реального массива 304 элементов до элемента. В других вариантах осуществления атрибут реального смещения может указывать количество элементов между началом реального массива 304 элементов и элементом. Варианты осуществления, где атрибут реального смещения указывает количество элементов, описываются по всему данному описанию изобретения. Однако следует понимать, что в других вариантах осуществления атрибуты реального смещения могут указывать расстояния от начала реального массива 304 элементов другими способами.

[0052] Атрибут длины у дескриптора фрагмента может указывать длину фрагмента различными способами. Например, в некоторых вариантах осуществления атрибут длины может указывать количество байтов во фрагменте. В других вариантах осуществления атрибут длины может указывать количество элементов во фрагменте. Варианты осуществления, где атрибуты длины указывают количества элементов, описываются по всему данному описанию изобретения. Однако следует понимать, что в других вариантах осуществления атрибуты длины могут указывать длины фрагментов другими способами.

[0053] Когда вычислительная система 100 первоначально загружает документ 106, имеется только один фрагмент в реальном массиве 304 элементов. Следовательно, таблица 302 дескрипторов фрагментов включает в себя единственный дескриптор 314 фрагмента. Дескриптор 314 фрагмента имеет атрибут реального смещения, равный 0, посредством этого указывая фрагмент, который начинается в начале реального массива 304 элементов. Дескриптор 314 фрагмента имеет атрибут длины, равный 6, указывающий, что фрагмент имеет длину в шесть элементов.

[0054] Дерево 300 индексов содержит иерархию одного или нескольких индексных узлов. Каждый из индексных узлов в дереве 300 индексов соответствует разному дескриптору фрагмента в таблице 302 дескрипторов фрагментов. Как проиллюстрировано в примере из фиг. 3, имеется только один дескриптор 314 фрагмента в таблице 302 дескрипторов фрагментов. Следовательно, дерево 300 индексов содержит единственный индексный узел 316.

[0055] В различных вариантах осуществления индексные узлы в дереве 300 индексов реализуются различными способами. Например, в некоторых вариантах осуществления индексные узлы в дереве 300 индексов реализуются в виде структур данных, имеющих атрибут левого потомка, атрибут правого потомка и атрибут дескриптора. В таких вариантах осуществления, если индексный узел имеет левый дочерний индексный узел в дереве 300 индексов, то атрибут левого потомка у индексного узла указывает левого потомка индексного узла. Если индексный узел имеет правый дочерний индексный узел в дереве 300 индексов, то атрибут правого потомка у индексного узла указывает правого потомка индексного узла. Атрибут дескриптора у индексного узла указывает дескриптор фрагмента в таблице 302 дескрипторов фрагментов. В примере из фиг. 3 атрибут дескриптора у индексного узла 316 указывает дескриптор 314 фрагмента. Варианты осуществления, где индексные узлы реализуются в виде структур данных, имеющих атрибуты левого потомка, атрибуты правого потомка и атрибуты дескриптора, описываются по всему данному описанию изобретения. Однако следует принять во внимание, что в других вариантах осуществления индексные узлы реализуются другими способами.

[0056] Фиг. 4 - блок-схема, иллюстрирующая примерное представление документа 106, когда вставляются элементы. Как проиллюстрировано в примере из фиг. 4, элементы 402A, 402B, 404A и 404B вставляются в один конец реального массива 304 элементов. Элементы 402A и 402B представляют элемент документа, который находится ниже элемента документа, представленного элементами 310A и 310B. Элементы 404A и 404B представляют элемент документа, который находится ниже элемента документа, представленного элементами 310A и 310B. Следовательно, в виртуальном массиве 306 элементов элементы 402A, 402B, 404A и 404B находятся между элементами 310A и 310B.

[0057] Заранее все элементы в реальном массиве 304 элементов были упорядочены должным образом. Следовательно, только один дескриптор 314 фрагмента был нужен для указания фрагмента реального массива 304 элементов, который включал в себя элементы между элементами 308A и 308B. Когда элементы 402A, 402B, 404A и 404B вставляются в реальный массив 304 элементов, элементы в реальном массиве 304 элементов уже не упорядочены должным образом. Вместо этого элементы в реальном массиве 304 элементов разделяются на три фрагмента: фрагмент реального массива 304 элементов, содержащий элементы, которые находятся слева от элементов 402A, 402B, 404A и 404B (то есть элементы 308A и 310A), фрагмент реального массива 304 элементов, содержащий элементы 402A, 402B, 404A и 404B, и фрагмент реального массива 304 элементов, содержащий элементы, которые находятся справа от элементов 402A, 402B, 404A и 404B (то есть элементы 310B, 312A, 312B и 308B).

[0058] Свойством таблицы 302 дескрипторов фрагментов является то, что значения атрибутов дескрипторов фрагментов нельзя изменить. Это свойство может гарантировать, что потоки-считыватели 110 могут считывать данные из дескрипторов фрагментов без необходимости учета вероятности, что поток-конструктор 108 может изменять данные в дескрипторах фрагментов, пока потоки-считыватели 110 считывают данные в дескрипторах фрагментов.

[0059] Поскольку значения атрибутов дескрипторов фрагментов не изменяются, а дескриптор фрагмента может указывать только одиночный фрагмент в реальном массиве 304 элементов, нужны дополнительные дескрипторы фрагментов. Чтобы добавить дополнительные дескрипторы фрагментов, поток-конструктор 108 формирует дескриптор 406 фрагмента, дескриптор 408 фрагмента и дескриптор 410 фрагмента. Дескриптор 406 фрагмента, дескриптор 408 фрагмента и дескриптор 410 фрагмента составляют активную версию таблицы 302 фрагментов. Активная версия таблицы 302 фрагментов является частью активного представления документа 106.

[0060] Дескриптор 406 фрагмента заменяет дескриптор 314 фрагмента. Однако поток-конструктор 108 сразу не удаляет дескриптор 314 фрагмента. Наоборот, дескриптор 314 фрагмента продолжает существовать как часть неактивной версии таблицы 302 фрагментов в неактивном представлении документа 106. Следовательно, потоки-считыватели 110 могут использовать дескриптор 314 фрагмента, пока поток-конструктор 108 выполняет операции над дескрипторами фрагментов в активной версии таблицы 302 дескрипторов фрагментов.

[0061] Дескриптор 406 фрагмента идентифицирует фрагмент реального массива 304 элементов, содержащий элементы 308A и 310A. Отметим, что дескриптор 406 фрагмента является клоном (то есть копией) дескриптора 314 фрагмента за исключением того, что атрибут длины у дескриптора 406 фрагмента отличается от атрибута длины у дескриптора 314 фрагмента. Дескриптор 408 фрагмента идентифицирует фрагмент реального массива 304 элементов, содержащий элементы 310B, 312A, 312B и 308B. Дескриптор 410 фрагмента идентифицирует фрагмент реального массива 304 элементов, содержащий элементы 402A, 402B, 404A и 404B.

[0062] Индексные узлы в дереве 300 индексов могут иметь вплоть до двух дочерних узлов. Высоты двух поддеревьев индексного узла в дереве 300 индексов отличаются не более чем на единицу. Например, глубина правого поддерева индексного узла не может быть равна 3, когда глубина левого поддерева индексного узла равна 1. В другом примере глубина правого поддерева индексного узла может быть равна 2, 1 или 0, когда глубина левого поддерева равна 1. В некоторых вариантах осуществления дерево 300 индексов является деревом AVL, B-деревом, красно-черным деревом или другим видом двоичного дерева.

[0063] Дерево 300 индексов обладает свойством сортировки. Свойство сортировки предусматривает, что для каждого индексного узла в дереве 300 индексов элементы, ассоциированные с индексными узлами в левом поддереве индексного узла, имеют виртуальные смещения меньше виртуальных смещений элементов, ассоциированных с индексным узлом. Кроме того, элементы, ассоциированные с индексными узлами в правом поддереве индексного узла, имеют виртуальные смещения больше виртуальных смещений элементов, ассоциированных с индексным узлом. Элемент ассоциируется с индексным узлом, когда элемент находится во фрагменте, указанном дескриптором фрагмента, указанным индексным узлом. Виртуальное смещение элемента является расстоянием от начала виртуального массива 306 элементов до положения элемента в виртуальном массиве 306 элементов.

[0064] К тому же свойством дерева 300 индексов является то, что значения атрибутов индексных узлов нельзя изменять. Это свойство может гарантировать, что потоки-считыватели 110 могут считывать данные из индексных узлов без необходимости учета вероятности, что поток-конструктор 108 может изменять данные в индексных узлах, пока потоки-считыватели 110 считывают данные в индексных узлах.

[0065] Для поддержания этих свойств поток-конструктор 108 формирует индексные узлы 412, 414 и 416, когда элементы 402A, 402B, 404A и 404B вставляются в реальный массив 304 элементов. Индексные узлы 412, 414 и 416 составляют активную версию дерева 300 индексов. Активная версия дерева 300 индексов является частью активного представления документа 106.

[0066] Индексный узел 414 заменяет индексный узел 316. Однако поток-конструктор 108 сразу не удаляет индексный узел 316. Наоборот, индексный узел 316 продолжает существовать как часть неактивной версии дерева 300 индексов, включенной в неактивное представление документа 106. Следовательно, потоки-считыватели 110 могут использовать индексный узел 316, пока поток-конструктор 108 выполняет операции для изменения активной версии дерева 300 индексов. Индексный узел 412 указывает дескриптор 406 фрагмента, индексный узел 414 указывает дескриптор 410 фрагмента, а индексный узел 416 указывает дескриптор 408 фрагмента.

[0067] Индексный узел 412 находится в левом поддереве индексного узла 414. Следовательно, индексный узел 412 ассоциируется с элементами, имеющими виртуальные смещения, которые меньше виртуальных смещений элементов, ассоциированных с индексным узлом 414. Индексный узел 416 находится в правом поддереве индексного узла 414. Следовательно, индексный узел 416 ассоциируется с элементами, имеющими виртуальные смещения больше виртуальных смещений элементов, ассоциированных с индексным узлом 414.

[0068] В примере из фиг. 4 активное представление документа 106 включает в себя активную версию дерева 300 индексов, активную версию таблицы 302 дескрипторов фрагментов и реальный массив 304 элементов. Когда поток-конструктор 108 завершает операцию для вставки элементов 402A, 402B, 404A и 404B, активная версия дерева 300 индексов включает в себя индексные узлы 412, 414 и 416, а активная версия таблицы 302 дескрипторов фрагментов включает в себя дескрипторы 406, 408 и 410 фрагментов. Неактивное представление документа 106 включает в себя неактивную версию дерева 300 индексов, неактивную версию таблицы 302 дескрипторов фрагментов и реальный массив 304 элементов. Неактивная версия дерева 300 индексов включает в себя всего лишь индексный узел 316. Неактивная версия таблицы 302 дескрипторов фрагментов включает в себя всего лишь дескриптор 314 фрагмента.

[0069] Фиг. 5 иллюстрирует примерное представление документа 106, когда удаляются элементы. Как проиллюстрировано в примере из фиг. 5, элементы 402A и 402B удаляются из виртуального массива 306 элементов. В реальном массиве 304 элементов элементы после элементов 402A и 404B не перемещаются. То есть в реальном массиве 304 элементов элемент 404A не становится соседним с элементом 308B, когда элементы 402A и 402B удаляются из виртуального массива 306 элементов. Однако в виртуальном массиве 306 элементов кажется, как будто элементы 402A и 402B полностью исчезли.

[0070] Когда элементы 402A и 402B удаляются, значения атрибута реального смещения и атрибута длины у дескриптора 410 фрагмента нужно изменить для того, чтобы указать, что фрагмент не включает в себя элементы 402A и 402B. Как упоминалось выше, свойством таблицы 302 дескрипторов фрагментов является то, что значения атрибутов дескрипторов фрагментов нельзя изменить. Следовательно, поток-конструктор 108 формирует дескриптор 500 фрагмента. Дескриптор 500 фрагмента, дескриптор 408 фрагмента и дескриптор 406 фрагмента составляют активную версию таблицы 302 дескрипторов фрагментов. Дескриптор 500 фрагмента заменяет дескриптор 410 фрагмента. Атрибут реального смещения и атрибут длины у дескриптора 500 фрагмента имеют надлежащие значения.

[0071] Даже если поток-конструктор 108 сформировал дескриптор 500 фрагмента, атрибут дескриптора у индексного узла 414 по-прежнему указывает дескриптор 410 фрагмента. Как упоминалось выше, свойством дерева 300 индексов является то, что значения атрибутов индексных узлов нельзя изменять. Следовательно, поток-конструктор 108 формирует новый индексный узел 502. Индексные узлы 502, 412 и 416 составляют активную версию дерева 300 индексов. Индексный узел 502 заменяет индексный узел 414. Атрибут дескриптора у индексного узла 502 указывает дескриптор 500 фрагмента. Поток-конструктор 108 сразу не удаляет индексный узел 414. Это позволяет потокам-считывателям 110 продолжить использование индексного узла 414 и дескриптора 410 фрагмента, пока поток-конструктор 108 изменяет активную версию дерева 300 индексов и активную версию таблицы 302 дескрипторов фрагментов.

[0072] Следует понимать, что индексный узел 316 и дескриптор 314 фрагмента по-прежнему могут существовать для использования потоками-считывателями 110, которые не используют индексный узел 414 в качестве корневого узла дерева 300 индексов. Корневой индексный узел является индексным узлом, не имеющим предков. Однако индексный узел 316 и дескриптор 314 фрагмента для ясности исключаются из фиг. 5.

[0073] Фиг. 6 иллюстрирует примерное представление документа 106, когда дополнительные элементы вставляются в существующий фрагмент. В примере из фиг. 6 поток-конструктор 108 вставляет элементы 600A и 600B в реальный массив 304 элементов. В виртуальном массиве 306 элементов элементы 600A и 600B находятся между элементами 312A и 312B. Другими словами, элементы 600A и 600B представляют элемент документа, который находится ниже элемента документа, представленного элементами 312A и 312B в дереве 200 документа.

[0074] Чтобы гарантировать, что элементы 600A и 600B имеют правильные положения в виртуальном массиве 306 элементов, поток-конструктор 108 создает новый дескриптор 602 фрагмента. Дескриптор 602 фрагмента идентифицирует фрагмент реального массива 304 элементов, содержащий элементы 600A и 600B. Поскольку фрагмент, содержащий элементы 600A и 600B, логически возникает во фрагменте, который содержал элементы 310B, 312A, 312B и 308B, поток-конструктор 108 формирует дескрипторы 604 и 606 фрагментов. Дескрипторы 406, 606, 500, 604 и 602 фрагментов составляют активную версию таблицы 302 дескрипторов фрагментов. Дескриптор 604 фрагмента указывает фрагмент реального массива 304 элементов, содержащий элементы, имеющие виртуальные смещения, которые больше виртуальных смещений у элементов 600A и 600B. Дескриптор 606 фрагмента указывает фрагмент реального массива 304 элементов, содержащий элементы, которые имеют виртуальные смещения, которые меньше виртуальных смещений у элементов 600A и 600B. Дескриптор 606 фрагмента заменяет дескриптор 408 фрагмента.

[0075] Поток-конструктор 108 затем формирует индексные узлы 608 и 610. Атрибут дескриптора у индексного узла 608 указывает дескриптор 606 фрагмента. Атрибут дескриптора у индексного узла 610 указывает дескриптор 604 фрагмента. Поскольку индексные узлы 608 и 610 ассоциируются с элементами слева и справа от элементов 600A и 600B, индексные узлы 608 и 610 должны быть дочерними узлами индексного узла, ассоциированного с элементами 600A и 600B. Следовательно, потребовалось бы изменить атрибут левого потомка, атрибут правого потомка и атрибут дескриптора у индексного узла 416. Поскольку индексный узел 416 не разрешено изменять, поток-конструктор 108 формирует индексный узел 612 для замены индексного узла 416. Атрибут левого потомка у индексного узла 612 указывает индексный узел 608. Атрибут правого потомка у индексного узла 612 указывает индексный узел 610. Атрибут дескриптора у индексного узла 612 указывает дескриптор 602 фрагмента.

[0076] Кроме того, атрибут правого потомка у индексного узла 502 следует изменить для указания нового индексного узла 612. Поскольку индексный узел 502 не разрешено изменять, поток-конструктор 108 формирует индексный узел 614. Атрибут левого потомка у индексного узла 614 продолжает указывать индексный узел 412, атрибут правого потомка у индексного узла 614 указывает индексный узел 612, а атрибут дескриптора у индексного узла 614 продолжает указывать дескриптор 500 фрагмента. Поэтому в примере из фиг. 6 индексные узлы 614, 412, 612, 608 и 610 составляют активную версию дерева 300 индексов.

[0077] Следует принять во внимание, что фиг. 4, 5 и 6 всего лишь иллюстрируют некоторые сочетания действий, которые поток-конструктор 108 выполняет над деревом 300 индексов и таблицей 302 дескрипторов фрагментов, чтобы поддерживать надлежащее отношение между реальным массивом 304 элементов и виртуальным массивом 306 элементов.

[0078] Фиг. 7 иллюстрирует примерное дерево 700 индексов. Дерево 700 индексов содержит пятнадцать индексных узлов 702 - 730. В примере из фиг. 7 размеры левых поддеревьев у индексных узлов показаны в индексных узлах. Например, размер левого поддерева у индексного узла 702 равен семи, поскольку имеется семь индексных узлов в левом поддереве индексного узла 702.

[0079] Свойством дерева 700 индексов является то, что размеры левых поддеревьев у индексных узлов не изменяются. Следовательно, в любой момент, когда поток-конструктор 108 добавляет индексный узел к дереву 700 индексов, который находится в левом поддереве любого индексного узла, поток-конструктор 108 формирует индексные узлы замены для всех предшествующих индексных узлов (предков) у индексного узла. Однако, чтобы добавить отдельный индексный узел к дереву 700 индексов, потоку-конструктору 108 не нужно формировать никакие замены для индексных узлов, которые не являются предшествующими индексными узлами у нового индексного узла. Это свойство демонстрируют примеры из фиг. 4 и 6.

[0080] Фиг. 8 иллюстрирует дерево 700 индексов с наложенными узлами замены, принадлежащими поздней версии дерева 700 индексов. В примере из фиг. 8 поток-конструктор 108 добавил индексный узел 802 к дереву 700 индексов. Следовательно, поток-конструктор 108 формирует индексные узлы 804, 806, 808 и 810 замены. В поздней версии дерева 700 индексов индексные узлы 804, 806, 808 и 810 замены заменяют индексные узлы 718, 708, 704 и 702.

[0081] Фиг. 9 - блок-схема алгоритма, иллюстрирующая примерную операцию 900, выполненную приложением 104, когда приложение 104 запускается. Как проиллюстрировано в примере из фиг. 9, операция 900 начинается, когда запускается приложение 104 (этап 902). В различных вариантах осуществления приложение 104 запускается в ответ на различные события. Например, в некоторых вариантах осуществления приложение 104 запускается, когда пользователь 102 дает операционной системе в вычислительной системе 100 указание запустить приложение 104. В других вариантах осуществления приложение 104 запускается в ответ на запрос от другого приложения.

[0082] После того, как запускается приложение 104, приложение 104 считывает документ 106 из локальной или удаленной системы хранения данных в память (этап 904). В некоторых вариантах осуществления приложение 104 не сразу считывает документ 106 в память после запуска, а ожидает некоторого события перед считыванием документа 106. Например, приложение 104 может считать документ 106, когда приложение 104 принимает ввод от пользователя 102 для открытия документа 106. Когда приложение 104 считывает документ 106 в память, приложение 104 сохраняет элементы, которые представляют элементы документа в документе 106, в реальном массиве 304 элементов.

[0083] Далее приложение 104 формирует таблицу 302 дескрипторов фрагментов (этап 906). Как показано в примере из фиг. 3, таблица 302 дескрипторов фрагментов первоначально содержит только один дескриптор фрагмента. Затем приложение 104 формирует дерево 300 индексов (этап 908). Как показано в пример из фиг. 3, дерево 300 индексов первоначально содержит только один индексный узел. Атрибут дескриптора у индексного узла указывает дескриптор фрагмента в таблице 302 дескрипторов фрагментов.

[0084] После формирования таблицы 302 дескрипторов фрагментов и дерева 300 индексов приложение 104 устанавливает указатель текущего дерева, чтобы тот указывал единственный индексный узел в дереве 300 индексов (этап 910). Как описано ниже в отношении фиг. 19, потоки-считыватели 110 используют указатель текущего дерева для определения корневого индексного узла в последней доступной неактивной версии дерева 300 индексов.

[0085] После того, как приложение 104 задает указатель текущего дерева, приложение 104 инициирует ("пробуждает") поток-конструктор 108 (этап 912). Инициирование потока есть процесс побуждения потока начать работать. После того, как поток-конструктор 108 инициируется, поток-конструктор 108 может изменить активное представление документа 106 в ответ на пользовательский ввод для изменения документа 106.

[0086] Каждый раз, когда поток-конструктор 108 принимает ввод для изменения документа 106, поток-конструктор 108 выполняет операцию, которая формирует новое активное представление документа 106. После того, как поток-конструктор 108 завершает ту операцию, новое активное представление документа 106 становится неактивным представлением документа 106, которое доступно для использования потоками-считывателями 110. Например, в некоторых вариантах осуществления поток-конструктор 108 выполняет операции вставки элементов и операции удаления элементов. Каждый раз, когда поток-конструктор 108 выполняет операцию вставки элемента, поток-конструктор 108 формирует новое активное представление документа 106, в котором виртуальный массив 306 элементов включает в себя один или несколько дополнительных элементов. В конце операции вставки элемента новое активное представление документа 106 становится неактивным представлением документа 106, которое доступно для использования потоками-считывателями 110. Примерная реализация операции вставки элемента иллюстрируется на фиг. 10-13. Каждый раз, когда поток-конструктор 108 выполняет операцию удаления элемента, поток-конструктор 108 формирует новое активное представление документа 106, в котором виртуальный массив 306 элементов включает в себя меньше элементов. В конце операции удаления элемента новое активное представление документа 106 становится неактивным представлением документа 106, которое доступно для использования потоками-считывателями 110. Примерная реализация операции удаления элемента иллюстрируется на фиг. 14-18.

[0087] Далее приложение 104 инициирует один или несколько потоков-считывателей 110 (этап 914). Каждый из одного или нескольких потоков-считывателей 110 выполняет операцию, которая сначала проверяет указатель текущего дерева для определения корневого индексного узла в последней доступной неактивной версии дерева 300 индексов. На время операций, выполняемых потоками-считывателями 110, потоки-считыватели 110 используют тот индексный узел и индексные узлы, указанные атрибутами левого и правого потомков индексного узла, для доступа к элементам в реальном массиве 304 элементов. Другими словами, во время операций, выполняемых потоками-считывателями 110, потоки-считыватели 110 не начинают проверку поздних версий дерева 300 индексов. Потоки-считыватели 110 могут выполнять повторяющиеся операции. Когда повторяется операция, выполненная одним из потоков-считывателей 110, поток-считыватель снова может проверить указатель текущего дерева для определения корневого индексного узла в последней доступной неактивной версии дерева 300 индексов.

[0088] Поскольку поток-конструктор 108 и потоки-считыватели 110 могут выполняться одновременно, поскольку поток-конструктор 108 не изменяет неактивные представления документа 106, и поскольку потоки-считыватели 110 не считывают из активного представления документа 106, логическая связность неактивного представления документа 106 обеспечивается без блокирования данных в неактивном представлении документа 106. Следовательно, поток-конструктор 108 может удалить заданный элемент из активного представления документа 106, пока потоки-считыватели 110 одновременно считывают тот же заданный элемент из одного или нескольких неактивных представлений документа 106. В этом примере заданный элемент представляет один и тот же документ в дереве документа 106.

[0089] Фиг. 10 - блок-схема алгоритма, иллюстрирующая примерную операцию 1000 вставки элемента. Как проиллюстрировано в примере из фиг. 10, операция 1000 вставки элемента начинается, когда поток-конструктор 108 принимает ввод, указывающий, что элементы нужно вставить в документ 106 (этап 1002). В различных вариантах осуществления поток-конструктор 108 может принимать такой ввод различными способами. Например, поток-конструктор 108 может прослушивать клавиатурный ввод от пользователя приложения 104. В другом примере поток-конструктор 108 может прослушивать команды от другого потока приложения 104 или другого приложения для вставки элементов.

[0090] В ответ на прием ввода поток-конструктор 108 вставляет один или несколько элементов в реальный массив 304 элементов (этап 1004). Вставленные элементы становятся новым фрагментом реального массива 304 элементов. В различных вариантах осуществления поток-конструктор 108 вставляет элементы в реальный массив 304 элементов различными способами. Например, в некоторых вариантах осуществления поток-конструктор 108 вставляет открывающий элемент и закрывающий элемент в реальный массив 304 элементов по меньшей мере для некоторых типов элементов документа. В таких вариантах осуществления поток-конструктор 108 вставляет одиночный элемент в реальный массив 304 элементов для других типов элементов.

[0091] Далее поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал корневой индексный узел в последней доступной неактивной версии дерева 300 индексов (этап 1006). В этом описании изобретения текущий индексный узел является индексным узлом, указанным указателем текущего узла. Кроме того, в этом описании изобретения текущий дескриптор фрагмента является дескриптором фрагмента, указанным текущим индексным узлом. Кроме того, в этом описании изобретения текущий фрагмент является фрагментом реального массива 304 элементов, указанным текущим дескриптором фрагмента.

[0092] После задания указателя текущего узла поток-конструктор 108 определяет, меньше ли виртуальное смещение нового фрагмента, чем виртуальное смещение текущего фрагмента (этап 1008). Новый фрагмент является фрагментом реального массива 304 элементов, содержащим вставленные элементы. Виртуальное смещение нового фрагмента является расстоянием от начала виртуального массива 306 элементов до крайнего левого элемента среди вставленных элементов. Виртуальное смещение текущего фрагмента является расстоянием от начала виртуального массива 306 элементов до крайнего левого элемента в текущем фрагменте.

[0093] Если виртуальное смещение нового фрагмента меньше виртуального смещения текущего фрагмента ("ДА" на этапе 1008), то поток-конструктор 108 помещает текущий индексный узел в стек (этап 1010). В различных вариантах осуществления поток-конструктор 108 помещает текущий индексный узел в стек различными способами. Например, в некоторых вариантах осуществления поток-конструктор 108 помещает текущий индексный узел в стек путем помещения в стек указателя на текущий индексный узел.

[0094] После помещения текущего индексного узла в стек поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал левый потомок текущего индексного узла (этап 1012). В результате установки указателя текущего узла, чтобы тот указывал левый потомок текущего индексного узла, левый потомок текущего индексного узла становится "текущим" индексным узлом. Поток-конструктор 108 затем снова определяет, меньше ли виртуальное смещение нового фрагмента, чем виртуальное смещение текущего фрагмента (этап 1008). Поток-конструктор 108 продолжает повторять этапы 1010 и 1012 до тех пор, пока виртуальное смещение нового фрагмента меньше виртуального смещения текущего фрагмента.

[0095] Если виртуальное смещение нового фрагмента не меньше виртуального смещения текущего фрагмента ("НЕТ" на этапе 1008), то поток-конструктор 108 определяет, является ли виртуальное смещение нового фрагмента таким же, как виртуальное смещение текущего фрагмента (этап 1014). Если поток-конструктор 108 определяет, что виртуальное смещение нового фрагмента является таким же, как виртуальное смещение текущего фрагмента ("ДА" на этапе 1014), то поток-конструктор 108 выполняет операцию "A", проиллюстрированную на фиг. 11. После того, как поток-конструктор 108 выполняет операцию "A", поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 13, чтобы завершить операцию 1000 вставки элемента.

[0096] Если поток-конструктор 108 определяет, что виртуальное смещение нового фрагмента не является таким же, как виртуальное смещение текущего фрагмента ("НЕТ" на этапе 1014), то поток-конструктор 108 определяет, находится ли виртуальное смещение нового фрагмента в диапазоне виртуальных смещений текущего фрагмента (этап 1016). Если поток-конструктор 108 определяет, что виртуальное смещение нового фрагмента находится в диапазоне виртуальных смещений текущего фрагмента ("ДА" на этапе 1016), то поток-конструктор 108 выполняет операцию "B", проиллюстрированную на фиг. 12. После того, как поток-конструктор 108 выполняет операцию "B", поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 13, чтобы завершить операцию 1000 вставки элемента.

[0097] Если поток-конструктор 108 определяет, что виртуальное смещение нового фрагмента не находится в диапазоне виртуальных смещений текущего фрагмента ("НЕТ" на этапе 1016), то поток-конструктор 108 помещает текущий индексный узел в стек (этап 1018). После помещения текущего индексного узла в стек поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал правый потомок текущего индексного узла (этап 1020). В результате установки указателя текущего узла, чтобы тот указывал правый потомок текущего индексного узла, правый потомок текущего индексного узла становится "текущим" индексным узлом. После установки указателя текущего узла, чтобы тот указывал правый потомок текущего индексного узла, поток-конструктор 108 снова определяет, меньше ли виртуальное смещение нового фрагмента, чем виртуальное смещение текущего фрагмента (этап 1008), и так далее.

[0098] Фиг. 11 - блок-схема алгоритма, иллюстрирующая продолжение 1100 примерной операции 1000 вставки элемента. Как проиллюстрировано в примере из фиг. 11, продолжение 1100 запускается, когда поток-конструктор 108 клонирует текущий индексный узел (этап 1102). В этом описании изобретения всякий раз, когда поток-конструктор 108 "клонирует" текущий индексный узел, поток-конструктор 108 формирует новый индексный узел, в этом документе называемый клонированным текущим индексным узлом. Клонированный текущий индексный узел, по меньшей мере сначала, имеет такой же атрибут левого потомка, атрибут правого потомка и атрибут дескриптора, как и текущий индексный узел. Таким образом, если текущий индексный узел имеет левого потомка, то левый потомок текущего индексного узла становится левым потомком клонированного текущего индексного узла. Кроме того, если текущий индексный узел имеет правого потомка, то правый потомок текущего индексного узла становится правым потомком клонированного текущего индексного узла. Кроме того, когда поток-конструктор 108 клонирует текущий индексный узел, поток-конструктор 108 устанавливает атрибут дескриптора у клонированного текущего узла, чтобы тот указывал текущий дескриптор фрагмента.

[0099] После клонирования текущего индексного узла поток-конструктор 108 формирует новый индексный узел (этап 1104). Как и другие индексные узлы, новый индексный узел имеет атрибут левого потомка, атрибут правого потомка и атрибут дескриптора. Поток-конструктор 108 устанавливает атрибут левого потомка у нового индексного узла, чтобы тот указывал левый потомок текущего индексного узла (этап 1106). Таким образом, левый потомок текущего индексного узла становится левым потомком нового индексного узла.

[0100] Далее поток-конструктор 108 конфигурирует атрибут левого потомка у клонированного индексного узла, чтобы тот указывал новый индексный узел (этап 1108). Таким образом, новый индексный узел становится левым потомком клонированного текущего индексного узла.

[0101] Затем поток-конструктор 108 формирует новый дескриптор фрагмента (этап 1110). Новый дескриптор фрагмента указывает фрагмент реального массива 304 элементов, содержащий вставленные элементы. Поток-конструктор 108 затем устанавливает атрибут дескриптора у нового индексного узла, чтобы тот указывал новый дескриптор фрагмента (этап 1112).

[0102] Поток-конструктор 108 затем повторно балансирует текущее поддерево (этап 1114). После повторной балансировки текущего поддерева поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 13, чтобы завершить операцию 1000 вставки элемента. Текущее поддерево является сочетанием левого поддерева клонированного текущего индексного узла, клонированного текущего индексного узла и правого поддерева клонированного текущего индексного узла.

[0103] Когда текущее поддерево балансируется повторно, индексные узлы в текущем поддереве переставляются так, что глубина левого поддерева и глубина правого поддерева у каждого узла в дереве индексов отличаются не более чем на единицу. Кроме того, когда текущее поддерево балансируется повторно, текущее поддерево поддерживает свойство сортировки. Свойство сортировки предусматривает, что для каждого заданного индексного узла в текущем поддереве индексные узлы в левом поддереве заданного индексного узла ассоциируются с элементами, имеющими виртуальные смещения меньше виртуальных смещений элементов, ассоциированных с заданным индексным узлом, а индексные узлы в правом поддереве заданного индексного узла ассоциируются с элементами, имеющими виртуальные смещения больше виртуальных смещений элементов, ассоциированных с заданным индексным узлом. В данной области техники известно несколько существующих алгоритмов "вращения дерева" для повторной балансировки деревьев AVL, например текущего дерева индексов.

[0104] Чтобы переставить индексные узлы в текущем дереве во время процесса повторной балансировки, поток-конструктор 108 изменяет атрибуты левого или правого потомков у некоторого из индексных узлов в текущем поддереве. Если потоку-конструктору 108 требуется изменить атрибуты левого или правого потомков у заданного индексного узла в текущем поддереве, то поток-конструктор 108 клонирует заданный индексный узел перед изменением атрибутов левого или правого потомков у заданного индексного узла.

[0105] Фиг. 12 - блок-схема алгоритма, иллюстрирующая продолжение 1200 примерной операции 1000 вставки элемента. Как проиллюстрировано в примере из фиг. 12, продолжение 1200 запускается, когда поток-конструктор 108 клонирует текущий индексный узел (этап 1202). Поток-конструктор 108 затем формирует первый новый индексный узел (этап 1204). Если существует левый потомок текущего индексного узла, то поток-конструктор 108 конфигурирует атрибут левого потомка у первого нового индексного узла, чтобы тот указывал левый потомок текущего индексного узла (этап 1206). Таким образом, левый потомок текущего индексного узла становится левым потомком первого нового индексного узла. Поток-конструктор 108 затем конфигурирует атрибут левого потомка у клонированного текущего индексного узла, чтобы тот указывал первый новый индексный узел (этап 1208). Таким образом, первый новый индексный узел становится левым потомком клонированного текущего индексного узла.

[0106] Далее поток-конструктор 108 клонирует текущий дескриптор фрагмента (этап 1212). Когда поток-конструктор 108 клонирует текущий дескриптор фрагмента, поток-конструктор 108 формирует новый дескриптор фрагмента, в этом документе называемый клонированным текущим дескриптором фрагмента. Клонированный текущий дескриптор фрагмента первоначально имеет такой же атрибут смещения и атрибут длины, как и текущий дескриптор фрагмента. Поток-конструктор 108 изменяет клонированный текущий дескриптор фрагмента (этап 1212). Поток-конструктор 108 изменяет клонированный текущий дескриптор фрагмента так, что текущий фрагмент ограничивается элементами, имеющими виртуальные смещения, которые меньше виртуальных смещений вставленных элементов. Например, если текущий фрагмент включал в себя элементы, имеющие реальные смещения от 10 до 20, то атрибут длины у текущего дескриптора фрагмента равен 21. В этом примере вставленные элементы имеют виртуальные смещения между виртуальными смещениями элементов, имеющих реальные смещения 15 и 16. Следовательно, в этом примере поток-конструктор 108 изменяет атрибут длины у клонированного текущего дескриптора фрагмента так, что атрибут длины имеет значение 6 вместо 21. Поток-конструктор 108 затем конфигурирует атрибут дескриптора у первого нового индексного узла, чтобы тот указывал клонированный текущий дескриптор фрагмента (этап 1214).

[0107] Далее поток-конструктор 108 формирует первый новый дескриптор фрагмента (этап 1216). Первый новый дескриптор фрагмента указывает текущий фрагмент. Поток-конструктор 108 затем конфигурирует атрибут дескриптора у клонированного текущего индексного узла, чтобы тот указывал первый новый дескриптор фрагмента (этап 1218).

[0108] Поток-конструктор 108 затем формирует второй новый индексный узел (этап 1220). Если существует правый потомок текущего индексного узла, то поток-конструктор 108 конфигурирует второй новый индексный узел так, что правый потомок текущего индексного узла является правым потомком второго нового индексного узла (этап 1222). Далее поток-конструктор 108 конфигурирует атрибут правого потомка у клонированного текущего индексного узла так, что атрибут правого потомка у клонированного текущего индексного узла указывает второй новый индексный узел (этап 1224).

[0109] Затем поток-конструктор 108 формирует второй новый дескриптор фрагмента (этап 1226). Второй новый дескриптор фрагмента указывает элементы, которые ранее находились в текущем фрагменте и которые имеют виртуальные смещения больше виртуальных смещений вставленных элементов. Например, если текущий фрагмент включал в себя элементы, имеющие реальные смещения от 10 до 20, и крайний левый вставленный элемент имеет виртуальное смещение между виртуальными смещениями элементов, имеющих реальные смещения 15 и 16, то второй новый дескриптор фрагмента имеет атрибут смещения, равный 16, и атрибут длины, равный 5. В этом примере элементы, имеющие реальные смещения между 16 и 20, являются элементами, которые ранее находились в текущем фрагменте и которые имеют виртуальные смещения больше виртуальных смещений вставленных элементов.

[0110] Поток-конструктор 108 затем конфигурирует атрибут дескриптора у второго нового индексного узла, чтобы тот указывал второй новый дескриптор фрагмента (этап 1228). После конфигурирования атрибута дескриптора у второго нового индексного узла, чтобы тот указывал второй новый дескриптор фрагмента, поток-конструктор 108 повторно балансирует текущее поддерево по необходимости (этап 1230). После повторной балансировки текущего поддерева поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 13, чтобы завершить операцию 1000 вставки элемента.

[0111] Фиг. 13 - блок-схема алгоритма, иллюстрирующая продолжение 1300 примерной операции 1000 вставки элемента. Как проиллюстрировано в примере из фиг. 13, продолжение 1300 начинается, когда поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал клонированный текущий индексный узел (этап 1302). Таким образом, клонированный текущий индексный узел становится "текущим" индексным узлом.

[0112] Далее поток-конструктор 108 определяет, есть ли какие-нибудь индексные узлы в стеке (этап 1304). Если имеется один или несколько индексных узлов в стеке, то поток-конструктор 108 извлекает индексный узел из стека (этап 1306). Поток-конструктор 108 затем клонирует извлеченный из стека индексный узел (этап 1308). Когда поток-конструктор 108 клонирует извлеченный из стека индексный узел, поток-конструктор 108 формирует новый индексный узел, в этом документе называемый клонированным извлеченным из стека индексным узлом. Когда поток-конструктор 108 клонирует извлеченный из стека индексный узел, атрибут левого потомка, атрибут правого потомка и атрибут дескриптора у клонированного извлеченного из стека индексного узла являются такими же, как атрибут левого потомка, атрибут правого потомка и дескриптор у извлеченного из стека индексного узла.

[0113] После клонирования извлеченного из стека индексного узла поток-конструктор 108 определяет, меньше ли виртуальное смещение фрагмента, ассоциированного с извлеченным из стека индексным узлом, виртуального смещения фрагмента, ассоциированного с текущим индексным узлом (этап 1310). Если виртуальное смещение фрагмента, ассоциированного с извлеченным из стека индексным узлом, меньше виртуального смещения фрагмента, ассоциированного с текущим индексным узлом ("ДА" на этапе 1310), то поток-конструктор 108 устанавливает атрибут левого потомка у клонированного извлеченного из стека индексного узла, чтобы тот указывал текущий индексный узел (этап 1312). Таким образом, текущий индексный узел становится левым потомком клонированного извлеченного из стека индексного узла.

[0114] В противном случае, если виртуальное смещение фрагмента, ассоциированного с извлеченным из стека индексным узлом, не меньше (то есть больше) виртуального смещения фрагмента, ассоциированного с текущим индексным узлом ("НЕТ" на этапе 1310), то поток-конструктор 108 устанавливает атрибут правого потомка у клонированного извлеченного из стека индексного узла, чтобы тот указывал текущий индексный узел (этап 1314). Таким образом, текущий индексный узел становится правым потомком клонированного извлеченного из стека индексного узла.

[0115] После установки атрибутов левого или правого потомков у клонированного извлеченного из стека индексного узла поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал клонированный извлеченный из стека индексный узел (этап 1316). Таким образом, клонированный извлеченный из стека индексный узел становится "текущим" индексным узлом. После установки указателя текущего узла, чтобы тот указывал клонированный извлеченный из стека индексный узел, поток-конструктор 108 снова определяет, есть ли какие-нибудь индексные узлы в стеке (этап 1304). Если в стеке имеются индексные узлы, то поток-конструктор 108 повторяет этапы 1306, 1308, 1310, 1312 либо 1314, 1316 и 1318. В противном случае, если индексные узлы в стеке отсутствуют, то поток-конструктор 108 устанавливает указатель текущего дерева, чтобы тот указывал текущий индексный узел (этап 1320). После установки указателя текущего дерева, чтобы тот указывал текущий индексный узел, операция 1000 вставки элемента завершается. Кроме того, после того как поток-конструктор 108 устанавливает указатель текущего дерева, активное представление документа 106 становится последним доступным неактивным представлением документа 106.

[0116] Фиг. 14 - блок-схема алгоритма, иллюстрирующая примерную операцию 1400 удаления элемента. Как проиллюстрировано в примере из фиг. 14, операция 1400 удаления элемента начинается, когда поток-конструктор 108 принимает ввод, указывающий, что элементы нужно удалить из документа 106 (этап 1402).

[0117] В ответ на прием этого ввода поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал корневой индексный узел в последней доступной неактивной версии дерева 300 индексов (этап 1404). Другими словами, поток-конструктор 108 устанавливает указатель текущего узла равным указателю текущего дерева.

[0118] Далее поток-конструктор 108 определяет, меньше ли виртуальное смещение крайнего левого удаленного элемента, чем виртуальное смещение текущего фрагмента (этап 1406). Текущий фрагмент является фрагментом реального массива 304 элементов, указанного дескриптором фрагмента, указанного текущим индексным узлом. Если виртуальное смещение крайнего левого удаленного элемента меньше виртуального смещения текущего фрагмента ("ДА" на этапе 1406), то поток-конструктор 108 помещает текущий индексный узел в стек (этап 1408). После помещения текущего индексного узла в стек поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал левый потомок текущего индексного узла (этап 1410). Таким образом, левый потомок текущего индексного узла становится "текущим" индексным узлом. После задания указателя текущего узла поток-конструктор 108 снова определяет, меньше ли виртуальное смещение крайнего левого удаленного элемента, чем виртуальное смещение текущего фрагмента (этап 1406). Поток-конструктор 108 продолжает повторять этапы 1408 и 1410 до тех пор, пока виртуальное смещение крайнего левого удаленного элемента меньше виртуального смещения текущего фрагмента.

[0119] Если виртуальное смещение крайнего левого удаленного элемента не меньше виртуального смещения текущего фрагмента ("НЕТ" на этапе 1406), то поток-конструктор 108 определяет, является ли виртуальное смещение крайнего левого удаленного элемента таким же, как виртуальное смещение текущего фрагмента (этап 1412). Если поток-конструктор 108 определяет, что виртуальное смещение крайнего левого удаленного элемента является таким же, как виртуальное смещение текущего фрагмента ("ДА" на этапе 1412), то поток-конструктор 108 выполняет операцию "A", проиллюстрированную на фиг. 15. После того, как поток-конструктор 108 выполняет операцию "A", поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0120] Если поток-конструктор 108 определяет, что виртуальное смещение крайнего левого удаленного элемента не является таким же, как виртуальное смещение текущего фрагмента ("НЕТ" на этапе 1412), то поток-конструктор 108 определяет, находится ли крайний левый удаленный элемент в диапазоне виртуальных смещений текущего фрагмента (этап 1414). Если поток-конструктор 108 определяет, что виртуальное смещение крайнего левого удаленного элемента находится в диапазоне виртуальных смещений текущего фрагмента ("ДА" на этапе 1414), то поток-конструктор 108 выполняет операцию "B", проиллюстрированную на фиг. 16. После того, как поток-конструктор 108 выполняет операцию "B", поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0121] В противном случае, если поток-конструктор 108 определяет, что виртуальное смещение крайнего левого удаленного элемента не находится в диапазоне виртуальных смещений текущего фрагмента ("НЕТ" на этапе 1414), то поток-конструктор 108 помещает текущий индексный узел в стек (этап 1416). Поток-конструктор 108 затем устанавливает указатель текущего узла, чтобы тот указывал правый потомок текущего индексного узла (этап 1418). Таким образом, правый потомок текущего индексного узла становится "текущим" индексным узлом. После установки указателя текущего узла, чтобы тот указывал правый потомок текущего индексного узла, поток-конструктор 108 определяет, меньше ли виртуальное смещение крайнего левого удаленного элемента, чем виртуальное смещение текущего фрагмента (этап 1406). Поток-конструктор 108 продолжает выполнять этапы 1406, 1408, 1410, 1412, 1414, 1416 и 1418 до тех пор, пока либо виртуальное смещение крайнего левого удаленного элемента не является таким же, как виртуальное смещение текущего фрагмента, либо виртуальное смещение крайнего левого удаленного элемента не находится в диапазоне виртуальных смещений текущего фрагмента.

[0122] Фиг. 15 - блок-схема алгоритма, иллюстрирующая продолжение 1500 примерной операции 1400 удаления элемента. Как проиллюстрировано в примере из фиг. 15, продолжение 1500 запускается, когда поток-конструктор 108 определяет, являются ли удаленные элементы всеми элементами в текущем фрагменте (этап 1502).

[0123] Если удаленные элементы не являются всеми элементами в текущем фрагменте ("НЕТ" на этапе 1502), то поток-конструктор 108 клонирует текущий дескриптор фрагмента (этап 1504). Когда поток-конструктор 108 клонирует текущий дескриптор фрагмента, поток-конструктор 108 формирует новый дескриптор фрагмента, в этом документе называемый клонированным текущим дескриптором фрагмента. Клонированный текущий дескриптор фрагмента первоначально имеет такой же атрибут смещения и атрибут длины, как и текущий дескриптор фрагмента.

[0124] Поток-конструктор 108 затем изменяет атрибут смещения у клонированного текущего дескриптора фрагмента так, что атрибут реального смещения указывает, что текущий фрагмент начинается с виртуального смещения крайнего левого элемента в текущем фрагменте после крайнего правого удаленного элемента (этап 1506). Например, если текущий фрагмент включает в себя элементы с реальными смещениями от 10 до 20, и элементы с реальными смещениями 10 и 11 нужно удалить из активного представления документа 106, то поток-конструктор 108 изменяет атрибут реального смещения у текущего дескриптора фрагмента так, что атрибут реального смещения равен 12. Это сценарий, проиллюстрированный в примере из фиг. 4.

[0125] Поток-конструктор 108 затем клонирует текущий индексный узел (этап 1508). После клонирования текущего индексного узла поток-конструктор 108 конфигурирует атрибут дескриптора у клонированного текущего индексного узла, чтобы тот указывал клонированный текущий дескриптор фрагмента (этап 1510). Поток-конструктор 108 затем устанавливает указатель текущего узла, чтобы тот указывал клонированный текущий индексный узел (этап 1512). После установки указателя текущего узла поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0126] В противном случае, если удаленные элементы являются всеми элементами в текущем фрагменте ("ДА" на этапе 1502), то поток-конструктор 108 определяет, имеет ли текущий индексный узел левого потомка (этап 1514). Если текущий индексный узел имеет левого потомок ("ДА" на этапе 1514), то поток-конструктор 108 выполняет операцию "D", проиллюстрированную на фиг. 16, а затем выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0127] С другой стороны, если текущий индексный узел не имеет левого потомка ("НЕТ" на этапе 1514), то поток-конструктор 108 определяет, имеет ли текущий индексный узел правого потомка (этап 1516). Если поток-конструктор 108 определяет, что текущий индексный узел имеет правого потомка ("ДА" на этапе 1516), то поток-конструктор 108 клонирует текущий индексный узел (этап 1518). После клонирования текущего индексного узла поток-конструктор 108 конфигурирует атрибут дескриптора у клонированного текущего индексного узла, чтобы тот указывал дескриптор фрагмента, указанный правым потомком текущего индексного узла (этап 1520). Поток-конструктор 108 затем конфигурирует атрибут правого потомка у клонированного текущего индексного узла, чтобы тот указывал отсутствие индексного узла (этап 1522). Поток-конструктор 108 затем устанавливает указатель текущего узла, чтобы тот указывал клонированный текущий индексный узел (этап 1512). После установки указателя текущего узла поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0128] Если текущий индексный узел не имеет правого потомка ("НЕТ" на этапе 1516), то поток-конструктор 108 извлекает индексный узел из стека (этап 1524). Извлеченный из стека индексный узел является родительским элементом текущего индексного узла. Поток-конструктор 108 затем клонирует извлеченный из стека индексный узел (этап 1526). Далее поток-конструктор 108 конфигурирует клонированный извлеченный из стека индексный узел, чтобы тот не указывал текущий индексный узел (этап 1528). Таким образом, поток-конструктор 108 удаляет текущий индексный узел из активного представления документа 106. Поток-конструктор 108 затем устанавливает указатель текущего узла, чтобы тот указывал клонированный извлеченный из стека индексный узел (этап 1530). Таким образом, клонированный извлеченный из стека индексный узел становится "текущим" индексным узлом. Поток-конструктор 108 затем выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0129] Фиг. 16 - блок-схема алгоритма, иллюстрирующая продолжение 1600 операции 1400 удаления элемента. Как проиллюстрировано в примере из фиг. 16, продолжение 1600 начинается, когда поток-конструктор 108 клонирует текущий индексный узел (этап 1602). Далее поток-конструктор 108 определяет, имеется ли только один узел в левом поддереве текущего индексного узла (этап 1604). Если имеется только один узел в левом поддереве текущего индексного узла ("ДА" на этапе 1604), то поток-конструктор 108 конфигурирует атрибут дескриптора у клонированного текущего индексного узла, чтобы тот указывал дескриптор фрагмента, указанный левым потомком текущего индексного узла (этап 1606). Таким образом, поток-конструктор 108 удаляет текущий дескриптор фрагмента из активной версии таблицы 302 дескрипторов фрагментов. Далее поток-конструктор 108 конфигурирует атрибут левого потомка у клонированного текущего индексного узла, чтобы тот указывал отсутствие другого индексного узла (этап 1608). Таким образом, поток-конструктор 108 удаляет левый потомок из активной версии дерева 300 индексов.

[0130] Если имеется более одного индексного узла в левом поддереве текущего индексного узла ("НЕТ" на этапе 1604), то поток-конструктор 108 конфигурирует атрибут дескриптора у клонированного текущего индексного узла, чтобы тот указывал дескриптор фрагмента, указанный крайним правым индексным узлом в левом поддереве текущего индексного узла (этап 1610). Таким образом, поток-конструктор 108 удаляет дескриптор фрагмента, первоначально указанный текущим индексным узлом, из активной версии таблицы 302 дескрипторов фрагментов. Для простоты объяснения это описание изобретения ссылается на крайний правый индексный узел в левом поддереве текущего индексного узла как на "крайний правый индексный узел". Далее поток-конструктор 108 клонирует предшествующие индексные узлы у крайнего правого индексного узла ниже текущего индексного узла (этап 1612). Например, если имеется три индексных узла в дереве 300 индексов между текущим индексным узлом и крайним правым индексным узлом, то поток-конструктор 108 клонирует эти три индексных узла.

[0131] После клонирования предшествующих индексных узлов поток-конструктор 108 конфигурирует атрибут правого потомка у родительского элемента крайнего правого индексного узла, чтобы тот не указывал никакой индексный узел (этап 1614). Таким образом, крайний правый индексный узел удаляется из активной версии дерева 300 индексов. Поток-конструктор 108 затем соединяет клонированные предшествующие индексные узлы крайнего правого индексного узла (этап 1616). Например, если имеется три индексных узла в дереве 300 индексов между текущим индексным узлом и крайним правым индексным узлом, то поток-конструктор 108 конфигурирует атрибуты левого или правого потомков у клонов этих трех индексных узлов так, что клоны этих трех индексных узлов имеют такие же отношения родитель-потомок, как и эти три индексных узла.

[0132] Поток-конструктор 108 затем устанавливает указатель текущего узла, чтобы тот указывал клонированный текущий индексный узел (этап 1618). После установки указателя текущего узла поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0133] Фиг. 17 - блок-схема алгоритма, иллюстрирующая дальнейшее продолжение 1700 операции 1400 удаления элемента. Как проиллюстрировано в примере из фиг. 17, продолжение 1700 начинается, когда поток-конструктор 108 клонирует текущий дескриптор фрагмента (этап 1702). Как обсуждалось выше, текущий дескриптор фрагмента является дескриптором фрагмента, указанным текущим индексным узлом. Когда поток-конструктор 108 клонирует текущий дескриптор фрагмента, поток-конструктор 108 формирует новый дескриптор фрагмента, в этом документе называемый клонированным текущим дескриптором фрагмента. По меньшей мере в начале клонированный текущий дескриптор фрагмента имеет такой же атрибут смещения и атрибут длины, как и текущий дескриптор фрагмента. Далее поток-конструктор 108 клонирует текущий индексный узел (этап 1704).

[0134] Поток-конструктор 108 затем определяет, имеются ли элементы в текущем фрагменте, имеющие виртуальные смещения больше виртуального смещения удаленных элементов (этап 1706). Если нет элементов в текущем фрагменте, имеющих виртуальные смещения больше виртуальных смещений удаленных элементов ("НЕТ" на этапе 1706), то поток-конструктор 108 изменяет атрибут длины у клонированного текущего дескриптора фрагмента (этап 1708). Поток-конструктор 108 изменяет атрибут длины у клонированного текущего дескриптора фрагмента, чтобы тот указывал фрагмент реального массива 304 элементов, который не продолжается до крайнего левого удаленного элемента. Например, если текущий фрагмент включает в себя элементы, имеющие реальные смещения от 10 до 20, и элементы с реальными смещениями 19 и 20 нужно удалить из активного представления документа 106, то поток-конструктор 108 изменяет атрибут длины у клонированного текущего дескриптора фрагмента так, что атрибут длины равен 9 вместо 11. После изменения атрибута длины у клонированного текущего дескриптора фрагмента поток-конструктор 108 выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0135] Далее поток-конструктор 108 конфигурирует атрибут дескриптора у клонированного текущего индексного узла, чтобы тот указывал клонированный текущий дескриптор фрагмента (этап 1710). Таким образом, клонированный текущий дескриптор фрагмента становится дескриптором фрагмента, указанным клонированным текущим индексным узлом. После конфигурирования атрибута дескриптора у клонированного текущего индексного узла, чтобы тот указывал клонированный текущий дескриптор фрагмента, поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал клонированный текущий индексный узел (этап 1712). Поток-конструктор 108 затем выполняет операцию "C", проиллюстрированную в примере из фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0136] В противном случае, если имеется один или несколько элементов в текущем фрагменте, имеющих виртуальные смещения больше виртуальных смещений удаленных элементов ("ДА" на этапе 1706), то поток-конструктор 108 изменяет атрибут длины у клонированного текущего дескриптора фрагмента так, что клонированный текущий дескриптор фрагмента указывает фрагмент реального массива 304 элементов, который продолжается только вплоть до крайнего левого удаленного элемента (этап 1714). Например, если текущий фрагмент включал в себя элементы, имеющие реальные смещения от 10 до 20, и элементы, имеющие реальные смещения 15 и 16, нужно удалить из активного представления документа 106, то поток-конструктор 108 изменяет атрибут длины у клонированного текущего дескриптора фрагмента так, что атрибут длины равен 5.

[0137] После изменения атрибута длины у клонированного текущего дескриптора фрагмента поток-конструктор 108 формирует новый индексный узел (этап 1716). Если текущий индексный узел имеет левого потомка, то поток-конструктор 108 затем конфигурирует атрибут левого потомка у нового индексного узла, чтобы тот указывал левый потомок текущего индексного узла (этап 1718). Таким образом, левый потомок текущего индексного узла становится левым потомком нового индексного узла. Поток-конструктор 108 затем конфигурирует атрибут дескриптора у нового индексного узла, чтобы тот указывал клонированный текущий дескриптор фрагмента (этап 1720). Таким образом, клонированный текущий дескриптор фрагмента становится дескриптором фрагмента, указанным новым индексным узлом.

[0138] Затем поток-конструктор 108 формирует новый дескриптор фрагмента (этап 1722). Новый дескриптор фрагмента указывает фрагмент реального массива 304 элементов, содержащий элементы, которые были частью текущего фрагмента, имеющие виртуальные смещения больше виртуальных смещений удаленных элементов. Например, если текущий фрагмент включал в себя элементы, имеющие реальные смещения от 10 до 20, а удаленные элементы являются элементами, имеющими реальные смещения 15 и 16, то новый дескриптор фрагмента имеет атрибут реального смещения, равный 17, и атрибут длины, равный 4.

[0139] Далее поток-конструктор 108 конфигурирует атрибут дескриптора у клонированного текущего индексного узла, чтобы тот указывал новый дескриптор фрагмента (этап 1724). Поток-конструктор 108 затем конфигурирует атрибут левого потомка у клонированного текущего индексного узла, чтобы тот указывал новый индексный узел (этап 1726). Таким образом, новый индексный узел становится левым потомком клонированного текущего индексного узла. Поток-конструктор 108 затем повторно балансирует текущее поддерево (этап 1728). После повторной балансировки текущего поддерева поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал корневой узел текущего поддерева (этап 1730). Поток-конструктор 108 затем выполняет операцию "C", проиллюстрированную на фиг. 18, чтобы завершить операцию 1400 удаления элемента.

[0140] Фиг. 18 - блок-схема алгоритма, иллюстрирующая дальнейшее продолжение 1800 операции 1400 удаления элемента. Как проиллюстрировано в примере из фиг. 18, продолжение 1800 начинается, когда поток-конструктор 108 определяет, есть ли какие-нибудь индексные узлы в стеке (этап 1802).

[0141] Если в стеке есть индексные узлы ("ДА" на этапе 1802), то поток-конструктор 108 извлекает индексный узел из стека (этап 1804). Поток-конструктор 108 затем клонирует извлеченный из стека индексный узел (этап 1806). Когда поток-конструктор 108 клонирует извлеченный из стека индексный узел, поток-конструктор 108 формирует новый индексный узел, в этом документе называемый клонированным извлеченным из стека индексным узлом. Когда поток-конструктор 108 клонирует извлеченный из стека индексный узел, атрибут левого потомка, атрибут правого потомка и атрибут дескриптора у клонированного извлеченного из стека индексного узла имеют такие же значения, как атрибут левого потомка, атрибут правого потомка и атрибут дескриптора у извлеченного из стека индексного узла.

[0142] После клонирования извлеченного из стека индексного узла поток-конструктор 108 определяет, меньше ли виртуальное смещение фрагмента, ассоциированного с извлеченным из стека индексным узлом, виртуального смещения фрагмента, ассоциированного с текущим индексным узлом (этап 1808). Если виртуальное смещение фрагмента, ассоциированного с извлеченным из стека индексным узлом, меньше виртуального смещения фрагмента, ассоциированного с текущим индексным узлом ("ДА" на этапе 1808), то поток-конструктор 108 устанавливает атрибут левого потомка у клонированного извлеченного из стека индексного узла, чтобы тот указывал текущий индексный узел (этап 1810). Таким образом, текущий узел становится левым потомком клонированного извлеченного из стека индексного узла.

[0143] В противном случае, если виртуальное смещение фрагмента, ассоциированного с извлеченным из стека индексным узлом, не меньше (то есть больше) виртуального смещения фрагмента, ассоциированного с текущим индексным узлом ("НЕТ" на этапе 1808), то поток-конструктор 108 устанавливает атрибут правого потомка у клонированного извлеченного из стека индексного узла, чтобы тот указывал текущий индексный узел (этап 1812). Таким образом, текущий индексный узел становится правым потомком клонированного извлеченного из стека индексного узла.

[0144] После установки атрибутов левого или правого потомков у клонированного извлеченного из стека индексного узла поток-конструктор 108 устанавливает указатель текущего узла, чтобы тот указывал клонированный извлеченный из стека индексный узел (этап 1814). Таким образом, клонированный извлеченный из стека индексный узел становится "текущим" индексным узлом. После установки указателя текущего узла, чтобы тот указывал клонированный извлеченный из стека индексный узел, поток-конструктор 108 снова определяет, есть ли какие-нибудь индексные узлы в стеке (этап 1802). Если в стеке имеются индексные узлы, то поток-конструктор 108 повторяет этапы 1804, 1806, 1808, 1810 либо 1812, 1814 и 1816. В противном случае, если индексные узлы в стеке отсутствуют, то поток-конструктор 108 устанавливает указатель текущего дерева, чтобы тот указывал текущий индексный узел (этап 1818). После установки указателя текущего дерева, чтобы тот указывал текущий индексный узел, операция 1400 удаления элемента завершается. Кроме того, после того как поток-конструктор 108 устанавливает указатель текущего дерева, активное представление документа 106 становится последним доступным неактивным представлением документа 106.

[0145] Фиг. 19 - блок-схема алгоритма, иллюстрирующая примерную операцию 1900 потока-считывателя 110A. Хотя операция 1900 описывается со ссылкой на поток-считыватель 110A, операция 1900 может выполняться любым из потоков-считывателей 110.

[0146] Операция 1900 потока-считывателя 110A начинается, когда приложение 104 инициирует поток-считыватель 110A. Когда инициируется поток-считыватель 110A, поток-считыватель 110A определяет, существует ли текущее неактивное дерево индексов (этап 1902). Текущее неактивное дерево индексов является деревом индексов, указанным указателем текущего дерева. Поскольку указатель текущего дерева указывает последнюю доступную неактивную версию дерева индексов, текущее дерево индексов является последней доступной неактивной версией дерева индексов. Поток-считыватель 110A определяет, что текущее дерево индексов не существует, когда указатель текущего дерева содержит пустое значение. Если текущее дерево индексов не существует ("НЕТ" на этапе 1904), то поток-считыватель 110A впоследствии снова определяет, существует ли текущее дерево индексов (этап 1904). Поток-считыватель 110A продолжает определять, существует ли текущее дерево индексов, до тех пор, пока не существует текущее дерево индексов.

[0147] Если поток-считыватель 110A определяет, что текущее дерево индексов существует ("ДА" на этапе 1904), то поток-считыватель 110A определяет, имеет ли текущее дерево индексов корневой индексный узел (этап 1906). В некоторых вариантах осуществления текущее дерево индексов является программным объектом, который может содержать индексные узлы. В таких вариантах осуществления текущее дерево индексов может существовать, когда создается экземпляр такого программного объекта, независимо от того, содержит ли программный объект какие-нибудь индексные узлы. Если текущее дерево индексов не имеет корневого индексного узла ("НЕТ" на этапе 1906), то поток-считыватель 110A впоследствии снова определяет, имеет ли текущее дерево индексов корневой индексный узел (этап 1906). Поток-считыватель 110A продолжает определять, имеет ли текущее дерево индексов корневой индексный узел, до тех пор, пока текущее дерево индексов не имеет корневого индексного узла.

[0148] Если текущее дерево индексов имеет корневой индексный узел, то поток-считыватель 110A устанавливает указатель считывания, чтобы тот указывал корневой индексный узел текущего дерева индексов (этап 1908). При использовании в данном документе корневой узел считывания является индексным узлом, указанным указателем считывания. Поток-считыватель 110A затем выполняет симметричный обход в глубину индексных узлов в дереве индексов считывания (этап 1910). Дерево индексов считывания является деревом индексов, корнем которого является корневой узел считывания. Когда поток-считыватель 110A обходит индексные узлы в дереве индексов считывания, поток-считыватель 110A может выполнять различные действия над элементами, ассоциированными с теми индексными узлами. Например, поток-считыватель 110A может выполнять операцию проверки орфографии, которая проверяет орфографию слов в элементах, ассоциированных с индексными узлами. В другом примере поток-считыватель 110A может обновить поисковый индекс на основе слов в элементах, ассоциированных с индексными узлами. В еще одном примере поток-считыватель 110A может записывать (например, сохранять) элементы в локальное или удаленное место хранения. Поскольку поток-считыватель 110A может работать одновременно с потоком-конструктором 108, пользователь 102 мог бы не ощущать никакой задержки или снижения производительности потока-конструктора 108 из-за работы потока-считывателя 110A.

[0149] После выполнения полного обхода индексных узлов в дереве индексов считывания поток-считыватель 110A определяет, завершена ли работа потока-считывателя 110A (этап 1912). Если работа потока-считывателя 110A завершена ("ДА" на этапе 1912), то поток-считыватель 110A переходит в режим ожидания (этап 1914).

[0150] В противном случае, если работа потока-считывателя 110A не завершена ("НЕТ" на этапе 1912), то поток-считыватель 110A устанавливает указатель считывания, чтобы тот указывал корневой индексный узел в текущем дереве индексов (этап 1908). Когда поток-считыватель 110A обходит индексные узлы в дереве индексов считывания, поток-конструктор 108 может исполняться одновременно, выполняя операции вставки элементов и/или удаления элементов. Поскольку поток-конструктор 108 не изменяет атрибуты никакого индексного узла в дереве индексов считывания, гарантируется логическая связность операций считывания из дерева индексов считывания. Однако поток-конструктор 108 может обновить указатель текущего дерева, чтобы тот указывал другое дерево индексов. Поэтому, когда поток-считыватель 110A устанавливает указатель считывания, чтобы тот указывал корневой индексный узел в текущем дереве индексов, текущее дерево индексов может быть иным деревом индексов, нежели дерево индексов считывания, которое только что обходил поток-считыватель 110A. Таким образом, поток-считыватель 110A начинает обход самого последнего дерева индексов.

[0151] Фиг. 20 - блок-схема, иллюстрирующая примерное вычислительное устройство 2000. В некоторых вариантах осуществления вычислительная система 100 реализуется с использованием одного или нескольких вычислительных устройств типа вычислительного устройства 2000. Следует принять во внимание, что в других вариантах осуществления вычислительная система 100 реализуется с использованием вычислительных устройств, имеющих аппаратные компоненты, отличные от проиллюстрированных в примере из фиг. 20.

[0152] Вычислительная система является системой, содержащей одно или несколько вычислительных устройств. Вычислительное устройство является физическим устройством, допускающим обработку информации. Примерные типы вычислительных устройств включают в себя настольные компьютеры, переносные компьютеры, изолированные серверы, blade-серверы, мобильные телефоны, персональные мультимедийные проигрыватели, игровые приставки, компьютеры, интегрированные в транспортные средства, телевизионные приставки, промежуточные сетевые устройства и другие типы физических устройств, которые допускают обработку информации.

[0153] В разных вариантах осуществления вычислительные устройства реализуются разными способами. Например, в примере из фиг. 20 вычислительное устройство 2000 содержит запоминающее устройство 2002, систему 2004 обработки, вспомогательное запоминающее устройство 2006, сетевую интерфейсную плату 2008, видеоинтерфейс 2010, устройство 2012 отображения, интерфейс 2014 внешних компонентов, внешнее запоминающее устройство 2016, устройство 2018 ввода, принтер 2020 и средства 2022 связи. В других вариантах осуществления вычислительные устройства реализуются с использованием большего или меньшего количества аппаратных компонентов. Например, в другом примерном варианте осуществления вычислительное устройство не включает в себя видеоинтерфейс, устройство отображения, внешнее запоминающее устройство или устройство ввода.

[0154] Запоминающее устройство 2002 является системой хранения данных. Система хранения данных является системой, которая содержит один или несколько машиночитаемых носителей информации. Машиночитаемый носитель информации является материальным устройством или изделием, которое хранит данные и/или исполняемые компьютером команды, считываемые вычислительным устройством. В разных вариантах осуществления запоминающее устройство 2002 реализуется разными способами. Например, в различных вариантах осуществления запоминающее устройство 2002 реализуется с использованием различных типов машиночитаемых носителей информации. Примерные типы машиночитаемых носителей информации включают в себя, но не ограничиваются, динамическое оперативное запоминающее устройство (DRAM), синхронное динамическое оперативное запоминающее устройство с удвоенной скоростью передачи данных (DDR SDRAM), DRAM с сокращенным временем ожидания, DDR2 SDRAM, DDR3 SDRAM, Rambus RAM, твердотельное запоминающее устройство, флэш-память, постоянное запоминающее устройство (ROM), электрически стираемое программируемое ROM и другие типы устройств и/или изделий, которые хранят данные.

[0155] Система 2004 обработки является системой, содержащей один или несколько блоков обработки. Блоки обработки включают в себя одну или несколько физических интегральных схем, которые выборочно исполняют программные команды. В различных вариантах осуществления система 2004 обработки реализуется различными способами. Например, в одном примерном варианте осуществления система 2004 обработки реализуется как одно или несколько обрабатывающих ядер. Например, в этом примерном варианте осуществления система 2004 обработки может быть реализована как один или несколько микропроцессоров Intel Core 2. В другом примерном варианте осуществления система 2004 обработки реализуется как один или несколько отдельных микропроцессоров. В еще одном примерном варианте осуществления система 2004 обработки реализуется как ASIC, которая предоставляет определенные функциональные возможности. В еще одном примерном варианте осуществления система 2004 обработки предоставляет определенные функциональные возможности с использованием ASIC и путем исполнения программных команд.

[0156] В разных вариантах осуществления система 2004 обработки выполняет программные команды в разных наборах команд. Например, в различных вариантах осуществления система 2004 обработки выполняет программные команды в таких наборах команд, как набор команд x86, набор команд POWER, набор команд RISC, набор команд SPARC, набор команд IA-64, набор команд MIPS и/или другие наборы команд.

[0157] Вспомогательное запоминающее устройство 2006 включает в себя один или несколько машиночитаемых носителей информации. Вспомогательное запоминающее устройство 2006 хранит данные и программные команды, не доступные напрямую системе 2004 обработки. Другими словами, система 2004 обработки выполняет операцию ввода/вывода для извлечения данных и/или программных команд из вспомогательного запоминающего устройства 2006. В различных вариантах осуществления вспомогательное запоминающее устройство 2006 реализуется различными типами машиночитаемых носителей информации. Например, вспомогательное запоминающее устройство 2006 может быть реализовано одним или несколькими магнитными дисками, накопителями на магнитной ленте, дисками CD-ROM, дисками DVD-ROM, дисками Blu-Ray, твердотельными запоминающими устройствами, картриджами Бернулли и/или другими типами машиночитаемых носителей информации.

[0158] Сетевая интерфейсная плата 2008 дает вычислительному устройству 2000 возможность отправлять данные и принимать данные от вычислительной сети связи. В разных вариантах осуществления сетевая интерфейсная плата 2008 реализуется разными способами. Например, в различных вариантах осуществления сетевая интерфейсная плата 2008 реализуется как интерфейс Ethernet, интерфейс кольцевой сети с маркерным доступом, интерфейс волоконно-оптической сети, интерфейс беспроводной сети (например, WiFi, WiMAX и т.д.) или другой тип сетевого интерфейса.

[0159] Видеоинтерфейс 2010 дает вычислительному устройству 2000 возможность выводить видеоинформацию в устройство 2012 отображения. В разных вариантах осуществления видеоинтерфейс 2010 реализуется разными способами. Например, в одном примерном варианте осуществления видеоинтерфейс 2010 интегрируется в материнскую плату вычислительного устройства 2000. В другом примерном варианте осуществления видеоинтерфейс 2010 является видеоплатой расширения. Примерные типы видеоплат расширения включают в себя графические платы Radeon, произведенные ATI Technologies, Inc. в Маркем, Онтарио, графические платы Geforce, произведенные Nvidia Corporation в г. Санта-Клара, шт. Калифорния, и другие типы графических плат.

[0160] В различных вариантах осуществления устройство 2012 отображения реализуется в виде различных типов устройств отображения. Примерные типы устройств отображения включают в себя, но не ограничиваются, дисплеи с электронно-лучевой трубкой, дисплеи LCD, плазменные дисплеи, сенсорные дисплеи, LED-экраны, проекторы и другие типы устройств отображения. В различных вариантах осуществления видеоинтерфейс 2010 взаимодействует с устройством 2012 отображения различными способами. Например, в различных вариантах осуществления видеоинтерфейс 2010 взаимодействует с устройством 2012 отображения посредством соединителя универсальной последовательной шины (USB), соединителя VGA, соединителя цифрового визуального интерфейса (DVI), соединителя S-Video, соединителя Интерфейса для мультимедиа высокой четкости (HDMI), соединителя DisplayPort или других типов соединителей.

[0161] Интерфейс 2014 внешних компонентов дает возможность вычислительному устройству 2000 взаимодействовать с внешними устройствами. В различных вариантах осуществления интерфейс 2014 внешних компонентов реализуется разными способами. Например, в одном примерном варианте осуществления интерфейс 2014 внешних компонентов является интерфейсом USB. В других примерных вариантах осуществления интерфейс 2014 внешних компонентов является интерфейсом FireWire, интерфейсом последовательного порта, интерфейсом параллельного порта, интерфейсом PS/2 и/или другим типом интерфейса, который дает возможность вычислительному устройству 2000 взаимодействовать с внешними компонентами.

[0162] В разных вариантах осуществления интерфейс 2014 внешних компонентов дает вычислительному устройству 2000 возможность взаимодействовать с разными внешними компонентами. Например, в примере из фиг. 20 интерфейс 2014 внешних компонентов дает вычислительному устройству 2000 возможность взаимодействовать с внешним запоминающим устройством 2016, устройством 2018 ввода и принтером 2020. В других вариантах осуществления интерфейс 2014 внешних компонентов дает вычислительному устройству 2000 возможность взаимодействовать с большим или меньшим количеством внешних компонентов. Другие примерные типы внешних компонентов включают в себя, но не ограничиваются, динамики, гнезда зарядки телефонов, модемы, стыковочные узлы мультимедийных проигрывателей, другие вычислительные устройства, сканеры, цифровые камеры, считыватель отпечатков пальцев и другие устройства, которые можно подключить к вычислительному устройству 2000.

[0163] Внешнее запоминающее устройство 2016 является внешним компонентом, содержащим один или несколько машиночитаемых носителей информации. Разные реализации вычислительного устройства 2000 взаимодействуют с разными типами внешних запоминающих устройств. Примерные типы внешних запоминающих устройств включают в себя, но не ограничиваются, накопители на магнитной ленте, модули флэш-памяти, накопители на магнитных дисках, накопители на оптических дисках, блоки флэш-памяти, накопители на zip-дисках, проигрыватели с автоматической сменой компакт-дисков и другие типы устройств, содержащих один или несколько машиночитаемых носителей информации. Устройство 2018 ввода является внешним компонентом, который предоставляет пользовательский ввод вычислительному устройству 2000. Разные реализации вычислительного устройства 2000 взаимодействуют с разными типами устройств ввода. Примерные типы устройств ввода включают в себя, но не ограничиваются, клавиатуры, мыши, шаровые манипуляторы, устройства ввода со световым пером, клавишные панели, микрофоны, джойстики, сенсорные экраны дисплеев и другие типы устройств, которые предоставляют пользовательский ввод вычислительному устройству 2000. Принтер 2020 является внешним устройством, которое печатает данные на бумаге. Разные реализации вычислительного устройства 2000 взаимодействуют с разными типами принтеров. Примерные типы принтеров включают в себя, но не ограничиваются, лазерные принтеры, струйные принтеры, фотопринтеры, копировальные аппараты, факсимильные аппараты, чековые принтеры, точечно-матричные принтеры или другие типы устройств, которые печатают данные на бумаге.

[0164] Средства 2022 связи облегчают взаимодействие между аппаратными компонентами вычислительного устройства 2000. В разных вариантах осуществления средства 2022 связи облегчают взаимодействие между разными компонентами вычислительного устройства 2000. Например, в примере из фиг. 20 средства 2022 связи облегчают взаимодействие между запоминающим устройством 2002, системой 2004 обработки, вспомогательным запоминающим устройством 2006, сетевой интерфейсной платой 2008, видеоинтерфейсом 2010 и интерфейсом 2014 внешних компонентов. В разных реализациях вычислительного устройства 2000 средства 2022 связи реализуются разными способами. Например, в разных реализациях вычислительного устройства 2000 средства 2022 связи могут быть реализованы в виде шины PCI, шины PCI Express, шины ускоренного графического порта (AGP), межсоединения Infiniband, межсоединения последовательного интерфейса ATA, межсоединения параллельного интерфейса ATA, волоконно-оптического межсоединения, шины USB, интерфейса малых вычислительных систем (SCSI) или другого типа средств связи.

[0165] Запоминающее устройство 2002 хранит различные типы данных и/или программных команд. Например, в примере из фиг. 20 запоминающее устройство 2002 хранит базовую систему 2024 ввода/вывода (BIOS), операционную систему 2026, прикладное программное обеспечение 2028 и программные данные 2030. BIOS 2024 включает в себя набор программных команд, которые при исполнении системой 2004 обработки заставляют загрузиться вычислительное устройство 2000. Операционная система 2026 включает в себя набор программных команд, которые при исполнении системой 2004 обработки заставляют вычислительное устройство 2000 предоставить операционную систему, которая координирует действия и совместное использование ресурсов вычислительного устройства 2000. Примерные типы операционных систем включают в себя, но не ограничиваются, MICROSOFT® WINDOWS®, Linux, Unix, Apple OS X, Apple OS X iPhone, Palm webOS, Palm OS, Google Chrome OS, Google Android OS и так далее. Прикладное программное обеспечение 2028 включает в себя набор программных команд, которые при исполнении системой 2004 обработки заставляют вычислительное устройство 2000 предоставить приложения пользователю вычислительного устройства 2000. Программные данные 2030 являются данными, сформированными и/или используемыми прикладным программным обеспечением 2028.

[0166] Описанные выше различные варианты осуществления предоставляются только в качестве иллюстрации и не должны толковаться как ограничивающие. Специалисты в данной области техники без труда признают различные модификации и изменения, которые можно произвести, не следуя примерным вариантам осуществления и применениям, проиллюстрированным и описанным в этом документе. Например, варианты осуществления описаны в отношении документа. Однако другие варианты осуществления применяют методики, описанные в этом описании изобретения, к другим типам иерархических структур данных. Кроме того, показанные на фигурах операции всего лишь являются примерами. В различных вариантах осуществления аналогичные операции могут включать в себя больше или меньше этапов, чем показано на фигурах. Кроме того, в других вариантах осуществления аналогичные операции могут включать в себя показанные на фигурах этапы операций в других порядках.


ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
ОДНОВРЕМЕННОЕ ИСПОЛЬЗОВАНИЕ ДОКУМЕНТА НЕСКОЛЬКИМИ ПОТОКАМИ
Источник поступления информации: Роспатент

Showing 1-10 of 499 items.
10.06.2015
№216.013.5597

Регулировка громкости на основании местоположения слушателя

Изобретение относится к средствам регулировки громкости на основании местоположения слушателя. Технический результат заключается в осуществлении возможности регулирования громкости на основании местоположения слушателя. Идентифицируется местоположение одного или более громкоговорителей и...
Тип: Изобретение
Номер охранного документа: 0002553432
Дата охранного документа: 10.06.2015
27.06.2015
№216.013.5800

Смоделированное видео с дополнительными точками обзора и повышенной разрешающей способностью для камер наблюдения за движением транспорта

Изобретение относится к формированию смоделированного видеоизображения. Техническим результатом является получение смоделированных видеоизображений движения транспортных средств, имеющих высокую частоту кадров, высокую разрешающую способность и многочисленные виды, путем обработки видео от...
Тип: Изобретение
Номер охранного документа: 0002554069
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.581e

Выбираемые пользователем операционные среды для устройств мобильной связи

Изобретение относится к системам связи. Технический результат заключается в осуществлении передач в зависимости от типа операционной среды. В устройстве мобильной связи принимают передачу информации от источника передачи. Получают указатель типа операционной среды, связанного с источником...
Тип: Изобретение
Номер охранного документа: 0002554099
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5946

Система и способ для выбора вкладки в браузере с вкладками

Изобретение относится к средствам управления и выбора одной из набора открытых вкладок в браузере с вкладками. Технический результат заключается в уменьшении времени доступа к необходимой вкладке. Отображают web-браузер в окне дисплея, причем окно web-браузера отображает множество открытых...
Тип: Изобретение
Номер охранного документа: 0002554395
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5acc

Поддержание возможности отмены и возврата при объединениях метаданных

Группа изобретений относится к средствам для совместной работы над документами. Технический результат заключается в обеспечении сохранения метаданных во время операции отмены на клиентском компьютере при совместной работе над документами. Для этого представлен способ для сохранения метаданных...
Тип: Изобретение
Номер охранного документа: 0002554785
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5b08

Синхронизация частей файла с использованием серверной модели хранения информации

Изобретение относится к области синхронизации частей файла с помощью серверной модели хранения информации в клиент-серверной компьютерной сети. Техническим результатом является повышение защищенности данных при синхронизации. Изменения в содержимом электронного документа могут быть приняты на...
Тип: Изобретение
Номер охранного документа: 0002554845
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5b0a

Контрольные точки для файловой системы

Изобретение относится к средствам обеспечения контрольных точек. Технический результат заключается в уменьшении времени восстановления. Указывают, что первый набор обновлений подлежит связыванию с первой контрольной точкой. Определяют необходимость записи данных контрольной точки, относящихся к...
Тип: Изобретение
Номер охранного документа: 0002554847
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5b0e

Захват и загрузка состояний операционной системы

Изобретение относится к области захвата и загрузки состояний операционной системы. Техническим результатом является повышение эффективности восстановления операционной системы к базовому состоянию. В одном варианте воплощения выполняется сохранение состояний памяти операционной системы...
Тип: Изобретение
Номер охранного документа: 0002554851
Дата охранного документа: 27.06.2015
10.07.2015
№216.013.5c7e

Использование предварительной обработки на сервере для развертывания представлений электронных документов в компьютерной сети

Изобретение относится к области компьютерных сетей, а именно к клиент-серверным компьютерным сетям. Технический результат заключается в увеличении производительности сети и снижении задержки в доставке электронных документов, запрошенных пользователями. Технический результат достигается за счет...
Тип: Изобретение
Номер охранного документа: 0002555219
Дата охранного документа: 10.07.2015
10.07.2015
№216.013.5c7f

Управление виртуальными портами

Группа изобретений относится к устройствам ввода с возможностью обеспечения одновременной работы нескольких пользователей. Технический результат заключается в обеспечении обратной связи между пользователями вычислительной среды. Каждый такой виртуальный порт может иметь различные относящиеся к...
Тип: Изобретение
Номер охранного документа: 0002555220
Дата охранного документа: 10.07.2015
Showing 1-10 of 235 items.
10.06.2015
№216.013.5597

Регулировка громкости на основании местоположения слушателя

Изобретение относится к средствам регулировки громкости на основании местоположения слушателя. Технический результат заключается в осуществлении возможности регулирования громкости на основании местоположения слушателя. Идентифицируется местоположение одного или более громкоговорителей и...
Тип: Изобретение
Номер охранного документа: 0002553432
Дата охранного документа: 10.06.2015
27.06.2015
№216.013.5800

Смоделированное видео с дополнительными точками обзора и повышенной разрешающей способностью для камер наблюдения за движением транспорта

Изобретение относится к формированию смоделированного видеоизображения. Техническим результатом является получение смоделированных видеоизображений движения транспортных средств, имеющих высокую частоту кадров, высокую разрешающую способность и многочисленные виды, путем обработки видео от...
Тип: Изобретение
Номер охранного документа: 0002554069
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.581e

Выбираемые пользователем операционные среды для устройств мобильной связи

Изобретение относится к системам связи. Технический результат заключается в осуществлении передач в зависимости от типа операционной среды. В устройстве мобильной связи принимают передачу информации от источника передачи. Получают указатель типа операционной среды, связанного с источником...
Тип: Изобретение
Номер охранного документа: 0002554099
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5946

Система и способ для выбора вкладки в браузере с вкладками

Изобретение относится к средствам управления и выбора одной из набора открытых вкладок в браузере с вкладками. Технический результат заключается в уменьшении времени доступа к необходимой вкладке. Отображают web-браузер в окне дисплея, причем окно web-браузера отображает множество открытых...
Тип: Изобретение
Номер охранного документа: 0002554395
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5acc

Поддержание возможности отмены и возврата при объединениях метаданных

Группа изобретений относится к средствам для совместной работы над документами. Технический результат заключается в обеспечении сохранения метаданных во время операции отмены на клиентском компьютере при совместной работе над документами. Для этого представлен способ для сохранения метаданных...
Тип: Изобретение
Номер охранного документа: 0002554785
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5b08

Синхронизация частей файла с использованием серверной модели хранения информации

Изобретение относится к области синхронизации частей файла с помощью серверной модели хранения информации в клиент-серверной компьютерной сети. Техническим результатом является повышение защищенности данных при синхронизации. Изменения в содержимом электронного документа могут быть приняты на...
Тип: Изобретение
Номер охранного документа: 0002554845
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5b0a

Контрольные точки для файловой системы

Изобретение относится к средствам обеспечения контрольных точек. Технический результат заключается в уменьшении времени восстановления. Указывают, что первый набор обновлений подлежит связыванию с первой контрольной точкой. Определяют необходимость записи данных контрольной точки, относящихся к...
Тип: Изобретение
Номер охранного документа: 0002554847
Дата охранного документа: 27.06.2015
27.06.2015
№216.013.5b0e

Захват и загрузка состояний операционной системы

Изобретение относится к области захвата и загрузки состояний операционной системы. Техническим результатом является повышение эффективности восстановления операционной системы к базовому состоянию. В одном варианте воплощения выполняется сохранение состояний памяти операционной системы...
Тип: Изобретение
Номер охранного документа: 0002554851
Дата охранного документа: 27.06.2015
10.07.2015
№216.013.5c7e

Использование предварительной обработки на сервере для развертывания представлений электронных документов в компьютерной сети

Изобретение относится к области компьютерных сетей, а именно к клиент-серверным компьютерным сетям. Технический результат заключается в увеличении производительности сети и снижении задержки в доставке электронных документов, запрошенных пользователями. Технический результат достигается за счет...
Тип: Изобретение
Номер охранного документа: 0002555219
Дата охранного документа: 10.07.2015
10.07.2015
№216.013.5c7f

Управление виртуальными портами

Группа изобретений относится к устройствам ввода с возможностью обеспечения одновременной работы нескольких пользователей. Технический результат заключается в обеспечении обратной связи между пользователями вычислительной среды. Каждый такой виртуальный порт может иметь различные относящиеся к...
Тип: Изобретение
Номер охранного документа: 0002555220
Дата охранного документа: 10.07.2015
+ добавить свой РИД