Euphoria
Ticket #860:
in map.e lookup() return an index 0
-
Reported by
coconut
Apr 03, 2013
When lookup() function doesn't find the key and there is no removed slot in the map it return 0 crashing get() and puts()
lookup() should never return 0, it should return and index to EMPTY or REMOVED slot. something going wrong in this weird 'while' loop. Too smart algo that everage Joe doesn't understand at first glance. Should be replaced by a simple 'for' loop that iterate 'slots' sequence.
Details
1. Comment by mattlewis
Apr 04, 2013
I'm having trouble reproducing this. The idea behind the loop is not to iterate simply, because that would be a more inefficient way to resolve hash conflicts. I've had to modify the original algorithm to take removed keys into account.
The only way I can see this function returning 0 is if we've tried looking at more slots than the number of slots, and we never found one that was removed. This shouldn't happen, because there should always be free slots (we grow the hash table long before it fills up). However, this assumes that the perturbation looks at the entire space. I suspect this may be due to to changing from a 0-based index to a 1-based index.
I suspect that removing:
index_hash += 1
...will fix this. Can you post the raw data for the map causing this? The data is stored in std/eumem.e:ram_space[map] (where 'map' is the particular map).
2. Comment by coconut
Apr 04, 2013
ex.err
/usr/share/euphoria/include/std/map.e:507 in function get()
subscript value 0 is out of bounds, reading from a sequence of length 256
the_map_p = 99
key = 1483
default = {}
hashval = 854924930
slots = {
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
14360323,
867,
{
{77'M',85'U',76'L',84'T',73'I',80'P',76'L',89'Y'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
799664137,
1035,
{
{70'F',55'7'}
}
},
{-2,0,0},
{-2,0,0},
{
1015547148,
1273,
{
{70'F',50'2',52'4'}
}
},
{
253405453,
811,
{
{78'N',85'U',77'M',80'P',65'A',68'D',54'6'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
691706642,
559,
{
{68'D',79'O',87'W',78'N'}
}
},
{-2,0,0},
{-2,0,0},
{
273100309,
1301,
{
{83'S',67'C',82'R',79'O',76'L',76'L'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
859251744,
1427,
{
{66'B',82'R',79'O',87'W',83'S',69'E',82'R',95'_',82'R',
69'E',70'F',82'R',69'E',83'S',72'H'}
}
},
{-2,0,0},
{-2,0,0},
{
530802211,
391,
{
{67'C',79'O',78'N',86'V',69'E',82'R',84'T'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
461356579,
1329,
{
{82'R',83'S',72'H',73'I',70'F',84'T'}
}
},
{
46877740,
1189,
{
{70'F',49'1',56'8'}
}
},
{-2,0,0},
{
1012279900,
1147,
{
{70'F',49'1',53'5'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
516127797,
447,
{
{83'S',80'P',65'A',67'C',69'E'}
}
},
{
130811528,
713,
{
{83'S',76'L',69'E',69'E',80'P'}
}
},
{-2,0,0},
{-2,0,0},
{
569254969,
1371,
{
{76'L',77'M',69'E',78'N',85'U'}
}
},
{
1003923806,
1399,
{
{66'B',82'R',79'O',87'W',83'S',69'E',82'R',95'_',66'B',
65'A',67'C',75'K'}
}
},
{-2,0,0},
{-2,0,0},
{
380812861,
1245,
{
{70'F',50'2',50'2'}
}
},
{
807846836,
1105,
{
{70'F',49'1',50'2'}
}
},
{
102531391,
587,
{
{80'P',82'R',73'I',78'N',84'T'}
}
},
{
538275392,
503,
{
{72'H',79'O',77'M',69'E'}
}
},
{-2,0,0},
{
759522370,
461,
{
{80'P',82'R',73'I',79'O',82'R'}
}
},
{
648405283,
839,
{
{78'N',85'U',77'M',80'P',65'A',68'D',56'8'}
}
},
{-2,0,0},
{
853044805,
573,
{
{83'S',69'E',76'L',69'E',67'C',84'T'}
}
},
{
1050180448,
1007,
{
{70'F',53'5'}
}
},
{-2,0,0},
{
891310664,
965,
{
{70'F',50'2'}
}
},
{
833776201,
797,
{
{78'N',85'U',77'M',80'P',65'A',68'D',53'5'}
}
},
{-2,0,0},
{-2,0,0},
{
961359180,
643,
{
{68'D',69'E',76'L',69'E',84'T',69'E'}
}
},
{
216493389,
825,
{
{78'N',85'U',77'M',80'P',65'A',68'D',55'7'}
}
},
{-2,0,0},
{
469774159,
657,
{
{72'H',69'E',76'L',80'P'}
}
},
{
957459536,
307,
{
{67'C',65'A',80'P',73'I',84'T',65'A',76'L'}
}
},
{-2,0,0},
{-2,0,0},
{
1047330387,
419,
{
{65'A',67'C',67'C',69'E',80'P',84'T'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
616067930,
1203,
{
{70'F',49'1',57'9'}
}
},
{-2,0,0},
{
360527545,
195,
{
{66'B',65'A',67'C',75'K'}
}
},
{
815327581,
1119,
{
{70'F',49'1',51'3'}
}
},
{
485288164,
475,
{
{78'N',69'E',88'X',84'T'}
}
},
{
14480735,
1063,
{
{70'F',57'9'}
}
},
{
1005201760,
615,
{
{83'S',78'N',65'A',80'P',83'S',72'H',79'O',84'T'}
}
},
{-2,0,0},
{
831870050,
601,
{
{69'E',88'X',69'E',67'C',85'U',84'T',69'E'}
}
},
{
458251875,
111'o',
{
{76'L',66'B',85'U',84'T',84'T',79'O',78'N'}
}
},
{
141114468,
167,
{
{88'X',66'B',85'U',84'T',84'T',79'O',78'N',49'1'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
775850345,
881,
{
{65'A',68'D',68'D'}
}
},
{
531660262,
909,
{
{83'S',85'U',66'B',84'T',82'R',65'A',67'C',84'T'}
}
},
{-2,0,0},
{
101818476,
1287,
{
{78'N',85'U',77'M',76'L',79'O',67'C',75'K'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
1005490288,
363,
{
{72'H',65'A',78'N',74'J',65'A'}
}
},
{
751195761,
405,
{
{78'N',79'O',78'N',67'C',79'O',78'N',86'V',69'E',82'R',
84'T'}
}
},
{
194713458,
139,
{
{67'C',65'A',78'N',67'C',69'E',76'L'}
}
},
{
66448755,
1455,
{
{66'B',82'R',79'O',87'W',83'S',69'E',82'R',95'_',83'S',
69'E',65'A',82'R',67'C',72'H'}
}
},
{-2,0,0},
{
216340853,
1175,
{
{70'F',49'1',55'7'}
}
},
{
870951030,
727,
{
{78'N',85'U',77'M',80'P',65'A',68'D',48'0'}
}
},
{
341279095,
671,
{
{76'L',87'W',73'I',78'N'}
}
},
{-2,0,0},
{-2,0,0},
{
420186746,
1161,
{
{70'F',49'1',54'6'}
}
},
{-2,0,0},
{
85340777,
1021,
{
{70'F',54'6'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
420934018,
979,
{
{70'F',51'3'}
}
},
{
523667843,
125'}',
{
{82'R',66'B',85'U',84'T',84'T',79'O',78'N'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
815053704,
517,
{
{76'L',69'E',70'F',84'T'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
684029837,
293,
{
{80'P',65'A',85'U',83'S',69'E'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
693669272,
1441,
{
{66'B',82'R',79'O',87'W',83'S',69'E',82'R',95'_',83'S',
84'T',79'O',80'P'}
}
},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{-2,0,0},
{
...
index = 0
slot = <no value>
3. Comment by mattlewis
Apr 04, 2013
That's part of the information. Before that call to get, do:
include std/eumem.e
? ram_space[99]
You can replace 99 with the map variable. The provided information doesn't give all of the map data required to reproduce this.
4. Comment by SDPringle
May 18, 2014
This routine, lookup(), cannot possibly return 0 because what it returns is and has always been used in a sequence member read operation before returning.
It is not a problem with the routine, perhaps something went wrong with the interpreter a year ago and it appeared as a problem with the routine.
GitHub