func sortDirectory(directory *filesystem.Directory) {
	// Sort regular files.
	var regularFileList regularFileList
	regularFileList = directory.RegularFileList
	sort.Sort(regularFileList)
	directory.RegularFileList = regularFileList
	// Sort symlinks.
	var symlinkList symlinkList
	symlinkList = directory.SymlinkList
	sort.Sort(symlinkList)
	directory.SymlinkList = symlinkList
	// Sort files.
	var fileList fileList
	fileList = directory.FileList
	sort.Sort(fileList)
	directory.FileList = fileList
	// Sort directories.
	var directoryList directoryList
	directoryList = directory.DirectoryList
	sort.Sort(directoryList)
	directory.DirectoryList = directoryList
	// Recurse through directories.
	for _, subdir := range directory.DirectoryList {
		sortDirectory(subdir)
	}
}

func (decoderData *decoderData) addFile(header *tar.Header,
	parent *filesystem.Directory, name string) error {
	var newInode filesystem.Inode
	if header.Typeflag == tar.TypeChar {
		newInode.Mode = filesystem.FileMode((header.Mode & ^syscall.S_IFMT) |
			syscall.S_IFCHR)
	} else if header.Typeflag == tar.TypeBlock {
		newInode.Mode = filesystem.FileMode((header.Mode & ^syscall.S_IFMT) |
			syscall.S_IFBLK)
	} else if header.Typeflag == tar.TypeFifo {
		newInode.Mode = filesystem.FileMode((header.Mode & ^syscall.S_IFMT) |
			syscall.S_IFIFO)
	} else {
		return errors.New(fmt.Sprintf("unsupported type: %v", header.Typeflag))
	}
	newInode.Uid = uint32(header.Uid)
	newInode.Gid = uint32(header.Gid)
	newInode.MtimeNanoSeconds = int32(header.ModTime.Nanosecond())
	newInode.MtimeSeconds = header.ModTime.Unix()
	if header.Devminor > 255 {
		return errors.New(fmt.Sprintf("minor device number: %d too large",
			header.Devminor))
	}
	newInode.Rdev = uint64(header.Devmajor<<8 | header.Devminor)
	decoderData.inodeTable[header.Name] = decoderData.nextInodeNumber
	decoderData.fileSystem.InodeTable[decoderData.nextInodeNumber] =
		&newInode
	var newEntry filesystem.File
	newEntry.Name = name
	newEntry.InodeNumber = decoderData.nextInodeNumber
	parent.FileList = append(parent.FileList, &newEntry)
	decoderData.nextInodeNumber++
	return nil
}

func addFile(directory *filesystem.Directory, fileSystem, oldFS *FileSystem,
	name string, directoryPathName string, stat *syscall.Stat_t) error {
	inode, isNewInode := fileSystem.getInode(stat)
	var file filesystem.File
	file.Name = name
	file.InodeNumber = stat.Ino
	file.SetInode(inode)
	if isNewInode {
		err := scanFile(&file, fileSystem, directoryPathName)
		if err != nil {
			return err
		}
		if oldFS != nil && oldFS.InodeTable != nil {
			if oldInode, found := oldFS.InodeTable[stat.Ino]; found {
				if filesystem.CompareInodes(inode, oldInode, nil) {
					inode = oldInode
					file.SetInode(inode)
					fileSystem.InodeTable[stat.Ino] = inode
				}
			}
		}
	}
	directory.FileList = append(directory.FileList, &file)
	return nil
}

