Name type value storage

1. Technical Field

The invention relates to the storage of information for use in Internet and World Wide Web (“Web”) based applications. More particularly, the invention relates to storing data in name-type-value triplets.

2. Description of the Prior Art

First generation World Wide Web (“Web”) applications are referenced by CGI (common gateway interface), in which a form is submitted from a Web page, where the data elements in the form are represented by a name of an element and a corresponding user entered value, i.e. as a name-value pair. This value could be a value from a list or a hand typed value. FIG. 1 is a schematic representation of a Web page 10 which provides a form into which data may be entered by a user. Various fields 11 - 13 are provided to receives such data, e.g. city, state, and zip code. The entered data correspond to name-value pairs 11 a - 13 a in a name-value list. It can be seen that the data may be hand entered, as for city or zip code, or that the user may select the data from a list, as for state. It is always necessary to use lists of values of this type when writing Web applications. Over time it was gradually realized that the use of lists of values provides a very powerful way to represent data because one of the typical ways in which data are passed from one computer application to another is through a predefined set of values. For example, if it was desired to create a new customer account, it would be necessary to know that it is required to pass such information as, e.g. a name, address, city, and state, in a defined list of values with known types (see FIG. 1 ).

One of the limitations of this approach is presented when one wants to change the application program interface (“API”) for the underlying application program or system platform. Such activity is a very cumbersome process because it is necessary to find every place in a document or application that the API was called, where the value for the source API is no longer valid for the target API. That is , it is necessary to provide an additional value because the target API expects a different value than that of the source API.

It would be advantageous to provide a technique that allowed a list of values to contain any type of information desired. It would be further advantageous if such list of values could be readily used across various system platforms without regard to an underlying API.

The invention provides a feature referred to as Name Type Value storage (“NTV”). This feature provides a very flexible technique for storing data for use, for example in the Internet and in World Wide Web based applications. NTV storage is an extension of the familiar and powerful concept of storing data in name-value pairs, but with several significant enhancements. For example, one advantage of NTV is that values are stored in their native types, so that they can be manipulated without costly and inconvenient parsing and validation.

The preferred embodiment of NTV provides a list of values or names, referred to as triplets. In each triplet, NTV provides both an identifier and a name of a type, where a type can be one of several things, e.g. a type can be an integer, a floating point number, a string, an array of values, or another NTV object. NTV allows one to nest the various types. A third part of the triplet is the actual value itself, which is stored in its native type.

FIG. 1 is a schematic diagram of a Web page showing a list of name-value pairs;

FIG. 2 is a schematic diagram showing a list of name-type value triplets according to the invention;

FIG. 3 is a schematic diagram showing multiple platforms that are interconnected over a network according to the invention;

FIG. 4 is a schematic diagram showing an NTV data structure embedded in the value field of another NTV data structure according to the invention;

FIG. 5 is a schematic diagram showing iterator construction according to the invention; and

FIG. 6 is a flow diagram showing, in part, iterator construction, as well as NTV data structure list processing according to the invention.

The invention provides a feature referred to as Name Type Value storage (“NTV”). This feature provides a very flexible technique for storing data for use, for example in the Internet and in World Wide Web based applications. NTV storage is an extension of the familiar and powerful concept of storing data in name-value pairs, but with several significant enhancements. For example, one advantage of NTV is that values are stored in their native types, so that they can be manipulated without costly and inconvenient parsing and validation.

NTV provides a list of values or names, referred to as triplets. FIG. 2 is a schematic diagram of an NTV triplet 20 , showing a name field 21 , a type filed 22 , and a value field 23 . In each triplet, NTV provides both an identifier and a name of a type, where a type can be one of several things, e.g. a type can be an integer, a floating point number, a string, an array of values, or an another NTV object. NTV allows one to nest the various types. A third part of the triplet is the actual value itself, which is stored in its native type. In FIG. 2, the name field 21 describes the triplet as containing an address 24 , the type of data within the triplet, described by the type field 22 , is a string 25 , and the value 26 is contained in the value field.

For purposes of the discussion herein, native type refers to the internal storage format of the resident platform. An integer such as the number five can either be stored the way the computer actually represents five or in a platform independent fashion, for example, as the ASCII value five. In many Web applications, ASCII characters are sent from a Web browser to the server because of cross platform issues, e.g. going from a MAC, to a UNIX machine, to a VMS machine. In this case, the Web browser represents the characters as ASCII because ASCII provides essentially the same effect as if the various systems were the same platform.

