Kiln » Dependencies » Dulwich Read More
Clone URL:  
Pushed to one repository · View In Graph Contained in master

object_store: Make iter_tree_contents depth-first.

This mimics the behavior of os.walk as well as common tools like find
and ls -R.

Memory usage may also be better, as directory trees tend to have a
higher branching factor than depth. (Note that the overhead of Python
stack frames may make this not true in many cases, and I haven't run
any benchmarks.)

Changeset 1d2133e1cffb…

Parent 2ffac0eafcd1…

committed by Jelmer Vernooij

authored by Dave Borowitz

Changes to 3 files · Browse files at 1d2133e1cffb Showing diff from parent 2ffac0eafcd1 Diff from another changeset...

Change 1 of 1 Show Entire File NEWS Stacked
 
16
17
18
 
 
 
 
 
19
20
21
 
16
17
18
19
20
21
22
23
24
25
26
@@ -16,6 +16,11 @@
  * Web server supports streaming progress/pack output. (Dave Borowitz)     * New public function dulwich.pack.write_pack_header. (Dave Borowitz) + + API CHANGES + + * ObjectStore.iter_tree_contents now walks contents in depth-first, sorted + order. (Dave Borowitz)      0.6.1 2010-07-22
Change 1 of 1 Show Entire File dulwich/​object_store.py Stacked
 
175
176
177
178
179
180
181
182
183
 
 
 
 
 
 
 
 
 
184
185
186
187
188
189
190
191
192
 
 
 
 
 
 
 
 
193
194
195
 
175
176
177
 
 
 
 
 
 
178
179
180
181
182
183
184
185
186
187
 
 
 
 
 
 
 
 
188
189
190
191
192
193
194
195
196
197
198
@@ -175,21 +175,24 @@
  else:   todo.add((None, newhexsha, childpath))   - def iter_tree_contents(self, tree): - """Yield (path, mode, hexsha) tuples for all non-Tree objects in a tree. - - :param tree: SHA1 of the root of the tree - """ - todo = set([(tree, "")]) + def iter_tree_contents(self, tree_id): + """Iterate the contents of a tree and all subtrees. + + Iteration is depth-first, as in e.g. os.walk. + + :param tree_id: SHA1 of the tree. + :yield: Tuples of (path, mode, hexhsa) for objects in a tree. + """ + todo = [('', stat.S_IFDIR, tree_id)]   while todo: - (tid, tpath) = todo.pop() - tree = self[tid] - for name, mode, hexsha in tree.iteritems(): - path = posixpath.join(tpath, name) - if stat.S_ISDIR(mode): - todo.add((hexsha, path)) - else: - yield path, mode, hexsha + path, mode, hexsha = todo.pop() + if stat.S_ISDIR(mode): + entries = reversed(self[hexsha].iteritems()) + for name, entry_mode, entry_hexsha in entries: + entry_path = posixpath.join(path, name) + todo.append((entry_path, entry_mode, entry_hexsha)) + else: + yield path, mode, hexsha     def find_missing_objects(self, haves, wants, progress=None,   get_tagged=None):
Change 1 of 2 Show Entire File dulwich/​tests/​test_object_store.py Stacked
 
23
24
25
 
 
 
26
27
28
 
75
76
77
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
78
79
80
 
23
24
25
26
27
28
29
30
31
 
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
@@ -23,6 +23,9 @@
 import shutil  import tempfile   +from dulwich.index import ( + commit_tree, + )  from dulwich.objects import (   Blob,   ) @@ -75,6 +78,24 @@
  r = self.store[testobject.id]   self.assertEquals(r, testobject)   + def test_iter_tree_contents(self): + blob_a = make_object(Blob, data='a') + blob_b = make_object(Blob, data='b') + blob_c = make_object(Blob, data='c') + for blob in [blob_a, blob_b, blob_c]: + self.store.add_object(blob) + + blobs = [ + ('a', blob_a.id, 0100644), + ('ad/b', blob_b.id, 0100644), + ('ad/bd/c', blob_c.id, 0100755), + ('ad/c', blob_c.id, 0100644), + ('c', blob_c.id, 0100644), + ] + tree_id = commit_tree(self.store, blobs) + self.assertEquals([(p, m, h) for (p, h, m) in blobs], + list(self.store.iter_tree_contents(tree_id))) +    class MemoryObjectStoreTests(ObjectStoreTests, TestCase):