Serie ficheros virtuales

 

 

 

 

C Ficheros virtuales

 

 

 

 

 

A.I.5 El núcleo. SRRCM como implementación de caché y soporte de listas de datos simples

 

A.I.5.1 Introducción

A.I.5.2 Instrucciones básicas

A.I.5.3 Esquema de funcionamiento del mecanismo de inserción dicotómica

A.I.5.4 La inserción dicotómica en índice

A.I.5.5 Un programa ejemplo de emulación del mecanismo de inserción dicotómica en índice

A.I.5.6 La implementación del WRITE. La extensión automática de la memoria unidimensional

A.I.5.7 La implementación del CHAIN

A.I.5.8 La implementación del READ

A.I.5.9 La implementación del UPDATE

A.I.5.10 La implementación del DELETE

A.I.5.11 La implementación del REORGANIZE

A.I.5.12 La extensión automática de la memoria bidimensional

A.I.5.13 Prototipos de salida veloz (Para iSeries)

 

                                                                                                  _______

 

A.I.5.1 Introducción

 

Tal como se indicaba en el capítulo anterior, las instrucciones básicas de caché son el WRITE y el CHAIN. Con este reducido núcleo de instrucciones surgió la primera versión del producto, que se denominó SRRCM, acrónimo de SR=Servicio de, RC=Rutinas en C para, M=Gestión de memoria.

 

Inicialmente, su funcionamiento se basaba en una técnica de búsqueda lineal, pero una vez que se resolvió el problema de la extensión automática de la asignación de memoria, se pasó a la optimización del algoritmo de búsqueda, sustituyéndose la técnica lineal por una dicotómica; al comienzo sobre las propias claves, y posteriormente en los índices asociados.

 

SRRCM se amplió posteriormente con unos servicios adicionales codificados en SRRCN que recogían el grupo de instrucciones de lectura por clave, ampliando la posibilidad de usar el producto como si fuera un fichero; por último se le añadió la capa externa final SRRCW para uso en C (y SRAGM para RPG) añadiendo identificadores de tipo nombre, la posibilidad de crear vías de acceso adicionales, tratamientos globales de fichero y métodos sobrecargados para facilitar el uso.

 

En este capítulo presentaremos el programa núcleo SRRCM, comenzando por las instrucciones básicas WRITE y CHAIN, para lo que describiremos el funcionamiento de la inserción dicotómica en índice con esquemas y ejemplos, que redondearemos con una exposición dedicada a la extensión automática de memoria, concretando con ello la implementación efectiva del WRITE. Desde este punto de partida pasaremos a describir la implementación del resto de instrucciones relevantes del programa: CHAIN, READ, UPDATE, DELETE y REORGANIZE, resultantes de transcribir el esquema llave que se presentó en el capítulo anterior.

 

Terminaremos exponiendo el mecanismo de ampliación de memoria bidimensional que soporta el armazón donde se van engarzando los ficheros individuales, que a su vez también precisa ser extendido conforme el número de los mismos se incrementa.

 

También se irán incluyendo enlaces a los capítulos homólogos de sus blogs hermanos, para contrastar desarrollos, ejemplos y soluciones equivalentes en otros lenguajes.

 

                                                                                                  _______

 

 

A.I.5.2 Instrucciones básicas. WRITE y CHAIN.

 

Todo lo expuesto nace entonces de las instrucciones básicas WRITE y CHAIN, que pueden resumirse indicando que bajo la técnica dicotómica de inserción en índice el acceso de lectura/escritura indexada se basa en disponer de un conjunto de datos, de otro conjunto con sus claves asociadas y de un conjunto más de índices auxiliares para direccionar las claves; así, cuando se graba un nuevo ítem, se localiza su posición en el conjunto de claves valiéndose del direccionamiento que indican sus índices; luego, se almacenan las claves y los datos al final de los mismos y se inserta el nuevo índice en el orden apropiado en su propio conjunto, manteniéndose así la indexación del fichero.

 

Técnicamente, en la nomenclatura de fundamentos de sistemas de bases de datos, SRRCM proporciona soporte para un índice primario denso, en que cada valor de clave es único. El resto de la aplicación llegará a dar soporte en SRRCW al equivalente de índices secundarios densos en campos que no pertenecen a la clave primaria.

 

Veámoslo en detalle paso a paso, comenzando por el WRITE y el CHAIN hasta recorrer el conjunto de funciones de SRRCM, cuyos prototipos son:

 

 

 

long SRRCM_CHAIN(long lNIDp, const void *vClav, void *vDato);

 

Acceso por clave

 

short int SRRCM_CLRF(long lNIDp);

 

Limpiar datos

 

short int SRRCM_CLRFC(long lNIDp, long *lNBAJp);

 

Ídem versión ampliada

 

short int SRRCM_CLOSE(void);

 

Cierre de aplicación

 

long SRRCM_DELETE(long lNIDp, const void *vClav);

 

Eliminación de ítem

 

short int SRRCM_ERASE(long lNIDp);

 

Eliminación de fichero

 

short int SRRCM_INF(long lNIDp, int *iDimCp, long *lDimDp, long *lNITEMp,

                    long *lBAJASp,  long *lNIDDp)

 

Recupera información estadística del fichero

 

long SRRCM_NEW(int iDimC, long lDimD);

 

Crea un nuevo fichero

 

long SRRCM_NEWC(int iDimC, long lDimD, long lMaxNreg);

 

Idem versión ampliada

 

short int SRRCM_READ(long lNIDp, long lINDIp, void *vDato);

 

Lectura secuencial

 

short int SRRCM_READC(long lNIDp, long lINDIp, void *vDato, void *vClav);

 

Idem versión ampliada

 

short int SRRCM_REORGANIZE(long lNIDp);

 

Reorganización (Depura registros borrados)

 

short int SRRCM_REORGANIZEC(long lNIDp, long *lNBAJp);

 

