# cmuparlay/pam architecture

> Architecture diagram of the GitHub repository cmuparlay/pam, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-10-15). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/cmuparlay/pam
- Repository: https://github.com/cmuparlay/pam

## Overview

##### Project Type and Purpose
- Type: C++ parallel library (open-source tool) providing sequence, ordered set/map, and augmented-map interfaces with multiple balancing schemes.
- Purpose: Expose a header-only (plus optional compiled interface) library that clients link against, supporting highly parallel algorithms via join-based tree operations.  Includes examples, tests, and benchmarks to illustrate and validate functionality.

##### File Structure
Top level:
– CMakeLists.txt, Makeheader, .gitmodules  → Build and submodule setup
– include/pam/…                       → Public library headers
– benchmark/                           → Performance tests
– examples/                            → Sample applications in domains (interval, range_query, segment, rectangle, index, tpch)
– tests/                               → Unit and parallel tests
Key patterns:
- Header-only API living under include/pam
- Modular tree implementations (avl_tree, treap, red_black_tree, weight_balanced_tree)
- Utility modules (gc, parsing, timing)
- Examples organized by algorithm/domain
- Dependence on ParlayLib (git submodule)

##### README for Insights
– Architecture described in papers: join-based balanced trees + prefix structures
– External dependency: ParlayLib for parallel primitives (sorting, scan, scheduler)
– Build via CMake with option to download ParlayLib
– Runtime options for scheduler backends (Cilk, OpenMP, TBB, sequential)

##### Main Components and Their Interactions
a. Components:
1. Client Applications
- examples/…
- tests/
- benchmark/
2. PAM Public API (include/pam/pam.h and friends)
3. PAM Core Modules
- Tree Data Structures: avl_tree, red_black_tree, treap, weight_balanced_tree
- Augmentation & Sequence Ops: augmented_ops, sequence_ops, map_ops, build
- Utilities: gc (garbage collection), get_time, parse_command_line, utils
4. Third-Party Library
- ParlayLib (parallel algorithms, scheduler)
5. Build System
- CMake + Makeheader + git submodule
6. Hardware / Runtime
- Multicore CPU, 128-bit CMPXCHG

b. Relationships and Data Flow:
– Client code invokes PAM Public API
– Public API delegates to Core Modules (tree operations, augmentation, sequence ops)
– Core Modules perform parallel algorithms by calling ParlayLib routines
– ParlayLib issues tasks to the scheduler and uses low-level atomic operations/HW
– Build system orchestrates compilation and configuration (including optional download of ParlayLib)

c. Architectural Patterns & Principles:
– Layered architecture (clients → API → core modules → external library → hardware)
– Modular: pluggable balancing schemes via templates
– Join-based divide-and-conquer parallelism
– Header-only design for ease of integration (with optional compiled library)
– Extensible augmentation via user-provided entry struct

d. Key Technologies & Frameworks:
– C++17 templates and inline implementations
– CMake for cross-platform builds
– ParlayLib for parallel primitives
– Optional backends: Cilk Plus, OpenMP, TBB

##### Elements
– API calls from clients to public API
– Internal calls from API to core modules
– Calls from core modules to ParlayLib
– Data flow from hardware back up through layers (for timing, GC)
– Library code (e.g., blue rectangles)
– Applications/tests (e.g., green rectangles)
– External dependencies (e.g., orange rectangles)
– Build/configuration (e.g., gray parallelograms)