func addSymlink(directory *filesystem.Directory, fileSystem, oldFS *FileSystem,
	name string, directoryPathName string, stat *syscall.Stat_t) error {
	inode, isNewInode := fileSystem.getSymlinkInode(stat)
	var symlink filesystem.Symlink
	symlink.Name = name
	symlink.InodeNumber = stat.Ino
	symlink.SetInode(inode)
	if isNewInode {
		err := scanSymlink(&symlink, fileSystem, directoryPathName)
		if err != nil {
			return err
		}
		if oldFS != nil && oldFS.SymlinkInodeTable != nil {
			if oldInode, found := oldFS.SymlinkInodeTable[stat.Ino]; found {
				if filesystem.CompareSymlinkInodes(inode, oldInode, nil) {
					inode = oldInode
					symlink.SetInode(inode)
					fileSystem.SymlinkInodeTable[stat.Ino] = inode
				}
			}
		}
	}
	directory.SymlinkList = append(directory.SymlinkList, &symlink)
	return nil
}

func (decoderData *decoderData) addHardlink(header *tar.Header,
	parent *filesystem.Directory, name string) error {
	header.Linkname = normaliseFilename(header.Linkname)
	if inum, ok := decoderData.regularInodeTable[header.Linkname]; ok {
		var newEntry filesystem.RegularFile
		newEntry.Name = name
		newEntry.InodeNumber = inum
		parent.RegularFileList = append(parent.RegularFileList, &newEntry)
	} else if inum, ok := decoderData.symlinkInodeTable[header.Linkname]; ok {
		var newEntry filesystem.Symlink
		newEntry.Name = name
		newEntry.InodeNumber = inum
		parent.SymlinkList = append(parent.SymlinkList, &newEntry)
	} else if inum, ok := decoderData.inodeTable[header.Linkname]; ok {
		var newEntry filesystem.File
		newEntry.Name = name
		newEntry.InodeNumber = inum
		parent.FileList = append(parent.FileList, &newEntry)
	} else {
		return errors.New(fmt.Sprintf("missing hardlink target: %s",
			header.Linkname))
	}
	return nil
}

func (decoderData *decoderData) addSymlink(header *tar.Header,
	parent *filesystem.Directory, name string) error {
	var newInode filesystem.SymlinkInode
	newInode.Uid = uint32(header.Uid)
	newInode.Gid = uint32(header.Gid)
	newInode.Symlink = header.Linkname
	decoderData.symlinkInodeTable[header.Name] = decoderData.nextInodeNumber
	decoderData.fileSystem.SymlinkInodeTable[decoderData.nextInodeNumber] =
		&newInode
	var newEntry filesystem.Symlink
	newEntry.Name = name
	newEntry.InodeNumber = decoderData.nextInodeNumber
	parent.SymlinkList = append(parent.SymlinkList, &newEntry)
	decoderData.nextInodeNumber++
	return nil
}

func (decoderData *decoderData) addDirectory(header *tar.Header,
	parent *filesystem.Directory, name string) error {
	var newEntry filesystem.Directory
	newEntry.Name = name
	newEntry.Mode = filesystem.FileMode((header.Mode & ^syscall.S_IFMT) |
		syscall.S_IFDIR)
	newEntry.Uid = uint32(header.Uid)
	newEntry.Gid = uint32(header.Gid)
	parent.DirectoryList = append(parent.DirectoryList, &newEntry)
	decoderData.directoryTable[header.Name] = &newEntry
	return nil
}

func (decoderData *decoderData) addRegularFile(tarReader *tar.Reader,
	dataHandler DataHandler, header *tar.Header, parent *filesystem.Directory,
	name string) error {
	var newInode filesystem.RegularInode
	newInode.Mode = filesystem.FileMode((header.Mode & ^syscall.S_IFMT) |
		syscall.S_IFREG)
	newInode.Uid = uint32(header.Uid)
	newInode.Gid = uint32(header.Gid)
	newInode.MtimeNanoSeconds = int32(header.ModTime.Nanosecond())
	newInode.MtimeSeconds = header.ModTime.Unix()
	newInode.Size = uint64(header.Size)
	if header.Size > 0 {
		data, err := ioutil.ReadAll(tarReader)
		if err != nil {
			return errors.New("error reading file data" + err.Error())
		}
		if int64(len(data)) != header.Size {
			return errors.New(fmt.Sprintf(
				"failed to read file data, wanted: %d, got: %d bytes",
				header.Size, len(data)))
		}
		newInode.Hash, err = dataHandler.HandleData(data)
		if err != nil {
			return err
		}
	}
	decoderData.regularInodeTable[header.Name] = decoderData.nextInodeNumber
	decoderData.fileSystem.RegularInodeTable[decoderData.nextInodeNumber] =
		&newInode
	var newEntry filesystem.RegularFile
	newEntry.Name = name
	newEntry.InodeNumber = decoderData.nextInodeNumber
	parent.RegularFileList = append(parent.RegularFileList, &newEntry)
	decoderData.nextInodeNumber++
	return nil
}

func addDirectory(directory *filesystem.Directory,
	fileSystem, oldFS *FileSystem,
	name string, directoryPathName string, stat *syscall.Stat_t) error {
	myPathName := path.Join(directoryPathName, name)
	if fileSystem.directoryInodeList[stat.Ino] {
		return errors.New("Hardlinked directory: " + myPathName)
	}
	fileSystem.directoryInodeList[stat.Ino] = true
	var dir filesystem.Directory
	dir.Name = name
	dir.Mode = filesystem.FileMode(stat.Mode)
	dir.Uid = stat.Uid
	dir.Gid = stat.Gid
	err := scanDirectory(&dir, fileSystem, oldFS, directoryPathName)
	if err != nil {
		return err
	}
	directory.DirectoryList = append(directory.DirectoryList, &dir)
	return nil
}

func scanDirectory(directory *filesystem.Directory,
	fileSystem, oldFS *FileSystem, parentName string) error {
	myPathName := path.Join(parentName, directory.Name)
	file, err := os.Open(path.Join(fileSystem.rootDirectoryName, myPathName))
	if err != nil {
		return err
	}
	names, err := file.Readdirnames(-1)
	file.Close()
	if err != nil {
		return err
	}
	sort.Strings(names)
	for _, name := range names {
		if directory == &fileSystem.Directory && name == ".subd" {
			continue
		}
		filename := path.Join(myPathName, name)
		if fileSystem.configuration.ScanFilter.Match(filename) {
			continue
		}
		var stat syscall.Stat_t
		err := syscall.Lstat(path.Join(fileSystem.rootDirectoryName, filename),
			&stat)
		if err != nil {
			if err == syscall.ENOENT {
				continue
			}
			return err
		}
		if stat.Dev != fileSystem.dev {
			continue
		}
		if stat.Mode&syscall.S_IFMT == syscall.S_IFDIR {
			err = addDirectory(directory, fileSystem, oldFS, name, myPathName,
				&stat)
		} else if stat.Mode&syscall.S_IFMT == syscall.S_IFREG {
			err = addRegularFile(directory, fileSystem, oldFS, name, myPathName,
				&stat)
		} else if stat.Mode&syscall.S_IFMT == syscall.S_IFLNK {
			err = addSymlink(directory, fileSystem, oldFS, name, myPathName,
				&stat)
		} else if stat.Mode&syscall.S_IFMT == syscall.S_IFSOCK {
			continue
		} else {
			err = addFile(directory, fileSystem, oldFS, name, myPathName, &stat)
		}
		if err != nil {
			if err == syscall.ENOENT {
				continue
			}
			return err
		}
	}
	// Save file and directory lists which are exactly the right length.
	regularFileList := make([]*filesystem.RegularFile,
		len(directory.RegularFileList))
	copy(regularFileList, directory.RegularFileList)
	directory.RegularFileList = regularFileList
	symlinkList := make([]*filesystem.Symlink, len(directory.SymlinkList))
	copy(symlinkList, directory.SymlinkList)
	directory.SymlinkList = symlinkList
	fileList := make([]*filesystem.File, len(directory.FileList))
	copy(fileList, directory.FileList)
	directory.FileList = fileList
	directoryList := make([]*filesystem.Directory, len(directory.DirectoryList))
	copy(directoryList, directory.DirectoryList)
	directory.DirectoryList = directoryList
	return nil
}