Idem versión ampliada

 

short int SRRCM_RESIZE(long lNIDp, long lMaxNreg);

 

Cambio de tamaño máximo

 

long SRRCM_SETLL(long lNIDp, const void *vClav);

 

Posicionado por menor ó igual

 

long SRRCM_SETEQ(long lNIDp, const void *vClav);

 

Posicionado por igual

 

long SRRCM_WRITE(long lNIDp, const void *vClav, const void *vDato);

 

Grabación de registro

 

long SRRCM_UPDATE(long lNIDp, const void *vClav, const void *vDato);

 

Actualización de registro

 

 

                                                                                                  _______

 

 

Seguiremos el orden siguiente:

 

WRITE y CHAIN como núcleo, introduciendo previamente el funcionamiento del mecanismo de inserción dicotómica que los soporta.

 

Como instrucciones derivadas veremos a continuación la implementación del READ, del UPDATE, del DELETE y del REORGANIZE

 

El resto de funciones, como SETLL y SETEQ, es mejor presentarlas en sus versiones finales de la capa exterior del producto pues, a diferencia de las otras funciones citadas antes, su naturaleza se ampliará para dotarlas de una perspectiva que les permitirá engarzar con las funciones de lectura por clave que se introducirán posteriormente, quedando reservado su uso en el sentido original precisamente para la propia implementación interna de esta familia de funciones de lectura por clave, tal y como se verá en el próximo capítulo.

 

Como regla general, la codificación en el libro se presentará extractada y con comentarios ampliados. Al extractar se prescindirá de listar sentencias de filtro y control necesarias en la codificación real, pero que no aportan ningún elemento esencial a la algorítmica y cuya inclusión podría distraer del seguimiento de la idea base de la implementación que se vaya mostrando. En el mismo sentido, se eludirán las sentencias repetitivas y los fragmentos añadidos automáticamente por el sistema, salvo mención expresa.

 

                                                                                                  _______

 

 

A.I.5.3 Esquema de funcionamiento del mecanismo de inserción dicotómica

 

En primer lugar restrinjamos el problema a considerar sólo las propias claves.

 

 

Gráficamente el proceso se produce como sigue:

 

 

 

+ 4  ->

4

Inserción directa

 

 

 

+ 0  ->

a) 4

Debemos desplazar el 4

 

b) 0 4

Luego insertar el 0

 

 

 

 

+ 6 ->

0 4 6

Se añade directamente al final

 

 

 

+ 1 ->

a) 0 4 6

Debemos desplazar el 4 y el 6

 

b) 0 1 4 6

Luego insertar el 1

 

 

 

Y así sucesivamente.

 

 

Como primera idea este esquema funciona, pero puede refinarse. Veremos como en el siguiente epígrafe.

 

 

                                                                                                  _______

 

 

A.I.5.4 La inserción dicotómica en índice

 

Si las claves fuesen una estructura, particularmente si se tratase de estructuras complejas, el mecanismo de inserción y desplazamiento puede llevar su tiempo. Tanto más cuanto más grande y compleja sea la estructura de clave.

 

Sin embargo, hay un mecanismo sencillo de optimización.

 

Puede utilizarse una serie de índice auxiliar, que mantenga simplemente la relación de orden de las claves y que garantice un tiempo constante de respuesta relacionado con el propio tamaño del índice.

 

Bajo la técnica de índice auxiliar, las claves se colocan sucesivamente sin más y es la propia serie índice la que sufre las operaciones de inserción.

 

Ahora vamos a presentar un resumen comentado de la codificación de la rutina de localización dicotómica SRRCU_BS que utiliza SRRCM como base del CHAIN, y cuyo código completo se puede encontrar en el apéndice C y en las carpetas de proyecto.

 

 

SRRCU_BS localiza en una serie ascendente un ítem según una serie índice. A diferencia de otras implementaciones, esta rutina siempre devuelve un resultado compuesto, de un lado con el valor de índice localizado igual o más próximo inferior, y de otro la marca resultado de la comparación.

 

 

Su codificación es:

 

long SRRCU_BS(const void *d,  // Dato de entrada a localizar

              int iSize,      // Tamaño del dato a localizar

              long nSd,       // Dimensión efectiva de la serie de datos donde se busca

              const long *Si, // Serie índice

              const void *Sd, // Serie de datos

              int *iComp)     // Resultado comparación (del último) memcmp empleado  [ - si fue menor,  0 si fue igual,  + si fue mayor ]

                              // iComp complementa al índice encontrado que se devuelve como valor de retorno, así si iComp=0

                              // la localización es exacta, en caso contrario se devuelve el índice más próximo inferior.

 

{

  long ab2 = 0; // Indice de rango semisuma en el algoritmo de búsqueda

 

  // Inz

  char *cSd = (char *) Sd; // Establece cSd y cd como variables de trabajo char *,

  char *cd = (char *) d;   // visualizables en depuración

 

 

  // Rango inicial (En este resumen se eluden las comprobaciones de límite)

  long a = 0;

  long b = nSd;

 

 

  // Ciclo de Contracción Dicotómica

  do

  {

   ab2 = (a + b) >> 1; // (a+b)/2

 

 

   // Sentencia central de localización del dato en la serie de búsqueda según la serie de índices

 

   *iComp = memcmp(cd, cSd + (Si[ab2-1] * iSize), iSize);

 

 

   // Localización exacta e inexacta

 

   if (!*iComp) return ab2;

 

   if (ab2 <= a) return a;

 

 

   // Compara, Divide Rango y Continua Ciclo de Proceso

 

   if (*iComp > 0) a = ab2; else b = ab2;

  }

  while (a < b);

 

 

  return ab2;

}

                                                                                                  _______

 

Puede compararse con la versión en VBA para aplicaciones que se muestra junto con ejemplos adicionales en el epígrafe

 VBA. Búsqueda dicotómica, del blog VBA. Ficheros virtuales.

 

