From 8033d9604aedac4430797fcc414d8880f7eb967f Mon Sep 17 00:00:00 2001 From: bdemsky Date: Tue, 30 Jul 2019 18:23:10 -0700 Subject: [PATCH] Get code to compile --- cyclegraph.cc | 6 +- execution.cc | 116 +++++----- funcinst.cc | 18 +- funcnode.cc | 40 ++-- fuzzer.cc | 2 +- history.cc | 6 +- stl-model.h | 572 +++++++++++++++++++++++++------------------------- 7 files changed, 380 insertions(+), 380 deletions(-) diff --git a/cyclegraph.cc b/cyclegraph.cc index 3da8dc54..e56c9128 100644 --- a/cyclegraph.cc +++ b/cyclegraph.cc @@ -139,12 +139,12 @@ void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw) void CycleGraph::addEdges(SnapList * edgeset, const ModelAction *to) { for(sllnode * it = edgeset->begin();it!=NULL;) { - ModelAction *act = it->getVal(); + ModelAction *act = it->getVal(); CycleNode *node = getNode(act); sllnode * 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 *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()); } } diff --git a/execution.cc b/execution.cc index 5668fc36..cfb0b0bc 100644 --- a/execution.cc +++ b/execution.cc @@ -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 * 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 * 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 * 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* 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* 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 *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; isize(); + vec->resize(uninit_id + 1); + for(int i=oldsize;i *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; inext_thread_id; i++) - new (&vec[i]) action_list_t(); + uint oldsize =vec->size(); + vec->resize(priv->next_thread_id); + for(uint i=oldsize;inext_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 *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; inext_thread_id; i++) - new (&vec[i]) action_list_t(); + uint oldsize = vec->size(); + vec->resize(priv->next_thread_id); + for(uint i=oldsize;inext_thread_id;i++) + new (&vec[i]) action_list_t(); } (*vec)[tid].push_back(act); } } void insertIntoActionList(action_list_t *list, ModelAction *act) { - sllnode * rit = list->end(); + sllnode * 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 * rit = list->end(); + sllnode * 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 *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; inext_thread_id; i++) - new (&vec[i]) action_list_t(); + uint oldsize =vec->size(); + vec->resize(priv->next_thread_id); + for(uint i=oldsize;inext_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 *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; inext_thread_id; i++) - new (&vec[i]) action_list_t(); + uint oldsize =vec->size(); + vec->resize(priv->next_thread_id); + for(uint i=oldsize;inext_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* 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* 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 * ModelExecution::build_may_read_from(ModelAction *cu action_list_t *list = &(*thrd_lists)[i]; sllnode * 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 *it; + sllnode *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* 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]; diff --git a/funcinst.cc b/funcinst.cc index 21298839..8d9c23ba 100644 --- a/funcinst.cc +++ b/funcinst.cc @@ -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 * 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* 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* it; + for (it = collisions.begin();it != NULL;it=it->getNext()) { + FuncInst * inst = it->getVal(); if ( inst->get_type() == type ) return inst; } diff --git a/funcnode.cc b/funcnode.cc index c2a0ea9d..1c5d681c 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -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* 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* it = inst_list->begin(); + sllnode* 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::iterator it; - for (it = read_locations.begin();it != read_locations.end();it++) { - if (location == *it) { + mllnode * 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::iterator it; - for (it = read_locations.begin();it != read_locations.end();it++) { - if ( !read_map->contains(*it) ) + mllnode * 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); } } diff --git a/fuzzer.cc b/fuzzer.cc index fff0c1e2..679b0af4 100644 --- a/fuzzer.cc +++ b/fuzzer.cc @@ -20,7 +20,7 @@ Thread * Fuzzer::selectNotify(action_list_t * waiters) { int random_index = random() % numwaiters; sllnode * it = waiters->begin(); while(random_index--) - it=it->getNext(); + it=it->getNext(); Thread *thread = model->get_thread(it->getVal()); waiters->erase(it); return thread; diff --git a/history.cc b/history.cc index 3c000e7d..b1516913 100644 --- a/history.cc +++ b/history.cc @@ -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* 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()); } diff --git a/stl-model.h b/stl-model.h index 77040e2c..489939b7 100644 --- a/stl-model.h +++ b/stl-model.h @@ -8,306 +8,306 @@ typedef unsigned int uint; template 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 - 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 + friend class ModelList; }; template 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 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 - 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 + friend class SnapList; }; template 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; }; -- 2.34.1