src/list.c

   1 /* the Music Player Daemon (MPD)
   2  * Copyright (C) 2003-2007 by Warren Dukes (warren.dukes@gmail.com)
   3  * This project's homepage is: http://www.musicpd.org
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19 #include "list.h"
  20 #include "utils.h"
  21
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <assert.h>
  25 #include <time.h>
  26 #include <stdio.h>
  27
  28 static void makeListNodesArray(List * list)
  29 {
  30         ListNode *node = list->firstNode;
  31         long i;
  32
  33         if (!list->numberOfNodes)
  34                 return;
  35
  36         list->nodesArray = xrealloc(list->nodesArray,
  37                                    sizeof(ListNode *) * list->numberOfNodes);
  38
  39         for (i = 0; i < list->numberOfNodes; i++) {
  40                 list->nodesArray[i] = node;
  41                 node = node->nextNode;
  42         }
  43 }
  44
  45 static void freeListNodesArray(List * list)
  46 {
  47         if (!list->nodesArray)
  48                 return;
  49         free(list->nodesArray);
  50         list->nodesArray = NULL;
  51 }
  52
  53 List *makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys)
  54 {
  55         List *list = xmalloc(sizeof(List));
  56
  57         assert(list != NULL);
  58
  59         list->sorted = 0;
  60         list->firstNode = NULL;
  61         list->lastNode = NULL;
  62         list->freeDataFunc = freeDataFunc;
  63         list->numberOfNodes = 0;
  64         list->nodesArray = NULL;
  65         list->strdupKeys = strdupKeys;
  66
  67         return list;
  68 }
  69
  70 ListNode *insertInListBeforeNode(List * list, ListNode * beforeNode, int pos,
  71                                  char *key, void *data)
  72 {
  73         ListNode *node;
  74
  75         assert(list != NULL);
  76         assert(key != NULL);
  77         /*assert(data!=NULL); */
  78
  79         node = xmalloc(sizeof(ListNode));
  80         assert(node != NULL);
  81
  82         node->nextNode = beforeNode;
  83         if (beforeNode == list->firstNode) {
  84                 if (list->firstNode == NULL) {
  85                         assert(list->lastNode == NULL);
  86                         list->lastNode = node;
  87                 } else {
  88                         assert(list->lastNode != NULL);
  89                         assert(list->lastNode->nextNode == NULL);
  90                         list->firstNode->prevNode = node;
  91                 }
  92                 node->prevNode = NULL;
  93                 list->firstNode = node;
  94         } else {
  95                 if (beforeNode) {
  96                         node->prevNode = beforeNode->prevNode;
  97                         beforeNode->prevNode = node;
  98                 } else {
  99                         node->prevNode = list->lastNode;
 100                         list->lastNode = node;
 101                 }
 102                 node->prevNode->nextNode = node;
 103         }
 104
 105         if (list->strdupKeys)
 106                 node->key = xstrdup(key);
 107         else
 108                 node->key = key;
 109
 110         node->data = data;
 111
 112         list->numberOfNodes++;
 113
 114         if (list->sorted) {
 115                 list->nodesArray = xrealloc(list->nodesArray,
 116                                            list->numberOfNodes *
 117                                            sizeof(ListNode *));
 118                 if (node == list->lastNode) {
 119                         list->nodesArray[list->numberOfNodes - 1] = node;
 120                 } else if (pos < 0)
 121                         makeListNodesArray(list);
 122                 else {
 123                         memmove(list->nodesArray + pos + 1,
 124                                 list->nodesArray + pos,
 125                                 sizeof(ListNode *) * (list->numberOfNodes -
 126                                                       pos - 1));
 127                         list->nodesArray[pos] = node;
 128                 }
 129         }
 130
 131         return node;
 132 }
 133
 134 ListNode *insertInList(List * list, char *key, void *data)
 135 {
 136         ListNode *node;
 137
 138         assert(list != NULL);
 139         assert(key != NULL);
 140         /*assert(data!=NULL); */
 141
 142         node = xmalloc(sizeof(ListNode));
 143         assert(node != NULL);
 144
 145         if (list->nodesArray)
 146                 freeListNodesArray(list);
 147
 148         if (list->firstNode == NULL) {
 149                 assert(list->lastNode == NULL);
 150                 list->firstNode = node;
 151         } else {
 152                 assert(list->lastNode != NULL);
 153                 assert(list->lastNode->nextNode == NULL);
 154                 list->lastNode->nextNode = node;
 155         }
 156
 157         if (list->strdupKeys)
 158                 node->key = xstrdup(key);
 159         else
 160                 node->key = key;
 161
 162         node->data = data;
 163         node->nextNode = NULL;
 164         node->prevNode = list->lastNode;
 165
 166         list->lastNode = node;
 167
 168         list->numberOfNodes++;
 169
 170         return node;
 171 }
 172
 173 int insertInListWithoutKey(List * list, void *data)
 174 {
 175         ListNode *node;
 176
 177         assert(list != NULL);
 178         assert(data != NULL);
 179
 180         node = xmalloc(sizeof(ListNode));
 181         assert(node != NULL);
 182
 183         if (list->nodesArray)
 184                 freeListNodesArray(list);
 185
 186         if (list->firstNode == NULL) {
 187                 assert(list->lastNode == NULL);
 188                 list->firstNode = node;
 189         } else {
 190                 assert(list->lastNode != NULL);
 191                 assert(list->lastNode->nextNode == NULL);
 192                 list->lastNode->nextNode = node;
 193         }
 194
 195         node->key = NULL;
 196         node->data = data;
 197         node->nextNode = NULL;
 198         node->prevNode = list->lastNode;
 199
 200         list->lastNode = node;
 201
 202         list->numberOfNodes++;
 203
 204         return 1;
 205 }
 206
 207 /* if _key_ is not found, *_node_ is assigned to the node before which
 208         the info would be found */
 209 int findNodeInList(List * list, char *key, ListNode ** node, int *pos)
 210 {
 211         long high;
 212         long low;
 213         long cur;
 214         ListNode *tmpNode;
 215         int cmp;
 216
 217         assert(list != NULL);
 218
 219         if (list->sorted && list->nodesArray) {
 220                 high = list->numberOfNodes - 1;
 221                 low = 0;
 222                 cur = high;
 223
 224                 while (high > low) {
 225                         cur = (high + low) / 2;
 226                         tmpNode = list->nodesArray[cur];
 227                         cmp = strcmp(tmpNode->key, key);
 228                         if (cmp == 0) {
 229                                 *node = tmpNode;
 230                                 *pos = cur;
 231                                 return 1;
 232                         } else if (cmp > 0)
 233                                 high = cur;
 234                         else {
 235                                 if (low == cur)
 236                                         break;
 237                                 low = cur;
 238                         }
 239                 }
 240
 241                 cur = high;
 242                 if (cur >= 0) {
 243                         tmpNode = list->nodesArray[cur];
 244                         *node = tmpNode;
 245                         *pos = high;
 246                         cmp = tmpNode ? strcmp(tmpNode->key, key) : -1;
 247                         if (0 == cmp)
 248                                 return 1;
 249                         else if (cmp > 0)
 250                                 return 0;
 251                         else {
 252                                 *pos = -1;
 253                                 *node = NULL;
 254                                 return 0;
 255                         }
 256                 } else {
 257                         *pos = 0;
 258                         *node = list->firstNode;
 259                         return 0;
 260                 }
 261         } else {
 262                 tmpNode = list->firstNode;
 263
 264                 while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) {
 265                         tmpNode = tmpNode->nextNode;
 266                 }
 267
 268                 *node = tmpNode;
 269                 if (tmpNode)
 270                         return 1;
 271         }
 272
 273         return 0;
 274 }
 275
 276 int findInList(List * list, char *key, void **data)
 277 {
 278         ListNode *node;
 279         int pos;
 280
 281         if (findNodeInList(list, key, &node, &pos)) {
 282                 if (data)
 283                         *data = node->data;
 284                 return 1;
 285         }
 286
 287         return 0;
 288 }
 289
 290 ListNode *getNodeByPosition(List *list, int pos)
 291 {
 292         ListNode *tmpNode;
 293
 294         assert(list != NULL);
 295         if (pos < 0 || pos >= list->numberOfNodes)
 296                 return NULL;
 297
 298         tmpNode = list->firstNode;
 299         while (pos-- > 0)
 300                 tmpNode = tmpNode->nextNode;
 301
 302         return tmpNode;
 303 }
 304
 305 int deleteFromList(List * list, char *key)
 306 {
 307         ListNode *tmpNode;
 308
 309         assert(list != NULL);
 310
 311         tmpNode = list->firstNode;
 312
 313         while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) {
 314                 tmpNode = tmpNode->nextNode;
 315         }
 316
 317         if (tmpNode != NULL)
 318                 deleteNodeFromList(list, tmpNode);
 319         else
 320                 return 0;
 321
 322         return 1;
 323 }
 324
 325 void deleteNodeFromList(List * list, ListNode * node)
 326 {
 327         assert(list != NULL);
 328         assert(node != NULL);
 329
 330         if (node->prevNode == NULL) {
 331                 list->firstNode = node->nextNode;
 332         } else {
 333                 node->prevNode->nextNode = node->nextNode;
 334         }
 335         if (node->nextNode == NULL) {
 336                 list->lastNode = node->prevNode;
 337         } else {
 338                 node->nextNode->prevNode = node->prevNode;
 339         }
 340         if (list->freeDataFunc) {
 341                 list->freeDataFunc(node->data);
 342         }
 343
 344         if (list->strdupKeys)
 345                 free(node->key);
 346         free(node);
 347         list->numberOfNodes--;
 348
 349         if (list->nodesArray) {
 350                 freeListNodesArray(list);
 351                 if (list->sorted)
 352                         makeListNodesArray(list);
 353         }
 354
 355 }
 356
 357 void freeList(void *list)
 358 {
 359         ListNode *tmpNode;
 360         ListNode *tmpNode2;
 361
 362         assert(list != NULL);
 363
 364         tmpNode = ((List *) list)->firstNode;
 365
 366         if (((List *) list)->nodesArray)
 367                 free(((List *) list)->nodesArray);
 368
 369         while (tmpNode != NULL) {
 370                 tmpNode2 = tmpNode->nextNode;
 371                 if (((List *) list)->strdupKeys)
 372                         free(tmpNode->key);
 373                 if (((List *) list)->freeDataFunc) {
 374                         ((List *) list)->freeDataFunc(tmpNode->data);
 375                 }
 376                 free(tmpNode);
 377                 tmpNode = tmpNode2;
 378         }
 379
 380         free(list);
 381 }
 382
 383 static void swapNodes(ListNode * nodeA, ListNode * nodeB)
 384 {
 385         char *key;
 386         void *data;
 387
 388         assert(nodeA != NULL);
 389         assert(nodeB != NULL);
 390
 391         key = nodeB->key;
 392         data = nodeB->data;
 393
 394         nodeB->key = nodeA->key;
 395         nodeB->data = nodeA->data;
 396
 397         nodeA->key = key;
 398         nodeA->data = data;
 399 }
 400
 401 static void bubbleSort(ListNode ** nodesArray, long start, long end)
 402 {
 403         long i;
 404         long j;
 405         ListNode *node;
 406
 407         if (start >= end)
 408                 return;
 409
 410         for (j = start; j < end; j++) {
 411                 for (i = end - 1; i >= start; i--) {
 412                         node = nodesArray[i];
 413                         if (strcmp(node->key, node->nextNode->key) > 0) {
 414                                 swapNodes(node, node->nextNode);
 415                         }
 416                 }
 417         }
 418 }
 419
 420 static void quickSort(ListNode ** nodesArray, long start, long end)
 421 {
 422         if (start >= end)
 423                 return;
 424         else if (end - start < 5)
 425                 bubbleSort(nodesArray, start, end);
 426         else {
 427                 long i;
 428                 ListNode *node;
 429                 long pivot;
 430                 ListNode *pivotNode;
 431                 char *pivotKey;
 432
 433                 List *startList = makeList(free, 0);
 434                 List *endList = makeList(free, 0);
 435                 long *startPtr = xmalloc(sizeof(long));
 436                 long *endPtr = xmalloc(sizeof(long));
 437                 *startPtr = start;
 438                 *endPtr = end;
 439                 insertInListWithoutKey(startList, (void *)startPtr);
 440                 insertInListWithoutKey(endList, (void *)endPtr);
 441
 442                 while (startList->numberOfNodes) {
 443                         start = *((long *)startList->lastNode->data);
 444                         end = *((long *)endList->lastNode->data);
 445
 446                         if (end - start < 5) {
 447                                 bubbleSort(nodesArray, start, end);
 448                                 deleteNodeFromList(startList,
 449                                                    startList->lastNode);
 450                                 deleteNodeFromList(endList, endList->lastNode);
 451                         } else {
 452                                 pivot = (start + end) / 2;
 453                                 pivotNode = nodesArray[pivot];
 454                                 pivotKey = pivotNode->key;
 455
 456                                 for (i = pivot - 1; i >= start; i--) {
 457                                         node = nodesArray[i];
 458                                         if (strcmp(node->key, pivotKey) > 0) {
 459                                                 pivot--;
 460                                                 if (pivot > i) {
 461                                                         swapNodes(node,
 462                                                                   nodesArray
 463                                                                   [pivot]);
 464                                                 }
 465                                                 swapNodes(pivotNode,
 466                                                           nodesArray[pivot]);
 467                                                 pivotNode = nodesArray[pivot];
 468                                         }
 469                                 }
 470                                 for (i = pivot + 1; i <= end; i++) {
 471                                         node = nodesArray[i];
 472                                         if (strcmp(pivotKey, node->key) > 0) {
 473                                                 pivot++;
 474                                                 if (pivot < i) {
 475                                                         swapNodes(node,
 476                                                                   nodesArray
 477                                                                   [pivot]);
 478                                                 }
 479                                                 swapNodes(pivotNode,
 480                                                           nodesArray[pivot]);
 481                                                 pivotNode = nodesArray[pivot];
 482                                         }
 483                                 }
 484
 485                                 deleteNodeFromList(startList,
 486                                                    startList->lastNode);
 487                                 deleteNodeFromList(endList, endList->lastNode);
 488
 489                                 if (pivot - 1 - start > 0) {
 490                                         startPtr = xmalloc(sizeof(long));
 491                                         endPtr = xmalloc(sizeof(long));
 492                                         *startPtr = start;
 493                                         *endPtr = pivot - 1;
 494                                         insertInListWithoutKey(startList,
 495                                                                (void *)
 496                                                                startPtr);
 497                                         insertInListWithoutKey(endList,
 498                                                                (void *)endPtr);
 499                                 }
 500
 501                                 if (end - pivot - 1 > 0) {
 502                                         startPtr = xmalloc(sizeof(long));
 503                                         endPtr = xmalloc(sizeof(long));
 504                                         *startPtr = pivot + 1;
 505                                         *endPtr = end;
 506                                         insertInListWithoutKey(startList,
 507                                                                (void *)
 508                                                                startPtr);
 509                                         insertInListWithoutKey(endList,
 510                                                                (void *)endPtr);
 511                                 }
 512                         }
 513                 }
 514
 515                 freeList(startList);
 516                 freeList(endList);
 517         }
 518 }
 519
 520 void sortList(List * list)
 521 {
 522         assert(list != NULL);
 523
 524         list->sorted = 1;
 525
 526         if (list->numberOfNodes < 2)
 527                 return;
 528
 529         if (list->nodesArray)
 530                 freeListNodesArray(list);
 531         makeListNodesArray(list);
 532
 533         quickSort(list->nodesArray, 0, list->numberOfNodes - 1);
 534 }