A continuación se muestra un ejemplo numérico del mecanismo completo de inserción dicotómica en índice, posteriormente, al estudiar el código del CHAIN, basado en el de SRRCU_BS que se acaba de ver, se presentará otro ejemplo numérico del mecanismo embebido de localización dicotómica en índice, que ahora se obvia (Y que puede también verse de una forma alternativa en el enlace VBA indicado).

 

                                                                                                  _______

 

 

A.I.5.5 Un programa ejemplo de emulación del mecanismo de inserción dicotómica en índice

 

El programa que se lista luego emula el mecanismo completo de la inserción dicotómica en índice.

 

 

Si lo ejecutamos bajo la opción iDebug = 1, obtendríamos el resultado que se muestra a continuación en la siguiente tabla que presenta de un lado la disposición lógica de los datos, tal como puede accederse a ellos leyendo en el orden de clave, y de otro la disposición en que físicamente se disponen los datos en realidad, con las claves y los datos añadiéndose al final, manteniéndose el enlace mediante el índice asociado que se recalcula en cada inserción:

 

                  Disposición lógica                             Disposición Física

 

 ++SRRCM        Índice    Clave    Datos    Resultado SRRCW   Índice    Clave    Datos

               ========  =======  =======  ================= ========  =======  =======

    

   4  E  -->      1         4        E            1              1        4        E

 

 

   0  A  -->                                      1

 

                  1         0        A                           2        4        E

 

                  2         4        E                           1        0        A

 

 

   6  G  -->                                      3

                 

                  1         0        A                           2        4        E

 

                  2         4        E                           1        0        A

 

                  3         6        G                           3        6        G

 

 

   1  B  -->                                      2

 

                  1         0        A                           3        4        E

 

                  2         1        B                           1        0        A

 

                  3         4        E                           4        6        G

 

                  4         6        G                           2        1        B

 

 

   7  H -->                                       5

 

                  1         0       A                            3        4        E

 

                  2         1       B                            1        0        A

 

                  3         4       E                            4        6        G

 

                  4         6       G                            2        1        B

 

                  5         7       H                            5        7        H

 

 

   3  D -->                                       3

 

                  1         0       A                            4        4        E

 

                  2         1       B                            1        0        A

 

                  3         3       D                            5        6        G

 

                  4         4       E                            2        1        B

 

                  5         6       G                            6        7        H

 

                  6         7       H                            3        3        D

 

   5  F -->                                       5

 

                  1         0       A                            4        4        E

 

                  2         1       B                            1        0        A

 

                  3         3       D                            6        6        G

 

                  4         4       E                            2        1        B

 

                  5         5       F                            7        7        H

 

                  6         6       G                            3        3        D

                                                            

                  7         7       H                            5        5        F

 

   2  C -->                                       3

 

                  1         0       A                            5        4        E

 

                  2         1       B                            1        0        A

 

                  3         2       C                            7        6        G

 

                  4         3       D                            2        1        B

 

                  5         4       E                            8        7        H

 

                  6         5       F                            4        3        D

                                                             

                  7         6       G                            6        5        F

 

                  8         7       H                            3        2        C

 

   9  J -->                                       9

 

                  1         0       A                            5        4        E

 

                  2         1       B                            1        0        A

 

                  3         2       C                            7        6        G

 

                  4         3       D                            2        1        B

 

                  5         4       E                            8        7        H

 

                  6         5       F                            4        3        D

                                                            

                  7         6       G                            6        5        F

 

                  8         7       H                            3        2        C

 

                  9         9       J                            9        9        J

 

   8  I -->                                       9

 

                  1         0       A                            5        4        E

 

                  2         1       B                            1        0        A

 

                  3         2       C                            7        6        G

 

                  4         3       D                            2        1        B

 

                  5         4       E                            8        7        H

 

                  6         5       F                            4        3        D

                                                            

                  7         6       G                            6        5        F

 

                  8         7       H                            3        2        C

 

                  9         8       I                            9        9        J

 

                 10         9       J                           10        8        I

 

 

                                                                                                  _______

 

 

[Cuando se presente el código que estamos emulando, veremos que la agregación al final de cada paso se encargará a memcpy y que la inserción en índice se ejecutará con memmove]

 

 

Si, en cambio, el programa se ejecuta bajo iDebug = 0 se generan al azar series de muestras distintas para comprobar el funcionamiento del mecanismo en otras situaciones.

 

 

 

A continuación se lista el programa de muestra que replica este proceso:

 

 

short into eV_1(unsigned into iNpruebas)

{

  short int i = 0;  // Contador de for

  short iDebug = 0; // 0/1 Aplicar series fijas definidas a continuación bajo debug

  char *cITOC;      // Conversor de dígito a char, resultado de SRRCAL_itoc

 int iRand = 0;    // NºRandom 0 .. 9

  long lNID = 0;    // Identificador del fichero virtual de pruebas

  long lResul = 0;  // Resultados SRRCW

 

 

 // Series para pruebas fijas bajo debug

 

  int si[10] = {4, 0, 6, 1, 7, 3, 5, 2, 9, 8};

  char sc[10]= {'E', 'A', 'G', 'B', 'H', 'D', 'F', 'C', 'J', 'I'};

 

 

 

 

  // Definiciones del fichero virtual de prueba asociado

 

 

   // Ds’s de clave y datos del fichero virtual de prueba

 

   struct sDK {char ci[2];}; // Índice de acceso

   struct sDD {char cc;};    // Datos. Carácter asociado

 

 

 

   // Ds del fichero virtual de prueba

 

   struct sDF

   {

    struct sDK sDk; // Clave

    struct sDD sDd; // Datos

   } sDF_reg;

 

 

 

  // Comienzo de proceso

 

 

  // Crea el fichero virtual de prueba

 

 

 lNID = SRRCW_NEW("EV_1", sizeof(sDK), sizeof(sDF));

 

 

 

  // Inicia serie rand

 

 srand(iNpruebas);

 

 

 

  // Bucle de grabación demostrativa

 

  for(i=0;i<10;++i)

  {

   if (iDebug) iRand = si[i];

   else iRand = 10 * rand() / RAND_MAX;

 

 

   // Pasa campo de clave

 

   cITOC = SRRCAL_itoc(iRand);

 

   memcpy(sDF_reg.sDk.ci, cITOC, sizeof(sDK));

 

 

   // Pasa campo de datos

 

   sDF_reg.sDd.cc = 65 + iRand;

 

 

   // Graba resultado

 

   lResul = SRRCW_WRITE("EV_1", &sDF_reg);

  }

 

 

  // Elimina el fichero virtual utilizado

 

  lResul = SRRCW_ERASE("EV_1");

 

  return lResul;

}

 

 