However, representing such characters internally as ASCII results in a performance penalty because it becomes necessary to convert from the string representation of the character to the internal representation of the character if such operations as computations and comparisons are to be performed. One of the improvements provided by NTV is the ability to store characters in the value portion of the triplet, for example, internally as the characters' internal value so that the best performance is available. As discussed above, the triplet includes name, type, and value information.

There are certain advantages that are provided by representing the data in this way. One such advantage is that it is possible to represent the data on any platform because the “type” of data is identified to the target platform by the triplet. This allows the use of multiple platforms and any programming language, e.g. a Java representation, a C++ representation, or a Java Script representation. It is therefore possible to send a group of data, e.g. an object referred to as “customer” which represents an individual and all information related to that individual, as a list of triplets (i.e. an NTV data structure) and to manipulate that data in a C++ program which is on a server. Using NTV, it is thereafter possible to change that data, e.g. send the data to a Java application where one can, for example change the values, write the data into a report, or place the data into a JavaScript application where one can perform some manipulation on the data. The data are the same representation in all ways on all three platforms and, if it is desired to add a fourth platform or language, such as a Perl or Pascal, the data are common among each platform, such that the development process is sped up.

Another feature of NTV is that it is a self describing format. Thus, one NTV data structure can serialize itself into a string (e.g. in ASCII format), which allows one to save it to a file or send it across a wire, where it may be reconstituted at the other end. The data has one format when it is at a first location, but it can be turned into a string which then can be transmitted, and it can reassemble itself at the other end in the proper format, i.e. exactly the same format and the same structure. Therefore, if one decides to add a new value into a data structure that is being sent back and forth between various platforms, it is not necessary to change the data structure itself. That is, one does not have to add a field to a header file or recompile all of the code. Rather, one can add the new value and the new value passes through to the destination platform.

For example, FIG. 3 provides a schematic diagram showing multiple platforms 30 , 31 that are interconnected over a network 32 . An NTV data structure 33 stored in memory 50 includes one or more triplets, one of which has a value containing data “abc” 34 in a native format for a source platform 30 . A module 38 is provided at the source platform(platform 1 ) 30 that serializes the triplet and sends the triplet over the network. 32 , in a serialized format 35 . A module 39 is provided at a second platform (platform 2 ) 31 . That receives the serialized data and converts the data back to an NTV data structure 36 that includes the same triplet, but where the type of data indicated by the triplet was used to convert the serialized form of the data to a value “xyz” in a native format for the recipient platform 31 . The native triplet is then stored in memory 51 at the second platform.

Base data types supported by the presently preferred embodiment of NTV are shown in Table 1 below. It should be appreciated that the invention is readily applicable to other base data types through the exercise of ordinary skill in the art.

Some other advantages of NTV include:

NTV lists can be embedded within each other, allowing data structures of unlimited complexity to be constructed (see FIG. 4, which shows an NTV data structure 41 embedded in the value field of another NTV data structure 40 ).

Arrays of any supported type may be stored as values in NTV lists, including arrays of NTV lists.

NTV lists and the array value types support several iterator interfaces.

NTV lists can be serialized and deserialized simply, allowing any data structure to be stored in a file and reconstituted later, or for data structures to be transmitted between application components without specialized code.

NTV lists have a uniform structure, such that reflecting data structures into JavaScript, or exchanging data structures between C++ and Java does not require header files, class loaders, or object classes.

Using NTV

Most operations that are performed on NTV lists involve the setting and getting of values. The application program interface (API) functions used to do this are specialized to the type of data being handled, so that data may be passed in and out of an NTV list as the appropriate native type.

Set Functions. The ACNTVList methods used to set a value into an NTV list are typically as follows:

ACNTVList::set<TypeSpecifier>(String<name>, NativeType<value>[, ACNTVError<error object>]);

The parameters to these functions are the name with which the inserted value should be associated, the value to insert (as the correct native type), and an optional error object that is populated with a return condition code, if appropriate.

Dot Notation. NTV permits a name that is located several levels into the NTV list hierarchy to be specified by using dot notation. For example, if an NTV list contains another NTV list having the name “a” which, in turn, contains an integer having the name “b,” then the value of “b” could be changed to zero by calling setInt(“a.b”, 0) on the parent NTV list. If the NTV lists that are required to store a value with a dot notated name do not exist, they are created automatically. In other words, if a call is made to setInt(“a.b”, 0) on an empty NTV list, the NTV list having the name “a” is first inserted into the parent NTV list, and the integer having the name “b” is then inserted. This is a powerful feature, but it does incur a performance penalty, e.g. if a nested NTV list is accessed repeatedly, it is preferred to get a pointer directly to the embedded list.

