Re: Index format v5

[Thomas Gummerer <t.gummerer@gmail.com>]

On 05/10, Michael Haggerty wrote:
> On 05/10/2012 02:19 PM, Thomas Gummerer wrote:
> >== Flat loading
> >
> >Since internally git expects and works with lexicografic ordering,
> >a simple linear scan throught the subdirectories doesn't give
> >the right internal sorting. To achieve the right internal sorting
> >the loading will be done in the following way:
> >
> >The data structure is a stack of queues, to allow continous reading
> >of the file.
> >
> >s ->  queue1
> >t ->  queue2
> >a ->  queue3
> >c ->  queue4
> >k ->  queue5
> >
> >dirs = read_all_directories
> >
> >foreach dir in dirs do
> >     file = read_next_file
> >
> >     while element_on_top_of_stack.first_element<  nextdir
> >         indexentries.append(dequeue(element_on_top_of_stack))
> >         if element_on_top_of_stack == emtpy:
> >             remove_element_on_top_of_stack
> >
> >     if file[filename]<  nextdir
> >         indexentries.append(file)
> >     else
> >         queue.add(file)
> >         foreach f in rest_of_files_in_directory:
> >             queue.add(f)
> >         stack.push(queue)
> >
> >foreach queue in stack:
> >     foreach entry in queue:
> >         indexentry.append(entry)
> 
> 1. It seems to me that the first time that a file with a filename
> before nextdir is encountered, the reading of the directory
> containing the file will be terminated.  This would, for example, be
> the case for any directory that contains multiple files but no
> subdirectories.
> 
> 2. There is still a lot that is unnecessarily obscure.  For example,
> I suppose (but you don't say) that "rest_of_files_in_directory"
> means to read the files at that moment.  It would be more explicit
> (and no more verbose) to write
> 
>     while (f = read_next_file()) != NULL:
>         queue.add(f)
> 
> 3. You don't cover corner cases, like when read_next_file() is
> called but there are no files left in the directory, or when there
> is no nextdir (which itself is not defined).  OK, this pseudocode is
> only meant to be illustrative, so I guess we can wait until your
> real implementation to see such details.  On the other hand, you
> probably want to get all the details straight in pseudocode or
> Python before you start translating it into C.
> 
> 4. I think the algorithm would be easier to understand and implement
> if it were written recursively.  The call stack would replace your
> explicit stack (but you would still need one queue per directory
> level).  A key observation is that when "nextdir" precedes the next
> file, then all of the files in subdirectories of nextdir do as well.
> Thus an obvious recursion would be to call a function like
> read_all_files_under_dir(indexentries, dirs, dirindex) at this
> point, which would consume all of the directories that are
> subdirectories of dirs[dirindex] (i.e., all directories whose names
> have the string dirs[dirindex] as a prefix).  Using this method
> would mean that there is no need to compare each file under
> dirs[dirindex] against the next file in the outer directory.
> 
> Michael

Thanks for your feedback! To get clearer code I've now written a
working reader for the v5 index format in Python. The full reader
would probably be to long for the mailing list, but here is the
interesting part:


def readfiles(directories, dirnr, entries):
    global filedata
    f.seek(directories[dirnr]["foffset"])
    offset = struct.unpack("!I", fread(4))[0]
    f.seek(offset)
    filedata = list()
    queue = list()
    i = 0
    while i < directories[dirnr]["nfiles"]:
        filedata.append(struct.pack("!I", f.tell()))
        filename = ""
        byte = fread(1)
        while byte != '\0':
            filename += byte
            byte = fread(1)

        data = struct.unpack("!HHIII", fread(16))
        objhash = fread(20)
        readcrc = struct.pack("!i", binascii.crc32("".join(filedata)))
        crc = f.read(4)
        if readcrc != crc:
            print "Wrong CRC: " + filename
        filedata = list()

        i += 1

        queue.append(dict({"name": directories[dirnr]["pathname"] + filename, "flags": data[0], "mode": data[1], "mtimes": data[2], "mtimens": data[3], "statcrc": data[4], "objhash": binascii.hexlify(objhash)}))

    if len(directories) > dirnr:
        i = 0
        while i < len(queue):
            if len(directories) - 1 > dirnr and queue[i]["name"] > directories[dirnr + 1]["pathname"]:
                entries, dirnr = readfiles(directories, dirnr + 1, entries)
            else:
                entries.append(queue[i])
                i += 1
        return entries, dirnr

The full reader can be found here:
https://github.com/tgummerer/git/blob/pythonprototype/git-read-index-v5.py

-- 
Thomas