<commit_before>// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
// vim: ts=8 sw=2 smarttab
/*
 * Ceph - scalable distributed file system
 *
 * Copyright (C) 2004-2006 <NAME> <<EMAIL>>
 *
 * This is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License version 2.1, as published by the Free Software 
 * Foundation.  See file COPYING.
 * 
 */

#ifndef CEPH_FRAG_H
#define CEPH_FRAG_H

#include <stdint.h>
#include <map>
#include <list>
#include <iostream>
#include <stdio.h>

#include "buffer.h"

#include "ceph_frag.h"

/*
 * 
 * the goal here is to use a binary split strategy to partition a namespace.  
 * frag_t represents a particular fragment.  bits() tells you the size of the
 * fragment, and value() it's name.  this is roughly analogous to an ip address
 * and netmask.
 * 
 * fragtree_t represents an entire namespace and it's partition.  it essentially 
 * tells you where fragments are split into other fragments, and by how much 
 * (i.e. by how many bits, resulting in a power of 2 number of child fragments).
 * 
 * this vaguely resembles a btree, in that when a fragment becomes large or small
 * we can split or merge, except that there is no guarantee of being balanced.
 *
 * presumably we are partitioning the output of a (perhaps specialized) hash 
 * function.
 */

/**
 * frag_t
 *
 * description of an individual fragment.  that is, a particular piece
 * of the overall namespace.
 *
 * this is conceptually analogous to an ip address and netmask.
 *
 * a value v falls "within" fragment f iff (v & f.mask()) == f.value().
 *
 * we write it as v/b, where v is a value and b is the number of bits.
 * 0/0 (bits==0) corresponds to the entire namespace.  if we bisect that,
 * we get 0/1 and 1/1.  quartering gives us 0/2, 1/2, 2/2, 3/2.  and so on.
 *
 * this makes the right most bit of v the "most significant", which is the 
 * opposite of what we usually see.
 */

/*
 * TODO:
 *  - get_first_child(), next_sibling(int parent_bits) to make (possibly partial) 
 *    iteration efficient (see, e.g., try_assimilate_children()
 *  - rework frag_t so that we mask the left-most (most significant) bits instead of
 *    the right-most (least significant) bits.  just because it's more intutive, and
 *    matches the network/netmask concept.
 */

typedef uint32_t _frag_t;

class frag_t {
  /*
   * encoding is dictated by frag_* functions in ceph_fs.h.  use those
   * helpers _exclusively_.
   */
 public:
  _frag_t _enc;  
  
  frag_t() : _enc(0) { }
  frag_t(unsigned v, unsigned b) : _enc(ceph_frag_make(b, v)) { }
  frag_t(_frag_t e) : _enc(e) { }

  // constructors
  void from_unsigned(unsigned e) { _enc = e; }
  
  // accessors
  unsigned value() const { return ceph_frag_value(_enc); }
  unsigned bits() const { return ceph_frag_bits(_enc); }
  unsigned mask() const { return ceph_frag_mask(_enc); }
  unsigned mask_shift() const { return ceph_frag_mask_shift(_enc); }

  operator _frag_t() const { return _enc; }

  // tests
  bool contains(unsigned v) const { return ceph_frag_contains_value(_enc, v); }
  bool contains(frag_t sub) const { return ceph_frag_contains_frag(_enc, sub._enc); }
  bool is_root() const { return bits() == 0; }
  frag_t parent() const {
    assert(bits() > 0);
    return frag_t(ceph_frag_parent(_enc));
  }

  // splitting
  frag_t make_child(int i, int nb) const {
    assert(i < (1<<nb));
    return frag_t(ceph_frag_make_child(_enc, nb, i));
  }
  void split(int nb, std::list<frag_t>& fragments) const {
    assert(nb > 0);
    unsigned nway = 1 << nb;
    for (unsigned i=0; i<nway; i++) 
      fragments.push_back(make_child(i, nb));
  }

  // binary splitting
  frag_t left_child() const { return frag_t(ceph_frag_left_child(_enc)); }
  frag_t right_child() const { return frag_t(ceph_frag_right_child(_enc)); }

  bool is_left() const { return ceph_frag_is_left_child(_enc); }
  bool is_right() const { return ceph_frag_is_right_child(_enc); }
  frag_t get_sibling() const {
    assert(!is_root());
    return frag_t(ceph_frag_sibling(_enc));
  }

  // sequencing
  bool is_leftmost() const { return ceph_frag_is_leftmost(_enc); }
  bool is_rightmost() const { return ceph_frag_is_rightmost(_enc); }
  frag_t next() const {
    assert(!is_rightmost());
    return frag_t(ceph_frag_next(_enc));
  }

  // parse
  bool parse(const char *s) {
    int value, bits;
    int r = sscanf(s, "%x/%d", &value, &bits);
    if (r == 2) {
      *this = frag_t(value, bits);
      return true;
    }
    return false;
  }
};

inline std::ostream& operator<<(std::ostream& out, frag_t hb)
{
  return out << std::hex << hb.value() << std::dec << "/" << hb.bits();
}
<commit_msg>mds: make frag string rendering simpler<commit_after>// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
// vim: ts=8 sw=2 smarttab
/*
 * Ceph - scalable distributed file system
 *
 * Copyright (C) 2004-2006 <NAME> <<EMAIL>>
 *
 * This is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License version 2.1, as published by the Free Software 
 * Foundation.  See file COPYING.
 * 
 */