Restrictions on Names. Note that providing the dot notation feature makes it impossible to embed a dot in a name in an NTV list. If it is desired to use dot notation to access an NTV data structure from JavaScript, it is necessary that all inserted names are valid JavaScript identifiers. Memory Management. All values except Void types are copied into the NTVList. This feature of NTV has several implications:

First, it is necessary to provide a function that frees the memory occupied by the value passed in because the NTV list does not perform this function. On the other hand, it is not necessary that the NTV list modify any variable used to set a value.

Second, if an NTV list is inserted into another NTV list, then the entire inserted list is copied. This can be an expensive operation, so it is often better, if possible, to build the nested list in place. This involves inserting a new (empty) list, calling getNTVList to retrieve a pointer to the list in place, and using that pointer to create the list's contents. Note that the same procedure applies for array types.

If a value of any type exists in the NTV list before the function is called, it is replaced with the new name-type-value triplet. In general, any memory associated with the replaced value is freed. The exception to this rule is Void types in C++. Note that while the Void objects in a Void array are not freed, the memory occupied by the array itself is freed.

DateTimes and Booleans. Unlike other types, DateTimes can be inserted into NTVs using a number of different APIs. A first set of APIs allow values to be inserted using a native DateTime representation. Another set of APIs allow DateTimes to be inserted using a string and a corresponding format that describes the value. This format is constructed using various characters as described in Table 3.

Regardless of how DateTimes are set, they are stored internally in native format. If the values are inserted as strings, the resulting native value is created using the local time zone of the machine on which the application is running. This conversion takes into account all time zone offset information-including. Daylight Savings Time.

Boolean operators also provide an interface that is somewhat different than most types. In addition to the normal ability to insert values using a native type, Boolean operators may also be inserted using case insensitive versions of the strings “true” and “false.” Regardless of how Boolean operators are inserted, they are stored internally (and therefore extracted) in native format.

Classes for NTV data structures are discussed below. C++ Prototypes. Table 2 below lists set function prototypes.

Get Functions

NTVList methods used to get a value from an NTV list are typically as follows:

<NativeType>ACNTVList::get<Typespecifier>(String<name>, NativeType<default>[, ACNTVError<error object>]);

The parameters to these functions are the name associated with the desired value, an optional default value (in the correct native type), and an optional error object that is populated with a return condition code, if appropriate.

There is a special function in this group referred to as the getAsString( ) function, which has the same signature as getStr( ), but which converts the value to a string before returning it. This method works for all types other than arrays. For integers, doubles, and strings, the format of the resulting string value should be evident. Formats for other types are described in Table 3 below.

Default Values. The default value is returned unchanged if no value of the correct type is found in the list with the name supplied. If no default value is provided, these functions return an empty string, zero, or null, as appropriate to the type returned. Note that the get functions for array types do not support default values.

Special Considerations. The same dot notation feature and memory management considerations that apply to set methods also apply to get methods. In addition, it is important to note that where these methods return pointers, they point to the actual objects in the NTV list. This memory should not be freed by the caller.

C++ Prototypes. Table 4 below lists get function prototypes.

Arrays

For each base type (Int, Double, String, Void, Any, and NTV list), there is a corresponding array type. These array types are not actually native arrays, but instead are objects which handle memory management and which, in the preferred embodiment of the invention, support a subset of the Java Vector API.

Array Object Methods. The interface for NTV array objects is based on the Java API class java.util.Vector. These methods provide everything required to manipulate an array, while concealing the underlying implementation. Note that some of the methods listed below require the ability to test for value equality, and are not available for arrays of Void or NTV lists. These methods are marked in Table 5 with an *.

The methods executed on Int, Double, and String arrays expect and return values/references, while the methods executed on Void, Any, and NTV list arrays are concerned with pointers, as with the get/set methods on ACNTVList. Also, as with ACNTVList, values are always copied on the way in, but never on the way out.

Detailed information on how these methods work follows the documentation for java.util.Vector or netscape.util.Vector. Note, however that for both of these classes, the lastIndexOf method is documented incorrectly: the search begins not at index, but at index −1. Also, the lastIndexOf method is implemented using value equality, rather than object identity, the way netscape.util.Vector does it, rather than the way that java.util.Vector does.

