S. Grants Co., Ltd.

Fujitsu Corporation

Kousokuya, Inc.

Other

Makoto Yoshioka

Yoshioka, Makoto

Mitsuhiro Kokubun

Toshio Shinjo

Gengo Tazaki

Hiroyuki Yamamoto

Nobuhisa Shigemi

John W Mackin

Hiroaki Negishi

Koutaro Shinjo, Legal Representative

A storage area allocation method for allocating a storage area with a requested allocation size area may include receiving an allocation request for a storage area that includes the requested allocation size, acquiring an available storage area whose size is a smallest size of a product of all of the product of power-of-2 sizes and the region allocation unit size encompassing the requested allocation size from the region; obtaining a binary expression whose value is the requested allocation size divided by the allocation unit size; and allocating a contiguous storage area comprised of storage areas each of whose size is a product of the allocation unit size and a power of 2 of a value of a bit position wherein a 1 is set in the binary expression and which contiguous storage area is conjoined by the storage areas in a sequence of magnitude of sizes of the storage areas.

Storage region management method, storage region allocation method and program

To provide a technology that, regardless of the capacity of a storage device, enables its areas to be flexibly partitioned and managed, and, when a file is allocated to a region also, can also use its areas effectively by means of an efficient method. When a region size of a storage device is expressed as the sum of mutually differing power-of-2 values, and areas whose size is one of the power-of-2 sizes configuring that sum are taken to be master partitions, to partition the areas into partitions each of whose size is the size made by successively dividing each master partition in half and to generate an allocation table holding allocation information expressing the allocation status of each of the files that have partitions with each of the sizes included in the master partitions. To manage a region based on the allocation information stored in the allocation table.

Region management apparatus, region management method, and program

A storage area management method for a data storage apparatus partitions an acquired storage area into storage areas with differing power-of-2 sizes and manages each of them. Also, a storage area allocation method receives an allocation request for a storage area that includes a requested allocation size, and acquires an available storage area whose size is the smallest power-of-2 size encompassing the requested allocation size, and obtains a binary expression of the requested allocation size, and in response to the received allocation request, allocates a contiguous storage area comprised of storage areas each of whose size is a power of 2 of a value of a bit position wherein a 1 is set in the binary expression.

A code ID range table holding code ID ranges for each code of a same code type and a next code ID table holding next code IDs are created. Code ID ranges of code types of codes configuring a search code string are read out from the code ID range table for the search target code string, and the stored next code ID corresponding to a code ID included in the code ID range of the code type of the head code in the search code string is read out from the next code ID table while the stored next code IDs corresponding to the next codes are successively read out from the next code ID table, and the next code ID read out from the next code ID table is verified whether it is included in the code ID range read out from the code ID range table.

Code string search apparatus, search method, and program

The sort processing of keys to be sorted, which keys are expressed as bit strings involves a classification processing. In the classification processing, a bit string comparison between a reference key and a key which is an object of the classification is performed, and a difference bit position is obtained that is the bit position of the first bit that differs in the bit string comparison and the keys to be sorted are classified by the difference bit position into key groups with the same difference bit position.

Bit string data sorting apparatus, sorting method, and program

A coupled node tree has a root node and a node pair, the node pair being a branch node, which includes position information of a link target node pair, and a leaf node, which includes a search target index key, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas. The nodes of the coupled node tree are backed up in a depth precedence search sequence. The coupled node tree is restored by repeating the following process: reading out the nodes in the sequence they are backed up, storing in a stack the position information of the node to be restored, successively restoring child nodes as long as branch nodes are encountered, restoring a leaf node which is read out and then, tracing back up the stack, a decision being made as to which node is next to be restored.

Coupled node tree backup/restore apparatus, backup/restore method, and program

To realize a high speed merge sort method by applying a coupled node tree, which method extracts a smallest or largest key from a plurality of sorted key storage areas in each of which is stored keys including bit strings that are sorted, and generates a coupled node tree for merge while adding a processing source identifier that identifies the sorted storage area wherefrom the key has been extracted, and repeats the actions of writing out into the merged key storage area a key being obtained by a minimum or maximum value search on the coupled node tree and deleting the key, and inserting into the coupled node tree a key by extracting the key from one of the plurality of sorted key storage areas.

