The clustered-intset Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The clustered-intset Reference Manual

This is the clustered-intset Reference Manual, version 0.0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Aug 15 04:16:29 2022 GMT+0.

Table of Contents


1 Introduction

clustered-intset - a set-of-integers implementation favoring clustered keys

This is a hash-based set implementation supporting arbitrarily large non-negative integer keys, which is moderately well suited for large numbers of clustered key values.

The implementation uses Common Lisp's hash tables such that multiple set members share a hash key and hash value. This provides us the usual O(logN) capabilities of a hash table but reduces the required number of hash table entries by (for reasonably clustered data) by an order of magnitude. Furthermore, it uses only fixnums as hash table values (regardless of the size of integers in the set membership), thereby minimizing memory allocations. The net result is that if all your integer set members are fixnums, there are no extraneous allocations for references to boxed objects from your hash table (related to the intset data, at any rate). You can also have intset members which are larger than fixnums. In those cases only the hash table key is boxed, but not the value.

This release was tested in sbcl 2.1.6 and ABCL 1.8.0.

To load and run the sample tests

Assuming this has been provided by quicklisp and/or you've modified your quicklisp local-projects configuration to refer to the git repo cloned from https://github.com/dtenny/clustered-intset.

(ql:quickload :clustered-intset-test)
(clustered-intset-test:run-tests)

