Vlad писал(а):
Забить на статические массивы и использовать нормальные динамические строки :) В библиотеке. Как это сделали в C++ ;)
И в Delphi.
Я решил-таки сделать нормальную библиотеку для работы с динамическими строками. Естественно, разработка ведётся под XDS. По реализации выглядит примерно так: библиотека Strings, абстрактный тип Strings.Str. Реализация скрыта в типе Strings.Str2, расширении Str.
Я решил совместить подход Delphi (AnsiString со счётчиком ссылок) и ОС Oberon (со сборщиком мусора). Сделал так: строка - это цепочка записей типа Str2, связанная через поля next и prev. Данные хранятся не в Str2, а в отдельном типе Piece, в поле data:
Код:
CONST
PieceSize = 127;
TYPE
Piece = POINTER TO RECORD
ref: INTEGER;
data: ARRAY PieceSize OF CHAR;
END;
Str* = POINTER TO ABSTRACT RECORD
END;
Str2 = POINTER TO RECORD (Str)
piece: Piece;
beg, end: BYTE;
prev, next: Str2
END;
Piece.ref - это счётчик ссылок. Блоки Piece.data являются разделяемыми: на один и тот же блок может ссылаться несколько строк. Таким образом, копирование строки, разделение строк на несколько частей, удаление части, конкатенация - всё это не приводит к дублированию данных, а только к созданию цепочек ссылок из Str2 на уже существующие блоки, и увеличению их piece.ref. Уменьшается piece.ref либо при удалении куска строки, либо в финализаторе корневого Str2.
Зачем вообще нужен Piece? Почему не реализовать всё через POINTER TO ARRAY OF CHAR произвольной длины? Piece нужен ради Piece.ref, т.е. для подсчёта ссылок на Piece.data. Подсчёт ссылок, в свою очередь, нужен для того, чтобы при модификации содержимого строки можно было узнать, экслюзивно ли строка владеет данным блоком или нет, и если нет, то сделать себе отдельную копию. Если эксклюзивно, то копию делать не нужно. Если данные не модифицируются, то и копирования не происходит, только создаются дополнительные управляющие структуры. При PieceSize = 127 оверхед на управляющие структуры (цепочки из объектов Str2) составляет около 33%, т.е. на строку длиной 10Мб данных надо дополнительно разместить 3.3Мб объектов Str2/Piece.
Почему Piece.data имеет фиксированный размер? Это вопрос сложный, равно как и выбор значения PieceSize. С одной стороны, хочется избежать ситуации, когда управляющие структуры занимают в памяти больше места, чем полезный объём строки. С другой стороны, не хочется слишком раздувать минимальный размер строки. С третьей стороны, если Piece.data будет не ARRAY, а POINTER TO ARRAY динамического размера, то это дополнительно нагрузит сборщик мусора. Очень хотелось бы услышать альтернативные предложения или почитать что-то на эту тему. В настоящее время я подумываю о том, чтобы сделать собственный небольшой менеджер памяти, который бы брал память непосредственно у ОС. При фиксированном размере блока это тривиальная задача на один вечер. При наличии собственного менеджера, в памяти GC будут выделяться только управляющие структуры Str2, а полезные данные вместе со счётчиками ссылок будут размещаться в дополнительной, специально выделенной памяти. Счётчики ссылок позволят повторно использовать блоки, на которые больше нет ссылок из управляющих структур. При этом, ввиду фиксированного размера, поиск свободного блока будет происходить очень быстро. В памяти GC же будут выделяться только маленькие кусочки, что снизит фрагментацию. Плюс, собственный менеджер памяти позволит увидеть, насколько память нагружена строковыми данными, да и вообще даст некоторые показатели здоровья приложения.
Поля Str2.beg и Str2.end обозначают область piece.data [beg..end-1], используемую данным экземпляром Str2. Таким образом, длина строки вычисляется так:
Код:
PROCEDURE Length* (s: Str): LONGINT;
(** Return the number of characters in 's'. If 's' = NIL, return 0.
* Pre: (s = NIL) OR (s IS Str2), guarded
* Post: result >= 0, 60 *)
VAR
s2: Str2;
res: LONGINT;
BEGIN
(* Implementation note: the current algorithm shows performance increase of
* up to 42 times as compared to the linear 0X search for regular Oberon
* strings. Still, since all string operations are encapsulated in this
* module, it is possible to maintain current length of a string in a
* hidden field for completely instant retrieval. *)
res := 0;
IF s # NIL THEN
s2 := s (Str2);
IF s2.piece # NIL THEN
WHILE s2 # NIL DO
INC (res, s2.end - s2.beg);
s2 := s2.next;
END;
END;
END;
ASSERT (res >= 0, 60);
RETURN res
END Length;
Для конвертации из обычного символьного массива в Strings.Str и обратно используются следующие процедуры:
PROCEDURE Assign* (VAR s: ARRAY OF CHAR; VAR str: Str);
PROCEDURE Get* (src: Str; VAR dst: ARRAY OF CHAR);
Assign берёт данные из s до 0X, т.е. работает с обычными Oberon-строками, например, создаваемыми компилятором текстовыми константами. Get добавляет в конец экспортированного содержимого символ 0X, например, для последующей передачи в фукнцию ОС или другую Oberon-строку.
Поскольку строки реализованы в виде списков, наиболее эффективными в качестве базисных операций оказались следующие: Split, Join, Copy
Код:
PROCEDURE Split* (str: Str; at: LONGINT): Str;
(** Split the 'str' in two. str [at] is the first character of the new string.
* Pre: 0 <= at, 20
* Pre: at < Length (str), 21 or NIL dereference trap
* Post: Length (result) = Length (str) - at > 0
* Post: Length (str) = at *)
PROCEDURE Join* (VAR str: Str; tail: Str);
(** Move 'tail's contents to the end of 'str' and empty 'tail'. If 'tail' =
* NIL, do nothing. Split and Join are mutually inverse operations on the
* contents: Join (str, Split (str, x)) = str, where 0 <= x < Length (str).
* Post: str # NIL
* Post: Length (str') = Length (str) + Length (tail)
* Post: Length (tail) = 0 *)
PROCEDURE Copy* (src: Str; VAR dst: Str);
(** Copy the entire contents of string 'src' into 'dst'. Prefer creating cheap
* copy of the string, i.e. with as little data moving overhead as possible.
* The operation logic of the procedure depending on the parameters is guided
* by the following table:
* src dst
* 1) NIL NIL - do nothing, the strings are already equal;
* 2) NIL #NIL - set 'dst' = empty string (Length (dst) = 0);
* 3) #NIL NIL - create 'dst' and copy contents from 'src';
* 4) #NIL #NIL - if (src = dst), do nothing, otherwise replace the current
* contents of 'dst' with the contents of 'src'.
* Only in case 3) the value of the 'dst' variable will be replaced,
* otherwise it is preserved, as there may be other references to the string
* object in the client code. If 'src' is empty in case 3), the new empty 'dst'
* is created.
* Post: dst is a valid string, 60
* Post: Length (src) = Length (dst), 61 *)
Для индексированного доступа к содержимому собираюсь сделать Reader и Writer по образцу ОС Oberon. Благодаря инкапсуляции доступа к содержимому строк, надеюсь в этом году перевести Amadeus на Unicode.
Вход
FAQ
Поиск
