dwm.1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

.TH DWM 1 dwm-VERSION
.SH NAME
dwm \- dynamic window manager
.SH SYNOPSIS
.B dwm
.RB [ \-v ]
.SH DESCRIPTION
dwm is a dynamic window manager for X. It manages windows in tiling and
swimming layouts. Either layout can be applied dynamically, optimizing the
environment for the application in use and the task performed.
.P
In tiling layout windows are managed in a master and stacking area. The master
area contains the windows which currently need most attention, whereas the
stacking area contains all other windows. In swimming layout windows can be
resized and moved freely. Dialog windows are always managed swimming,
regardless of the layout applied.
.P
Windows are grouped by tags. Each window can be tagged with one or multiple
tags. Selecting certain tags displays all windows with these tags.
.P
dwm contains a small status bar which displays all available tags, the layout,
the title of the focused window, and the text read from standard input. The
selected tags are indicated with a different color. The tags of the focused
window are indicated with a filled square in the top left corner.  The tags
which are applied to one or more windows are indicated with an empty square in
the top left corner.
.P
dwm draws a small border around windows to indicate the focus state.
.SH OPTIONS
.TP
.B \-v
prints version information to standard output, then exits.
.SH USAGE
.SS Status bar
.TP
.B Standard input
is read and displayed in the status text area.
.TP
.B Button1
click on a tag label to display all windows with that tag, click on the layout
label toggles between tiling and swimming layout.
.TP
.B Button3
click on a tag label adds/removes all windows with that tag to/from the view.
.TP
.B Button4
click on the layout label increases the number of windows in the master area (tiling layout only).
.TP
.B Button5
click on the layout label decreases the number of windows in the master area (tiling layout only).
.TP
.B Mod1-Button1
click on a tag label applies that tag to the focused window.
.TP
.B Mod1-Button3
click on a tag label adds/removes that tag to/from the focused window.
.SS Keyboard commands
.TP
.B Mod1-Shift-Return
Start
.BR xterm (1).
.TP
.B Mod1-Tab
Focus next window.
.TP
.B Mod1-Shift-Tab
Focus previous window.
.TP
.B Mod1-Return
Zooms/cycles current window to/from master area (tiling layout), toggles maximization of current window (swimming layout).
.TP
.B Mod1-g
Grow master area (tiling layout only).
.TP
.B Mod1-s
Shrink master area (tiling layout only).
.TP
.B Mod1-i
Increase the number of windows in the master area (tiling layout only).
.TP
.B Mod1-d
Decrease the number of windows in the master area (tiling layout only).
.TP
.B Mod1-Shift-[1..n]
Apply
.RB nth
tag to current window.
.TP
.B Mod1-Shift-0
Apply all tags to current window.
.TP
.B Mod1-Control-Shift-[1..n]
Add/remove
.B nth
tag to/from current window.
.TP
.B Mod1-Shift-c
Close focused window.
.TP
.B Mod1-space
Toggle between tiling and swimming layout (affects all windows).
.TP
.B Mod1-Shift-space
Toggle focused window between swimming and non-swimming state (tiling layout only).
.TP
.B Mod1-[1..n]
View all windows with
.BR nth
tag.
.TP
.B Mod1-0
View all windows with any tag.
.TP
.B Mod1-Control-[1..n]
Add/remove all windows with
.BR nth
tag to/from the view.
.TP
.B Mod1-Shift-q
Quit dwm.
.SS Mouse commands
.TP
.B Mod1-Button1
Move current window while dragging (swimming layout only).
.TP
.B Mod1-Button2
Zooms/cycles current window to/from master area (tiling layout), toggles maximization of current window (swimming layout).
.TP
.B Mod1-Button3
Resize current window while dragging (swimming layout only).
.SH CUSTOMIZATION
dwm is customized by creating a custom config.h and (re)compiling the source
code. This keeps it fast, secure and simple.
.SH SEE ALSO
.BR dmenu (1)
.SH BUGS
The status bar may display
.BR "EOF"
when dwm has been started by an X session manager like
.BR xdm (1),
because those close standard output before executing dwm.
.P
Java applications which use the XToolkit/XAWT backend may draw grey windows
only. The XToolkit/XAWT backend breaks ICCCM-compliance in recent JDK 1.5 and early
JDK 1.6 versions, because it assumes a reparenting window manager. As a workaround
you can use JDK 1.4 (which doesn't contain the XToolkit/XAWT backend) or you
can set the following environment variable (to use the older Motif
backend instead):
.BR AWT_TOOLKIT=MToolkit .
/*
 * include/shard/WIRS.h
 *
 * Copyright (C) 2023 Dong Xie <dongx@psu.edu>
 *                    Douglas Rumbaugh <drumbaugh@psu.edu>
 *
 * All rights reserved. Published under the Modified BSD License.
 *
 */
#pragma once


#include <vector>
#include <cassert>
#include <queue>
#include <memory>
#include <concepts>

#include "psu-ds/PriorityQueue.h"
#include "util/Cursor.h"
#include "psu-ds/Alias.h"
#include "psu-ds/BloomFilter.h"
#include "util/bf_config.h"
#include "framework/MutableBuffer.h"
#include "framework/RecordInterface.h"
#include "framework/ShardInterface.h"
#include "framework/QueryInterface.h"

using psudb::CACHELINE_SIZE;
using psudb::BloomFilter;
using psudb::PriorityQueue;
using psudb::queue_record;
using psudb::Alias;

namespace de {

thread_local size_t wirs_cancelations = 0;

template <WeightedRecordInterface R>
struct wirs_query_parms {
    decltype(R::key) lower_bound;
    decltype(R::key) upper_bound;
    size_t sample_size;
    gsl_rng *rng;
};

template <WeightedRecordInterface R, bool Rejection>
class WIRSQuery;

template <WeightedRecordInterface R>
struct wirs_node {
    struct wirs_node<R> *left, *right;
    decltype(R::key) low, high;
    decltype(R::weight) weight;
    Alias* alias;
};

template <WeightedRecordInterface R>
struct WIRSState {
    decltype(R::weight) total_weight;
    std::vector<wirs_node<R>*> nodes;
    Alias* top_level_alias;
    size_t sample_size;

    WIRSState() {
        total_weight = 0;
        top_level_alias = nullptr;
    }

    ~WIRSState() {
        if (top_level_alias) delete top_level_alias;
    }
};

template <WeightedRecordInterface R>
struct WIRSBufferState {
    size_t cutoff;
    Alias* alias;
    std::vector<Wrapped<R>> records;
    decltype(R::weight) max_weight;
    size_t sample_size;
    decltype(R::weight) total_weight;

    ~WIRSBufferState() {
        delete alias;
    }

};

template <WeightedRecordInterface R>
class WIRS {
private:

    typedef decltype(R::key) K;
    typedef decltype(R::value) V;
    typedef decltype(R::weight) W;

public:

    // FIXME: there has to be a better way to do this
    friend class WIRSQuery<R, true>;
    friend class WIRSQuery<R, false>;

    WIRS(MutableBuffer<R>* buffer)
    : m_reccnt(0), m_tombstone_cnt(0), m_total_weight(0), m_root(nullptr) {

        m_alloc_size = (buffer->get_record_count() * sizeof(Wrapped<R>)) + (CACHELINE_SIZE - (buffer->get_record_count() * sizeof(Wrapped<R>)) % CACHELINE_SIZE);
        assert(m_alloc_size % CACHELINE_SIZE == 0);
        m_data = (Wrapped<R>*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size);

        m_bf = new BloomFilter<R>(BF_FPR, buffer->get_tombstone_count(), BF_HASH_FUNCS);

        size_t offset = 0;
        m_reccnt = 0;
        auto base = buffer->get_data();
        auto stop = base + buffer->get_record_count();

        std::sort(base, stop, std::less<Wrapped<R>>());

        while (base < stop) {
            if (!(base->is_tombstone()) && (base + 1) < stop) {
                if (base->rec == (base + 1)->rec && (base + 1)->is_tombstone()) {
                    base += 2;
                    wirs_cancelations++;
                    continue;
                }
            } else if (base->is_deleted()) {
                base += 1;
                continue;
            }

            // FIXME: this shouldn't be necessary, but the tagged record
            // bypass doesn't seem to be working on this code-path, so this
            // ensures that tagged records from the buffer are able to be
            // dropped, eventually. It should only need to be &= 1
            base->header &= 3;
            m_data[m_reccnt++] = *base;
            m_total_weight+= base->rec.weight;

            if (m_bf && base->is_tombstone()) {
                m_tombstone_cnt++;
                m_bf->insert(base->rec);
            }
            
            base++;
        }

        if (m_reccnt > 0) {
            build_wirs_structure();
        }
    }

    WIRS(WIRS** shards, size_t len)
    : m_reccnt(0), m_tombstone_cnt(0), m_total_weight(0), m_root(nullptr) {
        std::vector<Cursor<Wrapped<R>>> cursors;
        cursors.reserve(len);

        PriorityQueue<Wrapped<R>> pq(len);

        size_t attemp_reccnt = 0;
        size_t tombstone_count = 0;
        
        for (size_t i = 0; i < len; ++i) {
            if (shards[i]) {
                auto base = shards[i]->get_data();
                cursors.emplace_back(Cursor{base, base + shards[i]->get_record_count(), 0, shards[i]->get_record_count()});
                attemp_reccnt += shards[i]->get_record_count();
                tombstone_count += shards[i]->get_tombstone_count();
                pq.push(cursors[i].ptr, i);
            } else {
                cursors.emplace_back(Cursor<Wrapped<R>>{nullptr, nullptr, 0, 0});
            }
        }

        m_bf = new BloomFilter<R>(BF_FPR, tombstone_count, BF_HASH_FUNCS);

        m_alloc_size = (attemp_reccnt * sizeof(Wrapped<R>)) + (CACHELINE_SIZE - (attemp_reccnt * sizeof(Wrapped<R>)) % CACHELINE_SIZE);
        assert(m_alloc_size % CACHELINE_SIZE == 0);
        m_data = (Wrapped<R>*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size);
        
        while (pq.size()) {
            auto now = pq.peek();
            auto next = pq.size() > 1 ? pq.peek(1) : queue_record<Wrapped<R>>{nullptr, 0};
            if (!now.data->is_tombstone() && next.data != nullptr &&
                now.data->rec == next.data->rec && next.data->is_tombstone()) {
                
                pq.pop(); pq.pop();
                auto& cursor1 = cursors[now.version];
                auto& cursor2 = cursors[next.version];
                if (advance_cursor<Wrapped<R>>(cursor1)) pq.push(cursor1.ptr, now.version);
                if (advance_cursor<Wrapped<R>>(cursor2)) pq.push(cursor2.ptr, next.version);
            } else {
                auto& cursor = cursors[now.version];
                if (!cursor.ptr->is_deleted()) {
                    m_data[m_reccnt++] = *cursor.ptr;
                    m_total_weight += cursor.ptr->rec.weight;
                    if (m_bf && cursor.ptr->is_tombstone()) {
                        ++m_tombstone_cnt;
                        if (m_bf) m_bf->insert(cursor.ptr->rec);
                    }
                }
                pq.pop();
                
                if (advance_cursor<Wrapped<R>>(cursor)) pq.push(cursor.ptr, now.version);
            }
        }

        if (m_reccnt > 0) {
            build_wirs_structure();
        }
   }

    ~WIRS() {
        if (m_data) free(m_data);
        for (size_t i=0; i<m_alias.size(); i++) {
            if (m_alias[i]) delete m_alias[i];
        }

        if (m_bf) delete m_bf;

        free_tree(m_root);
    }

    Wrapped<R> *point_lookup(const R &rec, bool filter=false) {
        if (filter && !m_bf->lookup(rec)) {
            return nullptr;
        }

        size_t idx = get_lower_bound(rec.key);
        if (idx >= m_reccnt) {
            return nullptr;
        }

        while (idx < m_reccnt && m_data[idx].rec < rec) ++idx;

        if (m_data[idx].rec == rec) {
            return m_data + idx;
        }

        return nullptr;
    }

    Wrapped<R>* get_data() const {
        return m_data;
    }
    
    size_t get_record_count() const {
        return m_reccnt;
    }

    size_t get_tombstone_count() const {
        return m_tombstone_cnt;
    }

    const Wrapped<R>* get_record_at(size_t idx) const {
        if (idx >= m_reccnt) return nullptr;
        return m_data + idx;
    }


    size_t get_memory_usage() {
        return m_alloc_size + m_node_cnt * sizeof(wirs_node<Wrapped<R>>);
    }

private:

    size_t get_lower_bound(const K& key) const {
        size_t min = 0;
        size_t max = m_reccnt - 1;

        const char * record_key;
        while (min < max) {
            size_t mid = (min + max) / 2;

            if (key > m_data[mid].rec.key) {
                min = mid + 1;
            } else {
                max = mid;
            }
        }

        return min;
    }

    bool covered_by(struct wirs_node<R>* node, const K& lower_key, const K& upper_key) {
        auto low_index = node->low * m_group_size;
        auto high_index = std::min((node->high + 1) * m_group_size - 1, m_reccnt - 1);
        return lower_key < m_data[low_index].rec.key && m_data[high_index].rec.key < upper_key;
    }

    bool intersects(struct wirs_node<R>* node, const K& lower_key, const K& upper_key) {
        auto low_index = node->low * m_group_size;
        auto high_index = std::min((node->high + 1) * m_group_size - 1, m_reccnt - 1);
        return lower_key < m_data[high_index].rec.key && m_data[low_index].rec.key < upper_key;
    }

    void build_wirs_structure() {
        m_group_size = std::ceil(std::log(m_reccnt));
        size_t n_groups = std::ceil((double) m_reccnt / (double) m_group_size);
        
        // Fat point construction + low level alias....
        double sum_weight = 0.0;
        std::vector<W> weights;
        std::vector<double> group_norm_weight;
        size_t i = 0;
        size_t group_no = 0;
        while (i < m_reccnt) {
            double group_weight = 0.0;
            group_norm_weight.clear();
            for (size_t k = 0; k < m_group_size && i < m_reccnt; ++k, ++i) {
                auto w = m_data[i].rec.weight;
                group_norm_weight.emplace_back(w);
                group_weight += w;
                sum_weight += w;
            }

            for (auto& w: group_norm_weight)
                if (group_weight) w /= group_weight;
                else w = 1.0 / group_norm_weight.size();
            m_alias.emplace_back(new Alias(group_norm_weight));

            
            weights.emplace_back(group_weight);
        }

        assert(weights.size() == n_groups);

        m_root = construct_wirs_node(weights, 0, n_groups-1);
    }

     struct wirs_node<R>* construct_wirs_node(const std::vector<W>& weights, size_t low, size_t high) {
        if (low == high) {
            return new wirs_node<R>{nullptr, nullptr, low, high, weights[low], new Alias({1.0})};
        } else if (low > high) return nullptr;

        std::vector<double> node_weights;
        W sum = 0;
        for (size_t i = low; i < high; ++i) {
            node_weights.emplace_back(weights[i]);
            sum += weights[i];
        }

        for (auto& w: node_weights)
            if (sum) w /= sum;
            else w = 1.0 / node_weights.size();
        
        m_node_cnt += 1; 
        size_t mid = (low + high) / 2;
        return new wirs_node<R>{construct_wirs_node(weights, low, mid),
                                construct_wirs_node(weights, mid + 1, high),
                                low, high, sum, new Alias(node_weights)};
    }

    void free_tree(struct wirs_node<R>* node) {
        if (node) {
            delete node->alias;
            free_tree(node->left);
            free_tree(node->right);
            delete node;
        }
    }

    Wrapped<R>* m_data;
    std::vector<Alias *> m_alias;
    wirs_node<R>* m_root;
    W m_total_weight;
    size_t m_reccnt;
    size_t m_tombstone_cnt;
    size_t m_group_size;
    size_t m_alloc_size;
    size_t m_node_cnt;
    BloomFilter<R> *m_bf;
};


template <WeightedRecordInterface R, bool Rejection=true>
class WIRSQuery {
public:

    constexpr static bool EARLY_ABORT=false;
    constexpr static bool SKIP_DELETE_FILTER=false;

    static void *get_query_state(WIRS<R> *wirs, void *parms) {
        auto res = new WIRSState<R>();
        decltype(R::key) lower_key = ((wirs_query_parms<R> *) parms)->lower_bound;
        decltype(R::key) upper_key = ((wirs_query_parms<R> *) parms)->upper_bound;

        // Simulate a stack to unfold recursion.        
        double total_weight = 0.0;
        struct wirs_node<R>* st[64] = {0};
        st[0] = wirs->m_root;
        size_t top = 1;
        while(top > 0) {
            auto now = st[--top];
            if (wirs->covered_by(now, lower_key, upper_key) ||
                (now->left == nullptr && now->right == nullptr && wirs->intersects(now, lower_key, upper_key))) {
                res->nodes.emplace_back(now);
                total_weight += now->weight;
            } else {
                if (now->left && wirs->intersects(now->left, lower_key, upper_key)) st[top++] = now->left;
                if (now->right && wirs->intersects(now->right, lower_key, upper_key)) st[top++] = now->right;
            }
        }
        
        std::vector<double> weights;
        for (const auto& node: res->nodes) {
            weights.emplace_back(node->weight / total_weight);
        }
        res->total_weight = total_weight;
        res->top_level_alias = new Alias(weights);
        res->sample_size = 0;

        return res;
    }

    static void* get_buffer_query_state(MutableBuffer<R> *buffer, void *parms) {
        WIRSBufferState<R> *state = new WIRSBufferState<R>();
        auto parameters = (wirs_query_parms<R>*) parms;
        if constexpr (Rejection) {
            state->cutoff = buffer->get_record_count() - 1;
            state->max_weight = buffer->get_max_weight();
            state->total_weight = buffer->get_total_weight();
            state->sample_size = 0;
            return state;
        }

        std::vector<double> weights;

        state->cutoff = buffer->get_record_count() - 1;
        double total_weight = 0.0;

        for (size_t i = 0; i <= state->cutoff; i++) {
            auto rec = buffer->get_data() + i;

            if (rec->rec.key >= parameters->lower_bound && rec->rec.key <= parameters->upper_bound && !rec->is_tombstone() && !rec->is_deleted()) {
              weights.push_back(rec->rec.weight);
              state->records.push_back(*rec);
              total_weight += rec->rec.weight;
            }
        }

        for (size_t i = 0; i < weights.size(); i++) {
            weights[i] = weights[i] / total_weight;
        }

        state->total_weight = total_weight;
        state->alias = new Alias(weights);
        state->sample_size = 0;

        return state;
    }

    static void process_query_states(void *query_parms, std::vector<void*> &shard_states, void *buff_state) {
        auto p = (wirs_query_parms<R> *) query_parms;
        auto bs = (WIRSBufferState<R> *) buff_state;

        std::vector<size_t> shard_sample_sizes(shard_states.size()+1, 0);
        size_t buffer_sz = 0;

        std::vector<decltype(R::weight)> weights;
        weights.push_back(bs->total_weight);

        decltype(R::weight) total_weight = 0;
        for (auto &s : shard_states) {
            auto state = (WIRSState<R> *) s;
            total_weight += state->total_weight;
            weights.push_back(state->total_weight);
        }

        std::vector<double> normalized_weights;
        for (auto w : weights) {
            normalized_weights.push_back((double) w / (double) total_weight);
        }

        auto shard_alias = Alias(normalized_weights);
        for (size_t i=0; i<p->sample_size; i++) {
            auto idx = shard_alias.get(p->rng);            
            if (idx == 0) {
                buffer_sz++;
            } else {
                shard_sample_sizes[idx - 1]++;
            }
        }


        bs->sample_size = buffer_sz;
        for (size_t i=0; i<shard_states.size(); i++) {
            auto state = (WIRSState<R> *) shard_states[i];
            state->sample_size = shard_sample_sizes[i+1];
        }
    }


    static std::vector<Wrapped<R>> query(WIRS<R> *wirs, void *q_state, void *parms) { 
        auto lower_key = ((wirs_query_parms<R> *) parms)->lower_bound;
        auto upper_key = ((wirs_query_parms<R> *) parms)->upper_bound;
        auto rng = ((wirs_query_parms<R> *) parms)->rng;

        auto state = (WIRSState<R> *) q_state;