Get code to compile
authorbdemsky <bdemsky@uci.edu>
Wed, 31 Jul 2019 01:23:10 +0000 (18:23 -0700)
committerbdemsky <bdemsky@uci.edu>
Wed, 31 Jul 2019 01:23:10 +0000 (18:23 -0700)
cyclegraph.cc
execution.cc
funcinst.cc
funcnode.cc
fuzzer.cc
history.cc
stl-model.h

index 3da8dc5..e56c912 100644 (file)
@@ -139,12 +139,12 @@ void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw)
 
 void CycleGraph::addEdges(SnapList<ModelAction *> * edgeset, const ModelAction *to) {
        for(sllnode<ModelAction*> * it = edgeset->begin();it!=NULL;) {
-         ModelAction *act = it->getVal();
+               ModelAction *act = it->getVal();
                CycleNode *node = getNode(act);
                sllnode<ModelAction*> * it2 = it;
                it2=it2->getNext();
                for(;it2!=NULL; ) {
-                 ModelAction *act2 = it2->getVal();
+                       ModelAction *act2 = it2->getVal();
                        CycleNode *node2 = getNode(act2);
                        if (checkReachable(node, node2)) {
                                it = edgeset->erase(it);
@@ -162,7 +162,7 @@ endouterloop:
                ;
        }
        for(sllnode<ModelAction*> *it = edgeset->begin();it!=NULL;it=it->getNext()) {
-         ModelAction *from = it->getVal();
+               ModelAction *from = it->getVal();
                addEdge(from, to, from->get_tid() == to->get_tid());
        }
 }
index 5668fc3..cfb0b0b 100644 (file)
@@ -391,7 +391,7 @@ bool ModelExecution::process_mutex(ModelAction *curr)
                action_list_t *waiters = get_safe_ptr_action(&condvar_waiters_map, curr->get_location());
                //activate all the waiting threads
                for (sllnode<ModelAction *> * rit = waiters->begin();rit != NULL;rit=rit->getNext()) {
-                 scheduler->wake(get_thread(rit->getVal()));
+                       scheduler->wake(get_thread(rit->getVal()));
                }
                waiters->clear();
                break;
@@ -443,7 +443,7 @@ bool ModelExecution::process_fence(ModelAction *curr)
                sllnode<ModelAction *> * rit;
                /* Find X : is_read(X) && X --sb-> curr */
                for (rit = list->end();rit != NULL;rit=rit->getPrev()) {
-                 ModelAction *act = rit->getVal();
+                       ModelAction *act = rit->getVal();
                        if (act == curr)
                                continue;
                        if (act->get_tid() != curr->get_tid())
@@ -806,7 +806,7 @@ bool ModelExecution::r_modification_order(ModelAction *curr, const ModelAction *
                action_list_t *list = &(*thrd_lists)[tid];
                sllnode<ModelAction *> * rit;
                for (rit = list->end();rit != NULL;rit=rit->getPrev()) {
-                 ModelAction *act = rit->getVal();
+                       ModelAction *act = rit->getVal();
 
                        /* Skip curr */
                        if (act == curr)
@@ -938,7 +938,7 @@ void ModelExecution::w_modification_order(ModelAction *curr)
                action_list_t *list = &(*thrd_lists)[i];
                sllnode<ModelAction*>* rit;
                for (rit = list->end();rit != NULL;rit=rit->getPrev()) {
-                 ModelAction *act = rit->getVal();
+                       ModelAction *act = rit->getVal();
                        if (act == curr) {
                                /*
                                 * 1) If RMW and it actually read from something, then we
@@ -1012,7 +1012,7 @@ bool ModelExecution::mo_may_allow(const ModelAction *writer, const ModelAction *
                action_list_t *list = &(*thrd_lists)[i];
                sllnode<ModelAction *>* rit;
                for (rit = list->end();rit != NULL;rit=rit->getPrev()) {
-                 ModelAction *act = rit->getVal();
+                       ModelAction *act = rit->getVal();
 
                        /* Don't disallow due to act == reader */
                        if (!reader->happens_before(act) || reader == act)
@@ -1102,10 +1102,10 @@ void ModelExecution::add_action_to_lists(ModelAction *act)
                list->push_front(uninit);
                SnapVector<action_list_t> *vec = get_safe_ptr_vect_action(&obj_wr_thrd_map, act->get_location());
                if (uninit_id >= (int)vec->size()) {
-                 int oldsize = (int) vec->size();
-                 vec->resize(uninit_id + 1);
-                 for(int i=oldsize; i<uninit_id+1; i++)
-                   new (&vec[i]) action_list_t(); 
+                       int oldsize = (int) vec->size();
+                       vec->resize(uninit_id + 1);
+                       for(int i=oldsize;i<uninit_id+1;i++)
+                               new (&vec[i]) action_list_t();
                }
                (*vec)[uninit_id].push_front(uninit);
        }
@@ -1119,10 +1119,10 @@ void ModelExecution::add_action_to_lists(ModelAction *act)
        // Update obj_thrd_map, a per location, per thread, order of actions
        SnapVector<action_list_t> *vec = get_safe_ptr_vect_action(&obj_thrd_map, act->get_location());
        if (tid >= (int)vec->size()) {
-         uint oldsize =vec->size();
-         vec->resize(priv->next_thread_id);
-         for(uint i=oldsize; i<priv->next_thread_id; i++)
-           new (&vec[i]) action_list_t(); 
+               uint oldsize =vec->size();
+               vec->resize(priv->next_thread_id);
+               for(uint i=oldsize;i<priv->next_thread_id;i++)
+                       new (&vec[i]) action_list_t();
        }
        (*vec)[tid].push_back(act);
        if (uninit)
@@ -1148,46 +1148,46 @@ void ModelExecution::add_action_to_lists(ModelAction *act)
 
                SnapVector<action_list_t> *vec = get_safe_ptr_vect_action(&obj_thrd_map, mutex_loc);
                if (tid >= (int)vec->size()) {
-                 uint oldsize = vec->size();
-                 vec->resize(priv->next_thread_id);
-                 for(uint i=oldsize; i<priv->next_thread_id; i++)
-                   new (&vec[i]) action_list_t(); 
+                       uint oldsize = vec->size();
+                       vec->resize(priv->next_thread_id);
+                       for(uint i=oldsize;i<priv->next_thread_id;i++)
+                               new (&vec[i]) action_list_t();
                }
                (*vec)[tid].push_back(act);
        }
 }
 
 void insertIntoActionList(action_list_t *list, ModelAction *act) {
-  sllnode<ModelAction*> * rit = list->end();
+       sllnode<ModelAction*> * rit = list->end();
        modelclock_t next_seq = act->get_seq_number();
        if (rit == NULL || (rit->getVal())->get_seq_number() == next_seq)
-         list->push_back(act);
+               list->push_back(act);
        else {
-         for(;rit != NULL;rit=rit->getPrev()) {
-           if ((rit->getVal())->get_seq_number() == next_seq) {
-             list->insertAfter(rit, act);
-             break;
-           }
-         }
+               for(;rit != NULL;rit=rit->getPrev()) {
+                       if ((rit->getVal())->get_seq_number() == next_seq) {
+                               list->insertAfter(rit, act);
+                               break;
+                       }
+               }
        }
 }
 
 void insertIntoActionListAndSetCV(action_list_t *list, ModelAction *act) {
-  sllnode<ModelAction*> * rit = list->end();
+       sllnode<ModelAction*> * rit = list->end();
        modelclock_t next_seq = act->get_seq_number();
        if (rit == NULL) {
                act->create_cv(NULL);
        } else if (rit->getVal()->get_seq_number() == next_seq) {
-         act->create_cv(rit->getVal());
-         list->push_back(act);
+               act->create_cv(rit->getVal());
+               list->push_back(act);
        } else {
-         for(;rit != NULL;rit=rit->getPrev()) {
-           if (rit->getVal()->get_seq_number() == next_seq) {
-             act->create_cv(rit->getVal());
-             list->insertAfter(rit, act);
-             break;
-           }
-         }
+               for(;rit != NULL;rit=rit->getPrev()) {
+                       if (rit->getVal()->get_seq_number() == next_seq) {
+                               act->create_cv(rit->getVal());
+                               list->insertAfter(rit, act);
+                               break;
+                       }
+               }
        }
 }
 
@@ -1210,10 +1210,10 @@ void ModelExecution::add_normal_write_to_lists(ModelAction *act)
        // Update obj_thrd_map, a per location, per thread, order of actions
        SnapVector<action_list_t> *vec = get_safe_ptr_vect_action(&obj_thrd_map, act->get_location());
        if (tid >= (int)vec->size()) {
-         uint oldsize =vec->size();
-         vec->resize(priv->next_thread_id);
-         for(uint i=oldsize; i<priv->next_thread_id; i++)
-           new (&vec[i]) action_list_t();
+               uint oldsize =vec->size();
+               vec->resize(priv->next_thread_id);
+               for(uint i=oldsize;i<priv->next_thread_id;i++)
+                       new (&vec[i]) action_list_t();
        }
        insertIntoActionList(&(*vec)[tid],act);
 
@@ -1227,10 +1227,10 @@ void ModelExecution::add_write_to_lists(ModelAction *write) {
        SnapVector<action_list_t> *vec = get_safe_ptr_vect_action(&obj_wr_thrd_map, write->get_location());
        int tid = id_to_int(write->get_tid());
        if (tid >= (int)vec->size()) {
-         uint oldsize =vec->size();
-         vec->resize(priv->next_thread_id);
-         for(uint i=oldsize; i<priv->next_thread_id; i++)
-           new (&vec[i]) action_list_t();
+               uint oldsize =vec->size();
+               vec->resize(priv->next_thread_id);
+               for(uint i=oldsize;i<priv->next_thread_id;i++)
+                       new (&vec[i]) action_list_t();
        }
        (*vec)[tid].push_back(write);
 }
@@ -1296,17 +1296,17 @@ ModelAction * ModelExecution::get_last_seq_cst_fence(thread_id_t tid, const Mode
        sllnode<ModelAction*>* rit = list->end();
 
        if (before_fence) {
-         for (;rit != NULL;rit=rit->getPrev())
-           if (rit->getVal() == before_fence)
-             break;
-         
-         ASSERT(rit->getVal() == before_fence);
-         rit=rit->getPrev();
+               for (;rit != NULL;rit=rit->getPrev())
+                       if (rit->getVal() == before_fence)
+                               break;
+
+               ASSERT(rit->getVal() == before_fence);
+               rit=rit->getPrev();
        }
 
        for (;rit != NULL;rit=rit->getPrev()) {
-         ModelAction *act = rit->getVal();
-         if (act->is_fence() && (tid == act->get_tid()) && act->is_seqcst())
+               ModelAction *act = rit->getVal();
+               if (act->is_fence() && (tid == act->get_tid()) && act->is_seqcst())
                        return act;
        }
        return NULL;
@@ -1328,8 +1328,8 @@ ModelAction * ModelExecution::get_last_unlock(ModelAction *curr) const
        /* Find: max({i in dom(S) | isUnlock(t_i) && samevar(t_i, t)}) */
        sllnode<ModelAction*>* rit;
        for (rit = list->end();rit != NULL;rit=rit->getPrev())
-         if (rit->getVal()->is_unlock() || rit->getVal()->is_wait())
-           return rit->getVal();
+               if (rit->getVal()->is_unlock() || rit->getVal()->is_wait())
+                       return rit->getVal();
        return NULL;
 }
 
@@ -1394,7 +1394,7 @@ SnapVector<ModelAction *> *  ModelExecution::build_may_read_from(ModelAction *cu
                action_list_t *list = &(*thrd_lists)[i];
                sllnode<ModelAction *> * rit;
                for (rit = list->end();rit != NULL;rit=rit->getPrev()) {
-                 ModelAction *act = rit->getVal();
+                       ModelAction *act = rit->getVal();
 
                        if (act == curr)
                                continue;
@@ -1459,7 +1459,7 @@ ModelAction * ModelExecution::get_uninitialized_action(ModelAction *curr) const
 
 static void print_list(action_list_t *list)
 {
-  sllnode<ModelAction*> *it;
+       sllnode<ModelAction*> *it;
 
        model_print("------------------------------------------------------------------------------------\n");
        model_print("#    t    Action type     MO       Location         Value               Rf  CV\n");
@@ -1468,7 +1468,7 @@ static void print_list(action_list_t *list)
        unsigned int hash = 0;
 
        for (it = list->begin();it != NULL;it=it->getNext()) {
-         const ModelAction *act = it->getVal();
+               const ModelAction *act = it->getVal();
                if (act->get_seq_number() > 0)
                        act->print();
                hash = hash^(hash<<3)^(it->getVal()->hash());
@@ -1488,7 +1488,7 @@ void ModelExecution::dumpGraph(char *filename)
        ModelAction **thread_array = (ModelAction **)model_calloc(1, sizeof(ModelAction *) * get_num_threads());
 
        for (sllnode<ModelAction*>* it = action_trace.begin();it != NULL;it=it->getNext()) {
-         ModelAction *act = it->getVal();
+               ModelAction *act = it->getVal();
                if (act->is_read()) {
                        mo_graph->dot_print_node(file, act);
                        mo_graph->dot_print_edge(file,
@@ -1512,7 +1512,7 @@ void ModelExecution::dumpGraph(char *filename)
 #endif
 
 /** @brief Prints an execution trace summary. */
-void ModelExecution::print_summary() 
+void ModelExecution::print_summary()
 {
 #if SUPPORT_MOD_ORDER_DUMP
        char buffername[100];
index 2129883..8d9c23b 100644 (file)
@@ -19,9 +19,9 @@ FuncInst::FuncInst(ModelAction *act, FuncNode *func_node) :
  */
 bool FuncInst::add_pred(FuncInst * other)
 {
-       func_inst_list_mt::iterator it;
-       for (it = predecessors.begin();it != predecessors.end();it++) {
-               FuncInst * inst = *it;
+       mllnode<FuncInst*> * it;
+       for (it = predecessors.begin();it != NULL;it=it->getNext()) {
+               FuncInst * inst = it->getVal();
                if (inst == other)
                        return false;
        }
@@ -32,9 +32,9 @@ bool FuncInst::add_pred(FuncInst * other)
 
 bool FuncInst::add_succ(FuncInst * other)
 {
-       func_inst_list_mt::iterator it;
-       for (it = successors.begin();it != successors.end();it++) {
-               FuncInst * inst = *it;
+       mllnode<FuncInst*>* it;
+       for (it = successors.begin();it != NULL;it=it->getNext()) {
+               FuncInst * inst = it->getVal();
                if ( inst == other )
                        return false;
        }
@@ -47,9 +47,9 @@ FuncInst * FuncInst::search_in_collision(ModelAction *act)
 {
        action_type type = act->get_type();
 
-       func_inst_list_mt::iterator it;
-       for (it = collisions.begin();it != collisions.end();it++) {
-               FuncInst * inst = *it;
+       mllnode<FuncInst*>* it;
+       for (it = collisions.begin();it != NULL;it=it->getNext()) {
+               FuncInst * inst = it->getVal();
                if ( inst->get_type() == type )
                        return inst;
        }
index c2a0ea9..1c5d681 100644 (file)
@@ -62,9 +62,9 @@ void FuncNode::add_entry_inst(FuncInst * inst)
        if (inst == NULL)
                return;
 
-       func_inst_list_mt::iterator it;
-       for (it = entry_insts.begin();it != entry_insts.end();it++) {
-               if (inst == *it)
+       mllnode<FuncInst*>* it;
+       for (it = entry_insts.begin();it != NULL;it=it->getNext()) {
+               if (inst == it->getVal())
                        return;
        }
 
@@ -79,28 +79,28 @@ void FuncNode::link_insts(func_inst_list_t * inst_list)
        if (inst_list == NULL)
                return;
 
-       func_inst_list_t::iterator it = inst_list->begin();
-       func_inst_list_t::iterator prev;
+       sllnode<FuncInst *>* it = inst_list->begin();
+       sllnode<FuncInst *>* prev;
 
        if (inst_list->size() == 0)
                return;
 
        /* add the first instruction to the list of entry insts */
-       FuncInst * entry_inst = *it;
+       FuncInst * entry_inst = it->getVal();
        add_entry_inst(entry_inst);
 
-       it++;
-       while (it != inst_list->end()) {
+       it=it->getNext();
+       while (it != NULL) {
                prev = it;
-               prev--;
+               prev = it->getPrev();
 
-               FuncInst * prev_inst = *prev;
-               FuncInst * curr_inst = *it;
+               FuncInst * prev_inst = prev->getVal();
+               FuncInst * curr_inst = it->getVal();
 
                prev_inst->add_succ(curr_inst);
                curr_inst->add_pred(prev_inst);
 
-               it++;
+               it=it->getNext();
        }
 }
 
@@ -126,9 +126,9 @@ void FuncNode::store_read(ModelAction * act, uint32_t tid)
 
        /* Store the memory locations where atomic reads happen */
        bool push_loc = true;
-       ModelList<void *>::iterator it;
-       for (it = read_locations.begin();it != read_locations.end();it++) {
-               if (location == *it) {
+       mllnode<void *> * it;
+       for (it = read_locations.begin();it != NULL;it=it->getNext()) {
+               if (location == it->getVal()) {
                        push_loc = false;
                        break;
                }
@@ -178,12 +178,12 @@ void FuncNode::print_last_read(uint32_t tid)
        ASSERT(thrd_read_map.size() > tid);
        read_map_t * read_map = thrd_read_map[tid];
 
-       ModelList<void *>::iterator it;
-       for (it = read_locations.begin();it != read_locations.end();it++) {
-               if ( !read_map->contains(*it) )
+       mllnode<void *> * it;
+       for (it = read_locations.begin();it != NULL;it=it->getNext()) {
+               if ( !read_map->contains(it->getVal()) )
                        break;
 
-               uint64_t read_val = read_map->get(*it);
-               model_print("last read of thread %d at %p: 0x%x\n", tid, *it, read_val);
+               uint64_t read_val = read_map->get(it->getVal());
+               model_print("last read of thread %d at %p: 0x%x\n", tid, it->getVal(), read_val);
        }
 }
index fff0c1e..679b0af 100644 (file)
--- a/fuzzer.cc
+++ b/fuzzer.cc
@@ -20,7 +20,7 @@ Thread * Fuzzer::selectNotify(action_list_t * waiters) {
        int random_index = random() % numwaiters;
        sllnode<ModelAction*> * it = waiters->begin();
        while(random_index--)
-         it=it->getNext();
+               it=it->getNext();
        Thread *thread = model->get_thread(it->getVal());
        waiters->erase(it);
        return thread;
index 3c000e7..b151691 100644 (file)
@@ -171,9 +171,9 @@ void ModelHistory::print()
                func_inst_list_mt * entry_insts = func_node->get_entry_insts();
                model_print("function %s has entry actions\n", func_node->get_func_name());
 
-               func_inst_list_mt::iterator it;
-               for (it = entry_insts->begin();it != entry_insts->end();it++) {
-                       FuncInst *inst = *it;
+               mllnode<FuncInst*>* it;
+               for (it = entry_insts->begin();it != NULL;it=it->getNext()) {
+                       FuncInst *inst = it->getVal();
                        model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position());
                }
 
index 77040e2..489939b 100644 (file)
@@ -8,306 +8,306 @@ typedef unsigned int uint;
 
 template<typename _Tp>
 class mllnode {
- public:
-  _Tp getVal() {return val;}
-  mllnode<_Tp> * getNext() {return next;}
-  mllnode<_Tp> * getPrev() {return prev;}
-
-  MEMALLOC;
-  
- private:
-  mllnode<_Tp> * next;
-  mllnode<_Tp> * prev;
-  _Tp val;
-  template<typename T>
-  friend class ModelList;
+public:
+       _Tp getVal() {return val;}
+       mllnode<_Tp> * getNext() {return next;}
+       mllnode<_Tp> * getPrev() {return prev;}
+
+       MEMALLOC;
+
+private:
+       mllnode<_Tp> * next;
+       mllnode<_Tp> * prev;
+       _Tp val;
+       template<typename T>
+       friend class ModelList;
 };
 
 template<typename _Tp>
 class ModelList
 {
-public:  
- ModelList() : head(NULL),
-    tail(NULL), _size(0) {
-  }
-
-  void push_front(_Tp val) {
-    mllnode<_Tp> * tmp = new mllnode<_Tp>();
-    tmp->prev = NULL;
-    tmp->next = head;
-    tmp->val = val;
-    if (head == NULL)
-      tail = tmp;
-    else
-      head->prev = tmp;
-    head = tmp;
-    _size++;
-  }
-
-  void push_back(_Tp val) {
-    mllnode<_Tp> * tmp = new mllnode<_Tp>();
-    tmp->prev = tail;
-    tmp->next = NULL;
-    tmp->val = val;
-    if (tail == NULL)
-      head = tmp;
-    else tail->next = tmp;
-    tail = tmp;
-    _size++;
-  }
-
-  void pop_front() {
-    mllnode<_Tp> *tmp = head;
-    head = head->next;
-    head->prev = NULL;
-    delete tmp;
-    _size--;
-  }
-
-  void pop_back() {
-    mllnode<_Tp> *tmp = tail;
-    tail = tail->next;
-    tail->next = NULL;
-    delete tmp;
-    _size--;
-  }
-
-  void clear() {
-    while(head != NULL) {
-      mllnode<_Tp> *tmp=head->next;
-      delete head;
-      head = tmp;
-    }
-    tail=NULL;
-    _size=0;
-  }
-  
-  void insertAfter(mllnode<_Tp> * node, _Tp val) {
-    mllnode<_Tp> *tmp = new mllnode<_Tp>();
-    tmp->val = val;
-    tmp->prev = node;
-    tmp->next = node->next;
-    node->next = tmp;
-    if (tmp->next == NULL) {
-      tail = tmp;
-    } else {
-      tmp->next->prev = tmp;
-    }
-    _size++;
-  }
-
-  void insertBefore(mllnode<_Tp> * node, _Tp val) {
-    mllnode<_Tp> *tmp = new mllnode<_Tp>();
-    tmp->val = val;
-    tmp->next = node;
-    tmp->prev = node->prev;
-    node->prev = tmp;
-    if (tmp->prev == NULL) {
-      head = tmp;
-    } else {
-      tmp->prev->next = tmp;
-    }
-    _size++;
-  }
-  
-  mllnode<_Tp> * erase(mllnode<_Tp> * node) {
-    if (head == node) {
-      head = node->next;
-    } else {
-      node->prev->next = node->next;
-    }
-
-    if (tail == node) {
-      tail = node->prev;
-    } else {
-      tail->next->prev = node->prev;
-    }
-    mllnode<_Tp> *next = node->next;
-    delete node;
-    _size--;
-    return next;
-  }
-  
-  mllnode<_Tp> * begin() {
-    return head;
-  }
-
-  mllnode<_Tp> * end() {
-    return tail;
-  }
-  
-  _Tp front() {
-    return head->val;
-  }
-
-  _Tp back() {
-    return tail->val;
-  }
-
-  uint size() {
-    return _size;
-  }
-
-  bool empty() {
-    return _size == 0;
-  }
-  
-  MEMALLOC;
- private:
-  mllnode<_Tp> *head;
-  mllnode<_Tp> *tail;
-  uint _size;
+public:
      ModelList() : head(NULL),
+               tail(NULL), _size(0) {
+       }
+
+       void push_front(_Tp val) {
+               mllnode<_Tp> * tmp = new mllnode<_Tp>();
+               tmp->prev = NULL;
+               tmp->next = head;
+               tmp->val = val;
+               if (head == NULL)
+                       tail = tmp;
+               else
+                       head->prev = tmp;
+               head = tmp;
+               _size++;
+       }
+
+       void push_back(_Tp val) {
+               mllnode<_Tp> * tmp = new mllnode<_Tp>();
+               tmp->prev = tail;
+               tmp->next = NULL;
+               tmp->val = val;
+               if (tail == NULL)
+                       head = tmp;
+               else tail->next = tmp;
+               tail = tmp;
+               _size++;
+       }
+
+       void pop_front() {
+               mllnode<_Tp> *tmp = head;
+               head = head->next;
+               head->prev = NULL;
+               delete tmp;
+               _size--;
+       }
+
+       void pop_back() {
+               mllnode<_Tp> *tmp = tail;
+               tail = tail->next;
+               tail->next = NULL;
+               delete tmp;
+               _size--;
+       }
+
+       void clear() {
+               while(head != NULL) {
+                       mllnode<_Tp> *tmp=head->next;
+                       delete head;
+                       head = tmp;
+               }
+               tail=NULL;
+               _size=0;
+       }
+
+       void insertAfter(mllnode<_Tp> * node, _Tp val) {
+               mllnode<_Tp> *tmp = new mllnode<_Tp>();
+               tmp->val = val;
+               tmp->prev = node;
+               tmp->next = node->next;
+               node->next = tmp;
+               if (tmp->next == NULL) {
+                       tail = tmp;
+               } else {
+                       tmp->next->prev = tmp;
+               }
+               _size++;
+       }
+
+       void insertBefore(mllnode<_Tp> * node, _Tp val) {
+               mllnode<_Tp> *tmp = new mllnode<_Tp>();
+               tmp->val = val;
+               tmp->next = node;
+               tmp->prev = node->prev;
+               node->prev = tmp;
+               if (tmp->prev == NULL) {
+                       head = tmp;
+               } else {
+                       tmp->prev->next = tmp;
+               }
+               _size++;
+       }
+
+       mllnode<_Tp> * erase(mllnode<_Tp> * node) {
+               if (head == node) {
+                       head = node->next;
+               } else {
+                       node->prev->next = node->next;
+               }
+
+               if (tail == node) {
+                       tail = node->prev;
+               } else {
+                       tail->next->prev = node->prev;
+               }
+               mllnode<_Tp> *next = node->next;
+               delete node;
+               _size--;
+               return next;
+       }
+
+       mllnode<_Tp> * begin() {
+               return head;
+       }
+
+       mllnode<_Tp> * end() {
+               return tail;
+       }
+
+       _Tp front() {
+               return head->val;
+       }
+
+       _Tp back() {
+               return tail->val;
+       }
+
+       uint size() {
+               return _size;
+       }
+
+       bool empty() {
+               return _size == 0;
+       }
+
+       MEMALLOC;
+private:
+       mllnode<_Tp> *head;
+       mllnode<_Tp> *tail;
+       uint _size;
 };
 
 template<typename _Tp>
 class sllnode {
- public:
-  _Tp getVal() {return val;}
-  sllnode<_Tp> * getNext() {return next;}
-  sllnode<_Tp> * getPrev() {return prev;}
-  SNAPSHOTALLOC;
-  
- private:
-  sllnode<_Tp> * next;
-  sllnode<_Tp> * prev;
-  _Tp val;
-  template<typename T>
-  friend class SnapList;
+public:
+       _Tp getVal() {return val;}
+       sllnode<_Tp> * getNext() {return next;}
+       sllnode<_Tp> * getPrev() {return prev;}
+       SNAPSHOTALLOC;
+
+private:
+       sllnode<_Tp> * next;
+       sllnode<_Tp> * prev;
+       _Tp val;
+       template<typename T>
+       friend class SnapList;
 };
 
 template<typename _Tp>
 class SnapList
 {
-public:  
- SnapList() : head(NULL),
-    tail(NULL), _size(0) {
-  }
-
-  void push_front(_Tp val) {
-    sllnode<_Tp> * tmp = new sllnode<_Tp>();
-    tmp->prev = NULL;
-    tmp->next = head;
-    tmp->val = val;
-    if (head == NULL)
-      tail = tmp;
-    else
-      head->prev = tmp;
-    head = tmp;
-    _size++;
-  }
-
-  void push_back(_Tp val) {
-    sllnode<_Tp> * tmp = new sllnode<_Tp>();
-    tmp->prev = tail;
-    tmp->next = NULL;
-    tmp->val = val;
-    if (tail == NULL)
-      head = tmp;
-    else tail->next = tmp;
-    tail = tmp;
-    _size++;
-  }
-  
-  void pop_front() {
-    sllnode<_Tp> *tmp = head;
-    head = head->next;
-    head->prev = NULL;
-    delete tmp;
-    _size--;
-  }
-
-  void pop_back() {
-    sllnode<_Tp> *tmp = tail;
-    tail = tail->next;
-    tail->next = NULL;
-    delete tmp;
-    _size--;
-  }
-
-  void clear() {
-    while(head != NULL) {
-      sllnode<_Tp> *tmp=head->next;
-      delete head;
-      head = tmp;
-    }
-    tail=NULL;
-    _size=0;
-  }
-  
-  void insertAfter(sllnode<_Tp> * node, _Tp val) {
-    sllnode<_Tp> *tmp = new sllnode<_Tp>();
-    tmp->val = val;
-    tmp->prev = node;
-    tmp->next = node->next;
-    node->next = tmp;
-    if (tmp->next == NULL) {
-      tail = tmp;
-    } else {
-      tmp->next->prev = tmp;
-    }
-    _size++;
-  }
-
-  void insertBefore(sllnode<_Tp> * node, _Tp val) {
-    sllnode<_Tp> *tmp = new sllnode<_Tp>();
-    tmp->val = val;
-    tmp->next = node;
-    tmp->prev = node->prev;
-    node->prev = tmp;
-    if (tmp->prev == NULL) {
-      head = tmp;
-    } else {
-      tmp->prev->next = tmp;
-    }
-    _size++;
-  }
-  
-  sllnode<_Tp> * erase(sllnode<_Tp> * node) {
-    if (head == node) {
-      head = node->next;
-    } else {
-      node->prev->next = node->next;
-    }
-
-    if (tail == node) {
-      tail = node->prev;
-    } else {
-      tail->next->prev = node->prev;
-    }
-
-    sllnode<_Tp> *next = node->next;
-    delete node;
-    _size--;
-    return next;
-  }
-  
-  sllnode<_Tp> * begin() {
-    return head;
-  }
-
-  sllnode<_Tp> * end() {
-    return tail;
-  }
-  
-  _Tp front() {
-    return head->val;
-  }
-
-  _Tp back() {
-    return tail->val;
-  }
-  uint size() {
-    return _size;
-  }
-  bool empty() {
-    return _size == 0;
-  }
-  
-  SNAPSHOTALLOC;
- private:
-  sllnode<_Tp> *head;
-  sllnode<_Tp> *tail;
-  uint _size;
+public:
      SnapList() : head(NULL),
+               tail(NULL), _size(0) {
+       }
+
+       void push_front(_Tp val) {
+               sllnode<_Tp> * tmp = new sllnode<_Tp>();
+               tmp->prev = NULL;
+               tmp->next = head;
+               tmp->val = val;
+               if (head == NULL)
+                       tail = tmp;
+               else
+                       head->prev = tmp;
+               head = tmp;
+               _size++;
+       }
+
+       void push_back(_Tp val) {
+               sllnode<_Tp> * tmp = new sllnode<_Tp>();
+               tmp->prev = tail;
+               tmp->next = NULL;
+               tmp->val = val;
+               if (tail == NULL)
+                       head = tmp;
+               else tail->next = tmp;
+               tail = tmp;
+               _size++;
+       }
+
+       void pop_front() {
+               sllnode<_Tp> *tmp = head;
+               head = head->next;
+               head->prev = NULL;
+               delete tmp;
+               _size--;
+       }
+
+       void pop_back() {
+               sllnode<_Tp> *tmp = tail;
+               tail = tail->next;
+               tail->next = NULL;
+               delete tmp;
+               _size--;
+       }
+
+       void clear() {
+               while(head != NULL) {
+                       sllnode<_Tp> *tmp=head->next;
+                       delete head;
+                       head = tmp;
+               }
+               tail=NULL;
+               _size=0;
+       }
+
+       void insertAfter(sllnode<_Tp> * node, _Tp val) {
+               sllnode<_Tp> *tmp = new sllnode<_Tp>();
+               tmp->val = val;
+               tmp->prev = node;
+               tmp->next = node->next;
+               node->next = tmp;
+               if (tmp->next == NULL) {
+                       tail = tmp;
+               } else {
+                       tmp->next->prev = tmp;
+               }
+               _size++;
+       }
+
+       void insertBefore(sllnode<_Tp> * node, _Tp val) {
+               sllnode<_Tp> *tmp = new sllnode<_Tp>();
+               tmp->val = val;
+               tmp->next = node;
+               tmp->prev = node->prev;
+               node->prev = tmp;
+               if (tmp->prev == NULL) {
+                       head = tmp;
+               } else {
+                       tmp->prev->next = tmp;
+               }
+               _size++;
+       }
+
+       sllnode<_Tp> * erase(sllnode<_Tp> * node) {
+               if (head == node) {
+                       head = node->next;
+               } else {
+                       node->prev->next = node->next;
+               }
+
+               if (tail == node) {
+                       tail = node->prev;
+               } else {
+                       tail->next->prev = node->prev;
+               }
+
+               sllnode<_Tp> *next = node->next;
+               delete node;
+               _size--;
+               return next;
+       }
+
+       sllnode<_Tp> * begin() {
+               return head;
+       }
+
+       sllnode<_Tp> * end() {
+               return tail;
+       }
+
+       _Tp front() {
+               return head->val;
+       }
+
+       _Tp back() {
+               return tail->val;
+       }
+       uint size() {
+               return _size;
+       }
+       bool empty() {
+               return _size == 0;
+       }
+
+       SNAPSHOTALLOC;
+private:
+       sllnode<_Tp> *head;
+       sllnode<_Tp> *tail;
+       uint _size;
 };