-
Notifications
You must be signed in to change notification settings - Fork 1
/
hood.py
184 lines (164 loc) · 4.75 KB
/
hood.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
# -*- coding: utf-8 -*-
import os
import sys
import hashlib
def keyhash(key):
return int(hashlib.md5(key).hexdigest(), 16)
class Keypair:
def __init__(self, key, val, dib=0):
self.key = key
self.val = val
self.hsh = keyhash(key)
self.dib = dib
class Hood:
def __init__(self, cap=2):
self.cap = cap
self.fill = 0
self.buckets = [None for x in range(self.cap)]
def insert(self, kp):
kp.dib=0
while 1:
#print 'inserting: key['+kp.key+'] val['+kp.val+']'
# Look up slot
pos = kp.hsh % self.cap
kp.dib=0
while 1:
pos = pos % self.cap
#print ' pos:', pos
kloc = self.buckets[pos]
if kloc == None:
#print ' free slot at dib=', kp.dib
# Free slot: insert
self.buckets[pos] = kp
self.fill+=1
break
# Compare local and candidate dib
if kloc.dib < kp.dib:
#print ' hood at', pos
# Insert in place
self.buckets[pos] = kp
# Re-insert kloc
#print ' displacing', kloc.key
self.insert(kloc)
break
else:
#print ' not hooding', kloc.dib, kp.dib
pass
# Continue searching
kp.dib+=1
pos+=1
break
nh = resize(self)
if nh:
self.cap = nh.cap
self.fill = nh.fill
self.buckets = nh.buckets
def lookup(self, key):
kp = Keypair(key, None)
pos = kp.hsh % self.cap
while 1:
if self.buckets[pos] == None:
return -1
if self.buckets[pos].hsh == kp.hsh:
return pos
pos=(pos+1) % self.cap
def find(self, key):
pos = self.lookup(key)
if pos>=0:
return self.buckets[pos].val
return None
def delete(self, key):
#print 'deleting:', key
pos = self.lookup(key)
#print 'lookup at', pos
if pos<0:
return
while 1:
# Delete keypair at pos
self.buckets[pos]=None
# Backtrack on later keypairs
npos = (pos+1)%self.cap
if self.buckets[npos] and self.buckets[npos].dib==0:
break
self.buckets[pos] = self.buckets[npos]
if self.buckets[npos]==None:
break
self.buckets[pos].dib-=1
pos = npos
self.fill-=1
def show(self):
print '----- hood', self.fill, self.cap
for kp in self.buckets:
if kp:
print 'key['+kp.key+'] val['+kp.val+']'
#else:
#print '--empty'
def resize(hood):
if 3*hood.fill < 2*hood.cap:
return None
print 'resizing to', hood.cap*2
newHood = Hood(hood.cap *2)
for kp in hood.buckets:
if kp:
kp.dib=0
newHood.insert(kp)
#newHood.show()
return newHood
def heavy():
size=10240
rh = Hood()
print 'start insertion'
for i in range(size):
rh.insert(Keypair(str(i), str(i)))
print 'stop insertion'
print 'start lookup'
for i in range(size):
val = rh.find(str(i))
if val != str(i):
print 'lookup failed [%d][%s]' % (i, val)
print 'stop lookup'
#rh.show()
print 'start delete'
for i in range(size):
rh.delete(str(i))
print 'stop delete'
print 'start lookup'
for i in range(size):
val = rh.find(str(i))
if val != None:
print 'lookup failed [%d][%s]' % (i, val)
print 'stop lookup'
rh.show()
def unit_test():
rh = Hood()
print '----- insertions'
rh.insert(Keypair('1', 'one'))
rh.insert(Keypair('2', 'two'))
rh.insert(Keypair('3', 'three'))
rh.insert(Keypair('4', 'four'))
rh.insert(Keypair('5', 'five'))
rh.insert(Keypair('6', 'six'))
rh.insert(Keypair('7', 'seven'))
rh.insert(Keypair('8', 'eight'))
rh.insert(Keypair('9', 'nine'))
rh.insert(Keypair('10', 'ten'))
rh.show()
print '----- lookups'
print rh.find('1')
print rh.find('2')
print rh.find('3')
print rh.find('4')
print rh.find('5')
print rh.find('6')
print rh.find('7')
print rh.find('8')
print rh.find('9')
print rh.find('10')
print rh.find('11')
print '----- delete'
for i in ['1','2','3','4','5','6','7','8','9','10']:
rh.delete(i)
rh.show()
rh.show()
if __name__=="__main__":
heavy()