Bit string merge sort device, method, and program

A coupled node tree comprises a root node and a node pair, the node pair being a branch node and leaf node, or a pair of branch nodes, or a pair of leaf nodes arranged in adjacent storage areas. The branch node includes a discrimination bit position of the search key and the first position information of a primary node, one node of a node pair of a link target. The leaf node includes the second position information of the storage area holding an index key that is the target of a search. According to a bit value of the search key of a discrimination bit position in the branch node, repeated linking to a primary node of a node pair of the link target or a node at a position in a memory area adjacent thereto until a leaf node is reached.

Bit string search apparatus, search method, and program

To provide a method that lessens the reduction in efficiency of processing using a coupled node tree even if the scale of the coupled node tree grows large. Is stored a termination node, whose discrimination bit position has a value smaller than 0, in a search path stack that holds the search history while successively storing therein branch nodes that have been traversed in the search path. The coupled node indicator of the stored branch node is converted to a value wherein a 1 is added if the link target is node

The minimum value or the maximum value of the index keys of a coupled node tree of a processing source is determined, and the index keys are successively deleted until the index key that is to be the splitting point is reached, the deleted index keys being inserted into the coupled node tree of the processing target, thereby splitting the coupled node tree. Deletion processing is done of one coupled node tree, taking as the processing source in the above-noted splitting method, and insertion processing is done of the other, taken as the processing target, thereby conjoining the coupled node trees.

Coupled node tree splitting/conjoining method and program

A coupled node tree comprises a root node and a node pair, the node pair being a branch node and leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas. The branch node includes a discrimination bit position of the search key and a position information of a primary node, which is one node of a node pair of a link target. The leaf node includes an index key that is a bit string that is the target of a search. A coupled node tree is searched using a longest-match/shortest-match search key and the longest-match/shortest-match node is determined through a comparison of the difference bit position between the index key resulting from the search and the longest-match/shortest-match search key and the discrimination bit position of a branch node on the search path memorized when the search is performed.

Longest-match/shortest-match search apparatus, search method, and program

An index key is a key string formed of three or more keys whose tail-end key is unique, and a search key string for a bit string search has a unique key as its tail-end key. A branch node includes a search key sequence number expressing the position information of a key in the search key string to be used in the bit string comparison during the bit string search and the discrimination bit position for that key. Search for index keys is performed by extracting from the search key string the key with the search key sequence number in the branch node and repeatedly linking to one of the nodes of a node pair of the link target in response to the bit value at the discrimination bit position of that key until the leaf node corresponding to that index key is reached.

To provide a method that minimizes efficiency reductions in processing coupled node trees even if the size of the coupled node tree grows large. In basic searching or maximum or minimum value searching, the search history, not only the address information of the storage area wherein a node is stored but also the discrimination bit position of branch nodes traversed in the search path, is stored in the search path stack.

Bit string searching apparatus, searching method, and program

Using a tree configuration wherein node groups of four or more nodes composed of combinations of branch nodes, leaf nodes or empty nodes are linked into a tree form, a bit string search by a search key string is enabled by repeatedly linking to one of the nodes of a node group to which a primary node belongs in response to the bit values of keys of the search key string at the discrimination bit position included in the branch node.

Bit strings search apparatus, search method, and program

Provided is a search method which is appropriate for handling a don't-care bit. A coupled node tree comprises a root node and a node pair, the node pair being a branch node and leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas. The branch node includes a discrimination bit position of a search key for the bit string search, which key is encoded so as to distinguish between don't-care bits and significant bits, and position information indicating a position of a primary node, which is one node of a node pair of a link target. A leaf node includes an index key which is a bit string in the status of either being or not being encoded. A search that takes in account the don't-care bit is performed by repeatedly linking in sequence to one of the nodes of a node pair that is the link target in accordance with the bit value of the search key at the discrimination bit position of a branch node until a leaf node is reached, and by tracing back up the path to the leaf node as necessary.

Growing community of inventors

Chiba, Japan

Mitsuhiro Kokubun