aboutsummaryrefslogtreecommitdiff
path: root/snapshot_array.c
blob: 9e0da2a5d36943b6556995a2e45c8b1395971a50 (plain)
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
// 1146. Snapshot Array
#include <stdio.h>
#include <stdlib.h>

/*
 * implement a 'SnapshotArray' class that supports the following interface
 * - 'SnapshotArray(int length)' initialises an array-like data structure with
 * the given length. initially, each element equals zero.
 * - 'void set(index, val)' sets the element at the given 'index' to be equal to
 * 'val'
 * - 'int snap()' takes a snapshot of the array and retusn the 'snap_id': the
 * total number of times we called 'snap()' minus 1
 * - 'int get(index, snap_id)' returns the value at the given 'index', at the
 * time we took the snapshot with the given 'snap_id'
 */

#define SIZE 50000

struct v {
  int v;
  int i;
  struct v *n;
};

typedef struct {
  struct v *vl[SIZE];
  int i;
} SnapshotArray;

SnapshotArray *snapshotArrayCreate(int length) {
  return calloc(1, sizeof(SnapshotArray));
}

void snapshotArraySet(SnapshotArray *obj, int index, int val) {
  SnapshotArray *s = obj;
  struct v *v = s->vl[s->i], *p = NULL;
  for (; v && index > v->i; p = v, v = v->n)
    ;
  if (v && index == v->i)
    v->v = val;
  else {
    struct v *n = calloc(1, sizeof(*n));
    n->v = val;
    n->i = index;
    n->n = v;
    p ? p->n = n : (s->vl[s->i] = n);
  }
}

int snapshotArraySnap(SnapshotArray *obj) {
  SnapshotArray *s = obj;
  struct v *h = s->vl[s->i++];
  for (struct v **p = &s->vl[s->i]; h; h = h->n) {
    (*p = calloc(1, sizeof(**p)))->v = h->v;
    (*p)->i = h->i;
    p = &(*p)->n;
  }
  return s->i - 1;
}

int snapshotArrayGet(SnapshotArray *obj, int index, int snap_id) {
  SnapshotArray *s = obj;
  struct v *h;
  for (h = s->vl[snap_id]; h && h->i < index; h = h->n)
    ;
  return h && h->i == index ? h->v : 0;
}

void snapshotArrayFree(SnapshotArray *obj) { free(obj); }

int main() {
  SnapshotArray *obj = snapshotArrayCreate(3);
  snapshotArraySet(obj, 0, 5);
  printf("%d\n", snapshotArraySnap(obj)); // expect: 0
  snapshotArraySet(obj, 0, 6);
  printf("%d\n", snapshotArrayGet(obj, 0, 0)); // expect: 5
}