cde/programs/dtcm/server/list.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: list.c /main/4 1995/11/09 12:45:31 rswiston $ */
  24 /*
  25  *  (c) Copyright 1993, 1994 Hewlett-Packard Company
  26  *  (c) Copyright 1993, 1994 International Business Machines Corp.
  27  *  (c) Copyright 1993, 1994 Novell, Inc.
  28  *  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
  29  */
  30
  31 #include <EUSCompat.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <sys/param.h>
  35 #include "tree.h"
  36 #include "list.h"
  37
  38 extern int debug;
  39
  40 typedef struct {
  41         _DtCmsGetKeyProc get;
  42         _DtCmsEnumerateProc enumerate;
  43         _DtCmsCompareProc compare;
  44 } Private;
  45
  46
  47 extern  List_node *
  48 hc_lookup_node (Hc_list *hc_list, caddr_t key)
  49 {
  50         Private         *private;
  51         register List_node      *p_node;
  52         register _DtCmsComparisonResult result;
  53
  54         p_node = hc_list->root;
  55         private = (Private *) hc_list->private;
  56         while (p_node != NULL)
  57         {
  58                 result = private->compare (key, p_node->data);
  59                 if (result == _DtCmsIsGreater)
  60                 {
  61                         p_node = hc_lookup_next (p_node);
  62                 }
  63                 else if (result == _DtCmsIsEqual)
  64                 {
  65                         return (p_node);
  66                 }
  67                 else
  68                 {
  69                         break;
  70                 }
  71         }
  72         return (NULL);
  73 }
  74
  75 extern  caddr_t
  76 hc_lookup (Hc_list *hc_list, caddr_t key)
  77 {
  78         List_node       *p_node;
  79
  80         p_node = hc_lookup_node (hc_list, key);
  81         if (p_node != NULL)
  82                 return ((caddr_t) p_node->data);
  83         return (NULL);
  84 }
  85
  86 extern  int
  87 hc_size (Hc_list *hc_list)
  88 {
  89         int             n = 0;
  90         register List_node      *p_node;
  91
  92         p_node = hc_list->root;
  93         while (p_node != NULL)
  94         {
  95                 n++;
  96                 p_node = hc_lookup_next (p_node);
  97         }
  98         return (n);
  99 }
 100
 101
 102 extern Hc_list *
 103 hc_create(_DtCmsGetKeyProc get, _DtCmsCompareProc compare)
 104 {
 105         Private *p;
 106         List_node       *root = NULL;
 107         Hc_list *list;
 108
 109         p = (Private *) calloc (1, sizeof (*p));
 110
 111         list = (Hc_list *) calloc (1, sizeof (*list));
 112         list->root = NULL;
 113         list->private = (caddr_t) p;
 114
 115         p->get = get;
 116         p->enumerate = NULL;
 117         p->compare = compare;
 118
 119         return (list);
 120 }
 121
 122 extern void
 123 hc_destroy(Hc_list *hc_list, Destroy_proc destroy_func)
 124 {
 125         Private *p;
 126         List_node       *p_node, *p_next;
 127
 128         if (hc_list == NULL)
 129                 return;
 130         if ((p = (Private *) hc_list->private) != NULL)
 131                 free (p);
 132
 133         p_node = hc_list->root;
 134         while (p_node != NULL)
 135         {
 136                 p_next = hc_lookup_next(p_node);
 137                 if (p_node->data != NULL)
 138                 {
 139                         if (destroy_func)
 140                                 destroy_func(p_node->data);
 141                 }
 142                 free (p_node);
 143                 p_node = p_next;
 144         }
 145 }
 146
 147 extern Rb_Status
 148 hc_insert_node (Hc_list *hc_list, register List_node *p_node, caddr_t key)
 149 {
 150         Private *private;
 151         register List_node      *p_curr;
 152
 153         if (hc_list == NULL)
 154                 return (rb_notable);
 155         private = (Private *) hc_list->private;
 156
 157         p_curr = hc_list->root;
 158         while (p_curr != NULL)
 159         {
 160                 if (private->compare (key, p_curr->data) == _DtCmsIsGreater)
 161                 {
 162                         if (p_curr->rlink != NULL)
 163                                 p_curr = p_curr->rlink;
 164                         else
 165                         {
 166                                 /* Insert at end of the list */
 167                                 p_curr->rlink = p_node;
 168                                 p_node->llink = p_curr;
 169                                 return (rb_ok);
 170                         }
 171                 }
 172                 else
 173                 {
 174                         /* Insert at head of the list */
 175                         if ((p_node->llink = p_curr->llink) == NULL)
 176                                 break;
 177
 178                         /* Insert before the current node */
 179                         p_curr->llink = p_node->llink->rlink = p_node;
 180                         p_node->rlink = p_curr;
 181                         return (rb_ok);
 182                 }
 183         }
 184
 185         /* Insert at head of the list */
 186         p_node->rlink = hc_list->root;
 187         if (p_node->rlink != NULL)
 188                 p_node->rlink->llink = p_node;
 189         hc_list->root = p_node;
 190         return (rb_ok);
 191 }
 192
 193 extern Rb_Status
 194 hc_insert(
 195         Hc_list         *hc_list,
 196         caddr_t         data,
 197         caddr_t         key,
 198         RepeatEvent     *re,
 199         List_node       **node_r)
 200 {
 201         List_node       *p_node;
 202         Rb_Status       stat;
 203
 204         if (hc_list == NULL)
 205                 return (rb_notable);
 206         p_node = (List_node *) calloc (1, sizeof(*p_node));
 207         p_node->data = data;
 208         p_node->re = re;
 209         stat = hc_insert_node (hc_list, p_node, key);
 210
 211         if (stat == rb_ok && node_r)
 212                 *node_r = p_node;
 213
 214         return (stat);
 215 }
 216
 217 extern List_node *
 218 hc_delete_node (Hc_list *hc_list, List_node     *p_node)
 219 {
 220         if (p_node->llink == NULL)
 221                 hc_list->root = p_node->rlink;
 222         else
 223                 p_node->llink->rlink = p_node->rlink;
 224         if (p_node->rlink != NULL)
 225                 p_node->rlink->llink = p_node->llink;
 226         return (p_node);
 227 }
 228
 229 extern List_node *
 230 hc_delete (Hc_list *hc_list, caddr_t key)
 231 {
 232         register List_node      *p_node;
 233         register Private *private;
 234
 235         p_node = hc_list->root;
 236         private = (Private *) hc_list->private;
 237         while (p_node != NULL)
 238         {
 239                 if (private->compare (key, p_node->data) == _DtCmsIsEqual)
 240                 {
 241                         (void) hc_delete_node (hc_list, p_node);
 242                         return (p_node);
 243                 }
 244                 p_node = hc_lookup_next(p_node);
 245         }
 246         return (NULL);
 247 }
 248
 249 extern caddr_t
 250 hc_lookup_smallest (Hc_list *hc_list)
 251 {
 252         if ((hc_list == NULL) || (hc_list->root == NULL))
 253                 return (NULL);
 254         return ((caddr_t) hc_list->root->data);
 255 }
 256
 257 extern caddr_t
 258 hc_lookup_next_larger (Hc_list *hc_list, caddr_t key)
 259 {
 260         register List_node      *p_node;
 261         register Private *private;
 262
 263         p_node = hc_list->root;
 264         private = (Private *) hc_list->private;
 265         while (p_node != NULL)
 266         {
 267                 if (private->compare (key, p_node->data) == _DtCmsIsLess)
 268                         return ((caddr_t) p_node->data);
 269                 p_node = hc_lookup_next(p_node);
 270         }
 271         return (NULL);
 272 }
 273
 274 extern caddr_t
 275 hc_lookup_largest (Hc_list *hc_list)
 276 {
 277         register List_node      *p_node;
 278
 279         if ((hc_list == NULL) || (hc_list->root == NULL))
 280                 return (NULL);
 281
 282         p_node = hc_list->root;
 283         while (p_node->rlink != NULL)
 284                 p_node = hc_lookup_next (p_node);
 285         return ((caddr_t) p_node->data);
 286 }
 287
 288 extern caddr_t
 289 hc_lookup_next_smaller (Hc_list *hc_list, caddr_t key)
 290 {
 291         register List_node      *p_node;
 292         register Private *private;
 293
 294         p_node = hc_list->root;
 295         private = (Private *) hc_list->private;
 296         while (p_node != NULL)
 297         {
 298                 if (private->compare (key, p_node->data) != _DtCmsIsGreater)
 299                 {
 300                         if (p_node->llink == NULL)
 301                                 return (NULL);
 302                         else
 303                                 return ((caddr_t) p_node->llink->data);
 304                 }
 305                 p_node = hc_lookup_next(p_node);
 306         }
 307         return (NULL);
 308 }
 309
 310 extern  Rb_Status
 311 hc_check_list (Hc_list *hc_list)
 312 {
 313         if ((hc_list == NULL) || (hc_list->root == NULL))
 314                 return (rb_notable);
 315         return (rb_ok);
 316 }
 317
 318
 319 extern void
 320 hc_enumerate_down(Hc_list *hc_list, _DtCmsEnumerateProc doit)
 321 {
 322         register List_node      *p_node;
 323
 324         p_node = hc_list->root;
 325         while (p_node != NULL)
 326         {
 327                 if (doit ((caddr_t)p_node, p_node->data))
 328                         return;
 329                 p_node = p_node->llink;
 330         }
 331 }
 332
 333 extern Rb_Status
 334 hc_enumerate_up(Hc_list *hc_list, _DtCmsEnumerateProc doit)
 335 {
 336         register List_node      *p_node;
 337
 338         p_node = hc_list->root;
 339         while (p_node != NULL)
 340         {
 341                 if (doit ((caddr_t)p_node, p_node->data))
 342                         return (rb_failed);
 343                 p_node = hc_lookup_next (p_node);
 344         }
 345
 346         return (rb_ok);
 347 }