1                 : /*
       2                 :  * Copyright (c) 1991, 1992, 1993 Brad Eacker,
       3                 :  *              (Music, Intuition, Software, and Computers)
       4                 :  * All Rights Reserved
       5                 :  */
       6                 : 
       7                 : #include <stdio.h>
       8                 : #include <fcntl.h>
       9                 : 
      10                 : #include "dbf.h"
      11                 : #include "dbf_ndx.h"
      12                 : 
      13                 : /*
      14                 :  * get the ndx header for this file
      15                 :  */
      16                 : ndx_header_t *ndx_get_header(int fd)
      17               0 : {
      18                 :         dndx_header_t   *dp;
      19                 :         ndx_header_t    *np;
      20                 : 
      21               0 :         if ((dp = (dndx_header_t *)malloc(NDX_PAGE_SZ)) == NULL)
      22               0 :                 return NULL;
      23               0 :         if ((np = (ndx_header_t *)malloc(sizeof(ndx_header_t))) == NULL) {
      24               0 :                 free(dp);
      25               0 :                 return NULL;
      26                 :         }
      27               0 :         if ((lseek(fd, 0, 0) < 0) || (read(fd, dp, NDX_PAGE_SZ) < 0)) {
      28               0 :                 free(dp); free(np);
      29               0 :                 return NULL;
      30                 :         }
      31               0 :         np->ndx_hpage = dp;
      32               0 :         np->ndx_fd = fd;
      33               0 :         np->ndx_start_pg = get_long(dp->dndx_st_pg);
      34               0 :         np->ndx_total_pgs = get_long(dp->dndx_tot_pg);
      35               0 :         np->ndx_key_len = get_short(dp->dndx_key_len);
      36               0 :         np->ndx_keys_ppg = get_short(dp->dndx_keys_ppg);
      37               0 :         np->ndx_key_type = get_short(dp->dndx_key_type);
      38               0 :         np->ndx_key_size = get_long(dp->dndx_size_key);
      39               0 :         np->ndx_key_name = dp->dndx_key_name;
      40               0 :         np->ndx_unique = dp->dndx_unique;
      41                 : 
      42               0 :         np->ndx_fp = NULL;
      43                 : 
      44               0 :         return np;
      45                 : }
      46                 : 
      47                 : static ndx_page_t *ndx_get_page(ndx_header_t *hp, int pageno)
      48               0 : {
      49                 :         ndx_page_t      *fp;
      50                 :         dndx_page_t     *dp;
      51                 :         ndx_record_t    *rp;
      52                 : 
      53                 : #if PHP_DEBUG
      54                 :         printf("getting page %d", pageno);
      55                 : #endif
      56               0 :         if ((fp = (ndx_page_t *)malloc(sizeof(ndx_page_t))) == NULL)
      57               0 :                 return NULL;
      58               0 :         if ((dp = (dndx_page_t *)malloc(NDX_PAGE_SZ)) == NULL) {
      59               0 :                 free(fp);
      60               0 :                 return NULL;
      61                 :         }
      62               0 :         if ((rp = (ndx_record_t *)malloc(sizeof(ndx_record_t) * hp->ndx_keys_ppg)) == NULL) {
      63               0 :                 free(dp); free(fp);
      64               0 :                 return NULL;
      65                 :         }
      66               0 :         fp->ndxp_page_data = dp;
      67               0 :         if ((lseek(hp->ndx_fd, pageno * NDX_PAGE_SZ, 0) < 0) ||
      68                 :                 (read(hp->ndx_fd, dp, NDX_PAGE_SZ) < 0)) {
      69               0 :                 free(fp); free(dp);
      70               0 :                 return NULL;
      71                 :         }
      72               0 :         fp->ndxp_parent = NULL;
      73               0 :         fp->ndxp_page_no = pageno;
      74               0 :         fp->ndxp_num_keys = get_long(dp->dndxp_num_keys);
      75               0 :         memset(rp, 0, sizeof(ndx_record_t) * hp->ndx_keys_ppg);
      76               0 :         fp->ndxp_records = rp;
      77               0 :         fp->ndxp_header_p = hp;
      78                 : #if PHP_DEBUG
      79                 :         printf(", n_keys %ld\n", fp->ndxp_num_keys);
      80                 : #endif
      81               0 :         return fp;
      82                 : }
      83                 : 
      84                 : /*
      85                 :  * get the first entry for this ndx
      86                 :  */
      87                 : static ndx_page_t *ndx_get_first_pg(ndx_header_t *hp)
      88               0 : {
      89                 :         ndx_page_t      *fp;
      90                 : 
      91               0 :         if (hp->ndx_fp)
      92               0 :                 return hp->ndx_fp;
      93               0 :         if ((fp = ndx_get_page(hp, hp->ndx_start_pg))) {
      94               0 :                 hp->ndx_fp = fp;
      95                 :         }
      96               0 :         return fp;
      97                 : }
      98                 : 
      99                 : static ndx_record_t *ndx_get_record(ndx_page_t *fp, int rec_no)
     100               0 : {
     101                 :         ndx_record_t            *rp;
     102               0 :         ndx_header_t            *hp = fp->ndxp_header_p;
     103                 :         struct dndx_record      *drp;
     104                 : 
     105                 : #if PHP_DEBUG
     106                 :         printf("page %ld, rec %d: ", fp->ndxp_page_no, rec_no);
     107                 : #endif
     108               0 :         if (rec_no >= fp->ndxp_num_keys)
     109               0 :                 return NULL;
     110               0 :         rp = &(fp->ndxp_records[rec_no]);
     111               0 :         if (!rp->ndxr_page) {
     112               0 :                 rp->ndxr_page = fp;
     113               0 :                 drp = (dndx_record_t *)((char *)&fp->ndxp_page_data->dndx_rp
     114                 :                                 + rec_no * hp->ndx_key_size);
     115               0 :                 rp->ndxr_left = get_long(drp->dndx_left_pg);
     116               0 :                 rp->ndxr_rec = get_long(drp->dndx_dbf_rec);
     117               0 :                 rp->ndxr_key_data = &drp->dndx_key_data;
     118               0 :                 rp->ndxr_p_nrec = rec_no;
     119                 :         }
     120                 : #if PHP_DEBUG
     121                 :         printf("left %ld, dbf_rec %ld, data '%s'\n", rp->ndxr_left,
     122                 :                 rp->ndxr_rec, rp->ndxr_key_data);
     123                 : #endif
     124               0 :         return rp;
     125                 : }
     126                 : 
     127                 : static ndx_record_t *ndx_scan_down(ndx_header_t *hp, ndx_page_t *fp, int recno)
     128               0 : {
     129                 :         ndx_page_t      *np;
     130                 :         ndx_record_t    *rp;
     131                 : 
     132               0 :         while ((rp = ndx_get_record(fp, recno)) && (rp->ndxr_rec == 0)) {
     133               0 :                 np = ndx_get_page(hp, rp->ndxr_left);
     134               0 :                 np->ndxp_parent = fp;
     135               0 :                 np->ndxp_par_rno = recno;
     136               0 :                 fp = np;
     137               0 :                 recno = 0;
     138                 :         }
     139               0 :         return rp;
     140                 : }
     141                 : 
     142                 : static ndx_record_t *ndx_scan_up(ndx_header_t *hp, ndx_page_t *fp, int recno)
     143               0 : {
     144                 :         ndx_record_t    *rp;
     145                 : 
     146               0 :         if (fp == NULL)
     147               0 :                 rp = NULL;
     148               0 :         else if (recno < fp->ndxp_num_keys) {
     149               0 :                 rp = ndx_scan_down(hp, fp, recno);
     150                 :         } else {
     151               0 :                 rp = ndx_scan_up(hp, fp->ndxp_parent, fp->ndxp_par_rno + 1);
     152                 :         }
     153               0 :         return rp;
     154                 : }
     155                 : 
     156                 : ndx_record_t *ndx_get_first_rec(ndx_header_t *hp)
     157               0 : {
     158                 :         ndx_page_t      *fp;
     159               0 :         ndx_record_t    *rp = NULL;
     160                 : 
     161               0 :         if ((fp = ndx_get_first_pg(hp))) {
     162               0 :                 fp->ndxp_last_key = 0;
     163               0 :                 rp = ndx_scan_down(hp, fp, 0);
     164                 :         }
     165               0 :         hp->ndx_cur_rec = rp;
     166               0 :         return rp;
     167                 : }
     168                 : 
     169                 : ndx_record_t *ndx_get_next_rec(ndx_header_t *hp, ndx_record_t *rp)
     170               0 : {
     171                 :         ndx_page_t      *fp;
     172                 :         int             rec_no;
     173                 : 
     174               0 :         fp = rp->ndxr_page;
     175               0 :         rec_no = rp->ndxr_p_nrec + 1;
     176               0 :         if (rec_no < fp->ndxp_num_keys) {
     177               0 :                 rp = ndx_scan_down(hp, fp, rec_no);
     178                 :         } else {
     179               0 :                 rp = ndx_scan_up(hp, fp->ndxp_parent, fp->ndxp_par_rno + 1);
     180                 :         }
     181               0 :         return rp;
     182                 : }
     183                 : 
     184                 : /*
     185                 :  * Local variables:
     186                 :  * tab-width: 4
     187                 :  * c-basic-offset: 4
     188                 :  * End:
     189                 :  * vim600: sw=4 ts=4 fdm=marker
     190                 :  * vim<600: sw=4 ts=4
     191                 :  */