Este esquema de inserción dicotómica en índice puede ampliarse utilizando índices multinivel que minimicen el desplazamiento de un solo índice grande cambiándolo por desplazamientos parciales de subíndices pequeños.

 

Sin embargo su implementación ya no tendría el carácter directo que corresponde al ejemplo que hemos visto y el alto grado de complejidad en el desarrollo que conlleva sólo puede llegar a compensar para grandes volúmenes de datos.

 

                                                                                                  _______

 

 

A.I.5.6 La implementación del WRITE. La extensión automática de la memoria unidimensional

 

Si SRRCM es el núcleo del sistema, SRRCM_WRITE es a su vez la rutina central porque integra en uno todos los principios del producto, pues debe realizar las siguientes tareas

 

1.    Evaluar la preexistencia del ítem a añadir utilizando implícitamente la rutina de búsqueda dicotómica 

2.    Ampliar los datos del fichero en curso si procede, utilizando malloc y realloc 

3.    Insertar el nuevo ítem dejándolo accesible para su extracción por clave, agregando los datos con memcpy y (re)insertando los índices con memmove como se verá en los puntos señalados más adelante.

 

 

La implementación resultante se codifica en la función SRRCM_WRITE , que se sintetiza a continuación, y cuyo fuente completo puede encontrarse en las carpetas de proyecto:

long SRRCM_WRITE(long lNIDp, const void *vClav, const void *vDato)

{

  cClav = (char *) vClav; // Uso local de vClav

  cDato = (char *) vDato; // Uso local de vDato

 

 

  // Posicionamiento dicotómico y control de clave ya existente

 

  if (SRRCM_SETEQ(lNIDp, cClav)) return 0;

 

 

 // SETEQ es un interfaz reducido de CHAIN, que se expone más adelante, para tomar el índice resultado lINBS de SRRCU_BS,

// pero sin paso de datos.

 

 // En la práctica nos deja situados en el fichero en la posición solicitada y de ahí su nombre, que toma prestado de la nomenclatura de RPG

 

 

 

  // Control de ampliación de Datos

 

  if ( SRRCM_CAMPDAT(lNIDp) ) return 0;

 

 

 

 

Aspecto embebido: La extensión automática de la memoria unidimensional

 

 

SRRCM_CAMPDAT evalúa si se deben ampliar datos por agotamiento del espacio reservado anteriormente

 

 

Hay una reserva inicial de 1000 ítems y ampliaciones posteriores de 10000. Es una alternativa a la técnica de ampliación 2^N que prefiero porque cuando N es pequeño 2^N no es muy grande y por el contrario si N es grande el paso de 2^(N-1) a 2^N es muy, muy grande y al sistema le lleva mucho tiempo reservar el nuevo

espacio y volcar el contenido anterior. Por otro lado, en la práctica se observa que la mayoría de aplicaciones no necesitan más que la reserva inicial, que sólo un pequeño porcentaje acude a la primera ampliación y que aún son más pocas las que precisan de ulteriores ampliaciones.

 

 

Las instrucciones de asignación que finalmente se invocan en SRRCM_CAMPDAT son:

 

 

char* SRRCM_AMpD(char *p, long lTamAnt, long lTamAmp, long lTamItem)

{

  char *q; // Puntero ampliándose

 

  // Al ser el resultado de malloc o realloc “q” tiene una persistencia global hasta su desasignación explícita

  // con free, lo que es tarea de SRRCM_CLRF.

 

 

  // Solicitud inicial

 

  if (! lTamAnt)

  {

   // Establece un bloque de lTamAmp como espacio para la lista de items

   q = (char *) malloc(lTamAmp * lTamItem * sizeof(char));

   return q;

  }

 

 

  // Ampliación posterior

 

  q = (char *) realloc(p, (lTamAnt + lTamAmp) * lTamItem * sizeof(char));

  return q;

}

 

 

 

  // Incrementa el contador de ítems en el fichero virtual

 

  ++lNITEM[lNIDc];

  lNITEM1 = lNITEM[lNIDc]-1;

 

 

 

  // Paso a memoria del ítem dado, apilándolo físicamente al final del fichero

 

 

  // -Parte de Datos

 

 memcpy(cDATOS[lNIDc]+lNITEM1*lSDimD[lNIDc], cDato, lSDimD[lNIDc]);

 

 

  // -Parte de clave

 

 memcpy(cCLAVES[lNIDc]+lNITEM1*iSDimC[lNIDc], cClav, iSDimC[lNIDc]);

 


 

 

  // -Inserta el índice

 

 

  // Desplaza situación anterior

 

  memmove(lINDICES[lNIDc]+(lINBS+1), lINDICES[lNIDc] + lINBS, (lNITEM1-lINBS)*sizeof(long));

 

 

 

 // -Inserta el nuevo, apuntando a la dirección del nuevo elemento en el final de los datos

 

  lINDICES[lNIDc][lINBS] = lNITEM1;

 

 

 

  // Devuelve índice en formato 1..N para facilitar el uso en RPG

 

 return (lINBS+1);

}

 

 

