Function splay_t

libCacheSim/dataStructure/splay_tuple.c:57–125

// static sTree_tuple * sedgewickized_splay (int i, sTree_tuple * t);

sTree_tuple *splay_t(splay_key_type_t i, sTree_tuple *t) {
  /* Simple top down splay, not requiring i to be in the sTree t.  */
  /* What it does is described above.                             */
  sTree_tuple N, *l, *r, *y;
  if (t == NULL) return t;
  N.left = N.right = NULL;
  l = r = &N;
  long l_size = 0, r_size = 0;

  for (;;) {
    if (key_cmp_t(i, t->key) < 0) {
      if (t->left == NULL) break;
      if (key_cmp_t(i, t->left->key) < 0) {
        y = t->left; /* rotate right */
        t->left = y->right;
        y->right = t;
        t->value = node_value_t(t->left) + node_value_t(t->right) + 1;
        t = y;
        if (t->left == NULL) break;
      }
      r->left = t; /* link right */
      r = t;
      t = t->left;
      r_size += 1 + node_value_t(r->right);
    } else if (key_cmp_t(i, t->key) > 0) {
      if (t->right == NULL) break;
      if (key_cmp_t(i, t->right->key) > 0) {
        y = t->right; /* rotate left */
        t->right = y->left;
        y->left = t;
        t->value = node_value_t(t->left) + node_value_t(t->right) + 1;
        t = y;
        if (t->right == NULL) break;
      }
      l->right = t; /* link left */
      l = t;
      t = t->right;
      l_size += 1 + node_value_t(l->left);
    } else {
      break;
    }
  }

  // TODO: there should be a better way to do this!!!!!!!!!

  l_size += node_value_t(t->left);  /* Now l_size and r_size are the sizes of */
  r_size += node_value_t(t->right); /* the left and right sTrees we just built.*/
  t->value = l_size + r_size + 1;

  l->right = r->left = NULL;

  /* The following two loops correct the size fields of the right path  */
  /* from the left child of the root and the right path from the left   */
  /* child of the root.                                                 */
  for (y = N.right; y != NULL; y = y->right) {
    y->value = l_size;
    l_size -= 1 + node_value_t(y->left);
  }