A Tyranny of File Paths

In a break to discussing bitflags, I thought I'd mention a wee issue that I find to be an occasional annoyance: File paths, and how to go about constructing them while making sure all the fiddly path delimiters are dealt with correctly.

Say I have a directory tree that is rooted somewhere, say C:\Foo. I have nested folders within that, say C:\Foo\Bar and C:\Foo\Bar\Too

Occasionally I need to call a method and pass it a path such as C:\Foo\Bar\Too, but I don't actually have that path on hand. All I know is that I get the path by adding 'C:\Foo', 'Bar', and 'Too' together in a meaningful way that results in a path the OS will understand.

So, I could write code like this:

CallMethod(IncludeTrailingPathDelimiter('C:\Foo') +
IncludeTrailingPathDelimiter('Bar') + 'Too');

I may even need to include an additional trailing path delimiter depending on the call semantics, which further complicates matters, like this:

CallMethod(IncludeTrailingPathDelimiter('C:\Foo') + IncludeTrailingPathDelimiter('Bar') + IncludeTrailingPathDelimiter('Too'));

or even like this:

CallMethod(IncludeTrailingPathDelimiter(IncludeTrailingPathDelimiter('C:\Foo') +
IncludeTrailingPathDelimiter('Bar') + 'Too'));

See. Icky isn't it?

What I really want is a tool to take a bunch of bits of a file path and assemble it all for me and give it back all ready to go. So, here's a little utility function that does just that (excuse the formatting - I'm still figuring out how to put nice code formatting in a blog without using screen grabs!):

Function ConstructFilePath
(const Paths : Array of TFileName;
const WantTrailingDelimiter : Boolean) : TFileName;
var I : Integer;
begin
Result := Paths[Low(Paths)];

for I := Succ(Low(Paths)) to High(Paths) do
Result := IncludeTrailingPathDelimiter(Result) + Paths[I];

if WantTrailingDelimiter then
Result := IncludeTrailingPathDelimiter(Result)
else
Result := ExcludeTrailingPathDelimiter(Result);
end;

So, to construct my FooBarToo path with a trailing delimiter and pass it to the method, I can now do this:

CallMethod(ConstructFilePath(['C:\Foo', 'Bar', 'Too'], True));

Which just seems so much nicer and easier to understand. :-)

Raymond.

Bitflags Part 3: Getting two dimensional

In my previous posts regarding bitflags I have discussed implementing bit flags in small groups and also larger collections in a way that efficiently stores the flags while providing intuitive interfaces and access to them.

Sometimes we need to think of flags in more complex fashions to provide efficient implementation strategies for problems at hand. In a previous post I suggested scanlines in Group 3 Fascimile images are actually just fixed length arrays of bitflags and may be implemented as such. Extending this metaphor suggests any black and white image is just a collection of fixed length arrays of bitflags. An array of arrays of bitflags is certainly a simple way of viewing this metaphor and could be represented by this interface (I've omitted the constructor and other interface elements for clarity):

type
TBWImage = class(TObject)

private
FLines : Array of TBitFlags;

Function GetBitFlag(X, Y : Integer) : Boolean;
Procedure SetBitFlag(X, Y : Integer);

public
property BitFlags[X, Y : Integer] : Boolean 
read GetBitFlag write SetBitFlag; Default;
end;

As a simple implementation, FLines is a dynamic array allowing us to flexibly cater for varying sizes of two-dimensional sets of bit flags. The public property permits the caller to conceptually think of the image as an array of booleans, handily hiding the implementation details via the setter & getter methods, and the use of the default modifier that allows the caller to treat TBWImage instances as if they were a direct implemention of the 2D bitflag array without needing to even know the name of the BitFlags property itself.

However, implementation of a 2D bitflag array in this way isn't as efficient as it could be. Construction of this class requires the independent construction of the entire array of bitflags instances where each those allows storage of arbitrarily long series of bitflags. This implies repeated overhead in each TBitFlags instance which is not strictly required when considering a 2D array of bitflags.

So, we still want to provide the same conceptual interface, but need to improve the implementation to improve algorithmic and storage efficiency.

One was of solving this is by allocating a single block of memory that stores N by M bits, meaning ~(N x M) DIV 8 bytes of storage in total and modifying the accessors to access the single block of memory, rather than individual set of bitflags representing each line. This reduces memory overhead and potential fragmentation, and makes construction and destruction of the class simpler too. However, in the context of this example (that of a black and white image) these issues are unlikely cause a problem in typical use cases.

So now we have a class that implements two dimensional sets of bitflags. It may be used for a variety of purposes and is efficient in both CPU and memory requirements.

But it has a weakness! It's rectangular. More to the point, it requires one bit of memory to be allocated for each location within the rectangular N x M coordinate system required. This is not an issue for most problem spaces, but what if the problem space is very large in terms of the N x M coordinate system? What if you need to create and manage many instances of such large 2D arrays of bitflags? Now we need to radically rethink how we implement the storage and access mechanisms for this data.

Which is the topic of the next article in this series :-)

