Show More
@@ -363,6 +363,39 b' static int lazymanifest_delitem(lazymani' | |||||
363 | return 0; |
|
363 | return 0; | |
364 | } |
|
364 | } | |
365 |
|
365 | |||
|
366 | /* Do a binary search for the insertion point for new, creating the | |||
|
367 | * new entry if needed. */ | |||
|
368 | static int internalsetitem(lazymanifest *self, line *new) { | |||
|
369 | int start = 0, end = self->numlines; | |||
|
370 | while (start < end) { | |||
|
371 | int pos = start + (end - start) / 2; | |||
|
372 | int c = linecmp(new, self->lines + pos); | |||
|
373 | if (c < 0) | |||
|
374 | end = pos; | |||
|
375 | else if (c > 0) | |||
|
376 | start = pos + 1; | |||
|
377 | else { | |||
|
378 | if (self->lines[pos].deleted) | |||
|
379 | self->livelines++; | |||
|
380 | start = pos; | |||
|
381 | goto finish; | |||
|
382 | } | |||
|
383 | } | |||
|
384 | /* being here means we need to do an insert */ | |||
|
385 | if (!realloc_if_full(self)) { | |||
|
386 | PyErr_NoMemory(); | |||
|
387 | return -1; | |||
|
388 | } | |||
|
389 | memmove(self->lines + start + 1, self->lines + start, | |||
|
390 | (self->numlines - start) * sizeof(line)); | |||
|
391 | self->numlines++; | |||
|
392 | self->livelines++; | |||
|
393 | finish: | |||
|
394 | self->lines[start] = *new; | |||
|
395 | self->dirty = true; | |||
|
396 | return 0; | |||
|
397 | } | |||
|
398 | ||||
366 | static int lazymanifest_setitem( |
|
399 | static int lazymanifest_setitem( | |
367 | lazymanifest *self, PyObject *key, PyObject *value) |
|
400 | lazymanifest *self, PyObject *key, PyObject *value) | |
368 | { |
|
401 | { | |
@@ -378,7 +411,6 b' static int lazymanifest_setitem(' | |||||
378 | char *dest; |
|
411 | char *dest; | |
379 | int i; |
|
412 | int i; | |
380 | line new; |
|
413 | line new; | |
381 | line *hit; |
|
|||
382 | if (!PyString_Check(key)) { |
|
414 | if (!PyString_Check(key)) { | |
383 | PyErr_Format(PyExc_TypeError, |
|
415 | PyErr_Format(PyExc_TypeError, | |
384 | "setitem: manifest keys must be a string."); |
|
416 | "setitem: manifest keys must be a string."); | |
@@ -446,32 +478,8 b' static int lazymanifest_setitem(' | |||||
446 | } |
|
478 | } | |
447 | new.from_malloc = true; /* is `start` a pointer we allocated? */ |
|
479 | new.from_malloc = true; /* is `start` a pointer we allocated? */ | |
448 | new.deleted = false; /* is this entry deleted? */ |
|
480 | new.deleted = false; /* is this entry deleted? */ | |
449 | hit = bsearch(&new, self->lines, self->numlines, |
|
481 | if (internalsetitem(self, &new)) { | |
450 | sizeof(line), &linecmp); |
|
482 | return -1; | |
451 | self->dirty = true; |
|
|||
452 | if (hit) { |
|
|||
453 | /* updating a line we already had */ |
|
|||
454 | if (hit->from_malloc) { |
|
|||
455 | free(hit->start); |
|
|||
456 | } |
|
|||
457 | if (hit->deleted) { |
|
|||
458 | self->livelines++; |
|
|||
459 | } |
|
|||
460 | *hit = new; |
|
|||
461 | } else { |
|
|||
462 | /* new line */ |
|
|||
463 | if (!realloc_if_full(self)) { |
|
|||
464 | PyErr_NoMemory(); |
|
|||
465 | return -1; |
|
|||
466 | } |
|
|||
467 | self->lines[self->numlines++] = new; |
|
|||
468 | self->livelines++; |
|
|||
469 | /* TODO: do a binary search and insert rather than |
|
|||
470 | * append and qsort. Also offer a batch-insert |
|
|||
471 | * interface, which should be a nice little |
|
|||
472 | * performance win. |
|
|||
473 | */ |
|
|||
474 | qsort(self->lines, self->numlines, sizeof(line), &linecmp); |
|
|||
475 | } |
|
483 | } | |
476 | return 0; |
|
484 | return 0; | |
477 | } |
|
485 | } |
@@ -133,6 +133,10 b' class testmanifest(unittest.TestCase):' | |||||
133 | self.assertRaises(KeyError, lambda : m['foo']) |
|
133 | self.assertRaises(KeyError, lambda : m['foo']) | |
134 | self.assertEqual(1, len(m)) |
|
134 | self.assertEqual(1, len(m)) | |
135 | self.assertEqual(1, len(list(m))) |
|
135 | self.assertEqual(1, len(list(m))) | |
|
136 | # now restore and make sure everything works right | |||
|
137 | m['foo'] = 'a' * 20, '' | |||
|
138 | self.assertEqual(2, len(m)) | |||
|
139 | self.assertEqual(2, len(list(m))) | |||
136 |
|
140 | |||
137 | def testManifestDiff(self): |
|
141 | def testManifestDiff(self): | |
138 | MISSING = (None, '') |
|
142 | MISSING = (None, '') |
General Comments 0
You need to be logged in to leave comments.
Login now