cde/lib/DtSvc/DtUtil1/inttab.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these libraries and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: inttab.c /main/5 1996/05/09 04:23:37 drk $ */
  24 /*
  25   routines to implement a table of int, int value pairs.
  26   the data is relocatable to allow use at various addresses
  27   (eg shared memory)
  28
  29   -1 is an illegal key
  30
  31   Tables are limited to 64K entries
  32
  33   */
  34
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <stdint.h>
  38 #include <sys/types.h>
  39 #include <sys/stat.h>
  40 #include <sys/mman.h>
  41 #include <string.h>
  42 #include "DtHash.h"
  43 #include "DtShmDb.h"
  44
  45 #define NOT_AN_INDEX 0
  46
  47 static int build_it(int * data, void * usr_arg, int key);
  48
  49 typedef struct inttab {
  50   int key;
  51   int data;
  52   unsigned short first;
  53   unsigned short next;
  54 } inttab_t;
  55
  56 typedef struct intlist {
  57   int num_entries;
  58   void * tbl;
  59 } intlist_t;
  60
  61 typedef struct builder {
  62   int         counter;
  63   intlist_t * intlist_ptr;
  64   inttab_t  * inttab_ptr;
  65 } builder_t;
  66
  67
  68 /*
  69   first entry is header block;
  70   contains key = size (not counting header)
  71   */
  72
  73 const int *
  74 _DtShmFindIntTabEntry(DtShmInttab inttab, unsigned int key)
  75 {
  76   const inttab_t * ptr = (const inttab_t *) inttab;
  77
  78   int i;
  79
  80   if ( !ptr->key)
  81         return(0);
  82
  83   i = ptr[key % ptr->key + 1].first;
  84
  85   while(i && key != ptr[i].key)
  86     i = ptr[i].next;
  87
  88   return(i?(&ptr[i].data):(const int *)NULL);
  89 }
  90
  91 DtShmProtoInttab
  92 _DtShmProtoInitInttab(int sizeguess)
  93 {
  94   intlist_t * ptr = (intlist_t *)malloc(sizeof(*ptr));
  95
  96   ptr->tbl = _DtUtilMakeIHash(sizeguess);;
  97   ptr->num_entries = 0;
  98
  99   return((void*)ptr);
 100 }
 101
 102 int _DtShmProtoAddInttab(DtShmProtoInttab intlist, unsigned int keyin,
 103                          int datain)
 104 {
 105   intlist_t * ptr = (intlist_t *) intlist;
 106   int ** data;
 107
 108   data = (int**)_DtUtilGetHash(ptr->tbl, (unsigned char *) (intptr_t) keyin);
 109
 110   if(!*data) /* new */ {
 111     *data = (int *) malloc(sizeof(int));
 112     ptr->num_entries++;
 113   }
 114
 115   **data = datain;
 116   return(0);
 117 }
 118
 119 int
 120 _DtShmProtoSizeInttab(DtShmProtoInttab intlist)
 121 {
 122   intlist_t * ptr = (intlist_t * ) intlist;
 123
 124   return(sizeof(inttab_t) * (ptr->num_entries +1));
 125 }
 126
 127 DtShmInttab
 128 _DtShmProtoCopyInttab(DtShmProtoInttab intlist, void * destination)
 129 {
 130   builder_t build;
 131
 132   build.counter = 1;
 133   build.intlist_ptr = (intlist_t * ) intlist;
 134   build.inttab_ptr = (inttab_t *) destination;
 135
 136   memset(destination, 0, (build.intlist_ptr->num_entries+1)*sizeof(inttab_t));
 137
 138   build.inttab_ptr->key = build.intlist_ptr->num_entries;
 139
 140   _DtUtilOperateHash(build.intlist_ptr->tbl, (DtHashOperateFunc)build_it, &build);
 141
 142   return(0);
 143 }
 144
 145 int
 146 _DtShmProtoDestroyInttab(DtShmProtoInttab intlist)
 147 {
 148   intlist_t * ptr = (intlist_t *)intlist;
 149   _DtUtilDestroyHash(ptr->tbl,  (DtHashDestroyFunc)free, NULL);
 150   free(intlist);
 151   return(0);
 152 }
 153
 154 static int build_it(int * data, void * usr_arg, int key)
 155 {
 156   builder_t * ptr = (builder_t *) usr_arg;
 157   inttab_t * a;
 158   inttab_t * b;
 159   unsigned short * add_ptr;
 160
 161   int bucket = key % (ptr->intlist_ptr->num_entries) + 1;
 162
 163   a = ptr->inttab_ptr + ptr->counter;
 164   a->key        = key;
 165   a->data       = *data;
 166   a->next       = NOT_AN_INDEX;
 167
 168   b = ptr->inttab_ptr + bucket;
 169
 170   if(b->first == NOT_AN_INDEX) {
 171     add_ptr = &b->first;
 172   } else {
 173     b = ptr->inttab_ptr + b->first;
 174     while(b->next != NOT_AN_INDEX)
 175       b = ptr->inttab_ptr + b->next;
 176     add_ptr = &b->next;
 177   }
 178
 179   *add_ptr = ptr->counter++;
 180   return(0);
 181 }
 182