# US 2010/0169322 A1 · Efficient access of bitmap array with huge usage variance along linear fashion, using pointers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169322 A1
- Document ID: US20100169322A1
- Status: Published application
- Kind: A1
- Application number: 12/344,356
- Filed: 2008-12-26
- Published: 2010-07-01
- Earliest claimed: 2008-12-26
- Assignees: Sun Microsystems, Inc.
- Inventors: Parthasarathy Selvaraj
- Web page: https://patentgrep.com/patent/US20100169322A1

## CPC

- G06F 12/023: {Free address space management}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method for locating an unallocated bit in a bitmap array includes traversing the bitmap array using a plurality of pointers to locate a unit. The unit includes a plurality of entities and at least one of the plurality of entities is unallocated. The method further includes traversing the at least one of the plurality of unallocated entities in the unit to obtain an unallocated entity. The unit is associated with at least one pointer, and the at least one pointer is associated with a plurality of threshold values and a fill count, the fill count being less than a maximum fill count of the bitmap array.

## Claims

### Claim 1

A method for locating at least one unallocated bit in a bitmap array, comprising:
traversing the bitmap array using a plurality of pointers to locate a unit, wherein the unit comprises a plurality of entities and at least one of the plurality of entities is unallocated, and
traversing the at least one of the plurality of unallocated entities in the unit to obtain an unallocated entity,
wherein the unit is associated with at least one pointer, and the at least one pointer is associated with a plurality of threshold values and a fill count, the fill count being less than a maximum fill count of the bitmap array.

### Claim 2 (depends on 1)

The method of claim 1, wherein the threshold values are predetermined.

### Claim 3 (depends on 1)

The method of claim 1, wherein the threshold values are updated based on entity usage.

### Claim 4 (depends on 1)

The method of claim 1, wherein traversing the at least one of the plurality of unallocated entities in the unit to obtain an unallocated entity comprises,
recursively searching the unit.

### Claim 5 (depends on 1)

The method of claim 1, wherein bit lengths of the plurality of the pointers are less than the bitmap array length.

### Claim 6 (depends on 1)

The method of claim 1, wherein the fill count is a non-negative integer.

### Claim 7 (depends on 1)

The method of claim 1, wherein the fill count corresponds to a number of allocated entities in the bitmap array.

### Claim 8 (depends on 1)

The method of claim 1, wherein the allocated entity references usage of a location in memory.

### Claim 9 (depends on 1)

The method of claim 1, wherein at least one pointer from the plurality of pointers is one selected from the group consisting of: one byte, two bytes, four bytes, and eight bytes.

### Claim 10 (depends on 1)

The method of claim 1, wherein bit length of each entity from the plurality of entities is equal to at least one bit.

### Claim 11

A system for locating unallocated bits, comprising:
a bitmap array, wherein the bitmap array comprises a plurality of entities and at least one of the plurality of entities is unallocated;
the system configured to:
traverse the bitmap array to locate a unit having the at least one unallocated entity,
wherein the unit is associated with at least one pointer, and the at least one pointer is associated with a plurality of threshold values and a fill count, the fill count being less than a maximum fill count of the bitmap array.

### Claim 12 (depends on 11)

The system of claim 11, wherein the threshold values are predetermined.

### Claim 13 (depends on 11)

The system of claim 11, wherein the threshold values are updated based on entity usage.

### Claim 14 (depends on 11)

The system of claim 11, wherein traversing the at least one of the plurality of unallocated entities in the unit to obtain an unallocated entity comprises,
recursively searching the unit.

### Claim 15 (depends on 11)

The system of claim 11, wherein bit lengths of the plurality of the pointers are less than the bitmap array length.

### Claim 16 (depends on 11)

The system of claim 11, wherein the fill count is a non-negative integer.

### Claim 17 (depends on 11)

The system of claim 11, wherein the fill count corresponds to a number of allocated entities in the bitmap array.

### Claim 18 (depends on 11)

The method of claim 11, wherein the allocated entity references usage of a location in memory.

### Claim 19 (depends on 11)

The method of claim 11, wherein at least one pointer from the plurality of pointers is one selected from the group consisting of: one byte, two bytes, four bytes, and eight bytes.

### Claim 20 (depends on 11)

The method of claim 11, wherein bit length of each entity from the plurality of entities is equal to at least one bit.