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 librararies 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 <sys/types.h>
  38 #include <sys/stat.h>
  39 #include <sys/mman.h>
  40 #include <malloc.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   register const inttab_t * ptr = (const inttab_t *) inttab;
  77
  78   register 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 _DtShmProtoAddInttab(DtShmProtoInttab intlist, unsigned int keyin, int datain)
 103 {
 104   intlist_t * ptr = (intlist_t *) intlist;
 105   int ** data;
 106
 107   data = (int**)_DtUtilGetHash(ptr->tbl, (unsigned char *)keyin);
 108
 109   if(!*data) /* new */ {
 110     *data = (int *) malloc(sizeof(int));
 111     ptr->num_entries++;
 112   }
 113
 114   **data = datain;
 115   return(0);
 116 }
 117
 118 int
 119 _DtShmProtoSizeInttab(DtShmProtoInttab intlist)
 120 {
 121   intlist_t * ptr = (intlist_t * ) intlist;
 122
 123   return(sizeof(inttab_t) * (ptr->num_entries +1));
 124 }
 125
 126 DtShmInttab
 127 _DtShmProtoCopyInttab(DtShmProtoInttab intlist, void * destination)
 128 {
 129   builder_t build;
 130
 131   build.counter = 1;
 132   build.intlist_ptr = (intlist_t * ) intlist;
 133   build.inttab_ptr = (inttab_t *) destination;
 134
 135   memset(destination, 0, (build.intlist_ptr->num_entries+1)*sizeof(inttab_t));
 136
 137   build.inttab_ptr->key = build.intlist_ptr->num_entries;
 138
 139   _DtUtilOperateHash(build.intlist_ptr->tbl, (DtHashOperateFunc)build_it, &build);
 140
 141   return(0);
 142 }
 143
 144 int
 145 _DtShmProtoDestroyInttab(DtShmProtoInttab intlist)
 146 {
 147   intlist_t * ptr = (intlist_t *)intlist;
 148   _DtUtilDestroyHash(ptr->tbl,  (DtHashDestroyFunc)free, NULL);
 149   free(intlist);
 150   return(0);
 151 }
 152
 153 static int build_it(int * data, void * usr_arg, int key)
 154 {
 155   builder_t * ptr = (builder_t *) usr_arg;
 156   inttab_t * a;
 157   inttab_t * b;
 158   unsigned short * add_ptr;
 159
 160   int bucket = key % (ptr->intlist_ptr->num_entries) + 1;
 161
 162   a = ptr->inttab_ptr + ptr->counter;
 163   a->key        = key;
 164   a->data       = *data;
 165   a->next       = NOT_AN_INDEX;
 166
 167   b = ptr->inttab_ptr + bucket;
 168
 169   if(b->first == NOT_AN_INDEX) {
 170     add_ptr = &b->first;
 171   } else {
 172     b = ptr->inttab_ptr + b->first;
 173     while(b->next != NOT_AN_INDEX)
 174       b = ptr->inttab_ptr + b->next;
 175     add_ptr = &b->next;
 176   }
 177
 178   *add_ptr = ptr->counter++;
 179   return(0);
 180 }
 181