Regards,
Raymond.

Bitflags Part 2: Larger sets/lists/arrays of flags

In my previous post Using Properties to Access Bitflags, I outlined how to implement a useful interface to a collection of flags on an object that preserves the intention of allowing access to the flags as if they were boolean quantities while implementing them efficiently as bit-flags (and hiding that implementation from the caller).

The example I worked through used a small set of flags within a class (or record) that could reasonable be stored within a byte (or word/integer etc depending on the number of bit-flags required for the implementation). But what to do when the number of flags required exceeds any reasonably handy base type supplied by the language (say, thousands of them)?

In these cases the flags are not usually identified individually by name, but usually have relevance based on their position in the set of flags or by an index value. A trivial example would be a scan line of a group 3 fax image where the pixels are identified by a collection of bits where zero (false) means white and one (true) means black. In this case the flags have an on/off semantic interpretation, rather than true/false.

In the requirement for larger sets of bitflags we need to allocate memory to hold the bits and provide accessors to make it appear as if we have an array of booleans. In this case I'll use the Delphi Array Of construct to make this a little simpler, though the old standbys GetMem() & FreeMem() work just as well.

The native integer type is usually the most efficient for the CPU to deal with, so we will break down the array of bits into chunks that big. So, for 32 bit systems we might write the following to kick things off:

type
  TBitArrayAtom = LongWord; // 32 bit unsigned integer

const
  kBitsPerBitArrayAtom = 8 * Sizeof(TBitArrayAtom);
  kBitArrayMSB = 1 SHL (kBitsPerBitArrayAtom - 1);

Given these basic premises about the structuring of the internal data storing the bitflags, we can develop an interface that presents these as an array of boolean values:

TBitArrayFoundEvent = Function(const Index : Integer) : Boolean of Object;

TBitArray = Record
// FBaseIndex specifies the number of the zero-th entry in the bit array.
  FBaseIndex : Integer;

private
  // FNumBits stored the number of bits we have stored in the bit array
  // We store this to remove the need to call Length(FBits) for range checking
  FNumBits : Integer;

  // FBits contains the actual bits. The MSB of FBits[0] is bit(0) in the array
  FBits : Array of TBitArrayAtom;

  // SetNumBits reallocates the array to increase or decrease the number of
  // stored bits to Value. When shrinking, bits are discarded from the end of
  // the array. When expanding bits are added to the end of the array and
  // initialised to 0 (false)

  procedure SetNumBits(const Value: Integer);

  function GetBit(Index: Integer): Boolean;
  procedure SetBit(Index: Integer; const Value: Boolean);

public
  property BaseIndex : Integer read FBaseIndex write FBaseIndex;
  property NumBits : Integer read FNumBits write SetNumBits;

  // Set all the bits in the bit array to 0
  Procedure Clear;

  // Scan the bit array between (inclusively) two indexes looking
  // for set bits in the array. Each set bit results in a call to
  // the provided OnFound event. If the event return false then
  // the scan is terminated.
  Procedure Scan(const Start, Finish : Integer;
                 OnFound : TBitArrayFoundEvent);

  // Items is the main accessor for the items in the bit array. The Origin
  // property allows the indexing in Items to be the 'external' numbering.
  property Items[Index : Integer] : Boolean read GetBit write SetBit; default;

  Constructor Create(ABaseIndex : Integer;
                     ANumEntries : Integer);
end;

Of particular note is the FBaseIndex item. This allows us to specify an arbitrary origin value to the list of bits. In effect, we are saying that the zero-th bit in the list corresponds the value of FBaseIndex. This is handy if, for instance, the bit flags array is representing items in a enumerated list or array of some kind. Also note the Scan() method. This is in effect an enumerator which calls the supplied callback function for every '1' element in the bit array and would trivially modifiable to use an anonymous method instead.

The part of the declaration that actually implements the bit flags accessor is this:

property Items[Index : Integer] : Boolean read GetBit write SetBit; default;

