Results 1 to 4 of 4

Thread: hashmaps

  1. #1
    Join Date
    Feb 2007
    Location
    PA, USA
    Posts
    5,240
    Mentioned
    36 Post(s)
    Quoted
    496 Post(s)

    Default hashmaps


  2. #2
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    It is very difficult to make any sort of containers in Simba without creating plugins.. I can do it via a plugin but again, Simba is always going to limit or slow down any progress and even through a plugin, you'd have type identifying problems.. Besides, relying on plugins for everything is getting annoying. Simba really is missing a lot and it's getting noticeable.


    For example, simulating Unique-Key-Value pair containers in Simba:

    Simba Code:
    type Pair = record
      Key: Pointer;
      Value: Pointer;
    end;

    type Iterator_Type = ^Pair;

    type Map = record
      size: Uint32;
      cap: Uint32;

      data: Array of Pair;
    end;

    Procedure Map.Init();
    Begin
      size := 0;
      cap := 0;
    End;

    Procedure Map.___resize(NewSize: Uint32);
    Begin
      cap := NewSize;
      SetLength(data, NewSize);
      If (size > cap) then
        size := cap;
    End;

    Procedure Map.Insert(var p: Pair);
    var
      I: Integer;
    Begin
      if (size >= cap) then
      begin
          if (cap = 0) then cap := 1;
          self.___resize(cap * 2);
      end;

      For I := 0 To Size Do
        If (data[I].Key = P.Key) Then
          Exit;

      data[size] := p;
      size := size + 1;
    End;

    Function Map.First(): Iterator_Type;
    Begin
      Result := @data[0];
    End;

    Function Map.Last(): Iterator_Type;
    Begin
      Result := @data[size - 1];
    End;

    Function Iterator_Type.Next(): Iterator_Type;
    Begin
      Result := self + sizeof(Pair);
    End;

    Function ToPair(Key: Pointer; Value: Pointer): Pair;
    Begin
      Result.Key := Key;
      Result.Value := Value;
    End;


    var
      MP: Map;
      K: Integer;
      V: Integer;
      type PInt = ^Integer;
    begin
      K := 100;
      V := 1024;
      MP.Insert(ToPair(@K, @V));

      writeln(Integer(MP.Last()^.Key^));
      MP.Insert(ToPair(@K, @V));

      writeln(MP.size);
    end.


    The limitation here is that there is no "typeof", "dynamic_cast", "type-id" or "decltype" mechanisms or any way to tell what type an Object or Pointer is.. There is no Generic Type or Compile Time Templates.. All type information is lost in translation. Thus the only solution is to store a raw/opaque pointer.

    The problem with this then becomes comparison. How exactly do you compare two raw/opaque pointers? Well the answer is that you can't.. The most you can do is compare their addresses. However, in the case of a Key-Value pair container, you want to compare their keys/values..

    Thus the only possible way to create a Key-Value-Pair container is to use Function-Pointer treachery:

    Simba Code:
    type Pair = record
      Key: Pointer;
      Value: Pointer;
    end;

    type Iterator_Type = ^Pair;
    type PairComparator = Function(Val: Pointer; Val2: Pointer): Boolean;

    type Map = record
      size: Uint32;
      cap: Uint32;
      comparator: PairComparator;

      data: Array of Pair;
    end;

    Procedure Map.Init(Comp: PairComparator);
    Begin
      size := 0;
      cap := 0;
      comparator := @comp;
    End;

    Procedure Map.___resize(NewSize: Uint32);
    Begin
      cap := NewSize;
      SetLength(data, NewSize);
      If (size > cap) then
        size := cap;
    End;

    Procedure Map.Insert(var p: Pair);
    var
      I: Integer;
    Begin
      if (@comparator = nil) then
        RaiseException('PAIR INVALID COMPARATOR!');

      if (size >= cap) then
      begin
          if (cap = 0) then cap := 1;
          self.___resize(cap * 2);
      end;

      For I := 0 To Size - 1 Do
        If (comparator(data[I].Key, p.Key)) Then
          Exit;

      data[size] := p;
      size := size + 1;
    End;

    Function Map.First(): Iterator_Type;
    Begin
      Result := @data[0];
    End;

    Function Map.Last(): Iterator_Type;
    Begin
      Result := @data[size];
    End;

    Function Iterator_Type.Next(): Iterator_Type;
    Begin
      Result := self + sizeof(Pair);
    End;

    Function ToPair(Key: Pointer; Value: Pointer): Pair;
    Begin
      Result.Key := Key;
      Result.Value := Value;
    End;


    Function IntComparator(Key: Pointer; Key2: Pointer): Boolean;
      type PInt = ^Integer;
    Begin
      Result := PInt(Key)^ = PInt(Key2)^;
    End;

    var
      MP: Map;
      K, V, K2, V2: Integer;
      it: Iterator_Type;
    begin
      K := 100;
      V := 1024;

      K2 := 1024;
      V2 := 100;


      MP.Init(@IntComparator);
      MP.Insert(ToPair(@K, @V));
      MP.Insert(ToPair(@K2, @V2));

      it := MP.First();

      while(it <> MP.Last()) do
      begin
        writeln(Integer(it^.Key^));
        it := it.Next();
      end;
    end.


    And now the limitation becomes the types that you can construct a Key-Value-Pair with.. Since the type being accepted is a raw pointer and we had to use a Comparator function pointer to do comparison, that means we can only pass "variables" to it..


    For example, we cannot do: ToPair(12, 100);. Instead we must create stupid variables such as K and V and set those to 12 and 100 respectively.

    This can be a real pain! Another thing I found as undefined behaviour but is acceptable as it seems to work in every case, is pointer scope. Storing a pointer to a type seems to store a reference count so even if the type goes out of scope or is local, its memory still exists and so does the pointer.. Somehow we are able to return and use the address of local-scope variables which isn't supposed to be legal but it works..


    One thing that will definitely solve this is to figure out at what offset is the pointer's information stored at. For example, when you writeln a pointer, it does a lookup and prints information about the data being pointed to or it might hardcode it into the script during translation.
    Last edited by Brandon; 01-24-2014 at 04:52 AM.
    I am Ggzz..
    Hackintosher

  3. #3
    Join Date
    Feb 2007
    Location
    PA, USA
    Posts
    5,240
    Mentioned
    36 Post(s)
    Quoted
    496 Post(s)

    Default

    Thanks for the reply Brandon. Could you explain what the ^ means?

  4. #4
    Join Date
    Mar 2012
    Location
    127.0.0.1
    Posts
    3,383
    Mentioned
    95 Post(s)
    Quoted
    717 Post(s)

    Default

    Quote Originally Posted by footballjds View Post
    Thanks for the reply Brandon. Could you explain what the ^ means?
    Look up pointers.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •