file   : algoritm.txt
author : Tormod Tjaberg
created: 2002-06-09
updated: 2002-09-30 21:46 TT

This document describes the workings of fdaz.

problem
=======

Determine if ZIP archives contain any duplicates across them.

solution
========

. Get list of ZIP archives to process

. Add the name of the archive to a tree (FileName_t)

. Open each archive and read the TOC (Table Of Contents)

. Attempt to insert the CRC32 of each file into a tree (CRC32_Item_t)

. Each item which is inserted has the following:
  . The CRC32 of the file in the archive which is used as the key
  . An index giving the position of the file in the TOC, since
    one archive may have duplicates within itself.
  . A pointer to the name of this archive. This pointer points
    into the FileName_t tree. 

. When an item is inserted into the CRC32 tree we have two 
  possible outcomes:
  . The item is not present in the tree and is successfully inserted.
  . The CRC32 is already present i.e. we have a duplicate.

. To get a nicely formatted list of duplicates we have another
  tree which is called the duplicate tree (DupeTree_t). The node
  of this tree contains the following:
  . A pointer to the object in the CRC32 tree.
  . A pointer to the next element in a linked list.
    This linked list contains a list of CRC32 objects which
    all have the same CRC32.

. When we have a duplicate in the CRC32 tree do the following:
  . Call DupeTreeInsert() with the original node in the 
    CRC32 (Primary) tree as well as the dupe (Secondary) found.
  . Attempt to insert primary object first, if it is 
    already present do nothing. We need to do this because...

  . Then insert the secondary object:
  . The second insertion will always be a duplicate. So go to the 
    end of the linked list and append the duplicate there. 

. After all files have been added we have a dupetree where
  each node contains a list of all the files which match.
. Do the traverser
. On dupes open the zip file and map cd_pos with one stored in
  the tree.

optimizations
=============

. Allocate the filename and tree node in one go
. Use pointers into existing structures
. Avoid any duplication of members
. Use the FSA (Fixed Size Allocator) library where possible

note
====

. The CRC32 tree will never contain the entire TOC of a file.
  It will NOT add duplicates to this tree (Nor can it)

