View Library

Author:

Ian Searle, ians@users.sourceforge.net

Introduction

The goal of the view library is to provide a memory allocation efficient set of operations for dealing with string operations such as appending, inserting, copying, etcetera. The efficiencies are achieved by allowing the programmer to construct "views" from string segments. Regardless of how many times a segment is referenced or used, it is never copied.

Some key features:

• Multiple views can reference the same string segment(s).

• Views can mask portions of their view of the segments without affecting a segment's data.

• Each view treats its segments as immutable atomic elements. They cannot be modified in any way shape or form as they could possibly belong to another view.

• Each view is indexed from 0 to length - 1.

• A view can contain data with embedded NULL characters. No C-language string functions are used in the view operations.

• The memory allocation routines are abstracted. You can leave them set to their default malloc() and free(), or you can call view_Init() and specify alternate memory allocation routines. This could be useful is you are using this library in kernel-space or have a pool allocator you wish to use.

Building

The view library has been written with portability in mind. But, it has been developed and tested on a single platform (Mac OS-X). To build the library look at the Makefile in the root directory. There are a few macros at the top that will probably need to be customized. If you are a developer, then customizing the Makefiles should be a fairly trivial task.

Within the root directory is a test directory. I recommend that you get the test programs to build and execute in order to verify proper functionality on your platform.

In a perfect world, you would unpack the tar-ball, and do:

  make
  make test > test.out
  diff -c ./test.out ./test.out.golden

If there are minimal differences (addresses are bound to be different) then the library is probably good to go. Simply copy the library and view.h to a convenient location and start using them.

Implementation

• Views are implemented as an ordered set of sub-segments. Each sub-segment is represented by a 3-tuple that contains: [ segment-addr, begin-pos, end-pos ]

• View coordinates begin at zero and end at (length - 1). Any arguments to a view function that are coordinates are always specified in view coordinates.

• When you specify begin and/or end view index values, the range you are identifying is inclusive of begin and end.

• So, a view is just an ordered collection of 3-tuples.

  Example: Given the following set of string segments:

  
                seg-a:  fu    
                seg-b:  bar   
                seg-c:  snatch

                A view might look like:

                s n a f u b a r 
                _ _ _ _ _ _ _ _
                c c c a a b b b   segment-id
                0 1 2 0 1 0 1 2   segment-index

                Which is achieved with a set of 3-tuples that look like:

                [ addr-seg-c, 0, 1 ]
                [ addr-seg-a, 0, 1 ]
                [ addr-seg-b, 0, 2 ]
  

• When creating a view, you can either create a view that is "owns" its own data (strings) or one that is borrowing its data. The determination is made when the view is created. The are two types of creation methods view_CreateOwned() and view_CreateBorrowed().

  The important distinction is that a view that owns its data can be used irrespective of the program scope, or the life-cycle of the data that was used to create it. However, a view that borrows its data must be carefully used. If the data it points to is destroyed before the view is destroyed, behavior is undefined (most likely very bad).

Copyright

Copyright 2003, 2004 Ian Searle. All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2: Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL IAN SEARLE OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

---