A search algorithm implemented in C++
Art works in the Technical Services Group for the New York State Office of Mental Health. He can be reached on CompuServe at 75730,3076.
Imaging systems require a way to store and retrieve large amounts of unstructured data. At the New York Office of Mental Health, for instance, we estimate that at each of our 30 facilities there might be as many as 100,000,000 documents to be archived. However, the stability of vendors offering archiving tools is often suspect. (Indeed, some of the software we're using was provided by a leading vendor who has since filed for Chapter 11.) Consequently, we needed an indexing system that would allow many different image- file formats, be simple enough to test and implement within the project time allowed, but not lock us into any vendor-specific solution.
Typically, a document image system uses at least two files to store and retrieve documents. The first is a traditional file that has a text description of the image along with a key to a second file. The second file contains the document location. The user selects a record from the first file using a search algorithm. This front end can be complex, as when the system supports keyword searches, or even icons of the documents. Once the user selects a record, the application keys into the location index, finds the document, and displays it. The name of the image to be displayed is not important to the user and is often generated by the system. The second file can be any traditional indexing structure. In this article, I'll discuss the search algorithm used in this second file to locate images.
Our first attempts used published B-tree code. Because the image filenames did not have to be readable or intelligent in any way, we generated a meaningless sequential name, similar to tmpnam in stdio.h. We wrote some batch-testing programs that generated thousands of filename keys and stored them in our B-tree. The filenames were 14 characters long, a length that caused some concern. Large data items in
B-trees cause the tree to be deeper and larger. Disk thrashing ensued, and all we proved was that B-trees don't handle ordered data very well. Obviously, we needed to build random names. Before heading down the path of hash tables and random generators, however, we found a better way.
The Mapper
One of the fastest ways to locate data in a file is by going to a direct offset into a file. In C, you can do this with the lseek or fseek functions. We could store any location directions we wished at the chosen offset. This would yield very fast search times, and there would be less worry about the size of the location entry. Even the size of the location entry is reduced by using the image filename itself to derive an offset into a "mapper" file which contains directions to locate the image.
For example, to store the location of a file named C:\AA\12345678.TIF, we create an entry in the mapper file that's at a 12,345,678-byte offset. At this location, we store the device, subdirectory, and file extension. Encoding and decoding the image filename to and from a meaningful offset is simple. Fortuitously, the 4-byte long value needed by or lseek can be represented by the eight hex characters which form the filename. They're decoded as offsets into the mapper file. We've encapsulated the functions to manipulate these index entries in the mapper class written in C++.
The Mapper class header (see Listing One, page 104) contains a member struct that describes the layout of a mapper record. You should tailor this to your needs. The struct we're using is shown in Example 1. The device member is the drive letter. The path is a 2-byte directory entry. A DOS path label may be any alphabetic character or digit, as well as one of the following: ! _ - @ # $ % ^ & ( ) ~ ` { }. In other words, there are 50 possible single-character paths available: 50x50+50=2550 directories on each device. We can tell which image viewer to use based on the FileExtension member. A .TIF extension will call the TIFF viewer, a WP5 extension will call the WordPerfect viewer, and so on. If your application uses a more intelligent viewer, you could drop this member.
The larger this struct is, the fewer mapper entries you'll be able to write. But don't get too ambitious in keeping the struct slim. Few systems have the need or the space to store as many files as the 6-byte struct given in this example (232/sizeof(struct)=715 million); see the text box entitled, "How Much Can We Store?".
At minimum, the struct should indicate whether the document is stored on a magnetic drive or on a removable, probably optical, drive. If you're using a removable optical drive, also known as an "autochanger" or a "jukebox," you'll need to store the directory information. Jukeboxes are treated as a single device, and each platter looks to the programmer like a subdirectory. Note that by storing the device in a file separate from the user interface you can easily update storage-location changes. If you write an archiving application, for example, you will only need to update one byte in the mapper file.
Multipage Documents
It would be nice if our imaging system could handle documents that have more than one page. Treating multipage documents is a little more complex. We still store the location information for each document page in the mapper file. A second file contains a doubly linked list. Each linked-list entry also points at a single mapper-file entry. This allows us to scan forward and backward through the document's pages. A separate LinkedList class handles file I/O to a linked-list file. The header is in Listing One (page 104), and the methods of this class and the Mapper class are in Listing Two (page 104). The layout of the linked-list file is shown in Example 2. Notice that the linked-list structure is larger than that of the mapper. You'll have to estimate the ratio of multipage to single-page documents. If every document is multipage you may consider using a singly linked list, which will eliminate one-third of the space required for the linked-list entries. The drawback, of course, is that the application will have to write its own routine for scanning the pages of a document in reverse.
Listing Three (page 105) contains the code for a program that exercises the Mapper and LinkedList classes. It writes out 1000 single-page document entries and 1000 four-page document entries, then reads them back.
The Mapper and LinkedList objects are contained in and contain other objects. I've omitted a class that provides extensive error messages. If there are run-time errors in this example, the objects will return a NULL if a character value was expected and a --1 if an integer value was expected; a 0 returned usually signals success.
The locking calls are compiler specific (Zortech), but I left them in to indicate likely places you should lock out other users. Scanners take several seconds, during which time you won't want your initialized index space updated by another scanner user. Turn off locking by defining NOLOCK=0.
You use the Mapper class to create the name of the image file. The Lock- Spot method does this and also locks the new record space in the mapper file. This might be necessary if more than one scanner is in operation. The filename returned does not include the extension.
You retrieve the location of the image file with the Read method which will construct a fully qualified filename. Essentially, this method returns the location instructions. You could expand these instructions beyond a simple file specification.
You should call Write after LockSpot. First your application will get the filename via LockSpot. Then you will scan the document using that filename. Finally, you'll write this information in the already locked and initialized MAPPER.DAT file.
At some time during the creation and storage of the image, you should get the long value that is the offset into the mapper file. This is done with the lMAPSSLOT number. If you're combining single- and multiple-page images, you'll indicate that the offset is to the Mapper by keeping it a positive value; offsets to the LinkedList are converted to a negative number.
Your application must know before creating the index whether the document is to have a single or multiple pages. Multipage documents can be stored and then retrieved in the same order. If the scanner operator picks multiple pages, your application will create an instance of the LinkedList class and call the LockSpot method. After getting a LinkedList slot, LockSpot gets the next available mapper slot and saves the value in the MapperAddress member of the LinkedListBuffer. The mapper value in hex is the filename you will use when scanning. This function returns a pointer to the Mapper value.
For the second and all subsequent pages, after you have called LockSpot and stored the next page of the image file, use Linkin to link the previous page with a call to this member.
You'll want several members to make it easy to traverse the linked list. LastImage is one that retrieves the fully qualified filename of the last image in a multipage document. To save space, I've not listed the others here.
The application will store the offset in a database somewhere. If the offset is a negative value, pass it to the Read member of the LinkedList class, which returns a pointer to a fully qualified filename. Read assumes you know that the value is in the LinkedList. Whether you pass a positive or negative number, LinkedList will save it as a positive value.
Open and Close could be put into the constructor and destructor. Having separate members will allow you to limit the number of open files. Close allows you to free the two file handles while maintaining the internal variable values. Open will automatically create a new file if one doesn't already exist. Open is called by almost every member function just to check if the file handle is valid. You can avoid this extra function call by checking for the existence of a valid file pointer.
What We'd Do Differently Next Time
The current design never cleans up space released by deleted images. We felt that going to optical storage would obviate the need to have a delete function. However, there were more scanning errors than we anticipated. The linked list and mapper should incorporate a single linked-list of deleted records. I first saw this in the B-tree code in Al Stevens's C Database Development (MIS Press, 1987). Both files would have a header that would indicate the first available slot. That slot would have a pointer to the next deleted slot, and so on.
Summary
A custom-tailored mapper file can open up new avenues for storage. For instance, if you have access to a mainframe, you could store location information for 9-track tape or high-density pack storage. You can use any location information that you can encode in your customized mapper struct. You can store images on a LAN, WAN, tape, optical disk, mainframe, or jukebox, and this system will locate and retrieve each image.
Example 1: The member struct that describes the layout of a mapper record.
struct Mapper
{
char Device ;
char Path [2] ;
char FileExtension [3] ;
};
Example 2: Layout of the linked-list file.
struct LinkedList
{
unsigned long Prev ;
unsigned long MapperOffset ;
unsigned long Next ;
} ;
How Much Can We Store?
The purpose of the mapper structure is to hold location information. Each mapper entry points to a single file. You want to make your structure flexible enough to describe many different types of storage, because when you get into image processing, disk sizes suddenly seem quite small. Imaging people buy storage big and often. If you plan to store your million or so images on magnetic disk, you may be in for a surprise. DOS uses a file-allocation table (FAT) to locate disk clusters. Each file will occupy at least one cluster. The FAT entry on DOS fixed disks larger than 17 megabytes is 16 bits long. So even the largest drives available, 2 gigabytes, will limit you to about 64K files (assuming that each file is <=32K). You will require 16 2-gigabyte drives to store a million images.
Even if the FAT entry were increased, a 2-gigabyte disk would not have the data space to store many more images. This is one of the reasons that removable storage becomes important in imaging systems.
On the other hand, removable optical storage, even jukeboxes, can be very slow when more than one user at a time requests data. So you must find a balance between fixed and removable storage. In an ordinary system, volatility is the most important part of the equation. Our image storage and retrieval applications do not ordinarily update images, so read demand becomes the more important ingredient.
--A.S.
Copyright © 1993, Dr. Dobb's Journal
[LISTING ONE]
// Mapper.hpp
#define NOLOCK 1
// these constants would be in a default file
// or WIN.INI (for a Windows app):
char cMap[] = "C:\\MAPTEST" ; // Mapper.Dat location
char cLinkL[] = "C:\\MAPTEST" ; // Linkedl.Dat location
#ifndef MAPPER
#define MAPPER
#include <stdio.h>
#include <sys\locking.h>
#include <share.h>
#include <io.h>
#include <fcntl.h>
#include <string.h>
class Mapper
{
private :
int fp ; // file pointer
long lBytePosition ;
char cBytePosition [9] ; // hex representation of long value
char * cMapperFileSpec ; // Mapper.dat full file name
struct MapperBuffer // layout of the Index entry
{
char cDevice [1] ; // device where image is
char cPath [2] ; // directory or Jukebox platter
char cFileExtension [3] ; // type of image
} Map ;
void WipeMapper(){strnset((char *)&Map,'\0',sizeof(Map));}
char cMwholefilename[19];
public :
Mapper() ;
~Mapper() ;
int Close() ;
char * Hexbytes(){return cBytePosition ;}
long lMapSlot() { return lBytePosition ; }
char * LockSpot() ;
int Open() ;
char * Read(long lOffset) ;
int Write() ; // commit to disk
int Write(char * Extension, // Image type
char * Path, // subdirectory or jukebox platter
char * Device) ;
} ;
#endif // MAPPER
#ifndef LINKEDLIST
#define LINKEDLIST
class LinkedList
{
private :
int fp ; // file pointer
long lBytePosition ;
char * cLinkedListFileSpec ;
struct LinkedListBuffer
{
long Previous ;
long Next ;
long MapperAddress ; // points at Mapper Index entry
} ll ;
Mapper * M;
public :
LinkedList() ;
~LinkedList() ;
int Close() ;
int Linkin(long OldEntry) ;
long lLinkSlot() { return lBytePosition ; }
char * LastImage(long lOffset) ;
char * LockSpot() ;
long MapAddress() {return ll.MapperAddress ;}
long Next(){return ll.Next ;}
int Open() ;
char * Read(long) ;
int Write(char * Extension, // Image type
char * Path, // subdir or jukebox platter
char * Device) ;
} ;
#endif // LINKEDLIST
[LISTING TWO]
#include "Mapper.hpp"
// M A P P E R M E T H O D S
//-----------------constructor-----------------------------
Mapper::Mapper()
{
fp = lBytePosition = 0 ;
Open() ;
}
//------------------------oblivion-------------------------
Mapper::~Mapper()
{
if (fp)
{
delete cMapperFileSpec ;
close(fp) ;
}
fp = 0 ;
}
//-------------------open and close members-----------------
Mapper::Open()
{
if (!fp)
{ // get file location defaults:
cMapperFileSpec = new char [strlen(cMap) + 13] ;
sprintf(cMapperFileSpec, "%s\\MAPPER.DAT", cMap) ;
// append if exists, otherwise create :
if (access(cMapperFileSpec, F_OK == -1))
{
FILE * fd = fopen(cMapperFileSpec, "w+") ;
fclose(fd) ;
}
if ((fp = sopen (cMapperFileSpec,
O_RDWR,
SH_DENYNO)) == -1)
return -1 ;
}
return 0 ;
}
//------------------Close-----------------------------------
Mapper::Close()
{
if (fp)
{
close(fp) ;
fp = 0 ;
}
return 0 ;
}
//-------------------LockSpot-------------------------------
char * Mapper::LockSpot()
{
if (!fp) Open() ;
lBytePosition = lseek(fp, 0L, SEEK_END) ;
WipeMapper() ;
if (write(fp, &Map, sizeof(Map) ) == -1)
return NULL ;
lseek(fp, lBytePosition, SEEK_SET) ;
#ifndef NOLOCK
// don't let anyone else append
if (locking(fp, LK_LOCK, (long)sizeof(Map)) == -1)
return NULL ;
#endif
sprintf(cBytePosition,"%8.8lx", lBytePosition) ;
return cBytePosition ;
}
//---------------------------Read---------------------------
char * Mapper::Read(long lOffset)
{
if (!fp) Open() ;
if (lseek(fp, lOffset, SEEK_SET) == -1)
return NULL ;
if (read(fp, &Map, 6 ) == -1) // device,dir, & extension
return NULL ;
sprintf(cBytePosition, "%8.8lx", lOffset); // filename
sprintf(cMwholefilename, "%1.1s:\\%1.2s\\%8.8s.%3.3s",
Map.cDevice, // Image device
Map.cPath, // Image path (or Jukebox disk)
cBytePosition, // filename/offset in hex
Map.cFileExtension ) ; // type (TIF,WP4,WP5...)
return cMwholefilename;
}
//--------------------------Write--------------------------
Mapper::Write(char * Extension,// Image type
char * Path, // Image subdir or juke platter
char * Device)// Image device (single letter)
{
if (!fp) Open() ;
memcpy((char *)&Map.cDevice, Device, 1) ;
memcpy((char *)&Map.cPath, Path, sizeof(Map.cPath)) ;
memcpy((char *)&Map.cFileExtension, Extension,
sizeof(Map.cFileExtension)) ;
return Write() ;
}
//----------------------------------------------------------
Mapper::Write()
{
lseek(fp, lBytePosition, SEEK_SET) ;
if (write(fp, &Map, sizeof(Map) ) == -1)
return -1 ; // should return error code here
#ifndef NOLOCK
if (locking(fp, LK_UNLCK, (long)sizeof(Map)) == -1)
return - 1 ; // should return error code here
#endif
return 0 ;
}
// L I N K E D L I S T M E T H O D S
//-------------------------constructor----------------------
LinkedList::LinkedList()
{
fp = 0 ;
Open() ;
M = new Mapper();
}
//------------------------oblivion--------------------------
LinkedList::~LinkedList()
{
if (fp)
close(fp) ;
delete M ;
}
//-------------------open and close members-----------------
LinkedList::Open()
{
int ok ;
if (!fp)
{
cLinkedListFileSpec = new char [strlen(cLinkL) + 13] ;
sprintf(cLinkedListFileSpec,"%s\\LINKEDL.DAT", cLinkL) ;
// append if exists, otherwise create :
if (access(cLinkedListFileSpec, F_OK == -1))
{
FILE * fd = fopen(cLinkedListFileSpec, "w+") ;
fclose(fd) ;
if ((fp = sopen (cLinkedListFileSpec,
O_RDWR,
SH_DENYNO)) == -1)
return -1 ;
lBytePosition = lseek(fp, 0L, SEEK_END) ;
// Write a -1 header because a '0' file name * -1 = 0
ll.Previous = ll.Next = 0 ;
ll.MapperAddress = -1 ;
lBytePosition = 0 ;
lseek(fp, lBytePosition, SEEK_SET) ;
if (write(fp, &ll, sizeof(ll) ) == -1)
return -1 ;
return 0 ;
}
else // file already exists
if ((fp = sopen (cLinkedListFileSpec,
O_RDWR,
SH_DENYNO)) == -1)
return -1 ;
}
return 0 ;
}
LinkedList::Close()
{
if (fp)
{
delete cLinkedListFileSpec ;
close(fp) ;
fp = 0 ;
}
return 0 ;
}
//---------------------LastImage----------------------------
char * LinkedList::LastImage(long lOffset)
{
Read(lOffset) ;
while (ll.Next)
Read(ll.Next);
return (M->Read(ll.MapperAddress)) ;
}
//--------------------------Read---------------------------
char * LinkedList::Read(long lOffset)
{
char lbuf[9];
char buffer[7];
if (lOffset < 0)
lOffset *= -1 ;
lBytePosition = lOffset ;
if (!fp) Open() ;
if (lseek(fp, lOffset, SEEK_SET) == -1)
return NULL ;
if (read(fp, &ll, sizeof(ll) ) == -1)
return NULL ;
return (M->Read(ll.MapperAddress));
}
//---------------------LockSpot-----------------------------
char * LinkedList::LockSpot()
{
if (!fp) Open() ;
lBytePosition = lseek(fp, 0L, SEEK_END) ;
ll.Next = ll.Previous = 0 ;
if (write(fp, &ll, sizeof(ll) ) == -1)
return NULL ;
lseek(fp, lBytePosition, SEEK_SET) ;
#ifndef NOLOCK
if (locking(fp, LK_LOCK, (long)sizeof(ll)) == -1)
return NULL ;
#endif
M->LockSpot() ;
ll.MapperAddress = M->lMapSlot() ;
return M->Hexbytes() ;
}
//---------------------------Write--------------------------
LinkedList::Write(char * Extension, // Image type
char * Path, // subdir or platter
char * Device)
{
if (!fp) Open() ;
lseek(fp, lBytePosition, SEEK_SET) ;
if (write(fp, &ll, sizeof(ll) ) == -1)
return -1 ;
#ifndef NOLOCK
if (locking(fp, LK_UNLCK, sizeof(ll)) == -1)
return -1 ;
#endif
M->Write(Extension, Path, Device) ;
return 0 ;
}
//---------------------------Write--------------------------
LinkedList::Linkin(long LLPr)
{
if (!fp) Open() ;
lseek(fp, LLPr, SEEK_SET) ;
if (read(fp, (char *)&ll, sizeof(ll) ) == -1)
return -1 ;
lseek(fp, LLPr, SEEK_SET) ;
ll.Next = lBytePosition ;
if (write(fp, (char *)&ll, sizeof(ll) ) == -1)
return -1 ;
lseek(fp, lBytePosition, SEEK_SET) ;
if (read(fp, (char *)&ll, sizeof(ll) ) == -1)
return -1 ;
lseek(fp, lBytePosition, SEEK_SET) ;
ll.Previous = LLPr ;
if (write(fp, &ll, sizeof(ll) ) == -1)
return -1 ;
#ifndef NOLOCK
if (locking(fp, LK_UNLCK, sizeof(ll)) == -1)
return -1 ;
#endif
return 0 ;
}
</PRE>
<P>
<h4><a name="022e_000e"><a name="022e_000f"><B>[LISTING THREE]</B></H4>
<P>
<PRE>
/* this program creates a Mapper.dat and LinkedL.dat and
writes 1,000 single image entries and 1,000 entries of 4 page
documents, then reads them back. The entries are stored in
a sequential file as 4 byte character strings. */
char cKey[] = "C:\\MAPTEST\\KEYS.X" ;
char cDev[] = "X"; // where 'images' are stored
const long TestCount = 1000 ;
const int MultiPage = 4 ; // # Images in multipage docs.
union value // converts 4 byte chars to long and visa-versa
{
long lValue ;
char cValue[sizeof(long)] ;
} uValue ;
Mapper * Map ;
LinkedList * LL ;
char * AvailableMapper ;
#include "stdlib.h"
int main(int argc, char * argv[])
{
char cmd [32] ;
FILE * fd ;
int fp ;
long i ;
long lLong ;
char szDir[3] ;
sprintf(cmd, "DEL %s\\MAPPER.DAT", cMap) ;
system(cmd) ;
sprintf(cmd, "DEL %s\\LINKEDL.DAT", cLinkL) ;
system(cmd) ;
fd = fopen(cKey, "w") ;
fclose(fd) ;
fp = open(cKey, O_WRONLY) ;
Map = new Mapper ;
itoa(1, szDir, 10) ; // make up directory names
for (i = 0; i < TestCount; i++)
{
Map->LockSpot() ;
Map->Write("TIF", szDir, cDev) ;
uValue.lValue = Map->lMapSlot() ;
lseek(fp, 0, SEEK_END) ;
write(fp, (char *)&uValue.cValue, sizeof(long)) ;
if ((i / 100) * 100 == i)
{
itoa(i, szDir, 10) ; // change directory name
printf("\t%ld", i) ;
}
}
delete Map ;
close(fp) ;
// Build some Multi-page:
fp = open(cKey, O_RDWR) ;
printf("\nMulti-page Documents\n") ;
LL = new LinkedList ;
itoa(1, szDir, 10) ; // make up directory names
for (i = 0; i < TestCount; i++)
{
LL->LockSpot() ;
LL->Write("TIF", szDir, cDev) ;
uValue.lValue = LL->lLinkSlot() ;
uValue.lValue *= -1 ; // say we are a linked list entry
lseek(fp, 0, SEEK_END) ;
write(fp, (char *)&uValue.cValue, sizeof(long)) ;
lLong = LL->lLinkSlot() ;
for (int j = 1; j < MultiPage; j++)
{ // next pages:
LL->LockSpot() ;
LL->Write("TIF", szDir, cDev) ;
LL->Linkin(lLong) ;
lLong = LL->lLinkSlot() ;
}
if ((i / 100) * 100 == i)
{
itoa(i, szDir, 10) ; // change directory name
printf("\t%ld", i) ;
}
}
close(fp) ;
delete LL ;
// we can read them all back now:
Map = new Mapper ;
LL = new LinkedList ;
fp = open(cKey, O_RDONLY) ; // open the keys
lseek(fp, 0, SEEK_SET) ;
printf("\n'Long'\tFilename\n") ;
while (read(fp, (char *)&uValue.cValue, sizeof(long)))
{
if (uValue.lValue >= 0)
printf("\n%ld\t%s",
uValue.lValue, Map->Read(uValue.lValue)) ;
else
{
printf("\n%ld\t%s",
uValue.lValue, LL->Read(uValue.lValue)) ;
while (LL->Next())
printf("\n%ld\t%s",
uValue.lValue, LL->Read(LL->Next())) ;
}
}
close(fp) ;
delete Map ;
delete LL ;
return 0 ;
}
End Listings
