← Back to branch summary

~lifeless/+junk/bzr-groupcompress

« back to all changes in this revision

Viewing changes to _groupcompress_c.pyx

  • Committer: Robert Collins
  • Date: 2008-07-25 03:13:26 UTC
  • mfrom: (14.1.33 groupcompress)
  • Revision ID: robertc@robertcollins.net-20080725031326-2c1xq6xusfoefxsi
Merge John.

Show diffs side-by-side

added added

removed removed

Lines of Context:
_groupcompress_c.pyx
175
175
        # size hash table. However, any collision would then have a long way to
176
176
        # traverse before it could find a 'free' slot.
177
177
        # So we set the minimum size to give us 33% empty slots.
178
 
        min_size = <Py_ssize_t>(needed * 1.5)
 
178
        min_size = <Py_ssize_t>(needed * 2)
179
179
        hash_size = 1
180
180
        while hash_size < min_size:
181
181
            hash_size = hash_size << 1
199
199
        # We start off with a 8k hash (after doubling), because there isn't a
200
200
        # lot of reason to go smaller than that (this class isn't one you'll be
201
201
        # instantiating thousands of, and you are always likely to grow here.)
202
 
        hash_size = 4096
 
202
        hash_size = 2048
203
203
        while hash_size < needed:
204
204
            hash_size = hash_size << 1
205
 
        # And we always give at least 2x blank space
206
 
        hash_size = hash_size << 1
 
205
        # And we always give at least 4x blank space
 
206
        hash_size = hash_size << 2
207
207
        return hash_size
208
208
 
209
209
    def _py_compute_recommended_hash_size(self, needed):
543
543
    cdef int i
544
544
    lst = []
545
545
    for i from 0 <= i < count:
546
 
        lst.append(array[i])
 
546
        PyList_Append(lst, array[i])
547
547
    return lst
548
548
 
549
549
 
 
550
cdef Py_ssize_t list_as_array(object lst, Py_ssize_t **array) except -1:
 
551
    """Convert a Python sequence to an integer array.
 
552
 
 
553
    :return: The size of the output, -1 on error
 
554
    """
 
555
    cdef int i
 
556
    cdef PyObject *seq
 
557
    cdef Py_ssize_t size
 
558
 
 
559
    seq = PySequence_Fast(lst, "expected a sequence for lst")
 
560
    try:
 
561
        size = PySequence_Fast_GET_SIZE(seq)
 
562
        array[0] = <Py_ssize_t*>safe_malloc(sizeof(Py_ssize_t) * size)
 
563
        for i from 0 <= i < size:
 
564
            array[0][i] = <object>PySequence_Fast_GET_ITEM(seq, i)
 
565
    finally:
 
566
        Py_DECREF(seq)
 
567
    return size
 
568
 
 
569
 
550
570
def _get_longest_match(equivalence_table, pos, max_pos, locations):
551
571
    """Get the longest possible match for the current position."""
552
572
    cdef EquivalenceTable eq
573
593
    copy_count = 0
574
594
 
575
595
    # TODO: Handle when locations is not None
 
596
    if locations is not None:
 
597
        match_count = list_as_array(locations, &matches)
576
598
    while cpos < cmax_pos:
577
599
        # TODO: Instead of grabbing the full list of matches and then doing an
578
600
        #       intersection, use a helper that does the intersection
579
601
        #       as-it-goes.
580
 
        line = PyList_GET_ITEM(eq._right_lines, cpos)
581
 
        safe_free(<void**>&matches)
582
 
        match_count = eq.get_raw_matches(line, &matches)
 
602
        if matches == NULL:
 
603
            line = PyList_GET_ITEM(eq._right_lines, cpos)
 
604
            safe_free(<void**>&matches)
 
605
            match_count = eq.get_raw_matches(line, &matches)
583
606
        if match_count == 0:
584
607
            # No more matches, just return whatever we have, but we know that
585
608
            # this last position is not going to match anything