Создание универсального стека

@_Pasha_ · Регистрация: 05.09.2011

Студворк — интернет-сервис помощи студентам

Прошу помощи в создании универсального стека. Вообще в реализации стека хранящего определенный тип (например : integer, char и т.д.) нет ни каких проблем. Вот пример:

Pascal

type
  pIntStack = ^tIntStack;
 
  tIntStack = record
    value : integer;
    prev  : pIntStack;
  end;
 
function push(top : pIntStack; value : integer) : pIntStack;
var
  ptmp : pIntStack;
begin
  new(ptmp);
  if top = nil then ptmp^.prev := nil
  else ptmp^.prev  := top;
  ptmp^.value := value;
  push := ptmp;
end;
 
function pop(top : pIntStack) : pIntStack;
begin
  pop := top^.prev;
  dispose(top);
end;

А вот с реализацией универсального стека возникают проблемы.

Pascal

pStack = ^tStack;
 
  tStack = record
    addr : pointer;
    prev : pStack;
  end;

Тогда функция push вторым параметром будет принимать адрес.

Pascal

1	function push(top : pStack; addr : pointer) : pStack;

Отсюда вытекает несколько вопросов:

1 Как получит значения по адресу addr?
2 Как выделить необходимое количество памяти для хранения значения находящегося по адресу addr?

deathNC · 05.09.2011, 04:47

Сообщение от _Pasha_

1. Как получит значения по адресу addr?

Вот так: addr^

Delphi

1	my_value := addr^;

Сообщение от _Pasha_

2 Как выделить необходимое количество памяти для хранения значения находящегося по адресу addr?

Delphi

type
  PMyType = ^TMyType;
  TMyType := String;
var
  sss: PMyType;
begin
  New(sss); // выделили память
  sss^ := 'dcdcdc';
  addr := sss;
end;

@_Pasha_ · 05.09.2011, 06:20 **[ТС]**

Сообщение от deathNC

Delphi

type
  PMyType = ^TMyType;
  TMyType := String;
var
  sss: PMyType;
begin
  New(sss); // выделили память
  sss^ := 'dcdcdc';
  addr := sss;
end;

Не с этим я полностью согласен, но это код не подойдет для pointer.
Немного пошевелив мозгами у меня вышло вот это:

Delphi

type
 
  pStack = ^tStack;
 
  tStack = record
    addr : pointer;
    size : integer;
    prev : pStack;
  end;
 
function push(top : pStack; addr : pointer; size : integer) : pStack;
var
  ptmp : pStack;
begin
  new(ptmp);
  getMem(ptmp^.addr, size);
  move(addr^, ptmp^.addr^, size);
 
  if top = nil then ptmp^.prev := nil
  else ptmp^.prev := top;
  push := ptmp;
end;
 
function pop(top : pStack; size : integer) : pStack;
begin
  freeMem(top^.addr, size);
  pop := top^.prev;
  dispose(top);
end;

С типами integer, char, byte и т.д. работает отлично, но с типом string беда.

Delphi

var
  top : pStack;
  s1 : string;
  ps : ^string;
 
begin
  s1 := 'Hello World';
  top := nil;
  top := push(top, @s1, sizeOf(s1) * length(s1));
  WriteLn('s1 = ', s1);
  ps := top^.addr;
  WriteLn('ps^ = ', ps^);
 
  s1 := 'Hello Moto';
  WriteLn('ps^ = ', ps^);
  WriteLn('s1 = ', s1);
  top := pop(top, top^.size);
  readln;
end.

Не понимаю в чем тут дело.

deathNC · 05.09.2011, 06:34

PChar - вот тебе стринг
PWideChar, PAnsiChar...

Добавлено через 6 минут

Не по теме:

Указатель в смысле на стринг...

@_Pasha_ · 05.09.2011, 06:37 **[ТС]**

Сообщение от deathNC

PChar - вот тебе стринг
PWideChar, PAnsiChar...

Спасибо. С этими типами все работает.
Ну, а все таки, что не так с типом string.

deathNC · 05.09.2011, 06:39

Ну, точно не помню. Я двое суток снова не спамши

Может, потому что стринг не фиксированного размера...

@Mawrat · 05.09.2011, 09:02

Сообщение от _Pasha_

С типами integer, char, byte и т.д. работает отлично, но с типом string беда.

Да - с типом String и с динамическими массивами и с вариантами (Variant) тот код не будет работать. Потому что String - это динамический тип с механизмом подсчёта ссылок.
Когда мы объявляем строковый тип:

Delphi

1 2	var S : String;

то, на самом деле, S - это указатель на первый байт области памяти, начиная с которого расположены текстовые данные. По смещению -4 расположено целое число, показывающее длину строки в виде количества символов. По смещению -8 - целое число, означающее количество ссылок на строку. По смещению -12 - целое число, показывающее сколько байт памяти выделено под все данные строки. - Это число относится уже к механизму менеджера памяти.
Пример, показывающий устройство строк:

Delphi

procedure TForm1.Button1Click(Sender: TObject);
var
  P, PSize, PRefCnt, PLen : ^Integer;
  i : Integer;
  Str1 : String;
begin
  SetLength(Str1, 20);
  for i := 1 to Length(Str1) do Str1[i] := '1';
  P := Pointer(Str1);
  PSize := Pointer( Integer(P) - 12 );
  PRefCnt := Pointer( Integer(P) - 8 );
  PLen := Pointer( Integer(P) - 4 );
  ShowMessage(
    'Строка: "' + Str1 + '"' + #10
    + 'Общий объём памяти (байт), выделенной для строки = ' + IntToStr(PSize^) + #10
    + 'Длина (количество символов) без учёта терм. нуля = ' + IntToStr(PLen^) + #10
    + 'Количество ссылок на строку = ' + IntToStr(PRefCnt^) + #10
  );
end;

За количеством ссылок следит менеджер памяти. Как только оказывается, что количество ссылок на строку равно нулю - в этом случае, менеджер памяти удаляет такую строку из памяти. Поэтому, когда выполняется код:

Delphi

1
2
3

function push(top : pStack; addr : pointer; size : integer) : pStack;
...
  move(addr^, ptmp^.addr^, size);

то копируется только указатель на текстовые данные строки, но счётчик ссылок на строку не изменяется. И как только внешняя строковая переменная, на которую ссылается addr, например, обнуляется, то менеджер памяти уменьшает её счётчик ссылок. И если этот счётчик оказывается равным нулю, то эта строка удаляется из памяти. В результате, та копия указателя на строку, которая добавлена в стек, оказывается недействительной. - Т. к., строки уже нет в той области памяти.

deathNC 1904 / 1015 / 123 Регистрация: 08.12.2009 Сообщений: 2,792 Записей в блоге: 2
	05.09.2011, 06:34	4
	PChar - вот тебе стринг PWideChar, PAnsiChar... Добавлено через 6 минут Не по теме: Указатель в смысле на стринг... 1

@_Pasha_ 0 / 0 / 0 Регистрация: 05.09.2011 Сообщений: 3
	05.09.2011, 06:37 [ТС]	5
	Сообщение от deathNC PChar - вот тебе стринг PWideChar, PAnsiChar... Спасибо. С этими типами все работает. Ну, а все таки, что не так с типом string. 0

deathNC 1904 / 1015 / 123 Регистрация: 08.12.2009 Сообщений: 2,792 Записей в блоге: 2
	05.09.2011, 06:39	6
	Ну, точно не помню. Я двое суток снова не спамши Может, потому что стринг не фиксированного размера... 0