Al centrarse la rutina WRITE en la localización dicotómica y en el uso de las instrucciones memcpy y memmove, todas ellas muy rápidas, se consigue a su vez un rendimiento singularmente veloz.

 

                                                                                                  _______

 

 

A.I.5.7 La implementación del CHAIN

 

La síntesis del CHAIN es más reducida y se centra en las instrucciones siguientes:

 

long SRRCM_CHAIN(long lNIDp, const void *vClav, void *vDato)

 

...

 

// Localización dicotómica comentada anteriormente

 

lINBS = SRRCU_BS(vClav, iSDimC[lNIDc], lNITEM[lNIDc], lINDICES[lNIDc], cCLAVES[lNIDc], &iComp);

 

 

// Si es inexacta se rechaza

 

if (iComp) return 0;

 

 

// Pasa datos asociados a localización exacta

 

lIndic = lINDICES[lNIDc][lINBS-1];

 

memcpy(vDato, cDATOS[lNIDc] + lIndic*lSDimD[lNIDc], lSDimD[lNIDc]);

 

...

 

 

En esencia se basa en la rutina de localización dicotómica y en el uso de la instrucción memcpy.

 

 

Veámoslo en detalle siguiendo el funcionamiento de un programa ejemplo que emula el mecanismo dicotómico descrito, que gráficamente puede representarse como

 

 

 

 

            |      |

     ->  ->   ->  |

            |

            |

 

 

 

 

Si el programa, que se lista luego, lo ejecutamos bajo la opción iDebug = 1, con 10000 elementos de base, con un número esperado de pruebas de alrededor de 14 [valor de log2(10000)], resultaría que partiendo de los datos que se muestran:

 

 

 

Posición Física

1

2

3

4

5

6

.. (De 1 a 10000 ítems)

Clave

0

1

3

5

7

9

.. (El 0 más 9999 impares, hasta llegar al número 19997)

Datos

0

1

2

3

4

5

.. (De 0 a 9999)

 

 

Si deseáramos localizar en esta tabla el ítem de clave 3333, se arrancaría un proceso dicotómico que avanzaría en pasos como los que siguen:

 

 

Paso

Actuación

Elemento

Índice

Valor Clave

Rango

División

0

Inicio

   De 1 a 10000

   De 0 a 9999

   De 0 a 19997

19997

Compara y comienza

1

Semisuma

5000

4999

9997

9997

A la izquierda

2

Semisuma

2500

2499

4997

4997

A la izquierda

3

Semisuma

1250

1249

2497

2497

A la derecha

4

Semisuma

1875

1874

3747

1250

A la izquierda

5

Semisuma

1562

1561

3121

626

A la derecha

6

Semisuma

1718

1717

3433

312

A la izquierda

7

Semisuma

1640

1639

3277

156

A la derecha

8

Semisuma

1679

1678

3355

78

A la izquierda

9

Semisuma

1659

1658

3315

40

A la derecha

10

Semisuma

1669

1668

3335

20

A la izquierda

11

Semisuma

1664

1663

3325

10

A la derecha

12

Semisuma

1666

1665

3329

6

A la derecha

13

Semisuma

1667

1666

3331

4

A la derecha

14

Semisuma

1668

1667

3333

2

Compara y termina 

 

 

Lo fascinante del procedimiento es que si ahora pasáramos de 10000 elementos a 100000 el nº de comparaciones a añadir sólo aumentaría en 3 por la naturaleza logarítmica del proceso, precisamente esto es lo que le vuelve tan poderoso.

 

Sólo es más rápido el algoritmo de inserción directa, que consiste en reservar un espacio prefijado en donde se colocan las claves como se ponen las llaves en el casillero de un hotel, aunque presenta el inconveniente de que es un mecanismo que sólo puede aplicarse para casos particulares con pocos elementos. También resultaría más rápido disponer de una función hash sin colisión, que es otra forma de inserción directa, pero no resulta un mecanismo general, sólo es factible para casos concretos.

                                                                                                  _______

 

 

Se incluye ahora el listado del programa de muestra

 

short int eV_2(long lNpruebas)

