FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
cache.h
1 #ifndef __CACHE_H__
2 #define __CACHE_H__
3 
4 /*
5  * Copyright 2014 Open Connectome Project (http://openconnecto.me)
6  * Written by Da Zheng (zhengda1936@gmail.com)
7  *
8  * This file is part of SAFSlib.
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
22 
23 #include <unistd.h>
24 #include <malloc.h>
25 #include <string.h>
26 #include <stdio.h>
27 #include <pthread.h>
28 #include <assert.h>
29 #include <numa.h>
30 
31 #include <memory>
32 #include <map>
33 
34 #include "common.h"
35 #include "concurrency.h"
36 #include "io_request.h"
37 #include "parameters.h"
38 
39 namespace safs
40 {
41 
42 const off_t PAGE_INVALID_OFFSET = ((off_t) -1) << LOG_PAGE_SIZE;
43 
44 enum {
45  /* All the 4 bites need to be protected by the lock bit. */
46  DATA_READY_BIT = 0,
47  IO_PENDING_BIT,
48  /* The two bits exclude each other. */
49  DIRTY_BIT,
50  OLD_DIRTY_BIT,
51  /*
52  * This flag indicates the IO request is in the queue for
53  * writing back.
54  */
55  PREPARE_WRITEBACK,
56 
57  LOCK_BIT,
58 
59  /*
60  * These bits don't need to be protected by the lock.
61  * They are used by LRU2Q, so it can be deleted in the future.
62  */
63  ACTIVE_BIT,
64  REFERENCED_BIT,
65 };
66 
67 static inline bool page_set_flag(char &flags, int flag, bool v)
68 {
69  char orig = flags;
70  if (v)
71  flags |= 0x1 << flag;
72  else
73  flags &= ~(0x1 << flag);
74  return orig & (0x1 << flag);
75 }
76 
77 typedef data_loc_t page_id_t;
78 
79 class page
80 {
81  /*
82  * the offset in the file in pages.
83  * it can cover a file of 8 TB.
84  */
85  int offset;
86  file_id_t file_id;
87 
88  /* offset in the file in bytes */
89  void set_offset(off_t off) {
90  offset = off >> LOG_PAGE_SIZE;
91  }
92 
93  /*
94  * in pages.
95  */
96 protected:
97  volatile void *data;
98  volatile short refcnt;
99  volatile char flags;
100  volatile unsigned char hits;
101  volatile char flush_score;
102 public:
103  page(): data(NULL) {
104  file_id = -1;
105  offset = -1;
106  refcnt = 0;
107  flags = 0;
108  hits = 0;
109  flush_score = 0;
110  }
111 
112  page(const page_id_t &pg_id, char *data) {
113  set_offset(pg_id.get_offset());
114  file_id = pg_id.get_file_id();
115  this->data = data;
116  refcnt = 0;
117  flags = 0;
118  hits = 0;
119  flush_score = 0;
120  }
121 
122  void set_id(const page_id_t &pg_id) {
123  set_offset(pg_id.get_offset());
124  file_id = pg_id.get_file_id();
125  }
126 
127  bool is_valid() const {
128  return offset != -1;
129  }
130 
131  bool set_flag(int flag, bool v) {
132  char orig = flags;
133  if (v)
134  flags |= 0x1 << flag;
135  else
136  flags &= ~(0x1 << flag);
137  return orig & (0x1 << flag);
138  }
139  char test_flags(char flags) {
140  return this->flags & flags;
141  }
142 
143  void set_flush_score(int score) {
144  this->flush_score = score;
145  }
146 
147  int get_flush_score() const {
148  return flush_score;
149  }
150 
151  bool initialized() const {
152  return offset != -1;
153  }
154 
155  file_id_t get_file_id() const { return file_id; }
156  off_t get_offset() const { return ((off_t) offset) << LOG_PAGE_SIZE; }
157  void *get_data() const { return (void *) data; }
158 
159  bool data_ready() const { return flags & (0x1 << DATA_READY_BIT); }
160  bool set_data_ready(bool ready) {
161  return set_flag(DATA_READY_BIT, ready);
162  }
163  bool is_dirty() const { return flags & (0x1 << DIRTY_BIT); }
164  bool set_dirty(bool dirty) {
165  return set_flag(DIRTY_BIT, dirty);
166  }
167 
168  bool is_old_dirty() const { return flags & (0x1 << OLD_DIRTY_BIT); }
169  bool set_old_dirty(bool dirty) {
170  return set_flag(OLD_DIRTY_BIT, dirty);
171  }
172 
173  bool is_prepare_writeback() const {
174  return flags & (0x1 << PREPARE_WRITEBACK);
175  }
176  bool set_prepare_writeback(bool writeback) {
177  return set_flag(PREPARE_WRITEBACK, writeback);
178  }
179 
180  bool set_referenced(bool referenced) {
181  return set_flag(REFERENCED_BIT, referenced);
182  }
183  bool referenced() const {
184  return flags & (0x1 << REFERENCED_BIT);
185  }
186 
187  bool set_active(bool active) {
188  return set_flag(ACTIVE_BIT, active);
189  }
190  bool active() const {
191  return flags & (0x1 << ACTIVE_BIT);
192  }
193 
194  void reset_hits() {
195  hits = 0;
196  }
197  int get_hits() const {
198  return hits;
199  }
200  void set_hits(int hits) {
201  assert (hits <= 0xff);
202  this->hits = hits;
203  }
204  /* the page is accessed */
205  void hit();
206 
207  virtual void inc_ref() {
208  refcnt++;
209  }
210  virtual void dec_ref() {
211  refcnt--;
212  }
213  virtual short get_ref() const {
214  return refcnt;
215  }
216 };
217 
218 class original_io_request;
219 
220 class thread_safe_page: public page
221 {
222 #ifdef PTHREAD_WAIT
223  pthread_cond_t ready_cond;
224  pthread_cond_t dirty_cond;
225  pthread_mutex_t mutex;
226 #endif
227 
228  bool set_flags_bit(int i, bool v) {
229  char orig;
230  if (v)
231  orig = __sync_fetch_and_or(&flags, 0x1 << i);
232  else
233  orig = __sync_fetch_and_and(&flags, ~(0x1 << i));
234  return orig & (0x1 << i);
235  }
236 
237  bool get_flags_bit(int i) const {
238  return flags & (0x1 << i);
239  }
240 
241  original_io_request *reqs;
242  int node_id;
243  pthread_spinlock_t _lock;
244 
245 public:
246  thread_safe_page(): page() {
247  pthread_spin_init(&_lock, PTHREAD_PROCESS_PRIVATE);
248 #ifdef PTHREAD_WAIT
249  pthread_cond_init(&ready_cond, NULL);
250  pthread_cond_init(&dirty_cond, NULL);
251  pthread_mutex_init(&mutex, NULL);
252 #endif
253  reqs = NULL;
254  node_id = -1;
255  }
256 
257  thread_safe_page(const page_id_t &pg_id, char *data,
258  int node_id): page(pg_id, data) {
259  pthread_spin_init(&_lock, PTHREAD_PROCESS_PRIVATE);
260 #ifdef PTHREAD_WAIT
261  pthread_cond_init(&ready_cond, NULL);
262  pthread_cond_init(&dirty_cond, NULL);
263  pthread_mutex_init(&mutex, NULL);
264 #endif
265  reqs = NULL;
266  this->node_id = node_id;
267  }
268 
269  ~thread_safe_page() {
270  pthread_spin_destroy(&_lock);
271 #ifdef PTHREAD_WAIT
272  pthread_mutex_destroy(&mutex);
273  pthread_cond_destroy(&ready_cond);
274  pthread_cond_destroy(&dirty_cond);
275 #endif
276  }
277 
278  int get_node_id() const {
279  return node_id;
280  }
281 
282  /* this is enough for x86 architecture */
283  bool data_ready() const { return get_flags_bit(DATA_READY_BIT); }
284  void wait_ready() {
285 #ifdef PTHREAD_WAIT
286  printf("wait data to be ready\n");
287  pthread_mutex_lock(&mutex);
288 #endif
289  while (!data_ready()) {
290 #ifdef PTHREAD_WAIT
291  pthread_cond_wait(&ready_cond, &mutex);
292  printf("thread %ld wait for data ready\n", pthread_self());
293 #endif
294  }
295 #ifdef PTHREAD_WAIT
296  pthread_mutex_unlock(&mutex);
297 #endif
298  }
299  bool set_data_ready(bool ready) {
300 #ifdef PTHREAD_WAIT
301  pthread_mutex_lock(&mutex);
302 #endif
303  bool ret = set_flags_bit(DATA_READY_BIT, ready);
304 #ifdef PTHREAD_WAIT
305  pthread_cond_signal(&ready_cond);
306  pthread_mutex_unlock(&mutex);
307 #endif
308  return ret;
309  }
310 
311  bool set_dirty(bool dirty) {
312 #ifdef PTHREAD_WAIT
313  pthread_mutex_lock(&mutex);
314 #endif
315  bool ret = set_flags_bit(DIRTY_BIT, dirty);
316 #ifdef PTHREAD_WAIT
317  pthread_cond_signal(&dirty_cond);
318  pthread_mutex_unlock(&mutex);
319 #endif
320  return ret;
321  }
322  void wait_cleaned() {
323 #ifdef PTHREAD_WAIT
324  pthread_mutex_lock(&mutex);
325 #endif
326  while (is_dirty()) {
327 #ifdef PTHREAD_WAIT
328  pthread_cond_wait(&dirty_cond, &mutex);
329  printf("thread %ld wait for the page to be written\n",
330  pthread_self());
331 #endif
332  }
333 #ifdef PTHREAD_WAIT
334  pthread_mutex_unlock(&mutex);
335 #endif
336  }
337 
338  bool is_io_pending() const {
339  return get_flags_bit(IO_PENDING_BIT);
340  }
341  bool set_io_pending(bool pending) {
342  return set_flags_bit(IO_PENDING_BIT, pending);
343  }
344  /* we set the status to io pending,
345  * and return the original status */
346  bool test_and_set_io_pending() {
347  int old = __sync_fetch_and_or(&flags, 0x1 << IO_PENDING_BIT);
348  return old & (0x1 << IO_PENDING_BIT);
349  }
350 
351  bool is_prepare_writeback() const {
352  return get_flags_bit(PREPARE_WRITEBACK);
353  }
354  bool set_prepare_writeback(bool writeback) {
355  return set_flags_bit(PREPARE_WRITEBACK, writeback);
356  }
357 
358  void lock() {
359  pthread_spin_lock(&_lock);
360 // int old;
361 // do {
362 // old = __sync_fetch_and_or(&flags, 0x1 << LOCK_BIT);
363 // } while (old & (0x1 << LOCK_BIT));
364  }
365  void unlock() {
366  pthread_spin_unlock(&_lock);
367 // set_flags_bit(LOCK_BIT, false);
368  }
369 
370  void inc_ref() {
371  __sync_fetch_and_add(&refcnt, 1);
372  }
373  void dec_ref() {
374  __sync_fetch_and_sub(&refcnt, 1);
375  }
376 
377  void wait_unused() {
378  while(get_ref()) {
379 #ifdef DEBUG
380  printf("thread %ld wait for used\n", pthread_self());
381 #endif
382  }
383  }
384 
385  void add_req(original_io_request *req);
386  original_io_request *reset_reqs();
387  original_io_request *get_io_req() const;
388 };
389 
390 class page_filter
391 {
392 public:
393  virtual int filter(const thread_safe_page *pages[], int num,
394  const thread_safe_page *returned_pages[]) = 0;
395 };
396 
397 class dirty_page_flusher;
398 class io_interface;
399 class page_filter;
400 class page_cache
401 {
402 public:
403  typedef std::shared_ptr<page_cache> ptr;
404 
405  virtual ~page_cache() {
406  }
413  virtual page *search(const page_id_t &pg_id, page_id_t &old_id) = 0;
418  virtual page *search(const page_id_t &pg_id) {
419  return NULL;
420  }
424  virtual long size() = 0;
425  /* This method should be called within each thread. */
426  virtual void init(std::shared_ptr<io_interface> underlying) {
427  }
428  virtual bool shrink(int npages, char *pages[]) {
429  return false;
430  }
431  virtual void create_flusher(std::shared_ptr<io_interface> io,
432  page_cache *global_cache) {
433  }
434  virtual void mark_dirty_pages(thread_safe_page *pages[], int num,
435  io_interface &io) {
436  }
437  virtual int flush_dirty_pages(page_filter *filter, int max_num) {
438  return 0;
439  }
440  virtual void flush_callback(io_request &req) {
441  }
442  virtual int get_node_id() const {
443  return -1;
444  }
445 
446  // For test
447  virtual void print_stat() const {
448  }
449 
450  virtual void sanity_check() const = 0;
451 };
452 
453 /*
454  * This is used to implement hashtable-based indexing.
455  */
456 class frame: public thread_safe_page
457 {
458  /* equivalent to the number of hits */
459  atomic_integer wcount;
460  /* equivalent to the number of references */
461  atomic_integer pinning;
462 
463 public:
464  frame(): thread_safe_page() {
465  }
466 
467  frame(const page_id_t &pg_id, char *data): thread_safe_page(pg_id, data, -1) {
468  }
469 
470  /*
471  * To remove the warning of clang++, I need to define a virtual destructor.
472  * But I really don't need to clean up anything.
473  */
474  virtual ~frame() {
475  }
476 
477  void *volatileGetValue() {
478  /*
479  * maybe a memory fence here,
480  * but it's not needed in the x86 machine.
481  */
482  return get_data();
483  }
484 
485  bool CASValue(void *expect,void *update) {
486  return __sync_bool_compare_and_swap(&data, expect, update);
487  }
488 
489  int getWC() const {
490  return wcount.get();
491  }
492 
493  void incrWC(int num = 1) {
494  wcount.inc(num);
495  }
496 
497  int decrWC(int num = 1) {
498  return wcount.dec(num);
499  }
500 
501  bool tryEvict() {
502  return pinning.CAS(0, -1);
503  }
504 
505  void evictUnshared() {
506  pinning.CAS(1, -1);
507  }
508 
509  int pinCount() const {
510  return pinning.get();
511  }
512 
513  bool pin() {
514  int x;
515  do {
516  x = pinning.get();
517  if (x <= -1)
518  return false;
519  } while (!pinning.CAS(x, x + 1));
520  return true;
521  }
522 
523  void dec_ref() {
524  unpin();
525  }
526 
527  void unpin() {
528  pinning.dec(1);
529  }
530 };
531 
532 /*
533  * The interface of allocating a page_byte_array.
534  */
535 class byte_array_allocator
536 {
537 public:
538  virtual ~byte_array_allocator() {
539  }
540 
541  virtual page_byte_array *alloc() = 0;
542  virtual void free(page_byte_array *) = 0;
543 };
544 
551 {
552  byte_array_allocator *alloc;
553 public:
554  static void destroy(page_byte_array *arr) {
555  assert(arr->alloc);
556  arr->alloc->free(arr);
557  }
558 
559  page_byte_array() {
560  alloc = NULL;
561  }
562 
563  page_byte_array(byte_array_allocator &alloc) {
564  this->alloc = &alloc;
565  }
566 
567  byte_array_allocator &get_allocator() {
568  return *alloc;
569  }
570 
571  virtual ~page_byte_array() {
572  }
573 
578  virtual void lock() = 0;
583  virtual void unlock() = 0;
588  virtual size_t get_size() const = 0;
592  virtual page_byte_array *clone() = 0;
593 
598  virtual off_t get_offset() const = 0;
599 
600  virtual off_t get_offset_in_first_page() const = 0;
601  virtual const char *get_page(int idx) const = 0;
602 
610  template<class T>
611  class const_iterator: public std::iterator<std::random_access_iterator_tag, T>
612  {
613  const page_byte_array *arr;
614 
615  // The byte offset in the pages.
616  off_t off;
617  // The end byte offset in the pages.
618  off_t end;
619  public:
620  typedef typename std::iterator<std::random_access_iterator_tag,
621  T>::difference_type difference_type;
622 
623  const_iterator(const page_byte_array *arr, off_t byte_off, off_t byte_end) {
624  this->arr = arr;
625  off = arr->get_offset_in_first_page() + byte_off;
626  end = arr->get_offset_in_first_page() + byte_end;
627  assert((size_t) byte_end <= arr->get_size());
628  // Either no elements cross the page boundary,
629  assert((PAGE_SIZE - (off % PAGE_SIZE)) % sizeof(T) == 0
630  // or the entire range is inside a page.
631  || end < PAGE_SIZE);
632  assert((byte_end - byte_off) % sizeof(T) == 0);
633  }
634 
639  T operator*() const {
640  off_t pg_idx = off / PAGE_SIZE;
641  off_t off_in_pg = off % PAGE_SIZE;
642  const char *data = arr->get_page(pg_idx);
643  return *(T *) (data + off_in_pg);
644  }
645 
652  difference_type operator-(const const_iterator<T> &it) const {
653  return (off - it.off) / sizeof(T);
654  }
655 
663  const_iterator<T> operator+(size_t num) const {
664  const_iterator<T> ret = *this;
665  ret.off += num * sizeof(T);
666  assert(ret.end >= ret.off);
667  return ret;
668  }
669 
676  off += sizeof(T);
677  return *this;
678  }
679 
686  bool operator==(const const_iterator<T> &it) const {
687  return off == it.off;
688  }
689 
696  bool operator!=(const const_iterator<T> &it) const {
697  return !(*this == it);
698  }
699 
708  off += num * sizeof(T);
709  assert(end >= off);
710  return *this;
711  }
712 
713  bool has_next() const {
714  return end - off >= sizeof(T);
715  }
716  };
717 
718  template<class T>
719  class seq_const_page_iterator
720  {
721  const T *data;
722  const T *data_end;
723  public:
724  seq_const_page_iterator() {
725  data = NULL;
726  data_end = NULL;
727  }
728 
729  seq_const_page_iterator(const char *page, off_t byte_off,
730  off_t byte_end) {
731  data = (const T *) (page + byte_off);
732  data_end = (const T *) (page + byte_end);
733  }
734 
735  int get_num_entries() const {
736  return data_end - data;
737  }
738 
739  bool has_next() const {
740  return data < data_end;
741  }
742 
743  T next() {
744  const T *old_data = data;
745  data++;
746  return *old_data;
747  }
748 
749  T curr() const {
750  return *data;
751  }
752  };
753 
759  template<class T>
761  {
762  const page_byte_array *arr;
763  seq_const_page_iterator<T> curr_page_it;
764 
765  off_t start;
766  // The byte offset in the pages.
767  off_t off;
768  // The end byte offset in the pages.
769  off_t end;
770  public:
771  seq_const_iterator(const page_byte_array *arr, off_t byte_off,
772  off_t byte_end) {
773  this->arr = arr;
774  assert((size_t) byte_end <= arr->get_size());
775  assert(byte_off <= byte_end);
776 
777  start = arr->get_offset_in_first_page() + byte_off;
778  off = arr->get_offset_in_first_page() + byte_off;
779  end = arr->get_offset_in_first_page() + byte_end;
780 
781  if (byte_off == byte_end) {
782  curr_page_it = seq_const_page_iterator<T>();
783  }
784  else {
785  off_t pg_end;
786  if (end - ROUND_PAGE(off) >= PAGE_SIZE)
787  pg_end = PAGE_SIZE;
788  else
789  pg_end = end - ROUND_PAGE(off);
790  curr_page_it = seq_const_page_iterator<T>(arr->get_page(
791  off / PAGE_SIZE), off % PAGE_SIZE, pg_end);
792  }
793  // TODO remove the constraints later.
794  assert((PAGE_SIZE - (off % PAGE_SIZE)) % sizeof(T) == 0
795  // or the entire range is inside a page.
796  || end < PAGE_SIZE);
797  assert((byte_end - byte_off) % sizeof(T) == 0);
798  }
799 
805  bool has_next() {
806  if (curr_page_it.has_next())
807  return true;
808  else {
809  off = ROUNDUP_PAGE(off + 1);
810  if (off < end) {
811  curr_page_it = seq_const_page_iterator<T>(arr->get_page(
812  off / PAGE_SIZE), 0, min(PAGE_SIZE, end - off));
813  return true;
814  }
815  else {
816  return false;
817  }
818  }
819  }
820 
826  int get_num_tot_entries() const {
827  return (end - off) / sizeof(T);
828  }
829 
836  return curr_page_it.get_num_entries();
837  }
838 
843  T next() {
844  return curr_page_it.next();
845  }
846 
847  bool move_to(size_t idx) {
848  off = start + idx * sizeof(T);
849  if (off >= end)
850  return false;
851 
852  off_t pg_end;
853  if (end - ROUND_PAGE(off) >= PAGE_SIZE)
854  pg_end = PAGE_SIZE;
855  else
856  pg_end = end - ROUND_PAGE(off);
857  curr_page_it = seq_const_page_iterator<T>(arr->get_page(
858  off / PAGE_SIZE), off % PAGE_SIZE, pg_end);
859  return true;
860  }
861 
866  T curr() const {
868  // TODO I need to fix this.
869  BOOST_VERIFY(it->has_next());
870  return curr_page_it.curr();
871  }
872  };
873 
882 #define PAGE_FOREACH(type, v, it) \
883  for (int page_foreach_idx = 0; (it).has_next();) { \
884  for (int page_foreach_i = 0; page_foreach_i < (it).get_num_entries_in_page();\
885  page_foreach_i++, page_foreach_idx++) { \
886  type v = it.next();
887 
888 
889 #define PAGE_FOREACH_END }}
890 
891  template<class T>
892  class iterator: public std::iterator<std::random_access_iterator_tag, T>
893  {
894  const page_byte_array *arr;
895 
896  // The byte offset in the page array.
897  off_t off;
898  // The end byte offset in the page array.
899  off_t end;
900  public:
901  typedef typename std::iterator<std::random_access_iterator_tag,
902  T>::difference_type difference_type;
903 
904  iterator(page_byte_array *arr, off_t byte_off, off_t byte_end) {
905  this->arr = arr;
906  off = arr->get_offset_in_first_page() + byte_off;
907  end = arr->get_offset_in_first_page() + byte_end;
908  assert((size_t) byte_end <= arr->get_size());
909  // Either no elements cross the page boundary,
910  assert((PAGE_SIZE - (off % PAGE_SIZE)) % sizeof(T) == 0
911  // or the entire range is inside a page.
912  || end < PAGE_SIZE);
913  assert((byte_end - byte_off) % sizeof(T) == 0);
914 
915  // This iterator can change data, so I set all pages that can be
916  // accessed by the iterator dirty.
917  assert(0);
918 #if 0
919  off_t num_pages = ROUNDUP_PAGE(end) / PAGE_SIZE;
920  for (off_t i = off / PAGE_SIZE; i < num_pages; i++)
921  arr->get_page(i)->set_dirty(true);
922 #endif
923  }
924 
925  T &operator*() {
926  off_t pg_idx = off / PAGE_SIZE;
927  off_t off_in_pg = off % PAGE_SIZE;
928  const char *data = arr->get_page(pg_idx);
929  return *(T *) (data + off_in_pg);
930  }
931 
932  difference_type operator-(const iterator<T> &it) const {
933  return (off - it.off) / sizeof(T);
934  }
935 
936  // Prefix ++
937  iterator<T> &operator++() {
938  off += sizeof(T);
939  return *this;
940  }
941 
942  bool operator==(const iterator<T> &it) const {
943  return off == it.off;
944  }
945 
946  bool operator!=(const iterator<T> &it) const {
947  return !(*this == it);
948  }
949 
950  iterator<T> &operator+=(int num) {
951  assert(num >= 0);
952  off += num * sizeof(T);
953  assert(end >= off);
954  return *this;
955  }
956 
957  bool has_next() const {
958  return end - off >= sizeof(T);
959  }
960  };
961 
968  template<class T>
969  const_iterator<T> begin(off_t byte_off = 0) const {
970  return const_iterator<T>(this, byte_off, this->get_size());
971  }
972 
978  template<class T>
980  return const_iterator<T>(this, this->get_size(), this->get_size());
981  }
982 
991  template<class T>
992  std::pair<const_iterator<T>, const_iterator<T> > get_iterator(
993  off_t byte_off, off_t byte_end) const {
994  return std::pair<const_iterator<T>, const_iterator<T> >(
995  const_iterator<T>(this, byte_off, byte_end),
996  const_iterator<T>(this, byte_end, byte_end));
997  }
998 
1006  template<class T>
1007  seq_const_iterator<T> get_seq_iterator(off_t byte_off, off_t byte_end) const {
1008  return seq_const_iterator<T>(this, byte_off, byte_end);
1009  }
1010 
1011  template<class T>
1012  iterator<T> begin(off_t byte_off = 0) {
1013  return iterator<T>(this, byte_off, this->get_size());
1014  }
1015 
1016  template<class T>
1017  iterator<T> end() {
1018  return iterator<T>(this, this->get_size(), this->get_size());
1019  }
1020 
1021  template<class T>
1022  std::pair<iterator<T>, iterator<T> > get_iterator(
1023  off_t byte_off, off_t byte_end) const {
1024  return std::pair<iterator<T>, iterator<T> >(
1025  iterator<T>(this, byte_off, byte_end),
1026  iterator<T>(this, byte_end, byte_end));
1027  }
1028 
1029  template<class T>
1030  T get(off_t idx) const {
1031  T ele;
1032  memcpy(sizeof(T) * idx, (char *) &ele, sizeof(T));
1033  return ele;
1034  }
1035 
1036  template<class T>
1037  T get_off_in_bytes(off_t idx) const {
1038  T ele;
1039  memcpy(idx, (char *) &ele, sizeof(T));
1040  return ele;
1041  }
1042 
1049  void memcpy(off_t rel_off, char buf[], size_t size) const;
1050 
1051  static const page_byte_array &const_cast_ref(page_byte_array &arr) {
1052  return (const page_byte_array &) arr;
1053  }
1054 };
1055 
1056 /*
1057  * This class represents a region of an original array.
1058  */
1059 class sub_page_byte_array: public page_byte_array
1060 {
1061  page_byte_array &orig;
1062  off_t off;
1063 public:
1064  sub_page_byte_array(page_byte_array &arr, off_t off): orig(arr) {
1065  this->off = off;
1066  assert(arr.get_size() >= (size_t) off);
1067  }
1068 
1069  virtual void lock() {
1070  }
1071 
1076  virtual void unlock() {
1077  }
1078 
1079  virtual off_t get_offset() const {
1080  return off + orig.get_offset();
1081  }
1082 
1087  virtual size_t get_size() const {
1088  return orig.get_size() - off;
1089  }
1090 
1094  virtual page_byte_array *clone() {
1095  return NULL;
1096  }
1097 
1098  virtual off_t get_offset_in_first_page() const {
1099  return (off + orig.get_offset_in_first_page()) % PAGE_SIZE;
1100  }
1101 
1102  virtual const char *get_page(int idx) const {
1103  return orig.get_page((off
1104  + orig.get_offset_in_first_page()) / PAGE_SIZE + idx);
1105  }
1106 };
1107 
1108 }
1109 
1110 #endif
bool has_next()
Definition: cache.h:805
std::pair< const_iterator< T >, const_iterator< T > > get_iterator(off_t byte_off, off_t byte_end) const
Definition: cache.h:992
int get_num_tot_entries() const
Definition: cache.h:826
virtual page_byte_array * clone()=0
Definition: cache.h:550
const_iterator< T > begin(off_t byte_off=0) const
Definition: cache.h:969
void memcpy(off_t rel_off, char buf[], size_t size) const
T operator*() const
Definition: cache.h:639
T curr() const
Definition: cache.h:866
bool operator!=(const const_iterator< T > &it) const
Definition: cache.h:696
const_iterator< T > & operator++()
Definition: cache.h:675
const_iterator< T > end() const
Definition: cache.h:979
virtual off_t get_offset() const =0
const_iterator< T > & operator+=(size_t num)
Definition: cache.h:707
virtual size_t get_size() const =0
const_iterator< T > operator+(size_t num) const
Definition: cache.h:663
virtual void lock()=0
difference_type operator-(const const_iterator< T > &it) const
Definition: cache.h:652
seq_const_iterator< T > get_seq_iterator(off_t byte_off, off_t byte_end) const
Definition: cache.h:1007
bool operator==(const const_iterator< T > &it) const
Definition: cache.h:686
virtual void unlock()=0
int file_id_t
Definition: io_request.h:176
int get_num_entries_in_page() const
Definition: cache.h:835