gobo-eiffel-develop

[gobo-eiffel-develop] Crash in DS_HASH_TABLE

[Wolfgang J. <wj...@so...>]

High Eric,

some time ago I already asked a related question and you
gave an answer. But I may have misunderstood something.
The problem is as follows. I have a class like

  class C
  inherit
    DS_EQUALITY_TESTER [KEY_TYPE]
      redefine test
    end

  feature

    table: DS_HASH_TABLE [ITEM_TYPE,KEY_TYPE]

    make is
      do
        create table.make_with_equality_testers(1000, Void, Current)
      end

    build(k: KEY_TYPE): ITEM_TYPE is
      do
        if table.has(k) then
          Result := table.item(k)
        else
          create Result.make(k)
          table.force(Result,k)
        end
      end

    test(u,v: STRING) is
      do
        -- I would like to do this more intelligent,
        -- but this is a different problem
        Result := u = v
      end

   -- other features

  end

This works very well for some time (hundreds of calls)
but then routine `search_position' enters an infinite loop:
Lines 590,591 of DS_SPARSE_CONTAINER are
  prev := i
  i := clashes_item(i)
and have the effect that `prev=1', `i=1', i.e. no further
progress happens. A particular observation:
`table' has currently 1028 elements.

So, what has gone wrong and how can I fix the bug?

Regards
WJ

-- 
Wolfgang Jansen
University of Potsdam, Germany
mailto: wj...@so...

Re: [gobo-eiffel-develop] Crash in DS_HASH_TABLE

[Eric B. <er...@go...>]

Wolfgang Jansen wrote:
> some time ago I already asked a related question and you
> gave an answer. But I may have misunderstood something.
> The problem is as follows. I have a class like
> 
>   class C
>   inherit
>     DS_EQUALITY_TESTER [KEY_TYPE]
>       redefine test
>     end
> 
>   feature
> 
>     table: DS_HASH_TABLE [ITEM_TYPE,KEY_TYPE]
> 
>     make is
>       do
>         create table.make_with_equality_testers(1000, Void, Current)
>       end
> 
>     build(k: KEY_TYPE): ITEM_TYPE is
>       do
>         if table.has(k) then
>           Result := table.item(k)
>         else
>           create Result.make(k)
>           table.force(Result,k)
>         end
>       end
> 
>     test(u,v: STRING) is
>       do
>         -- I would like to do this more intelligent,
>         -- but this is a different problem
>         Result := u = v
>       end
> 
>    -- other features
> 
>   end
> 
> This works very well for some time (hundreds of calls)
> but then routine `search_position' enters an infinite loop:
> Lines 590,591 of DS_SPARSE_CONTAINER are
>   prev := i
>   i := clashes_item(i)
> and have the effect that `prev=1', `i=1', i.e. no further
> progress happens. A particular observation:
> `table' has currently 1028 elements.
> 
> So, what has gone wrong and how can I fix the bug?

Is the value of the hash_code of your keys changing while
these keys are used in the hash table?

-- 
Eric Bezault
mailto:er...@go...
http://www.gobosoft.com

Re: [gobo-eiffel-develop] Crash in DS_HASH_TABLE

[Wolfgang J. <wj...@so...>]

Eric Bezault wrote:
> Wolfgang Jansen wrote:
>> some time ago I already asked a related question and you
>> gave an answer. But I may have misunderstood something.
>> The problem is as follows. I have a class like
>>
>>   class C
>>   inherit
>>     DS_EQUALITY_TESTER [KEY_TYPE]
>>       redefine test
>>     end
>>
>>   feature
>>
>>     table: DS_HASH_TABLE [ITEM_TYPE,KEY_TYPE]
>>
>>     make is
>>       do
>>         create table.make_with_equality_testers(1000, Void, Current)
>>       end
>>
>>     build(k: KEY_TYPE): ITEM_TYPE is
>>       do
>>         if table.has(k) then
>>           Result := table.item(k)
>>         else
>>           create Result.make(k)
>>           table.force(Result,k)
>>         end
>>       end
>>
>>     test(u,v: STRING) is
>>       do
>>         -- I would like to do this more intelligent,
>>         -- but this is a different problem
>>         Result := u = v
>>       end
>>
>>    -- other features
>>
>>   end
>>
>> This works very well for some time (hundreds of calls)
>> but then routine `search_position' enters an infinite loop:
>> Lines 590,591 of DS_SPARSE_CONTAINER are
>>   prev := i
>>   i := clashes_item(i)
>> and have the effect that `prev=1', `i=1', i.e. no further
>> progress happens. A particular observation:
>> `table' has currently 1028 elements.
>>
>> So, what has gone wrong and how can I fix the bug?
>
> Is the value of the hash_code of your keys changing while
> these keys are used in the hash table?
>
I don't know, the key type is ET_FEATURE.
So, you may answer this best yourself.

-- 
Wolfgang Jansen
University of Potsdam, Germany
mailto: wj...@so...

Re: [gobo-eiffel-develop] Crash in DS_HASH_TABLE

[Eric B. <er...@go...>]

Wolfgang Jansen wrote:
> Eric Bezault wrote:
>> Wolfgang Jansen wrote:
>>> some time ago I already asked a related question and you
>>> gave an answer. But I may have misunderstood something.
>>> The problem is as follows. I have a class like
>>>
>>>   class C
>>>   inherit
>>>     DS_EQUALITY_TESTER [KEY_TYPE]
>>>       redefine test
>>>     end
>>>
>>>   feature
>>>
>>>     table: DS_HASH_TABLE [ITEM_TYPE,KEY_TYPE]
>>>
>>>     make is
>>>       do
>>>         create table.make_with_equality_testers(1000, Void, Current)
>>>       end
>>>
>>>     build(k: KEY_TYPE): ITEM_TYPE is
>>>       do
>>>         if table.has(k) then
>>>           Result := table.item(k)
>>>         else
>>>           create Result.make(k)
>>>           table.force(Result,k)
>>>         end
>>>       end
>>>
>>>     test(u,v: STRING) is
>>>       do
>>>         -- I would like to do this more intelligent,
>>>         -- but this is a different problem
>>>         Result := u = v
>>>       end
>>>
>>>    -- other features
>>>
>>>   end
>>>
>>> This works very well for some time (hundreds of calls)
>>> but then routine `search_position' enters an infinite loop:
>>> Lines 590,591 of DS_SPARSE_CONTAINER are
>>>   prev := i
>>>   i := clashes_item(i)
>>> and have the effect that `prev=1', `i=1', i.e. no further
>>> progress happens. A particular observation:
>>> `table' has currently 1028 elements.
>>>
>>> So, what has gone wrong and how can I fix the bug?
>> Is the value of the hash_code of your keys changing while
>> these keys are used in the hash table?
>>
> I don't know, the key type is ET_FEATURE.
> So, you may answer this best yourself.

No, the hash_code is set once and for all when creating the feature
object.

Here are more questions:

Do you change the value of `key_equality_tester' in your hash table
at some point in your program?

