← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_dirstate_helpers_c.pyx

  • Committer: John Arbash Meinel
  • Date: 2007-07-11 00:01:54 UTC
  • mto: This revision was merged to the branch mainline in revision 2643.
  • Revision ID: john@arbash-meinel.com-20070711000154-4et8yf8si3jgxmgc
(broken) Try to properly implement DirState._bisect*
Involves rewriting some helper functions.
Currently something is wrong.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_dirstate_helpers_c.pyx
50
50
    char *strchr(char *s1, char c)
51
51
    int strncmp(char *s1, char *s2, int len)
52
52
    int strcmp(char *s1, char *s2)
 
53
    void *memchr(void *s, int c, size_t len)
 
54
    int memcmp(void *b1, void *b2, size_t len)
 
55
    # ??? memrchr is a GNU extension :(
 
56
    # void *memrchr(void *s, int c, size_t len)
 
57
 
 
58
 
 
59
cdef void* _my_memrchr(void *s, int c, size_t n):
 
60
    # memrchr seems to be a GNU extension, so we have to implement it ourselves
 
61
    # We semi-cheat, and just call memchr repeatedly until we run out of path.
 
62
    # And then return the last match.
 
63
    cdef void *pos
 
64
    cdef void *end
 
65
    cdef void *last_pos
 
66
 
 
67
    last_pos = NULL
 
68
    end = <void*>((<char*>s) + n)
 
69
    pos = memchr(s, c, n)
 
70
    while pos != NULL and pos < end:
 
71
        last_pos = pos
 
72
        pos = memchr(pos+1, c, end-pos)
 
73
    return last_pos
 
74
 
 
75
 
 
76
def _py_memrchr(s, c):
 
77
    """Just to expose _my_memrchr for testing.
 
78
 
 
79
    :param s: The Python string to search
 
80
    :param c: The character to search for
 
81
    :return: The offset to the last instance of 'c' in s
 
82
    """
 
83
    cdef void *_s
 
84
    cdef void *found
 
85
    cdef int length
 
86
    cdef char *_c
 
87
 
 
88
    _s = PyString_AsString(s)
 
89
    length = PyString_Size(s)
 
90
 
 
91
    _c = PyString_AsString(c)
 
92
    assert PyString_Size(c) == 1,\
 
93
        'Must be a single character string, not %s' % (c,)
 
94
    found = _my_memrchr(_s, _c[0], length)
 
95
    if found == NULL:
 
96
        return None
 
97
    return found - _s
53
98
 
54
99
 
55
100
cdef int _cmp_by_dirs(char *path1, int size1, char *path2, int size2):
135
180
                        PyString_Size(path2))
136
181
 
137
182
 
 
183
def cmp_path_by_dirblock_c(path1, path2):
 
184
    """Compare two paths based on what directory they are in.
 
185
 
 
186
    This generates a sort order, such that all children of a directory are
 
187
    sorted together, and grandchildren are in the same order as the
 
188
    children appear. But all grandchildren come after all children.
 
189
 
 
190
    :param path1: first path
 
191
    :param path2: the second path
 
192
    :return: positive number if ``path1`` comes first,
 
193
        0 if paths are equal
 
194
        and a negative number if ``path2`` sorts first
 
195
    """
 
196
    return _cmp_path_by_dirblock(PyString_AsString(path1),
 
197
                                 PyString_Size(path1),
 
198
                                 PyString_AsString(path2),
 
199
                                 PyString_Size(path2))
 
200
 
 
201
 
 
202
cdef _cmp_path_by_dirblock(char *path1, int path1_len,
 
203
                           char *path2, int path2_len):
 
204
    cdef char *dirname1
 
205
    cdef int dirname1_len
 
206
    cdef char *dirname2
 
207
    cdef int dirname2_len
 
208
    cdef char *basename1
 
209
    cdef int basename1_len
 
210
    cdef char *basename2
 
211
    cdef int basename2_len
 
212
    cdef int cur_len
 
213
    cdef int cmp_val
 
214
 
 
215
    dirname1 = path1
 
216
    dirname1_len = path1_len
 
217
 
 
218
    dirname2 = path2
 
219
    dirname2_len = path2_len
 
220
 
 
221
    if path1_len == 0 and path2_len == 0:
 
222
        return 0
 
223
 
 
224
    if path1_len == 0:
 
225
        return -1
 
226
 
 
227
    if path2_len == 0:
 
228
        return 1
 
229
 
 
230
    basename1 = <char*>_my_memrchr(dirname1, c'/', dirname1_len)
 
231
 
 
232
    if basename1 == NULL:
 
233
        basename1 = dirname1
 
234
        dirname1 = ''
 
235
        dirname1_len = 0
 
236
    else:
 
237
        cur_len = basename1 - dirname1
 
238
        basename1 = basename1 + 1
 
239
        basename1_len = dirname1_len - cur_len - 1
 
240
        dirname1_len = cur_len
 
241
 
 
242
    basename2 = <char*>_my_memrchr(dirname2, c'/', dirname2_len)
 
243
 
 
244
    if basename2 == NULL:
 
245
        basename2 = dirname2
 
246
        dirname2 = ''
 
247
        dirname2_len = 0
 
248
    else:
 
249
        cur_len = basename2 - dirname2
 
250
        basename2 = basename2 + 1
 
251
        basename2_len = dirname2_len - cur_len - 1
 
252
        dirname2_len = cur_len
 
253
 
 
254
    cmp_val = _cmp_by_dirs(dirname1, dirname1_len,
 
255
                           dirname2, dirname2_len)
 
256
    if cmp_val != 0:
 
257
        return cmp_val
 
258
 
 
259
    cur_len = basename1_len
 
260
    if basename2_len < basename1_len:
 