More on representation (skip if you don't care).

When an integer 'k' is added to the set, its hash table key is (/ k fixnum-bits), and its hashtable value is a fixnum used as a bitset for members in the range 0 - fixnum-bits relative to the base (floor k fixnum-bits).

Using SBCL as an example, it has 62 bit fixnums on the machine where this was developed. Every hash table entry could represent up to 62 integer values in a single hash table entry. An abusive example such as a dense value interval [0-1,000,000) would have 16,129 entries in the hash table, all keys and all values being fixnums.

This implementation isn't designed for additional dense set techniques such as compression. It's fairly simple, and benchmarks were satisfactory w.r.t. the primary use-case that motivated this implementation. If you need more support for sparse or dense bitsets, see the references at the end of this note, in particular CL-ROARING.

Set members exceeding MOST-POSITIVE-FIXNUM will also work, potentially resulting in non-fixnum keys, but the hash-table values will still be fixnums.

Motivating use-case

I wanted to do some processing which involved representing many integer primary keys from a database in memory. In my case, I might want to pull in a million primary keys at a time and process them in ascending order.

With respect to Common Lisp tools, a million integers isn't a problem IF THEY START AT ZERO. You could use a bit-vector for that. The problem is when your integer primary key values have a range starting in the millions or billions. Billion element bit-vectors would require 125 megabytes of memory unless you do something smarter, and unfortunately I couldn't find any Common Lisp bit vector tools that were smarter with the possible exception of FSET (see below). Plain hash tables can handle large integers just fine, though you'll find that this package can substantially reduce memory requirements for large cardinality sets.

And so here we are. It isn't elegant, but it seems to do what I wanted it to do.

Primary functionality of the initial release.

The focus is on integer set membership. The main things supported in the initial release are:

Hopefully the above actions are reasonably efficient.

The package doesn't presently support any bitmap-smashing types of operations. Certainly UNION (OR), INTERSECTION (AND), XOR and similar types of behaviours could be added, but since I didn't need them I haven't added them.

Feel free so submit a PR for this stuff, or you may be interested in the CL-ROARING package mentioned above and below, which supports a variety of logical bitmap operations.

Performance

I ran some very simple benchmarks (see integer-set-testing.lisp) of various approaches to integer sets for the element quantity and key ranges that I required in my use-case. The benchmark may or may not run for you, it isn't something I plan to keep up to date, was just proof of concept stuff for me.

See the lisp file for full details, here's some highlights:

;;; Using 1,000,000 intset entries, 20% holes, ranging from 1,000,000 to 2,250,239
;;; Duration in seconds, followed by bytes consed (Kilobytes/Megabytes/Gigabytes etc).
;;; Lower numbers are better.
;;;
;;;                                                    Ascending
;;; Implementation     Loading           Membership    Traversal
;;; =================  ===============   ===========   =============
;;; Simple Bit Vector   0.005s,  ~281K   0.003s,  0K   0.008s,    0K 
;;; Hash Table          0.032s,   ~24M   0.032s,  0K   0.299s,   ~8M
;;; Clustered Intset    0.046s,  ~490K   0.030s,  0K   0.022s, ~161K
;;; CL-Roaring (FFI)    0.014s,    N/A   0.024s, N/A   0.011s,   N/A
;;; FSET                1.592s,  ~1.5G   0.429s,  0K   0.006s,    0K  
;;; CL-intset          50.102s,  ~406G   0.016s,  0K   0.020s,    0K
;;;
;;; Using 1,000,000 intset entries, 20% holes, ranging from 1,000,000,000 to 1,001,248,861
;;;
;;;                                                    Ascending
;;; Implementation     Loading           Membership    Traversal
;;; =================  ===============   ===========   =============
;;; Simple Bit Vector   0.010s,  ~125M   0.004s,  0K   2.542s,    0K 
;;; Hash Table          0.032s,   ~24M   0.031s,  0K   0.297s,   ~8M
;;; Clustered Intset    0.048s,  ~490K   0.029s,  0K   0.022s, ~161K
;;; CL-Roaring (FFI)    0.013s,    N/A   0.023s, N/A   0.010s,   N/A
;;; FSET                1.535s,  ~1.5G   0.403s,  0K   0.005s,    0K  
;;; CL-intset              <cancelled after a couple of hours>

Key takeaways:

See also

I probably did not give FSET a fair shake. I wasn't really looking for immutable semantics, and by the time I finally tried to use it I'd already written this package (CLUSTERED-INTSET) and also the CL-ROARING package. In my quick and dirty benchmark attempt, I also couldn't get FSET to load members efficiently. Probably all bad on my part, if there's something I missed let me know. There's also a question of how much memory it retains once it's loaded.

CL-INTSET uses single integers as bit sets, but that doesn't scale well to large keys such as database primary keys, e.g. set member 4,000,000 would require a four million bit bignum or bit-vector to represent it. It may have other scalability problems too, in benchmarking I had to kill the test where I ran set membership having range starting at one billion. There are a couple of packages that use integers as bitmaps, I'm not sure what the attraction of these implementations is, they are very impractical for large numbers.

In Clojure I've had very good experiences with data.int-map and its int-set capabilities. However aside from being written in a combination of java and clojure, the packaging is solving about 5 problems at once, most of which are more useful for Clojure than Common Lisp. Still, worth a look if you're seeking inspiration while writing another int-set or related class.

Finally, someone on reddit also suggested using FFI to access the roaringbitmap compressing bitmap implementations. In a weird development path, I wrote some of this CLUSTERED-INTSET package, then decided I didn't have anything to compare it to for benchmarking, so I wrote the CL-ROARING package, then I returned to this one.

I have to say using FFI for CL-ROARING was really nice and easy. Give it a look, it provides much more functionality than this lisp-only CLUSTERED-INTSET implementation, but it requires that you have the CRoaring shared library in your path, and it's limited to 32-bit unsigned integers, depending on where/how it was built.

Meanwhile, this package, CLUSTERED-INTSET, is pure lisp, easy to use, works well for large volumes and large values, and both the memory and CPU behavior of the package scale well enough with number of values and range of integers, subject to the limits of CL's hash-table implementation. It certainly works for my limited use case.


2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 clustered-intset

Implements a non-negative keyed set of integers favoring clustered keys.

Author

Dave Tenny

License

MIT

Version

0.0.1

Dependency

alexandria (system).

Source

clustered-intset.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 clustered-intset/clustered-intset.asd

Source

clustered-intset.asd.

Parent Component

clustered-intset (system).

ASDF Systems

clustered-intset.

Packages

clustered-intset-asd.


3.1.2 clustered-intset/package.lisp

Source

clustered-intset.asd.

Parent Component

clustered-intset (system).

Packages

clustered-intset.


3.1.3 clustered-intset/clustered-intset.lisp

Dependency

package.lisp (file).

Source

clustered-intset.asd.

Parent Component

clustered-intset (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 clustered-intset

Hash based int-set that is slightly more efficient for clustered keys such as a set of integer primary key values from a database.
All keys must be non-negative integers.

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

Previous: , Up: Packages   [Contents][Index]

4.2 clustered-intset-asd

Source

clustered-intset.asd.

Use List
  • asdf/interface.
  • common-lisp.

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


5.1.1 Ordinary functions

Function: add (k intset)

Add non-negative integer ’k’ to the the intset previously created with ‘make-intset‘. Return true if ’k’ was added, nil if ’k’ was already present.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: advance (iterator)

Advance an iterator returned by ‘iterator‘. Return the next integer value in the iteration, or nil if there are no more values.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: containsp (k intset)

Return T if the non-negative integer ’k’ is a member of the specified intset, NIL otherwise.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: count (intset)

Return the count of integers held by the intset. Named for sequence-like compatibiltiy.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: delete (k intset)

Remove non-negative integer ’k’ from the intset previously created with ‘make-intset‘. Return true if ’k’ was removed, nil if ’k’ was already absent.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: first (intset)

Return the smallest valued integer in the intset, or NIL if there are no members. This is not an efficient implementation, it is O(n).

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: intset->list (intset &key direction)

Accumulate all members of the intset into a list and return it.

DIRECTION may be one of:

:UNORDERED (the default), which produces unordered results as efficiently as possible. :ASCENDING, which produces intset members in ascending order.
:DESCENDING, which produces intset members in descending order.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: intset->vector (intset vector &key direction)

Accumulate all members of the intset into a vector and return it.

VECTOR may be one of:
- nil, in which case a SIMPLE-VECTOR will be allocated, filled, and returned.
- a SIMPLE-VECTOR (i.e. ‘simple-vector-p‘ is true for the vector)
in which case elements are added from slots zero to N-1
where N is the number of elements in the intset. It is an error to specify an array of insufficient size in this case.
- a non-adjustable vector with a fill-pointer, in which case elements are added as by ‘vector-push‘. Note that vector-push does not yield errors if the array would overflow, it does nothing.
- a adjustable vector with a fill pointer, in which case elements are added as by ‘vector-push-extend‘.

Note that you can determine the size of the array to preallocate in full by allocating ‘(count intset)‘ elements.

DIRECTION may be one of:

:UNORDERED (the default), which produces unordered results as efficiently as possible. :ASCENDING, which produces intset members in ascending order.
:DESCENDING, which produces intset members in descending order.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: iterator (intset &key starting-with ending-with descending)

Creates and returns an unidirectional iterator for ordered traversal of the intset.
The iterator is called with ‘(advance <iterator>)‘ until it returns nil.

E.g. (loop with iterator = (iterator intset)
as value = (advance iterator)
while value
do ... something with value ...)

Values returned by ADVANCE will be ascending or descending according to the value of DESCENDING. By default, iteration proceeds with all intset values in ascending order.

If DESCENDING is true, iterataion proceeds in descending order. As explained below, DESCENDING affects comparison of STARTING-WITH and ENDING-WITH values.
A single iterator is always unidirectional

STARTING-WITH, if specified, is an inclusive value limiting the iteration to
start to the first value equal to or (> if DESCENDING, < if not DESCENDING) the value.

ENDING-WITH, is specified, is an exclusive value limiting the iteration
range end to the first value (> if DESCENDING, < if not DESCENDING) the value.

If both STARTING-WITH and ENDING-WITH are supplied and overlap in semantically incompatible ways an error will be signalled, e.g.

‘(iterator intset :starting-with 1 :ending-with 1)‘ => ERROR

The intset from which the iterator was created may be updated while iterating.
It is undefined whether newly added values will be produced by new calls to ADVANCE.
If a member k is deleted from the intset undergoing iteration after the iterator
is created, it will not appear in any ADVANCE calls after deletion.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: make-intset (&key size rehash-size)

Create an empty int-set.

If you’d like to create an intset with an input sequence see SEQ->INTSET.

:size - a non-negative integer hint as to how many keys (or key clusters) will
be in the underlying hashtable. Remember that if you have good clustering, you might have (/ N +FIXNUM-BITS+) keys, so be careful not to overallocate. You are NOT declaring an equivalent number of keys as you would with a hash-table.

:rehash-size - indicates how to expand the table when it fills up.
If an integer, add
space for that many elements. If a floating point number (which must be
greater than 1.0), multiply the size by that amount.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: map-intset (intset f)

Call ‘f‘, a function of one argument, with each member of the intset.

The order of element traversal is undefined. If you wanted ascending or descending traversal, see ‘map-sorted-inset‘.

Behavior is undefined if the function modifies the intset, or if concurrent updates are made from another thread.

Returns nil.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: map-sorted-intset (intset f direction)

Call ‘f‘, a function of one argument, with each member of the inset in the ascending or descending order according to the value of ‘direction‘, which must be :ascending or :descending.

Note that this function is less efficient than unordered traversals of ‘map-intset‘ as it requires a sort on the intset’s hash table keys (and only those keys). However the behavior is equally efficient to the unordered traversal within the range of up to clustered-intset:+fixnum-bits+ values that might be associated with a hash table key.

Behavior is undefined if the function modifies the intset, or if concurrent updates are made from another thread.

Returns nil.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: next (k intset)

For a given non-negative integer k, which does not have to be a member of the intset,
find the next larger member of the intset. Return NIL if there is no appropriate member.

This is not an efficient implementation, this is O(n) and is a misguided convenience function. Consider using the ITERATOR capability instead if that’s what you’re attempting to do,
or one of the mapping functions.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: seq->intset (seq)

Create and return an intset populated from the specified sequence (vector or list). Makes a rough guess about the number of hash table keys you need (HT capacity) based on the range, or quantity, of sequence elements.

Package

clustered-intset.

Source

clustered-intset.lisp.


5.1.2 Structures

Structure: iterator

An object representation iteration state over an INTSET

Package

clustered-intset.

Source

clustered-intset.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: ht
Type

hash-table

Readers

iterator-ht.

Writers

(setf iterator-ht).

Slot: intset
Type

clustered-intset::intset

Readers

iterator-intset.

Writers

(setf iterator-intset).

Slot: descending
Readers

iterator-descending.

Writers

(setf iterator-descending).

Slot: starting-with
Readers

iterator-starting-with.

Writers

(setf iterator-starting-with).

Slot: value-qualifies-fn
Type

function

Readers

iterator-value-qualifies-fn.

Writers

(setf iterator-value-qualifies-fn).

Slot: ending-with
Readers

iterator-ending-with.

Writers

(setf iterator-ending-with).

Slot: remaining-ht-keys
Type

(or null vector)

Readers

iterator-remaining-ht-keys.

Writers

(setf iterator-remaining-ht-keys).

Slot: state
Type

keyword

Readers

iterator-state.

Writers

(setf iterator-state).

Slot: current-ht-key
Type

clustered-intset::key-type

Initform

0

Readers

iterator-current-ht-key.

Writers

(setf iterator-current-ht-key).

Slot: current-ht-value
Type

clustered-intset::value-type

Initform

0

Readers

iterator-current-ht-value.

Writers

(setf iterator-current-ht-value).

Slot: current-bit-position
Type

clustered-intset::fix-mod-type

Initform

0

Readers

iterator-current-bit-position.

Writers

(setf iterator-current-bit-position).


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Constants

Constant: +fixnum-bits+
Package

clustered-intset.

Source

clustered-intset.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.2 Macros

Macro: with-hash-kv (vars k intset &body body)

Given an intset and a non-negative integer member k in the intset, bind vars in the list vars as follows:
first var - the hashtable key, effectively (/ k +fixnum-bits+).
second var - the hashtable value for the hashtable key, or zero if it doesn’t exist.
third var - the modulus of (/ k +fixnum-bits+) which is the bit position for k in hash-value. and execute ’body’ with those bindings.

Package

clustered-intset.

Source

clustered-intset.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.3 Ordinary functions

Function: %make-intset (&key count ht)
Package

clustered-intset.

Source

clustered-intset.lisp.

Function: copy-intset (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Function: copy-iterator (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Function: first-value (iterator)

An an iterator hasn’t been activated yet, activate it and begin looking for keys.
Return the next value, if any, or nil if there isn’t any. Update iterator state accordingly.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: ht-key-filter (ht starting-with ending-with descending)

Return a function which acts as a filter for hash table keys
to see if they quality for iteration according to ‘iterator‘ semantics below.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: initiate-new-ht-key (hash-key iterator)

We’re setting up for the first HT key in iteration, or moving to a new HT key.
Set the iterator state to reflect this HT key, and find the first bit position with a relevant value. Assuming the iterator initialization filtered any keys without any applicable values, we’ll always return a value for a new HT key here.

Does not maintain the remaining-ht-keys slot of the iterator.
Does update the ’current’ values iterator.

Returns the intset element value for the first value associated with the HT key, which should not be nil.

Package

clustered-intset.

Source

clustered-intset.lisp.

Reader: intset-count (instance)
Writer: (setf intset-count) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

count.

Reader: intset-ht (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

ht.

Function: intset-p (object)
Package

clustered-intset.

Source

clustered-intset.lisp.

Reader: iterator-current-bit-position (instance)
Writer: (setf iterator-current-bit-position) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

current-bit-position.

Reader: iterator-current-ht-key (instance)
Writer: (setf iterator-current-ht-key) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

current-ht-key.

Reader: iterator-current-ht-value (instance)
Writer: (setf iterator-current-ht-value) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

current-ht-value.

Reader: iterator-descending (instance)
Writer: (setf iterator-descending) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

descending.

Reader: iterator-ending-with (instance)
Writer: (setf iterator-ending-with) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

ending-with.

Reader: iterator-ht (instance)
Writer: (setf iterator-ht) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

ht.

Reader: iterator-intset (instance)
Writer: (setf iterator-intset) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

intset.

Function: iterator-next-bit-value (iterator)

For an active iterator, if there’s another value to be retrieved for the current hash-table key, advance the iterator to that bit and return the value. Otherwise return nil.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: iterator-next-key-value (iterator)

For an active iterator, if there’s another hash key to process, advance to that key and return the value. Otherwise mark the iterator inactive and return nil.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: iterator-p (object)
Package

clustered-intset.

Source

clustered-intset.lisp.

Reader: iterator-remaining-ht-keys (instance)
Writer: (setf iterator-remaining-ht-keys) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

remaining-ht-keys.

Reader: iterator-starting-with (instance)
Writer: (setf iterator-starting-with) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

starting-with.

Reader: iterator-state (instance)
Writer: (setf iterator-state) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

state.

Reader: iterator-value-qualifies-fn (instance)
Writer: (setf iterator-value-qualifies-fn) (instance)
Package

clustered-intset.

Source

clustered-intset.lisp.

Target Slot

value-qualifies-fn.

Function: make-iterator (&key ht intset descending starting-with value-qualifies-fn ending-with remaining-ht-keys state current-ht-key current-ht-value current-bit-position)
Package

clustered-intset.

Source

clustered-intset.lisp.

Function: next-ascending-key (ht-key ht)

Given a hash-table HT, and a key which may or may not be that hash-table,
return the next key (with multiple values) in the hashtable with a value greater than ‘ht-key‘, or nil if there is no such key.

HT-KEY may be -1, which is not usually accepted in this module, for a a ’first’ like behavior that will find the lowest valued key in the intset, there are any keys.

Returns (values nil nil) or (values next-key value-for-key).

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: next-value (iterator)

Advance an in-progress iterator if we can, returning the next value and updating iterator state. If there are no more values, deactivate the iterator and return nil.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: next-value-for-ht-key (ht-key ht-value bit-position)

Given a hash-table key, the value from the hash table, and the bit position of some set member stored in that key/value pair, return the next ascending value available for the
ht key/value pair or NIL if there is no next value.

HT-VALUE may be zero, in which case we assume there are no valid keys for the value and you just happened to have obtained it via ‘with-hash-kv‘.

BIT-POSITION may be nil if this is the first search for a value in HT-VALUE
otherwise it is deemed to be the position or an intset member for which we want to find
a successor value, i.e. the search starts at (1+ bit-position).

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: some-ht-val (ht k pred)

For some intset member K, check to see if there is some value in the hashtable value bits associated with the hashtable key for K ‘(floor k fixnum-bits)‘, for which
pred is true. For example:

(some-ht-val ht 43 #’<)

For 62 fixnum bits, would check ht key 0 for any ht value bits indicating quantities < 43. Similarly:

(some-ht-val ht 143 #’<=)

For 62 fixnum bits would check for values associated with that key from (* 2 62) to (* 3 62) that were <= 143.

If we find a PRED-qualified value, return true, otherwise return nil.

Package

clustered-intset.

Source

clustered-intset.lisp.

Function: value-predicate (starting-with ending-with descending)

Similar to ‘ht-key-filter‘, only in thise case we’re looking at intset members values
with the optional iteration controls (starting-with, ending-with, descending). Return a predicate which accepts an intset member value and returns true if an intset member qualifies, w.r.t. the optional range value, nil if it does not.

Package

clustered-intset.

Source

clustered-intset.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.4 Structures

Structure: intset
Package

clustered-intset.

Source

clustered-intset.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: count
Type

integer

Initform

0

Readers

intset-count.

Writers

(setf intset-count).

Slot: ht
Type

hash-table

Initform

(make-hash-table :test (function eql))

Readers

intset-ht.

Writers

This slot is read-only.


Previous: , Up: Internals   [Contents][Index]

5.2.5 Types

Type: fix-mod-type ()

Type of value resulting from ‘(mod k +fixnum-bits+)‘.
Generally used to specify the position of a bit in fixnum used as a bitvector.

Package

clustered-intset.

Source

clustered-intset.lisp.

Type: key-type ()

Type of keys stored in the hashtable.

Package

clustered-intset.

Source

clustered-intset.lisp.

Type: value-type ()

Type of values stored in the hashtable.

Package

clustered-intset.

Source

clustered-intset.lisp.


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   %   (  
A   C   D   F   H   I   M   N   S   V   W  
Index Entry  Section

%
%make-intset: Private ordinary functions

(
(setf intset-count): Private ordinary functions
(setf iterator-current-bit-position): Private ordinary functions
(setf iterator-current-ht-key): Private ordinary functions
(setf iterator-current-ht-value): Private ordinary functions
(setf iterator-descending): Private ordinary functions
(setf iterator-ending-with): Private ordinary functions
(setf iterator-ht): Private ordinary functions
(setf iterator-intset): Private ordinary functions
(setf iterator-remaining-ht-keys): Private ordinary functions
(setf iterator-starting-with): Private ordinary functions
(setf iterator-state): Private ordinary functions
(setf iterator-value-qualifies-fn): Private ordinary functions

A
add: Public ordinary functions
advance: Public ordinary functions

C
containsp: Public ordinary functions
copy-intset: Private ordinary functions
copy-iterator: Private ordinary functions
count: Public ordinary functions

D
delete: Public ordinary functions

F
first: Public ordinary functions
first-value: Private ordinary functions
Function, %make-intset: Private ordinary functions
Function, (setf intset-count): Private ordinary functions
Function, (setf iterator-current-bit-position): Private ordinary functions
Function, (setf iterator-current-ht-key): Private ordinary functions
Function, (setf iterator-current-ht-value): Private ordinary functions
Function, (setf iterator-descending): Private ordinary functions
Function, (setf iterator-ending-with): Private ordinary functions
Function, (setf iterator-ht): Private ordinary functions
Function, (setf iterator-intset): Private ordinary functions
Function, (setf iterator-remaining-ht-keys): Private ordinary functions
Function, (setf iterator-starting-with): Private ordinary functions
Function, (setf iterator-state): Private ordinary functions
Function, (setf iterator-value-qualifies-fn): Private ordinary functions
Function, add: Public ordinary functions
Function, advance: Public ordinary functions
Function, containsp: Public ordinary functions
Function, copy-intset: Private ordinary functions
Function, copy-iterator: Private ordinary functions
Function, count: Public ordinary functions
Function, delete: Public ordinary functions
Function, first: Public ordinary functions
Function, first-value: Private ordinary functions
Function, ht-key-filter: Private ordinary functions
Function, initiate-new-ht-key: Private ordinary functions
Function, intset->list: Public ordinary functions
Function, intset->vector: Public ordinary functions
Function, intset-count: Private ordinary functions
Function, intset-ht: Private ordinary functions
Function, intset-p: Private ordinary functions
Function, iterator: Public ordinary functions
Function, iterator-current-bit-position: Private ordinary functions
Function, iterator-current-ht-key: Private ordinary functions
Function, iterator-current-ht-value: Private ordinary functions
Function, iterator-descending: Private ordinary functions
Function, iterator-ending-with: Private ordinary functions
Function, iterator-ht: Private ordinary functions
Function, iterator-intset: Private ordinary functions
Function, iterator-next-bit-value: Private ordinary functions
Function, iterator-next-key-value: Private ordinary functions
Function, iterator-p: Private ordinary functions
Function, iterator-remaining-ht-keys: Private ordinary functions
Function, iterator-starting-with: Private ordinary functions
Function, iterator-state: Private ordinary functions
Function, iterator-value-qualifies-fn: Private ordinary functions
Function, make-intset: Public ordinary functions
Function, make-iterator: Private ordinary functions
Function, map-intset: Public ordinary functions
Function, map-sorted-intset: Public ordinary functions
Function, next: Public ordinary functions
Function, next-ascending-key: Private ordinary functions
Function, next-value: Private ordinary functions
Function, next-value-for-ht-key: Private ordinary functions
Function, seq->intset: Public ordinary functions
Function, some-ht-val: Private ordinary functions
Function, value-predicate: Private ordinary functions

H
ht-key-filter: Private ordinary functions

I
initiate-new-ht-key: Private ordinary functions
intset->list: Public ordinary functions
intset->vector: Public ordinary functions
intset-count: Private ordinary functions
intset-ht: Private ordinary functions
intset-p: Private ordinary functions
iterator: Public ordinary functions
iterator-current-bit-position: Private ordinary functions
iterator-current-ht-key: Private ordinary functions
iterator-current-ht-value: Private ordinary functions
iterator-descending: Private ordinary functions
iterator-ending-with: Private ordinary functions
iterator-ht: Private ordinary functions
iterator-intset: Private ordinary functions
iterator-next-bit-value: Private ordinary functions
iterator-next-key-value: Private ordinary functions
iterator-p: Private ordinary functions
iterator-remaining-ht-keys: Private ordinary functions
iterator-starting-with: Private ordinary functions
iterator-state: Private ordinary functions
iterator-value-qualifies-fn: Private ordinary functions

M
Macro, with-hash-kv: Private macros
make-intset: Public ordinary functions
make-iterator: Private ordinary functions
map-intset: Public ordinary functions
map-sorted-intset: Public ordinary functions

N
next: Public ordinary functions
next-ascending-key: Private ordinary functions
next-value: Private ordinary functions
next-value-for-ht-key: Private ordinary functions

S
seq->intset: Public ordinary functions
some-ht-val: Private ordinary functions

V
value-predicate: Private ordinary functions

W
with-hash-kv: Private macros

Jump to:   %   (  
A   C   D   F   H   I   M   N   S   V   W