In the first bit flags article we had individual named properties that used the index modifier to use a single pair of settor/accessor methods that manipulated the internal representation. Here we replace the notion of named items with indexed items. The implementation is not quite as trivial as in the first article as it needs to cope with the base origin, and the internal storage granularity, but you can see a repetition of the pattern:

function TBitArray.GetBit(Index: Integer): Boolean; 
begin 
  Dec(Index, FBaseIndex); 

  if (Index >= 0) and (Index <> 
Result := FBits[Index DIV kBitsPerBitArrayAtom] AND (kBitArrayMSB SHR (Index MOD kBitsPerBitArrayAtom)) <> 0 
else 
Result := False;
end;

Similarly SetBit() is analogous to the settor in the first article:

procedure TBitArray.SetBit(Index: Integer;
                           const Value: Boolean);
begin
  Dec(Index, FBaseIndex);

  if (Index >= 0) and (Index < FNumBits) then
    begin
      if Value then // Set the bit
        FBits[Index DIV kBitsPerBitArrayAtom] :=
          FBits[Index DIV kBitsPerBitArrayAtom] OR (kBitArrayMSB SHR (Index Mod kBitsPerBitArrayAtom))
      else // clear the bit
        FBits[Index DIV kBitsPerBitArrayAtom] :=
          FBits[Index DIV kBitsPerBitArrayAtom] AND NOT(kBitArrayMSB SHR (Index Mod kBitsPerBitArrayAtom));
    end;
end;

The last remaining significant aspect of this BitArray is the scanner which makes enumerating over items in the BitArray a snip:

procedure TBitArray.Scan(const Start, Finish: Integer;
                         OnFound: TBitArrayFoundEvent);
var
  StartIdx, FinishIdx : Integer;
  I, J : Integer;
  Value : Cardinal;
begin
  if not Assigned(OnFound) then
    Exit;

  StartIdx := (Start - FBaseIndex) DIV kBitsPerBitArrayAtom;
  FinishIdx := (Finish - FBaseIndex) DIV kBitsPerBitArrayAtom;

  for I := StartIdx to FinishIdx do
    begin
      Value := FBits[I];
      if Value <> 0 then
        begin
          for J := 0 to kBitsPerBitArrayAtom - 1 do
            if (Value AND (kBitArrayMSB SHR J)) <> 0 then
              if not OnFound((I * kBitsPerBitArrayAtom + J) + FBaseIndex) then
                Exit;
        end;
    end;
end;

Now we can efficiently store and access sets of bitflags of arbitrary size with a useful bitflag scanner to boot. While the example above is using a record, this is trivially simple to convert to a class instead if required. Similarly, the Scan() method is easily modified to use an anonymous method instead of a callback.

Raymond.

Bitflags Part 1: Using properties to access bitflags

You may have a need to record a series of yes/no, true/false type properties in a class or record. Each one of these may be thought of as a flag, or collectively as a set.

An approach often taken to implement sets of flags is as follows (Note: while I have used a class here, a record may be used with essentially the same approach):

type
TMyClass = class(TObject)
Flag1, Flag2, Flag2 : Boolean;
end;

or, if you're feeling like being more rigorous:

type
TMyClass = class(TObject)

private
FFlag1, FFlag2, FFlag2 : Boolean;

public
property Flag1 : Boolean read FFlag1 write FFlag1;
property Flag2 : Boolean read FFlag1 write FFlag2;
property Flag3 : Boolean read FFlag1 write FFlag3;
end;

Older hands look at this and say: You're using a byte for each flag, why not collapse the flags into a single flags byte and test the appropriate bit. After some jiggling, the code looks like this:

const
kFlag1 = $1;
kFlag2 = $2;
kFlag3 = $4;

type
TMyClass = class(TObject)
private
FFlags : Byte;
public
property Flags : Byte read FFlags write Flags;
end;

Yes, that simplified the declaration of the class all right, but it just complicated the code that uses instances of this class.

Before it was possible to write:

var
MyInstance : TMyClass;
...
if MyInstance.Flag1 then
...

Now you need to write it like this:

var
MyInstance : TMyClass;
...
if (MyInstance.Flags and kFlag1) <> 0 then
...

Which is nowhere near as clear, and plasters implementation details of TMyClass throughout the code that uses it.

We could encapsulate the bit flag testing in the class by extending it like this:

type
TMyClass = class(TObject)

private
FFlags : Byte;

procedure SetFlag1(Value : Boolean);
function GetFlag1 : Boolean;

procedure SetFlag2(Value : Boolean);
function GetFlag2 : Boolean;

procedure SetFlag3(Value : Boolean);
function GetFlag3 : Boolean;

public
property Flag1 : Boolean read GetFlag1 write SetFlag1;
property Flag2 : Boolean read GetFlag2 write SetFlag2;
property Flag3 : Boolean read GetFlag3 write SetFlag3;
end;

procedure TMyClass.SetFlag1(Value : Boolean);
begin
if Value then
FFlags := FFlags OR kFlag1
else
FFlags := FFlags AND NOT kFlag1;
end;

function TMyClass.GetFlag1 : Boolean;
begin
Result := (FFlags and kFlag1) <> 0;
end;

Note: I have omitted the Flag1 and Flag2 setter & getter methods for brevity.

Now the implementation detail of the flag is again encapsulated in the class and hidden from the caller which may treat the flag as if it were a boolean property. However, this is a bit clumsy as I have to write new setter and getter methods for each flag that differs only in the use of a particular kFlag(x) constant I have previously defined. Wouldn't it be nice to be able to declare a new flag as an additional boolean property, but not have to define additional constancts or setter/getter methods?

Well, you can! Enter the index modifier for property delcarations. This has been around for many Delphi versions.

Now I can write the class above in a way that generically deals with the flags:

type
TMyClass = class(TObject)
private
FFlags : Byte;

procedure SetFlag(Value : Boolean);
function GetFlag : Boolean;
public
property Flag1 : Boolean Index 0 read GetFlag write SetFlag;
property Flag2 : Boolean Index 1 read GetFlag write SetFlag;
property Flag3 : Boolean Index 2 read GetFlag write SetFlag;
end;

procedure TMyClass.SetFlag(Value : Boolean;
Index : integer);
begin
if Value then
FFlags := FFlags OR (1 SHL Index)
else
FFlags := FFlags AND NOT (1 SHL Index);
end;

function TMyClass.GetFlag(Index : integer) : Boolean;
begin
Result := (FFlags and (1 SHL index)) <> 0;
end;

See the difference? The use of the index keyword in the property delcaration provides an additional parameter to the setter and getter methods. Now, a single pair of setter/getter methods can support all the flags in class. To add a fourth flag all I need to do is to add an additional property declaring it with a different index number and I'm done!

No constants need to be defined, the implementation is completely hidden from the caller, and the caller may treat the flags as if they were individual boolean values.

So, why would I do this? It introduces overhead into the querying of the value of a flag and might seem to complicate a class (or record) unnecessarily. In many cases you would not worry about it, especially if the instances of the classes or records in question were singletons, or not numerous. However, in some cases there may be very many instances present, and in these cases the memory savings may become significant, especially if there are many flags present in each instance.

How many is very many? There are algorithms in the products I work on that may manipulate many millions of such instances. In these cases every byte counts to maximise in-memory instance working sets and to optimise persistent store I/O and in-memory manipulations of sets of instances.

Using this approach smooths the code on the calling side, while maintaining optimal memory & storage use for the flags on the implementation side. In reality, the only overhead is that of a method call as the bit flag testing must be done at some point.

Another option to implement a series of flags is as a set (even if the individual items don't relate to one another as they would normally when declaring a set). This is really a misuse of the way sets are implemented in Delphi, and is at the mercy of set implementation rules in terms of the quantity of memory used to store the set. Similarly, in order to hide the fact the flags are implemented as a set (to avoid forcing the client to use set operators to access individual flags), there would still be a need to implement properties in the way I have described here.

Larger collections of bitflags is the topic of another blog.

Note: This is but one use of the very useful index modifier in property declarations.

Regards,
Raymond.

StackOverflow ahoy!

Joel Spolsky (of Joel on Software fame) and Jeff Atwood (of Coding Horror fame) have come up with a new way to think about Q&A sites, and decided to build one. Called StackOverflow, it has just been released as a public beta.

Think of it as a hybrid of blogs, forums and wikis, with a voting system that promotes the best answers to questions to the top of the heap and a tagging system to thread related questions and answers together.

I can see questions related to Delphi are already being asked, and answered, on the site! I'll definitely be using it ;-)

Delphi 2009 is here!

Well, it's definitely on it's way now with SA codes being sent out.

Unfortunately I wont be able to use it in anger for a little while until we complete some current project work.

I must admit to some trepidation in moving to Delphi 2009 from Delphi 2007 due the Unicode changes. We have a large source tree approaching two million lines of code, large pieces of which deal with file format conversion which would be sensitive to ANSI vs Unicode issues...