<commit_before>#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>

/*
  A Multiword Compare-And-Swap algorithm, defined in "Practical lock-freedom" chapter 3.2
*/

#define UNDECIDED 0
#define FAILED 1
#define SUCCESSFUL 2

typedef uint64_t word_t;

typedef struct {
  // Number of logical locations
  int N;
  // Address
  word_t **a;
  // Expected
  word_t *e;
  // New
  word_t *n;
  // UNDECIDED, FAILED, SUCCESSFUL
  word_t status;
} MCASDesc;

static int AddressCompare(const void *addr1, const void *addr2);
static void AddressSort(MCASDesc *d);

// Performs a multiword compare and swap on N positions, where for each
// i in [1..N], where a[i], e[i], and n[i] correspond to each other;
// atomic { if a[i] == e[i] then a[i] = n[i]; }
// We use descriptors so that MCASHelper can allow recursive helping.
bool MCAS(int N, word_t **a, word_t *e, word_t *n);

// Note that MCASRead will ONLY work if the address being read is manage properly
// through the MCASDesc abstraction!
word_t MCASRead(word_t *a);

// A recursive helper algorithm; each thread will attempt to set their descriptor to
// claim ownership of a contested location; if another descriptor is encountered,
// then that thread helps to ensure that progress is made.
bool MCASHelp(MCASDesc *d);

static int AddressCompare(const void *addr1, const void *addr2) {
  return (uintptr_t) addr1 - (uintptr_t) addr2;
}

static void AddressSort(MCASDesc *d) {<commit_msg>I think I got it! Non-Blocking reads and writes *should* be correct enough for the MCAS algorithm to be scalable.<commit_after>#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>

/*
  A Multiword Compare-And-Swap algorithm, defined in "Practical lock-freedom" chapter 3.2
*/

#define UNDECIDED 0
#define FAILED 1
#define SUCCESSFUL 2

typedef uint64_t word_t;

// Potential modification: Have the "expected" and "new" be apart of a union
// and add specific types for READ/WRITE/CAS...
// CAS = {e, n}
// Write = {n}
// Read = {r, n}
typedef struct {
  // Number of logical locations
  int N;
  // Address
  word_t **a;
  // Expected
  word_t *e;
  // New
  word_t *n;
  // UNDECIDED, FAILED, SUCCESSFUL
  word_t status;
} MCASDesc;

static int AddressCompare(const void *addr1, const void *addr2);
static void AddressSort(MCASDesc *d);

// Performs a multiword compare and swap on N positions, where for each
// i in [1..N], where a[i], e[i], and n[i] correspond to each other;
// atomic { if a[i] == e[i] then a[i] = n[i]; }
// We use descriptors so that MCASHelper can allow recursive helping.
bool MCAS(int N, word_t **a, word_t *e, word_t *n);

// Note that MCASRead will ONLY work if the address being read is managed properly
// through the MCASDesc abstraction!
// Idea:
//  curr <- d->a[i]
//  if isMCASDesc(curr) then
//    MCASHelp(curr)
//    continue
//  d->n[i] = curr;
//  if CCAS(d->a[i], curr, d, &d->status) then
//    ...
//
// Later on in MCASHelper when we're performing the decision point for a reader...
//  for (int i = 0; i < d->N; i++)
//    curr <- d->n[i];
//    if CAS(d->a[i], d, d->n[i]) then
//      d->r[i] = curr;
//
// The above guarantees forward progression in a non-blocking fashion for reads,
// and writes theh same value back after the descriptor is finished.
word_t *MCASRead(word_t *a, int N);

// Note that MCASWrite will ONLY work if the address being written is managed properly
// through the MCASDesc abstraction!
// Idea:
//  curr <- d->a[i]
//  if isMCASDesc(curr) then
//    MCASHelp(curr)
//    continue
//  if CCAS(d->a[i], curr, d, &d->status) then
//    ...
//
// Later on in MCASHelper when we're performing the decision point for a reader...
//  for (int i = 0; i < d->N; i++)
//    CAS(d->a[i], d, d->n[i])
//
// The above guarantees forward progression in a non-blocking fashion for reads,
// and writes theh same value back after the descriptor is finished.
void MCASWrite(word_t *a, int N);

// A recursive helper algorithm; each thread will attempt to set their descriptor to
// claim ownership of a contested location; if another descriptor is encountered,
// then that thread helps to ensure that progress is made.
bool MCASHelp(MCASDesc *d);

static int AddressCompare(const void *addr1, const void *addr2) {
  return (uintptr_t) addr1 - (uintptr_t) addr2;
}

static void AddressSort(MCASDesc *d) {
{'fraction_non_alphanumeric': 0.12575266327003243, 'fraction_numerical': 0.006947660954145438, 'mean_word_length': 3.3803245436105476, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1393562', 'n_tokens_mistral': 1508, 'n_tokens_neox': 1451, 'n_words': 572}