X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/f4c34c38f2c62087bbf7e0d6e618660f0e48023e..98e331147474997778f92d14b794a94f1dc3bedb:/src/btree.cpp?ds=inline diff --git a/src/btree.cpp b/src/btree.cpp index fc8c604..ddcb14c 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -1,9 +1,10 @@ #include "btree.h" -BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool create_new_file) +BTree::BTree (const std::string &name, unsigned int block_size, int tt, int kt, bool create_new_file) { key_type = kt; + tree_type = tt; uchar *node; BTreeNodeHeader nh; @@ -53,7 +54,13 @@ void BTree::WriteBlock (uchar *block, uint num) void BTree::AddKey (const Clave &k) { uint left, right; - Clave *kout = AddKeyR (k.Clone (), 0, left, right); + Clave *kout; + + try { + kout = AddKeyR (k.Clone (), 0, left, right); + } catch (Exception *e) { + throw e; + } if (kout) { unsigned short level; @@ -102,10 +109,19 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri ReadNodoHeader (node, &node_header); delete [] node; - if (node_header.level == 0) - return AddKeyLeafR (k, node_num, left_child, right_child); + if (node_header.level == 0) { + try { + return AddKeyLeafR (k, node_num, left_child, right_child); + } catch (Exception *e) { + throw e; + } + } - return AddKeyOtherR (k, node_num, left_child, right_child); + try { + return AddKeyOtherR (k, node_num, left_child, right_child); + } catch (Exception *e) { + throw e; + } } Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child) @@ -127,6 +143,14 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint while (it != node_keys.end ()) { datait = (*it); + if (tree_type == TYPE_UNIQUE) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } + if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -160,6 +184,13 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint while (it != node_keys.end ()) { BTreeData *datait; datait = (*it); + if (tree_type == TYPE_UNIQUE) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -199,7 +230,7 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint used += d->Size (); it++; } - kout = (*it++)->getClave (); // Esta se retorna al "padre" para que se la agregue + kout = (*it++)->GetKey (); // Esta se retorna al "padre" para que se la agregue while (it != node_keys.end ()) { BTreeData *d = (*it); @@ -253,6 +284,13 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin posterior = it; while (it != node_keys.end ()) { + if (tree_type == TYPE_UNIQUE) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*(*it))) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*(*it))) break; ultima = it; @@ -260,9 +298,9 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin } if (it == posterior) { - k = AddKeyR (k, lchild->getChild (), left_child, right_child); + k = AddKeyR (k, lchild->GetChild (), left_child, right_child); } else { - k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child); + k = AddKeyR (k, (*ultima)->GetChild (), left_child, right_child); } DeleteKeys (node_keys); @@ -282,6 +320,13 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin while (it != node_keys.end ()) { datait = (*it); + if (tree_type == TYPE_UNIQUE) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -317,6 +362,13 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin while (it != node_keys.end ()) { BTreeData *datait; datait = (*it); + if (tree_type == TYPE_UNIQUE) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -356,9 +408,9 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin used += d->Size (); it++; } - kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue + kout = (*it)->GetKey (); // Esta se retorna al "padre" para que se la agregue - new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ())); + new_node_keys.push_back ( new BTreeChildData ((*it)->GetChild ())); it++; while (it != node_keys.end ()) { BTreeData *d = (*it); @@ -391,7 +443,11 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin void BTree::DelKey (const Clave &k) { - DelKeyR (new BTreeLeafData (k.Clone ()), 0, 0); + std::string s = k; + std::cout << "========= Borrando " << s << " =================\n"; + BTreeData *b = new BTreeLeafData (k.Clone ()); + DelKeyR (b, 0, 0); + delete b; } void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) @@ -418,8 +474,21 @@ void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) if ((*k) == (*(*it))) { /* La encontre!, retorno */ if (node_header.level == 0) { - DelKeyFromLeaf (k->getClave (), node_num, padre); + DelKeyFromLeaf (k->GetKey (), node_num, padre); + } else { + uint left, right; + if (it == posterior) { + left = lchild->GetChild (); + right = (*it)->GetChild (); + } else { + left = (*ultima)->GetChild (); + right = (*it)->GetChild (); + } + std::cout << "Eliminar de Nodo con hijos : " << left << " y " << right << std::endl; + DelKeyFromNode (k->GetKey (), node_num, padre, left, right); } + DeleteKeys (node_keys); + delete [] node; return; } @@ -433,15 +502,15 @@ void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) * decir que no lo encontre */ if (node_header.level == 0) { - std::cout << "Clave no encontrada\n"; + std::cout << "*** Clave no encontrada ***\n"; return; } /* TODO: Aca faltaria liberar memoria */ if (it == posterior) { - DelKeyR (k, lchild->getChild (), node_num); + DelKeyR (k, lchild->GetChild (), node_num); } else { - DelKeyR (k, (*ultima)->getChild (), node_num); + DelKeyR (k, (*ultima)->GetChild (), node_num); } } @@ -456,13 +525,15 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) ReadNodoHeader (node, &node_header); node_keys = ReadKeys (node, node_header); - data = new BTreeLeafData (k); + data = new BTreeLeafData (k->Clone ()); std::list::iterator it; it = node_keys.begin (); while (it != node_keys.end ()) { if ((*data) == (*(*it))) { + BTreeData *aborrar = (*it); node_keys.erase (it); + delete aborrar; break; } it++; @@ -470,33 +541,53 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) delete data; - /* TODO : que pasa cuando el nodo se queda vacio o con - * muy pocas claveS?? - */ WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); WriteBlock (node, node_num); /* Veo si se cumple la condición de minimalidad */ - if ((node_header.free_space <= (header.block_size/2)) && (node_num != 0)) { + uint min_free = (header.block_size-sizeof(BTreeNodeHeader))/2; + if ((node_header.free_space > min_free) && (node_num != 0)) { /* Oops! Debo pedir prestada clave */ uint hi, hd; Clave *pedida; - FindB (node_num, padre, hi, hd); + FindBrothers (node_num, padre, hi, hd); if ((pedida = GetKey (hi, 1)) != NULL) { std::string s = *pedida; std::cout << "Clave Pedida : " << s << std::endl; + pedida = ReplaceKeyInFather (node_num, padre, pedida); + node_keys.insert (node_keys.begin (), new BTreeLeafData (pedida)); } else if ((pedida = GetKey (hd, 0)) != NULL) { std::string s = *pedida; std::cout << "Clave Pedida : " << s << std::endl; + pedida = ReplaceKeyInFather (node_num, padre, pedida); + node_keys.push_back (new BTreeLeafData (pedida)); } else { std::cout << "NADIE ME PUEDE PRESTAR, FUNDIR NODOS\n"; + uint join1, join2; + int tipoh; + if (hi != 0) { + std::cout << "Join con Hermano Izquierdo\n"; + join1 = hi; + join2 = node_num; + tipoh = 0; + } else { + std::cout << "Join con Hermano Derecho\n"; + join1 = node_num; + join2 = hd; + tipoh = 1; + } + + JoinNodes (join1, join2, padre, tipoh); + + DeleteKeys (node_keys); + delete [] node; return; } @@ -509,10 +600,157 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) delete [] node; std::cout << "Borrado de una hoja listo\n"; } + +void BTree::JoinNodes (uint node1, uint node2, uint padre, int tipohermano) +{ + uchar *n1, *n2, *npadre; + BTreeNodeHeader nh1, nh2, nhp; + std::list nk1, nk2, nkpadre; + + if (node1 == node2) { + std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n"; + exit (1); + } + if (node1 == padre) { + std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n"; + exit (1); + } + if (node2 == padre) { + std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n"; + exit (1); + } + + PrintNode (padre); + PrintNode (node1); + PrintNode (node2); + + /* Leo los nodos */ + n1 = ReadBlock (node1); + n2 = ReadBlock (node2); + npadre = ReadBlock (padre); + + ReadNodoHeader (n1, &nh1); + ReadNodoHeader (n2, &nh2); + ReadNodoHeader (npadre, &nhp); + + /* Apunto de Unir */ + uint tmp = header.block_size - sizeof (BTreeNodeHeader); + uint l = tmp - nh1.free_space; + l += tmp - nh1.free_space; + l += 4; + + std::cout << "Espacio ocupado despues de unir : " << l << " de " << tmp << std::endl; + + nk1 = ReadKeys (n1, nh1); + nk2 = ReadKeys (n2, nh2); + nkpadre = ReadKeys (npadre, nhp); + + /* Busco la clave del padre a juntar con los nodos */ + std::list::iterator it = nkpadre.begin (); + std::list::iterator borrar_padre; + std::list::iterator sig; + std::list::iterator anterior = it; + + Clave *cpadre; + BTreeData *lchild = (*it++); + + if (lchild->GetChild () == node1) { + cpadre = (*it)->GetKey (); + borrar_padre = it; + } else { + while (it != nkpadre.end ()) { + if (tipohermano == 0) { + if ((*it)->GetChild () == node2) + break; + } else { + if ((*it)->GetChild () == node1) + break; + } + anterior = it; + it++; + } + cpadre = (*it)->GetKey (); + borrar_padre = it; + } + if (it == nkpadre.end ()) { + std::cout << "PANIC : Me pase sin encontrar la clave!!\n"; + exit(1); + } + it++; + sig = it; + + std::list newkeys; + std::list::iterator i; + + i = nk1.begin (); + while (i != nk1.end ()) { + newkeys.push_back ( new BTreeLeafData ((*i)->GetKey ()->Clone ())); + i++; + } + //if (tipohermano == 0) + newkeys.push_back ( new BTreeLeafData (cpadre->Clone ())); + i = nk2.begin (); + while (i != nk2.end ()) { + newkeys.push_back ( new BTreeLeafData ((*i)->GetKey ()->Clone ())); + i++; + } + + std::cout << "Espacio ocupado por las nuevas claves : " << (newkeys.size()*4) << std::endl; + if ((newkeys.size()*4) > tmp) { + std::cout << "PANIC : El nodo fundido no entra !!!\n"; + exit (1); + } + + /* Para el padre, tener 2 items significa tener solo 1 clave, ya que + * el otro item es el LeftChild! + */ + if ((padre == 0) && (nhp.item_count == 2)) { + /* Si junte 2 nodos, cuyo padre era la raiz, y esta tenia + * solo una clave, quiere decir que lo que me queda + * es de nuevo solo una raiz con todas las claves + */ + nhp.level = 0; + WriteKeys (npadre, nhp, newkeys); + WriteNodoHeader (npadre, &nhp); + WriteBlock (npadre, padre); + + /* TODO: Recuperar nodo1 y nodo2 */ + } else { + WriteKeys (n1, nh1, newkeys); + WriteNodoHeader (n1, &nh1); + WriteBlock (n1, node1); + + /* TODO : Recuperar node2 */ + /* Actualizo punero al padre */ + (*anterior)->SetChild (node1); + nkpadre.erase (borrar_padre); + WriteKeys (npadre, nhp, nkpadre); + WriteNodoHeader (npadre, &nhp); + WriteBlock (npadre, padre); + } + + std::cout << " ----- Luego de Fundir -----\n"; + PrintNode (node1); + PrintNode (padre); + std::cout << " ---------------------------\n"; + + DeleteKeys (nk1); + DeleteKeys (nk2); + DeleteKeys (nkpadre); + DeleteKeys (newkeys); + + delete [] n1; + delete [] n2; + delete [] npadre; +} + Clave *BTree::GetKey (uint node_num, char maxmin) { - if (node_num == 0) return NULL; + if (node_num == 0) { + std::cout << "Nodo no me puede prestar ... es NULL\n"; + return NULL; + } uchar *node; BTreeNodeHeader node_header; @@ -527,13 +765,28 @@ Clave *BTree::GetKey (uint node_num, char maxmin) if (node_header.level != 0) it++; Clave *k; + uint free = node_header.free_space; // + (*it)->Size (); + uint min_free = (header.block_size - sizeof (BTreeNodeHeader))/2; + if (free > min_free) { + std::cout << "No puedo prestar : Free = " << free << " Minimo = " << min_free << std::endl; + PrintNode (node_num); + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + DeleteKeys (node_keys); + + delete [] node; + + return NULL; + } + if (maxmin == 0) { - k = (*it)->getClave ()->Clone (); + k = (*it)->GetKey ()->Clone (); node_keys.erase (it); } else { it = node_keys.end (); it--; - k = (*it)->getClave ()->Clone (); + k = (*it)->GetKey ()->Clone (); node_keys.erase (it); } @@ -542,10 +795,12 @@ Clave *BTree::GetKey (uint node_num, char maxmin) WriteBlock (node, node_num); DeleteKeys (node_keys); + delete [] node; + return k; } -void BTree::FindB (uint node_num, uint padre, uint &left, uint &right) +void BTree::FindBrothers (uint node_num, uint padre, uint &left, uint &right) { uchar *node; BTreeNodeHeader node_header; @@ -561,36 +816,179 @@ void BTree::FindB (uint node_num, uint padre, uint &left, uint &right) BTreeData *lchild = (*it++); - if (lchild->getChild () == node_num) { + if (lchild->GetChild () == node_num) { /* Solo tengo hermano derecho */ std::cout << "Hermano Izquierdo : NO TENGO" << std::endl; left = 0; - std::cout << "Hermano Derecho : " << (*it)->getChild () << std::endl; - right = (*it)->getChild (); + std::cout << "Hermano Derecho : " << (*it)->GetChild () << std::endl; + right = (*it)->GetChild (); return; } while (it != node_keys.end ()) { - if ((*it)->getChild () == node_num) + if ((*it)->GetChild () == node_num) break; anterior = it; it++; } siguiente = it++; - std::cout << "Hermano Izquierdo : " << (*anterior)->getChild () << std::endl; - left = (*anterior)->getChild (); + std::cout << "Hermano Izquierdo : " << (*anterior)->GetChild () << std::endl; + left = (*anterior)->GetChild (); if (siguiente != node_keys.end ()) { - right = (*siguiente)->getChild (); - std::cout << "Hermano Derecho : " << (*siguiente)->getChild () << std::endl; + right = (*siguiente)->GetChild (); + std::cout << "Hermano Derecho : " << (*siguiente)->GetChild () << std::endl; } else { right = 0; std::cout << "Hermano Derecho : NO TENGO" << std::endl; } } -void BTree::DelKeyFromOther (const Clave &k, BTreeFindResult *r) +Clave *BTree::ReplaceKeyInFather (uint node_num, uint padre, Clave *k) { + uchar *node; + BTreeNodeHeader node_header; + std::list node_keys; + + node = ReadBlock (padre); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + std::list::iterator it = node_keys.begin (); + std::list::iterator anterior = node_keys.begin (); + std::list::iterator siguiente; + + BTreeData *lchild = (*it++); + + if (lchild->GetChild () == node_num) { + Clave *ret = (*it)->GetKey (); + (*it)->SetKey (k); + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, padre); + DeleteKeys (node_keys); + + delete [] node; + return ret; + } + + while (it != node_keys.end ()) { + if ((*it)->GetChild () == node_num) + break; + anterior = it; + it++; + } + + Clave *ret = (*it)->GetKey (); + (*it)->SetKey (k); + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, padre); + DeleteKeys (node_keys); + + delete [] node; + return ret; +} + +void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right) +{ + uint padre_hijo; + uchar *node; + BTreeNodeHeader node_header; + std::list node_keys; + + node = ReadBlock (node_num); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + if (right != 0) { + std::cout << "Busco para la derecha y luego todo a la izquierda\n"; + uchar *node_r; + BTreeNodeHeader node_hr; + std::list node_keyr; + + /* Busco la clave inmediatamente superior en el arbol */ + padre_hijo = node_num; + do { + node_r = ReadBlock (right); + ReadNodoHeader (node_r, &node_hr); + if (node_hr.level != 0) { + BTreeData *data_r; + node_keyr = ReadKeys (node_r, node_hr); + data_r = *(node_keyr.begin ()); + padre_hijo = right; + right = data_r->GetChild (); + + DeleteKeys (node_keyr); + delete [] node_r; + } + } while (node_hr.level != 0); + + std::cout << "Voy a reemplazar en el nodo " << right << std::endl; + + /* Reemplazo la clave a borrar por la de la hoja */ + node_keyr = ReadKeys (node_r, node_hr); + BTreeData *reemplazar = *(node_keyr.begin ()); + + std::string ss = *reemplazar; + std::cout << "Voy a reemplazar por : " << ss << std::endl; + + BTreeData *data = new BTreeLeafData (k->Clone()); + + std::list::iterator it = node_keys.begin (); + while (it != node_keys.end ()) { + std::string ss1, ss2; + ss1 = *data; + ss2 = *(*it); + std::cout << ss1 << " == " << ss2 << std::endl; + if ((*data) == (*(*it))) { + break; + } + it++; + } + if (it == node_keys.end ()) { + std::cout << "PANIC : No encontre la clave en el nodo!!!!\n"; + std::string s = *data; + std::cout << s << std::endl; + PrintNode (node_num); + exit (1); + } + (*it)->SetKey (reemplazar->GetKey ()); + reemplazar->SetKey (k->Clone ()); + + std::cout << "Tengo todo reemplazado ...\n"; + + /* Grabo los nodos */ + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + DeleteKeys (node_keys); + delete [] node; + + WriteKeys (node_r, node_hr, node_keyr); + WriteNodoHeader (node_r, &node_hr); + WriteBlock (node_r, right); + DeleteKeys (node_keyr); + delete [] node_r; + + std::cout << "Grabe todo en disco ...\n"; + PrintNode (node_num); + PrintNode (right); + /* Ahora debo eliminar la clave que puse en el nodo hoja */ + std::cout << "Borro la clave desde la hoja!\n"; + + DelKeyFromLeaf (k, right, padre_hijo); + + std::cout << "Listo, Listo!\n"; + } else if (left != 0) { + std::cout << "PANIC : Deberia poder reemplazar en la derecha!!!!!\n"; + exit (1); + } else { + std::cout << "PANIC : No tengo hijos para reemplazar!!!!\n"; + exit (1); + } } void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header) @@ -635,11 +1033,6 @@ std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade } for (uint i=0; i BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade keys.push_back (data); } + DeAbrevKey (keys); return keys; } +void BTree::AbrevKey (std::list &lst) +{ + /* Claves Fijas No se abrevian */ + if (key_type == KEY_FIXED) return; + + BTreeData *primera = NULL; + std::list::iterator it = lst.begin (); + + while (it != lst.end ()) { + if ((*it)->Abrev (primera) == false) + primera = (*it); + it++; + } +} + +void BTree::DeAbrevKey (std::list &lst) +{ + /* Claves Fijas No se abrevian */ + if (key_type == KEY_FIXED) return; + + BTreeData *primera = NULL; + std::list::iterator it = lst.begin (); + + while (it != lst.end ()) { + if ((*it)->DesAbrev (primera) == false) + primera = (*it); + it++; + } +} + void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list &keys) { + AbrevKey (keys); + std::list::iterator it = keys.begin (); node += sizeof (BTreeNodeHeader); @@ -662,9 +1088,12 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::listToArray (); + acumulado += d->Size (); + //std::cout << "WriteKeys :: Acumulado = " << acumulado << std::endl; memcpy (node, n, d->Size ()); delete [] n; node += d->Size (); @@ -673,7 +1102,7 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::listClone ()); else - data = new BTreeData ((Clave *)k, 0); + data = new BTreeData (k->Clone (), 0); while (it != node_keys.end ()) { if ((*data) == (*(*it))) { /* La encontre!, retorno */ + delete data; delete [] node; DeleteKeys (node_keys); BTreeFindResult *result = new BTreeFindResult (); result->node = node_num; result->header = node_header; + return result; } @@ -771,11 +1202,27 @@ BTreeFindResult *BTree::FindKeyR (const Clave *k, uint node_num) it++; } + delete data; + + /* Si llego aca y estoy en nivel 0 (una hoja) quiere + * decir que no lo encontré + */ + if (node_header.level == 0) { + DeleteKeys (node_keys); + delete [] node; + return NULL; + } + /* TODO: Aca faltaria liberar memoria */ + BTreeFindResult *ret; if (it == posterior) - return FindKeyR (k, lchild->getChild ()); - - return FindKeyR (k, (*ultima)->getChild ()); + ret = FindKeyR (k, lchild->GetChild ()); + else + ret = FindKeyR (k, (*ultima)->GetChild ()); + + DeleteKeys (node_keys); + delete [] node; + return ret; } void BTree::DeleteKeys (std::list &keys)