261
        cur_len = basename2_len
 
262
 
 
263
    cmp_val = memcmp(basename1, basename2, cur_len)
 
264
    if cmp_val != 0:
 
265
        return cmp_val
 
266
    if basename1_len == basename2_len:
 
267
        return 0
 
268
    if basename1_len < basename2_len:
 
269
        return -1
 
270
    return 1
 
271
 
 
272
 
 
273
def bisect_path_left_c(paths, path):
 
274
    """Return the index where to insert path into paths.
 
275
 
 
276
    This uses a path-wise comparison so we get::
 
277
        a
 
278
        a-b
 
279
        a=b
 
280
        a/b
 
281
    Rather than::
 
282
        a
 
283
        a-b
 
284
        a/b
 
285
        a=b
 
286
    :param paths: A list of paths to search through
 
287
    :param path: A single path to insert
 
288
    :return: An offset where 'path' can be inserted.
 
289
    :seealso: bisect.bisect_left
 
290
    """
 
291
    cdef int _lo
 
292
    cdef int _hi
 
293
    cdef int _mid
 
294
    cdef char *path_str
 
295
    cdef int path_size
 
296
    cdef char *cur_str
 
297
    cdef int cur_size
 
298
    cdef void *cur
 
299
 
 
300
    if not PyList_CheckExact(paths):
 
301
        raise TypeError('you must pass a python list for paths')
 
302
    if not PyString_CheckExact(path):
 
303
        raise TypeError('you must pass a string for path')
 
304
 
 
305
    _hi = len(paths)
 
306
    _lo = 0
 
307
 
 
308
    path_str = PyString_AsString(path)
 
309
    path_size = PyString_Size(path)
 
310
 
 
311
    while _lo < _hi:
 
312
        _mid = (_lo + _hi) / 2
 
313
        cur = PyList_GetItem_object_void(paths, _mid)
 
314
        cur_str = PyString_AS_STRING_void(cur)
 
315
        cur_size = PyString_GET_SIZE_void(cur)
 
316
        if _cmp_path_by_dirblock(cur_str, cur_size, path_str, path_size) < 0:
 
317
            _lo = _mid + 1
 
318
        else:
 
319
            _hi = _mid
 
320
    return _lo
 
321
 
 
322
 
 
323
def bisect_path_right_c(paths, path):
 
324
    """Return the index where to insert path into paths.
 
325
 
 
326
    This uses a path-wise comparison so we get::
 
327
        a
 
328
        a-b
 
329
        a=b
 
330
        a/b
 
331
    Rather than::
 
332
        a
 
333
        a-b
 
334
        a/b
 
335
        a=b
 
336
    :param paths: A list of paths to search through
 
337
    :param path: A single path to insert
 
338
    :return: An offset where 'path' can be inserted.
 
339
    :seealso: bisect.bisect_right
 
340
    """
 
341
    cdef int _lo
 
342
    cdef int _hi
 
343
    cdef int _mid
 
344
    cdef char *path_str
 
345
    cdef int path_size
 
346
    cdef char *cur_str
 
347
    cdef int cur_size
 
348
    cdef void *cur
 
349
    cdef int cmp_val
 
350
 
 
351
    if not PyList_CheckExact(paths):
 
352
        raise TypeError('you must pass a python list for paths')
 
353
    if not PyString_CheckExact(path):
 
354
        raise TypeError('you must pass a string for path')
 
355
 
 
356
    _hi = len(paths)
 
357
    _lo = 0
 
358
 
 
359
    path_str = PyString_AsString(path)
 
360
    path_size = PyString_Size(path)
 
361
 
 
362
    while _lo < _hi:
 
363
        _mid = (_lo + _hi) / 2
 
364
        cur = PyList_GetItem_object_void(paths, _mid)
 
365
        cur_str = PyString_AS_STRING_void(cur)
 
366
        cur_size = PyString_GET_SIZE_void(cur)
 
367
        cmp_val = _cmp_path_by_dirblock(path_str, path_size, cur_str, cur_size)
 
368
        print 'c_left mid: %d, cmp_val %d, cur_str %r, path_str %r' % (
 
369
            _mid, cmp_val,
 
370
            PyString_FromStringAndSize(cur_str, cur_size),
 
371
            PyString_FromStringAndSize(path_str, path_size))
 
372
        if cmp_val < 0:
 
373
            _hi = _mid
 
374
        else:
 
375
            _lo = _mid + 1
 
376
    return _lo
 
377
 
 
378
 
138
379
def bisect_dirblock_c(dirblocks, dirname, lo=0, hi=None, cache=None):
139
380
    """Return the index where to insert dirname into the dirblocks.
140
381
 
168
409
    dirname_size = PyString_Size(dirname)
169
410
 
170
411
    while _lo < _hi:
171
 
        _mid = (_lo+_hi)/2
 
412
        _mid = (_lo + _hi) / 2
172
413
        # Grab the dirname for the current dirblock
173
414
        # cur = dirblocks[_mid][0]
174
415
        cur = PyTuple_GetItem_void_void(
176
417
        cur_str = PyString_AS_STRING_void(cur)
177
418
        cur_size = PyString_GET_SIZE_void(cur)
178
419
        if _cmp_by_dirs(cur_str, cur_size, dirname_str, dirname_size) < 0:
179
 
            _lo = _mid+1
 
420
            _lo = _mid + 1
180
421
        else:
181
422
            _hi = _mid
182
423
    return _lo
204
445
        """Return a pointer to the start of the next field."""
205
446
        cdef char *next
206
447
        next = self.cur
 
448
        # XXX: Change this to not use 'memchr' instead of 'strchr'
207
449
        self.cur = strchr(next, c'\0')
208
450
        size[0] = self.cur - next
209
451
        self.cur = self.cur + 1