C++ Prototypes. Table 5 below lists array object methods.

Iterators

There are currently two iterators provided by NTV, both of which support the same interface:

ACNTVListiterator is a fast iterator that does not provide a guarantee about order.

ACNTVListInsertionIterator is a slightly slower iterator that produces elements in the order in which they were inserted in the list.

Constructors

A listing that includes a variable index, a constructor index, variables, and constructors for the presently preferred embodiment of the invention is attached hereto as Appendix “A, ”. A listing that includes a variable index, a constructor index, variables, and constructors for the presently preferred embodiment of the invention is presented infra schematic diagram showing iterator construction according to the invention, while FIG. 6 is a flow diagram showing, in part, iterator construction, as well as NTV data structure list processing according to the invention. The iterator classes each have a single constructor 52 that takes a pointer to an NTV list 54 as a parameter. As with most iterator classes, iterators, the position of the iterator 53 is undefined immediately following its construction.

The constructors are as shown in Table 6 below.

Stepping Through the List. After constructing an iterator ( 100 ), the system steps through the list ( 110 ) by calling the RWCString* next( ) method. This method returns the name of the item in the list ( 120 ). When next( ) returns null, the end of the list has been reached. The name of the current item may also be retrieved by calling the getName( ) method.

Determining the Type of an Element ( 130 ). To operate on the data in the list, the system calls the int getType( ) method and compares the result to the constants shown in Table 7 below, which are available as a result of including acntvlist.h.

Getting the Element Data

After determining the type, one can retrieve the data ( 140 ) using get methods that function in manner similar to the corresponding methods on ACNTVList, except that they do not take any parameters because the name is already known and errors and misses should never happen.

C++ Prototypes. Table 8 below lists iterator get methods.

The iterators also support one other get method, i.e. ACNTVTriplet* getTriplet( ). This method returns the triplet used internally to store the data. One should avoid using this method if at all possible because it creates a dependency on the internal representation of NTV and is rarely necessary. Preferably, one can make full use of NTV without manipulating triplets directly.

Other Methods. The iterator classes also support a reset( ) method which restores the state that the iterator had immediately after construction.

Special Considerations. Note that the behavior of the iterator classes is undefined if the underlying list is modified after the iterator is constructed. of the inserted object are copied. This can be a computationally expensive operation. Accordingly, it is better to insert the object first, then fill the NTV list with data. In this case, the empty object insert is copied. To add data to the empty object insert, the appropriate get function is called to get a pointer to the new copy in the list. If data are added to the original object inserted, the data do not affect the contents of the parent list.

Support for “Any” Objects

There is a base class or interface that allows new classes to be created that are not in any way based on NTV lists, but that implement a core set of functions required to allow instances to be used as data values in NTV lists. In the current implementation, ACNTVAny should be implemented as an interface in Java.

Other Embodiments

The following provides a list of features that may be employed in other embodiments of the invention:

Type Methods on Iterator Classes. NTV provides type-specific methods such as isStr( ), isNTVList( ), and general type methods such as isArro or isNumber( ) which make the iterators easier to use.

getAsLocalizedString Methods. This method allows values to be retrieved as strings, as with getAsString, taking into account, e.g. locale-specific number and date formatting. This method is available from both NTV lists and iterators.

Internal Reference Counting. This feature avoids unnecessary internal copying that affects performance.

Case Insensitive Searching. This feature allows one to look a name up without paying attention to case.

Support Multi-Byte Strings. RWCString can be replaced with a new class that supports multi-byte.

Use Hash tables. NTV lists currently use binary trees.

Overload Functions to take char*. This feature alleviates the need for so many casts to avoid compiler warnings, and prevents unnecessary calling of RWCString constructors.

Constructor and Method Prototypes

Listed herein are the Constructor and Method Prototypes utilized in the preferred embodiment of the present invention. Table 9 defines variable types. Table 10 enumerates constructors. Table 11 presents a list of methods. Table 12 lists additional variable types. Table 13 lists the constructors methods and Table 14 presents the method prototypes.

Although the invention is described herein with reference to the preferred embodiment, one skilled in the art will readily appreciate that other applications may be substituted for those set forth herein without departing from the spirit and scope of the present invention. Accordingly, the invention should only be limited by the Claims included below.