Tiered arrays

Patent metadata

Field	Value
Publication number	US-9632760-B2
Application number	US-201615143970-A
Country	US
Kind code	B2
Filing date	May 2, 2016
Priority date	Sep 30, 2015
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for using tiered arrays to represent aggregated software dependencies. One of the methods includes receiving a request to generate a range of contiguous indexes having non-default values represented by a tiered array, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values. After descending one or more tiers to identify a first index that (i) is greater than or equal to the start index and (ii) has a non-default value, a system ascends one or more tiers in the tiered array and subsequently descends again to identify a second index that is a last index in a contiguous sequence of indexes having non-default values from the first index up to and including the second index.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving a request to compute, for an overall range of indexes comprising set indexes having non-default values and unset indexes having default values, all contiguous ranges of unset indexes within the overall range of indexes,
wherein the overall range of indexes is represented by a tiered array having a plurality of tiers, wherein each tier of the tiered array comprises one or more catalogs,
wherein each catalog in each tier, except for a bottom-most tier, comprises (i) non-default elements that each identify a respective catalog at a lower tier and (ii) default elements that do not identify any catalogs, and
wherein each bottom-most catalog in the bottom-most tier comprises one or more non-default elements having non-default values, each non-default value being stored at a respective index value in the bottom-most catalog;
setting a reference index to be initially equal to a minimum index, the minimum index corresponding to an index that is first in an ordering of the overall range of indexes;
performing a search, from the reference index, for a first range [a0, b0] of contiguously set indexes having non-default values, wherein a0 is a first index in the first range of contiguously set indexes and b0 is a last index in the first range of contiguously set indexes, wherein the index a0 is a first index in the tiered array having a non-default value;
if a0 is greater than the minimum index, generating a range of indexes [0, a0−1] having default values, wherein a0−1 is a last index in the range of indexes having default values;
repeatedly performing the following operations until an end of the tiered array is reached:
setting the reference index to be equal to b0+2;
performing a search, from the reference index, for a next range [a1, b1] of contiguously set indexes starting at or after the index b0+2,
after obtaining the next range of contiguously set indexes, outputting generating a range of indexes [b0+1, a1−1] having default values, and
updating b0 to be equal to b1; and

providing, in response to the request, the generated pairs of index values representing the contiguous ranges of unset indexes within the overall range of indexes.

2. The method of claim 1 , wherein obtaining the first range [a0, b0] of contiguously set indexes comprises:
obtaining an index a0 that is a first index in the tiered array having a non-default value, wherein the index a0 is greater than or equal to the minimum index of the tiered array; and
obtaining an index b0 that is a last index having a non-default value in a first contiguous range of indexes having non-default values from a0 to b0 in the overall range of indexes.

3. The method of claim 2 , wherein obtaining the index a0 comprises descending one or more tiers in the tiered array from a non-default element in a top-level catalog to identify a first index that (i) is greater than or equal to the minimum index and (ii) has a non-default value.

4. The method of claim 2 , wherein obtaining the index b0 comprises ascending one or more tiers in the tiered array and subsequently descending one or more tiers in the tiered array to identify a second index that is a last index in a contiguous range of indexes having non-default values.

5. The method of claim 4 , wherein an index c having a default value occurs immediately after the index b0.

6. The method of claim 1 , further comprising:
determining that an end of the tiered array has been reached;
determining that b1 is less than a maximum index, max_index, of the tiered array; and
in response, generating a range of indexes [b1+1, max_index] having default values.

7. The method of claim 1 , wherein the tiered array represents a plurality of dependencies inbound to or outbound from a node in a raw dependency graph of software elements in a project, wherein each node in the raw dependency graph represents a software element in the project, and wherein each link in the raw dependency graph represents a software dependency of a first software element on a second software element.

8. A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
receiving a request to compute, for an overall range of indexes comprising set indexes having non-default values and unset indexes having default values, all contiguous ranges of unset indexes within the overall range of indexes,
wherein the overall range of indexes is represented by a tiered array having a plurality of tiers, wherein each tier of the tiered array comprises one or more catalogs,
wherein each catalog in each tier, except for a bottom-most tier, comprises (i) non-default elements that each identify a respective catalog at a lower tier and (ii) default elements that do not identify any catalogs, and
wherein each bottom-most catalog in the bottom-most tier comprises one or more non-default elements having non-default values, each non-default value being stored at a respective index value in the bottom-most catalog;
setting a reference index to be initially equal to a minimum index, the minimum index corresponding to an index that is first in an ordering of the overall range of indexes;
performing a search, from the reference index, for a first range [a0, b0] of contiguously set indexes having non-default values, wherein a0 is a first index in the first range of contiguously set indexes and b0 is a last index in the first range of contiguously set indexes, wherein the index a0 is a first index in the tiered array having a non-default value;
if a0 is greater than the minimum index, generating a range of indexes [0, a0−1] having default values, wherein a0−1 is a last index in the range of indexes having default values;
repeatedly performing the following operations until an end of the tiered array is reached:
setting the reference index to be equal to b0+2;
performing a search, from the reference index, for a next range [a1, b1] of contiguously set indexes starting at or after the index b0+2,
after obtaining the next range of contiguously set indexes, generating a range of indexes [b0+1, a1−1] having default values, and
updating b0 to be equal to b1; and

providing, in response to the request, the generated pairs of index values representing the contiguous ranges of unset indexes within the overall range of indexes.

9. The system of claim 8 , wherein obtaining the first range [a0, b0] of contiguously set indexes comprises:
obtaining an index a0 that is a first index in the tiered array having a non-default value, wherein the index a0 is greater than or equal to the minimum index of the tiered array; and
obtaining an index b0 that is a last index having a non-default value in a first contiguous range of indexes having non-default values from a0 to b0 in the overall range of indexes.

10. The system of claim 9 , wherein obtaining the index a0 comprises descending one or more tiers in the tiered array from a non-default element in a top-level catalog to identify a first index that (i) is greater than or equal to the minimum index and (ii) has a non-default value.

11. The system of claim 9 , wherein obtaining the index b0 comprises ascending one or more tiers in the tiered array and subsequently descending one or more tiers in the tiered array to identify a second index that is a last index in a contiguous range of indexes having non-default values.

12. The system of claim 11 , wherein an index c having a default value occurs immediately after the index b0.

13. The system

Assignees

• Semmle Ltd

Inventors

• Hale Joshua George

Classifications

• G06T11/26

  Drawing of charts or graphs · CPC title

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F17/30324

  Physics · mapped topic

• H04L67/133

  Protocols for remote procedure calls [RPC] · CPC title

• G06F11/3604

  Analysis of software for verifying properties of programs (testing of software G06F11/3668) · CPC title