If you initially create the hash table with a capacity of 2000
instead of 1000, does it still crash? If so, does it crash with
the same number of items already inserted?

Do you have some code that I can use to try to reproduce the problem?
I guess that the code above will not help me (the feature `test' is
using STRINGs instead of ET_FEATUREs).

-- 
Eric Bezault
mailto:er...@go...
http://www.gobosoft.com

Re: [gobo-eiffel-develop] Crash in DS_HASH_TABLE

[Wolfgang J. <wj...@so...>]

Eric Bezault wrote:
> Wolfgang Jansen wrote:
>> Eric Bezault wrote:
>>> Wolfgang Jansen wrote:
>>>> some time ago I already asked a related question and you
>>>> gave an answer. But I may have misunderstood something.
>>>> The problem is as follows. I have a class like
>>>>
>>>>   class C
>>>>   inherit
>>>>     DS_EQUALITY_TESTER [KEY_TYPE]
>>>>       redefine test
>>>>     end
>>>>
>>>>   feature
>>>>
>>>>     table: DS_HASH_TABLE [ITEM_TYPE,KEY_TYPE]
>>>>
>>>>     make is
>>>>       do
>>>>         create table.make_with_equality_testers(1000, Void, Current)
>>>>       end
>>>>
>>>>     build(k: KEY_TYPE): ITEM_TYPE is
>>>>       do
>>>>         if table.has(k) then
>>>>           Result := table.item(k)
>>>>         else
>>>>           create Result.make(k)
>>>>           table.force(Result,k)
>>>>         end
>>>>       end
>>>>
>>>>     test(u,v: STRING) is
>>>>       do
>>>>         -- I would like to do this more intelligent,
>>>>         -- but this is a different problem
>>>>         Result := u = v
>>>>       end
>>>>
>>>>    -- other features
>>>>
>>>>   end
>>>>
>>>> This works very well for some time (hundreds of calls)
>>>> but then routine `search_position' enters an infinite loop:
>>>> Lines 590,591 of DS_SPARSE_CONTAINER are
>>>>   prev := i
>>>>   i := clashes_item(i)
>>>> and have the effect that `prev=1', `i=1', i.e. no further
>>>> progress happens. A particular observation:
>>>> `table' has currently 1028 elements.
>>>>
>>>> So, what has gone wrong and how can I fix the bug?
>>> Is the value of the hash_code of your keys changing while
>>> these keys are used in the hash table?
>>>
>> I don't know, the key type is ET_FEATURE.
>> So, you may answer this best yourself.
>
> No, the hash_code is set once and for all when creating the feature
> object.
>
> Here are more questions:
>
> Do you change the value of `key_equality_tester' in your hash table
> at some point in your program?
>
No.
> If you initially create the hash table with a capacity of 2000
> instead of 1000, does it still crash? If so, does it crash with
> the same number of items already inserted?
>
See below.
> Do you have some code that I can use to try to reproduce the problem?
> I guess that the code above will not help me (the feature `test' is
> using STRINGs instead of ET_FEATUREs).
>
Sorry, this was a typo: the arguments are ET_FEATUREs.

After changing some other things (that had to be changed anyway)
the crash does not longer occur. I cannot reproduce the class state of 
interest
(it was an intermediate state of today's work and has not been saved).
So we may forget the trouble for now.

-- 
Wolfgang Jansen
University of Potsdam, Germany
mailto: wj...@so...