##### Detailed Breakdown of Components
1. Client Layer:
– examples/index, examples/interval, examples/range_query, etc.
– tests/*.cpp, benchmark/timeOps.cpp
2. API Layer:
– include/pam/pam.h (entry point)
– pam_map, pam_set typedefs
3. Core Module Layer:
– Data structures: avl_tree.h, red_black_tree.h, treap.h, weight_balanced_tree.h
– Augmentation: augmented_map.h, augmented_node.h, augmented_ops.h
– Sequence operations: sequence_ops.h
– Build utilities: build.h, map_ops.h
– Support: gc.h, parse_command_line.h, get_time.h, utils.h
4. External Parallel Primitives:
– parlaylib submodule
5. Build & Deploy:
– CMakeLists.txt (+ subdirectories), .gitmodules, Makeheader
6. Hardware:

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% Client Layer
    subgraph "Client Layer"
        direction TB
        Examples["Examples"]:::client
        Tests["Tests"]:::client
        Benchmark["Benchmark"]:::client
    end

    %% API Layer
    subgraph "API Layer"
        direction TB
        pam_h["pam.h"]:::api
        map_h["map.h"]:::api
        build_h["build.h"]:::api
        map_ops_h["map_ops.h"]:::api
    end

    %% Core Modules
    subgraph "Core Modules"
        direction TB

        subgraph "Data Structures"
            AVL["avl_tree.h"]:::core
            RBT["red_black_tree.h"]:::core
            Treap["treap.h"]:::core
            WBT["weight_balanced_tree.h"]:::core
            Balance["balance_utils.h"]:::core
            Node["basic_node.h"]:::core
        end

        subgraph "Augmentation"
            AM["augmented_map.h"]:::core
            AN["augmented_node.h"]:::core
            AO["augmented_ops.h"]:::core
        end

        subgraph "Sequence Operations"
            Seq["sequence_ops.h"]:::core
        end

        subgraph "Utilities"
            GC["gc.h"]:::core
            Time["get_time.h"]:::core
            Parse["parse_command_line.h"]:::core
            Utils["utils.h"]:::core
        end
    end

    %% External Dependencies
    subgraph "External Parallel Primitives"
        ParlayLib["ParlayLib Submodule"]:::external
    end

    %% Build & Config
    subgraph "Build & Configuration"
        direction TB
        CMakeTop["CMakeLists.txt"]:::build
        GitMod[".gitmodules"]:::build
        MakeHdr["Makeheader"]:::build
        ExCMake["examples/CMakeLists.txt"]:::build
        BmCMake["benchmark/CMakeLists.txt"]:::build
        TstCMake["tests/CMakeLists.txt"]:::build
        TstMake["tests/makefile"]:::build
    end

    %% Hardware
    Hardware["Multicore CPU\n128-bit CMPXCHG"]:::hardware

    %% Connections
    Examples -->|uses| pam_h
    Tests -->|uses| pam_h
    Benchmark -->|uses| pam_h

    pam_h -->|includes| map_h
    pam_h -->|includes| build_h
    pam_h -->|includes| map_ops_h

    pam_h -->|delegates| AVL
    pam_h -->|delegates| RBT
    pam_h -->|delegates| Treap
    pam_h -->|delegates| WBT
    pam_h -->|delegates| AM
    pam_h -->|delegates| AO
    pam_h -->|delegates| Seq

    AVL -->|parallel ops| ParlayLib
    RBT -->|parallel ops| ParlayLib
    Treap -->|parallel ops| ParlayLib
    WBT -->|parallel ops| ParlayLib
    AO -->|uses| ParlayLib
    Seq -->|uses| ParlayLib

    ParlayLib -->|executes on| Hardware

    CMakeTop --> Examples
    CMakeTop --> Tests
    CMakeTop --> Benchmark
    CMakeTop --> pam_h
    CMakeTop --> AVL
    CMakeTop --> ParlayLib

    GitMod --> ParlayLib
    MakeHdr --> CMakeTop

    ExCMake --> Examples
    BmCMake --> Benchmark
    TstCMake --> Tests
    TstMake --> Tests

    %% Click Events
    click Examples "https://github.com/cmuparlay/pam/tree/master/examples/"
    click Tests "https://github.com/cmuparlay/pam/tree/master/tests/"
    click Benchmark "https://github.com/cmuparlay/pam/blob/master/benchmark/timeOps.cpp"
    click pam_h "https://github.com/cmuparlay/pam/blob/master/include/pam/pam.h"
    click map_h "https://github.com/cmuparlay/pam/blob/master/include/pam/map.h"
    click build_h "https://github.com/cmuparlay/pam/blob/master/include/pam/build.h"
    click map_ops_h "https://github.com/cmuparlay/pam/blob/master/include/pam/map_ops.h"
    click AVL "https://github.com/cmuparlay/pam/blob/master/include/pam/avl_tree.h"
    click RBT "https://github.com/cmuparlay/pam/blob/master/include/pam/red_black_tree.h"
    click Treap "https://github.com/cmuparlay/pam/blob/master/include/pam/treap.h"
    click WBT "https://github.com/cmuparlay/pam/blob/master/include/pam/weight_balanced_tree.h"
    click Balance "https://github.com/cmuparlay/pam/blob/master/include/pam/balance_utils.h"
    click Node "https://github.com/cmuparlay/pam/blob/master/include/pam/basic_node.h"
    click AM "https://github.com/cmuparlay/pam/blob/master/include/pam/augmented_map.h"
    click AN "https://github.com/cmuparlay/pam/blob/master/include/pam/augmented_node.h"
    click AO "https://github.com/cmuparlay/pam/blob/master/include/pam/augmented_ops.h"
    click Seq "https://github.com/cmuparlay/pam/blob/master/include/pam/sequence_ops.h"
    click GC "https://github.com/cmuparlay/pam/blob/master/include/pam/gc.h"
    click Time "https://github.com/cmuparlay/pam/blob/master/include/pam/get_time.h"
    click Parse "https://github.com/cmuparlay/pam/blob/master/include/pam/parse_command_line.h"
    click Utils "https://github.com/cmuparlay/pam/blob/master/include/pam/utils.h"
    click CMakeTop "https://github.com/cmuparlay/pam/blob/master/CMakeLists.txt"
    click GitMod "https://github.com/cmuparlay/pam/blob/master/.gitmodules"
    click MakeHdr "https://github.com/cmuparlay/pam/tree/master/Makeheader"
    click ExCMake "https://github.com/cmuparlay/pam/blob/master/examples/CMakeLists.txt"
    click BmCMake "https://github.com/cmuparlay/pam/blob/master/benchmark/CMakeLists.txt"
    click TstCMake "https://github.com/cmuparlay/pam/blob/master/tests/CMakeLists.txt"
    click TstMake "https://github.com/cmuparlay/pam/tree/master/tests/makefile"

    %% Styles
    classDef client fill:#aaffaa,stroke:#333,stroke-width:1px
    classDef api fill:#aaddff,stroke:#333,stroke-width:1px
    classDef core fill:#aaaaff,stroke:#333,stroke-width:1px
    classDef external fill:#ffcc88,stroke:#333,stroke-width:1px
    classDef build fill:#dddddd,stroke:#333,stroke-width:1px
    classDef hardware fill:#ffdddd,stroke:#333,stroke-width:1px,stroke-dasharray: 5 5
```