#ifndef CEPH_FRAG_H
#define CEPH_FRAG_H

#include <stdint.h>
#include <map>
#include <list>
#include <iostream>
#include <stdio.h>

#include "buffer.h"

#include "ceph_frag.h"

/*
 * 
 * the goal here is to use a binary split strategy to partition a namespace.  
 * frag_t represents a particular fragment.  bits() tells you the size of the
 * fragment, and value() it's name.  this is roughly analogous to an ip address
 * and netmask.
 * 
 * fragtree_t represents an entire namespace and it's partition.  it essentially 
 * tells you where fragments are split into other fragments, and by how much 
 * (i.e. by how many bits, resulting in a power of 2 number of child fragments).
 * 
 * this vaguely resembles a btree, in that when a fragment becomes large or small
 * we can split or merge, except that there is no guarantee of being balanced.
 *
 * presumably we are partitioning the output of a (perhaps specialized) hash 
 * function.
 */

/**
 * frag_t
 *
 * description of an individual fragment.  that is, a particular piece
 * of the overall namespace.
 *
 * this is conceptually analogous to an ip address and netmask.
 *
 * a value v falls "within" fragment f iff (v & f.mask()) == f.value().
 *
 * we write it as v/b, where v is a value and b is the number of bits.
 * 0/0 (bits==0) corresponds to the entire namespace.  if we bisect that,
 * we get 0/1 and 1/1.  quartering gives us 0/2, 1/2, 2/2, 3/2.  and so on.
 *
 * this makes the right most bit of v the "most significant", which is the 
 * opposite of what we usually see.
 */

/*
 * TODO:
 *  - get_first_child(), next_sibling(int parent_bits) to make (possibly partial) 
 *    iteration efficient (see, e.g., try_assimilate_children()
 *  - rework frag_t so that we mask the left-most (most significant) bits instead of
 *    the right-most (least significant) bits.  just because it's more intutive, and
 *    matches the network/netmask concept.
 */

typedef uint32_t _frag_t;

class frag_t {
  /*
   * encoding is dictated by frag_* functions in ceph_fs.h.  use those
   * helpers _exclusively_.
   */
 public:
  _frag_t _enc;  
  
  frag_t() : _enc(0) { }
  frag_t(unsigned v, unsigned b) : _enc(ceph_frag_make(b, v)) { }
  frag_t(_frag_t e) : _enc(e) { }

  // constructors
  void from_unsigned(unsigned e) { _enc = e; }
  
  // accessors
  unsigned value() const { return ceph_frag_value(_enc); }
  unsigned bits() const { return ceph_frag_bits(_enc); }
  unsigned mask() const { return ceph_frag_mask(_enc); }
  unsigned mask_shift() const { return ceph_frag_mask_shift(_enc); }

  operator _frag_t() const { return _enc; }

  // tests
  bool contains(unsigned v) const { return ceph_frag_contains_value(_enc, v); }
  bool contains(frag_t sub) const { return ceph_frag_contains_frag(_enc, sub._enc); }
  bool is_root() const { return bits() == 0; }
  frag_t parent() const {
    assert(bits() > 0);
    return frag_t(ceph_frag_parent(_enc));
  }

  // splitting
  frag_t make_child(int i, int nb) const {
    assert(i < (1<<nb));
    return frag_t(ceph_frag_make_child(_enc, nb, i));
  }
  void split(int nb, std::list<frag_t>& fragments) const {
    assert(nb > 0);
    unsigned nway = 1 << nb;
    for (unsigned i=0; i<nway; i++) 
      fragments.push_back(make_child(i, nb));
  }

  // binary splitting
  frag_t left_child() const { return frag_t(ceph_frag_left_child(_enc)); }
  frag_t right_child() const { return frag_t(ceph_frag_right_child(_enc)); }

  bool is_left() const { return ceph_frag_is_left_child(_enc); }
  bool is_right() const { return ceph_frag_is_right_child(_enc); }
  frag_t get_sibling() const {
    assert(!is_root());
    return frag_t(ceph_frag_sibling(_enc));
  }

  // sequencing
  bool is_leftmost() const { return ceph_frag_is_leftmost(_enc); }
  bool is_rightmost() const { return ceph_frag_is_rightmost(_enc); }
  frag_t next() const {
    assert(!is_rightmost());
    return frag_t(ceph_frag_next(_enc));
  }

  // parse
  bool parse(const char *s) {
    int value, bits;
    int r = sscanf(s, "%x/%d", &value, &bits);
    if (r == 2) {
      *this = frag_t(value, bits);
      return true;
    }
    return false;
  }
};

inline std::ostream& operator<<(std::ostream& out, frag_t hb)
{
  //return out << std::hex << hb.value() << std::dec << "/" << hb.bits();
  unsigned num = hb.bits();
  if (num) {
    unsigned val = hb.value();
    unsigned bit = 1 << hb.mask_shift();
    while (num--) {
      out << ((val & bit) ? '1':'0');
      bit--;	    
    }
  }
  return out << '*';
}

{'fraction_non_alphanumeric': 0.12272914946325351, 'fraction_numerical': 0.00856729975227085, 'mean_word_length': 3.4040909090909093, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 25, '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': '2440497', 'n_tokens_mistral': 3388, 'n_tokens_neox': 3265, 'n_words': 1092}