{

  char cc;                 // Auxiliar paso de resultado

  char cli[11];            // Auxiliar paso de resultado

  char *cLTOA;             // Conversor de long a char, resultado de SRRCAL_ltoal

  short iDebug = 0;        // 0/1 Aplicar serie fija de "impares" bajo debug

  unsigned int iSemilla=1; // Semilla iniciadora de rand 

  int iRand = 0;           // NºRandom 0 .. 9

  long l = 0;              // Contador de for

  long li = 0;             // Auxiliar paso resultado

  long lBusq = 0;          // Índice de prueba de búsqueda

  long lNID = 0;           // Identificador del fichero virtual de pruebas

  long lResul = 0;         // Resultados SRRCW

  div_t div_result;        // Soporte de división con resto y cociente

 

 

 

  // Definiciones del fichero virtual de prueba asociado

 

 

   // Ds de clave del fichero virtual de prueba

 

   struct sDK

   { // K

    char cli[11]; // Indice de acceso alfa 0 1 2 3 . . N

   };             //                       0 1 3 5 . . 2*(N-1) + 1

 

 

  // Ds de datos del fichero virtual de prueba

 

  struct sDD // D

  {          //                       0 1 2 3 . .  9 10 . . N

    long li;  // Indice de acceso long 0 1 3 5 . . 19 21 . . 2*(N-1) + 1

    char cc;  // Carácter asociado     A B C D . . J   A . . c

  };

 

 

   // Ds del fichero virtual de prueba

 

   struct sDF

  {

   struct sDK sDk; // Claves

   struct sDD sDd; // Datos

  } sDF_reg;

 

 

 

  // Comienzo de proceso

 

 

  // Crea el fichero virtual de prueba

 

  lNID = SRRCW_NEW("EV_2", sizeof(sDK), sizeof(sDF));

 

 

  // Inicia serie rand

 

  if (lNpruebas < 65636) iSemilla = lNpruebas;

  srand(iSemilla);

 

 

 

  // Bucle de grabación demostrativa

 

  for(l=0;l<lNpruebas;++l)

  {

 

   // Pasa campo de clave

 

   if (iDebug)

   if (!l) li = 0;        //                                    0 1 2 3 . .  9999

   else li = 2*(l-1) + 1; // Si debug, impares; incluyendo cero 0 1 3 5 . . 19997

   else li = rand();      // Usualmente al azar

 

   cLTOA = SRRCAL_ltoal(li);

   memcpy(sDF_reg.sDk.cli, cLTOA, 11);

 

 

   // Pasa campos de datos

 

   sDF_reg.sDd.li = li;

   div_result = div(l, 10);

 

   if (iDebug) iRand = div_result.rem;  // Bajo debug, secuencialmente A..J

   else iRand = 10 * rand() / RAND_MAX; // Usualmente al azar

 

   cc = 65 + iRand; // Caracteres alfabéticos, comenzando en la A

   sDF_reg.sDd.cc = cc;

 

 

   // Graba resultado

 

   lResul = SRRCW_WRITE("EV_2", &sDF_reg);

 }

 

 

  // Localización de prueba. Bajo debug se trata de un impar, por tanto existe y el mecanismo de su localización

 // se expresa en el ejemplo expuesto anteriormente

 

  if (iDebug) lBusq = lNpruebas / 3; // Bajo debug, fijada

  else lBusq = rand();               // Usualmente, al azar

 

  cLTOA = SRRCAL_ltoal(lBusq);

  memcpy(sDF_reg.sDk.cli, cLTOA, 11);

 

  lResul = SRRCW_CHAIN("EV_2", &sDF_reg);

 

  if (lResul)

 {

   memcpy(cli, sDF_reg.sDk.cli, 11);

   li = sDF_reg.sDd.li;

   cc = sDF_reg.sDd.cc;

 

 

 

  // Elimina el fichero virtual utilizado

 

  lResul = SRRCW_ERASE("EV_2");

 

  return lResul;

}

                                                                                                  _______

 

A.I.5.8 La implementación del READ

 

La implementación del READ se centra en las sentencias siguientes que consisten en recuperar la dirección física correspondiente al índice solicitado y a continuación copiar las claves y los datos asociados a las variables de salida.

 

El índice se considera en base uno, porque en los ficheros reales no existe registro cero. Por ello se utiliza lINDIp-1 para el acceso a las series de soporte en lugar de lINDIp.


Read se presenta en dos versiones READ y READC, debido a que C ANSI no permite la sobrecarga multifunción. Por comodidad, en la versión de SRRCW que se presenta en un capítulo posterior las dos versiones se integran en una, pues se utiliza desde un ambiente C++ que permite la sobrecarga. Por el contrario, la implementación para iSeries SRRCW está hecha en C ANSI y también se presenta en dos versiones, encargándose la sobrecarga al interfaz en RPG SRAGM. Como SRRCM realmente se utiliza desde SRRCW, no se le ha aplicado la comodidad de SRRCW y se ha mantenido en C ANSI puro para minimizar el uso de versiones.

// La versión READ no pasa vClav, mientras que la versión ampliada READC si

 

short int SRRCM_READ(long lNIDp, long lINDIp, void *vDato)                // Para ficheros que solapan claves y datos (Es lo habitual)

short int SRRCM_READC(long lNIDp, long lINDIp, void *vDato, void *vClav)  // Versión ampliada, si no hay solapamiento

 

. . .

 

// Recupera el valor de la posición física correspondiente al índice solicitado

lIndic = lINDICES[lNIDc][lINDIp-1];

 

// Recupera el valor de la clave del ítem

memcpy(vClav, cCLAVES[lNIDc] + lIndic*iSDimC[lNIDc], iSDimC[lNIDc]);

 

// Recupera los datos asociados

memcpy(vDato, cDATOS[lNIDc]+lIndic*lSDimD[lNIDc], lSDimD[lNIDc]);

. . .

 

Como resultado de disponer de orden intrínseco en las claves, el READ secuencial devuelve los ítems ordenados, feliz circunstancia que es básica para los ejemplos que se presentan posteriormente.

La aplicación completa permite además definir vías de acceso alternativas sobre los mismos datos posibilitando emitir diversos READ’s secuenciales, pero con distinto orden, lo que agrega un recurso que permite trascender al producto del nivel de mero manejo de listas ordenadas a la categoría de tratamiento de bases de datos y potente sustrato de la implementación de algorítmicas complejas.

 

 

Una extensión natural del READ es la lectura por clave READE, que se presentará en el capítulo siguiente.

 

 

                                                                                                  _______

 

Ahora una cuestión de detalle.

 

Se utiliza una implementación directa de la búsqueda binaria SRRCU_BS en vez de la bsearch del sistema por dos razones, la primera ya citada es que se trata de una rutina orientada al problema específico de inserción en un índice en vez de la inserción directa en la clave siendo necesario que devuelva siempre la localización inferior más próxima, y la segunda es una mera cuestión de seguimiento, aunque puede implementarse un interfaz sobre bsearch, resulta muy incómodo hacer un rastreo, cosa que no sucede en una rutina explícita como SRRCU_BS.

 

                                                                                                  _______

 

 

 

A.I.5.9 La implementación del UPDATE

 

Una vez que se dispone de CHAIN, el UPDATE es inmediato. Simplemente hay que utilizar el índice devuelto para actualizar los datos asociados con el nuevo valor, lo que se sintetiza muy brevemente como sigue:

 

long SRRCM_UPDATE(long lNIDp, const void *vClav, const void *vDato)

 

...

 

 

// Control solicitud actualización sobre registro no existente

 

lResult = SRRCM_SETEQ(lNIDp, cClav);

if (!lResult) return lResult;

 

 

 

// Actualiza datos del ítem encontrado

 

lIndic = lINDICES[lNIDc][lResult-1];

 

 

 

// lIndic es una variable auxiliar para simplificar la instrucción principal:

 

memcpy(cDATOS[lNIDc] + lIndic*lSDimD[lNIDc], cDato, lSDimD[lNIDc]);

 

...

 

                                                                                                  _______

 

 

A.I.5.10 La implementación del DELETE

 

Para el DELETE, en vez de una eliminación física, marcaremos el registro como borrado quemando su posición de índice con *hival y estableciendo el número de registros disponibles en uno menos, resultando así inaccesible el recién suprimido.

 

Esto es mucho más rápido que una reorganización completa para hacer desaparecer el registro totalmente, tanto de la zona de índices, como de la de claves y de la de datos, pues en la alternativa de la reorganización todas las zonas tendrían que ser desplazadas para hacer desaparecer el registro suprimido, que quedaría entonces ya sí físicamente eliminado.

 

Como lo habitual es que el nº de elementos borrados sea inexistente o muy reducido frente al nº de elementos total, el espacio que consumen los elementos borrados no supone, en la práctica, una penalización del conjunto.

 

En cualquier caso, si el nº se hace grande, puede utilizarse la función REORGANIZE para depurarlos, forzando a ejecutar el desplazamiento citado.

 

 

Para ver el funcionamiento gráfico del DELETE, tomamos el fichero ejemplo utilizado en la presentación del WRITE y procedamos a dar de baja el ítem de clave 6:

 

 

 

                  Disposición lógica                             Disposición Física

 

                Índice    Clave    Datos    Resultado SRRCW   Índice    Clave    Datos

               ========  =======  =======  ================= ========  =======  =======

 

                  1         0       A                            5        4        E

 

                  2         1       B                            1        0        A

 

                  3         2       C                            7        6        G

 

                  4         3       D                            2        1        B

 

                  5         4       E                            8        7        H

 

                  6         5       F                            4        3        D

                                                             

                  7         6       G                            6        5        F

 

                  8         7       H                            3        2        C

 

                  9         8       I                            9        9        J

 

                 10         9       J                           10        8        I

 

 

     6   -->                                     7 à 10

   

                  1         0       A                            5        4        E

 

                  2         1       B                            1        0        A

 

                  3         2       C                           10        *        G

 

                  4         3       D                            2        1        B

 

                  5         4       E                            7        7        H

 

                  6         5       F                            4        3        D

                                                            

                  7         7       H                            6        5        F                                               

 

                  8         8       I                            3        2        C

 

                  9         9       J                            9        9        J

 

                 10         *       G                            8        8        I

 

 

                                                                                                   _______

 

 

 

Sucede entonces que la disposición física de los datos no cambia, sin embargo su clave se pone a *HIVAL (representado por *), por lo que en cuanto a su disposición lógica el ítem pasa al final, a una región inaccesible según el número de ítems neto [= número de ítems total – número de ítems borrados].

 

 

En cuanto a su implementación, DELETE se sintetiza como sigue:

 

long SRRCM_DELETE(long lNIDp, const void *vClav)

 

...

 

 

// Recupera ítem a eliminar, controlando pre-existencia

 

lResult = SRRCM_SETEQ(lNIDp, vClav);

if (!lResult) return lResult;

 

 

 

// Reserva índice quemado

 

lIndic = lINDICES[lNIDc][lResult-1];

 

 

 

// Elimina registro de clave asociado (quemándolo con *HIVAL)

 

memcpy(cCLAVES[lNIDc] + lIndic*iSDimC[lNIDc], cBORRADOR, 1);

 

 

 

// Reordena resultados poniendo el índice quemado al final

 

 

// Desplaza índices posteriores al quemado SOBRE el quemado

 

memmove(lINDICES[lNIDc]+(lResult-1), lINDICES[lNIDc]+ lResult, (lNITEM[lNIDc]+1-lResult)*sizeof(long));

 

 

 

// Coloca el índice quemado al final de la lista

 

lINDICES[lNIDc][lNITEM[lNIDc]-1] = lIndic;

 

...

 

                                                                                                  _______

 

 

A.I.5.11 La implementación del REORGANIZE

 

 

El REORGANIZE, que depura los datos eliminados, puede extractarse como sigue:

 

// Como el READ, también se presenta en 2 versiones. Se remite a las notas indicadas allí.

 

short int SRRCM_REORGANIZE[C](long lNIDp[, long *lNBAJp]) 

...

 

 

// Recupera información actual del fichero (Eludiendo casos sin ítems borrados)

 

er = SRRCM_INF(lNIDp, &iDimC, &lDimD, &lNitem, &lBAJAS, &lNIDD);

 

 

 

// Crea fichero de trabajo temporal, para volcar los datos depurados

 

lNIDw = SRRCM_NEW(iDimC, lDimD);

 

 

 

// Lee del fichero origen y vuelca al temporal

 

 

for(l=1;l<=(lNitem-lBAJAS);++l)

{

  er = SRRCM_READC(lNIDp, l, vDatoW, vClaveW);

 

  lIndic = SRRCM_WRITE(lNIDw, vClaveW, vDatoW);

}

 

 

 

// Limpia el fichero origen

 

er = SRRCM_CLRF(lNIDp);

 

 

 

// Lee del fichero temporal y vuelca al origen, dejándolo ya depurado

 

 

for(l=1;l<=(lNitem-lBAJAS);++l)

{

  er = SRRCM_READC(lNIDw, l, vDatoW, vClaveW);

 

  lIndic = SRRCM_WRITE(lNIDp, vClaveW, vDatoW);

}

 

 

...

                                                                                                  _______

 

 

 

A.I.5.12 La extensión automática de la memoria bidimensional

 

Las rutinas que se han presentado forman el núcleo de la aplicación en cuanto a gestión de datos, y se completan con la gestión de la extensión automática de memoria, tanto para cada fichero individual como para los índices de cuenta de ficheros.

 

Se presentó antes la rutina final de ampliación de un fichero individual, centrémonos ahora en la gestión de las ampliaciones en su conjunto.

 

 

Esta consiste, en esencia, en invocar a malloc y realloc en función de la progresión del número de ficheros y registros y las constantes de control siguientes:

 

static const long lBLOQf=200L;

static const long lBLOQd=1000L;

static const long lBLOQd2=10000L;

 

 

Definidas con el siguiente propósito:

 

- lBLOQf controla la ampliación de la 1ª dimensión de las series

 

 

static long **lINDICES; // Conjuntos de índices

static char **cCLAVES;  // Conjuntos de claves.

static char **cDATOS;   // Conjuntos de datos asociados.

 

Series que dan soporte a cada fichero individual en cada uno de sus componentes, índices, claves y datos.

 

 

En el término figurativo introducido en el capítulo de los punteros, la primera dimensión direcciona la estantería donde se van colocando cada uno de los libros que representan los ficheros individuales y que se va ampliando por cada bloque de lBLOQf libros.

 

 

- lBLOQd controla la 1ª ampliación de la 2ª dimensión, ya de datos, de dichas series.

 

    En otros términos, cada libro se inicializa con un espacio de lBLOQd ítems.

 

 

- lBLOQd2 a su vez controla las ampliaciones posteriores en la 2ª dimensión.

 

 

    En otros términos, las ampliaciones posteriores de cada libro se hacen para conjuntos de lBLOQd2 ítems.

 

 

 

Y su uso se concreta en términos de instrucciones como sigue:

 

 

La asignación comienza direccionando la primera dimensión con malloc

 

         lINDICES = (long **) malloc(lBLOQf*sizeof(long *));

 

 

Cuando el contador de nº de ficheros agota el bloque asignado, se amplia en un nuevo bloque con realloc

 

 lINDICES = (long **) realloc(lINDICES, (lNID + lBLOQf)*sizeof(long *));

 

 

 

Se procede de la misma manera en la segunda dimensión:

 

Las instrucciones que vimos antes se pueden sintetizar en que cuando se va a grabar el 1er.elemento, se asigna un primer bloque de tamaño lBLOQd

 

  lINDICES[lNIDc] = (long *) malloc(lBLOQd*sizeof(long));

 

 

Y cuando el contador de nº de elementos agota el espacio, se reasigna en bloques de tamaño lBLOQd2 utilizando la sentencia

 

 lINDICES[lNIDc] = (long *) realloc( lINDICES[lNIDc], (lTamAnt + lBLOQd2)*sizeof(long) );

 

 

 

SRRCM presenta otras utilidades adicionales pero como se indicó antes es preferible verlas desde la perspectiva más evolucionada del interfaz final SRRCW, a diferencia de las utilidades del núcleo expuestas aquí.

 

                                                                                                  _______

 

 

A.I.5.13 Prototipos de salida veloz (Para iSeries)

 

Se pueden construir versiones de los procedimientos de salida que no copien datos y que pasen sólo direcciones.

 

Su uso directo en C, aunque factible, conlleva una complicación de sintaxis engorrosa. Por el contrario, en RPG su uso es similar al que se sigue con las funciones equivalentes ordinarias.

 

Se va a introducir como muestra la función SRRCM_VREAD a puros efectos ilustrativos y para su comparación con la versión ordinaria SRRCM_READ:

 

//-----------------------------------------------------------------

// FUNCION....: SRRCM_VREADC

//

// DESCRIPCION: Recupera un ítem de memoria secuencialmente.

// Como los elementos están ordenados por clave, una lectura secuencial devuelve los ítems ordenados.

//  Además devuelve el valor de clave del ítem, la versión más sencilla VREAD no.

//

// PARAMETROS.:

// (entrada)  lNIDp : Identificador del conjunto de ítems asociado

//            iINDIp: Índice secuencial recuperación (formato 1..N)

// (salida ) **vDato: Datos del ítem

//           **vClav: Clave del ítem

//

// RETORNO....:

//             0: Ítem leído satisfactoriamente

//             1: Error de Proceso (No encontrado(EOF), ...)

//

//-----------------------------------------------------------------

short int SRRCM_VREADC(long lNIDp, long lINDIp, void **vDato, void **vClav)

{

 

  // Control de solicitud errónea

 

 if (!lNIDp || !iSTAT[lNIDp-1] || (lINDIp <= 0) || (lNITEM[lNIDp-1] < lINDIp)   || !vDato) return 1;

 

 

  // Pasa parámetros recibidos a variables de trabajo

 

 lNIDc = lNIDp-1;

 

 

  // Recupera el valor de la clave del ítem, compara EOF

 

 lIndic = lINDICES[lNIDc][lINDIp-1];

  if (vClav)

  {

   *vClav = (void *) &cCLAVES[lNIDc][lIndic];    // Se sustituye el memcpy por la asignación directa

 

   iComp = memcmp(*vClav, cBORRADOR, 1);

   if(!iComp) return 1;

  }

 

 

  // Datos asociados   

 

 *vDato = (void *) &cDATOS[lNIDc][lIndic];       // Se sustituye el memcpy por la asignación directa

 

  return NO_ERRO;

}

                                                                                                  _______

 

 

 

 El código presentado es un extracto del original, al que se invita a acceder tras esta exposición, bien directamente o bien desde el capítulo

"C3 Detalle de relación de programas de servicio (DLL) soporte de de los ficheros virtuales"

 

 

También puede consultarse el capítulo dedicado al manual y los que presentan los ejemplos de uso para ver las instrucciones bajo la perspectiva de su utilización.

 

                                                                                                  _______